問題タブ [vehicle-routing]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 買い物ルート最適化アルゴリズム?
さまざまな価格の商品sを提供するショップが多数あります。aショップが特定の商品を提供していない可能性があります。お店同士（通り）をつなぐことができます。
タスクは、合計価格が最小になるように、あるホーム ロケーションから (およびホーム ロケーションに戻る) 最適なルート (サイクル) を見つけることです。合計価格は、商品の価格の合計と店舗間の距離の合計です。
商品の価格はショップごとにわかっています。この情報を入手するために店舗に行く必要はありません。
制約は次のとおりです。
- バイヤー/旅行者は記事のリストを購入したいと考えており、すべての記事の可能性もあります
- すべての商品は、少なくとも 1 つのショップで入手可能です
- 店舗間の距離はコストで表されるため、ルートの合計コストを計算する際に、購入した商品のコストに単純に追加できます。
- ショップは複数回訪れることができますが、それによって移動が増加し、ルートの総コストが高くなります
私はnetworkxで最初のモデリングを行い、各ノード (ショップ) が提供する製品のすべての価格のリストを保持する有向グラフ (距離/コストを重みとして) としてショップ (および家) をモデル化しました。
私の最初の試みは力ずくのソリューションを作成することでした。すべての単純なサイクルを反復することで成功しました。次に、サイクルごとに、移動コストと商品のコスト (つまり、サイクルのショップに表示される最低価格) を計算します。
現在、上記は機能しますが、スケーリングしません: すべてのサイクルを列挙するための時間の複雑さはO((n+e)(c+1))、n 個のノード、e 個のエッジ、および c 個の基本回路 (有向グラフのすべての基本回路を見つけることです。DB Johnson、SIAM Journal on Computing 4、いいえ. 1, 77-84, 1975 )。そして、サイクル (回路) の数は非常に急速に増加します。
よりスケーラブルな問題の説明について何か提案はありますか? 動的または線形計画法のソリューションについて考えていますが、アイデアを聞きたいです。
更新: このトピックに関する博士論文全体を見つけました: ftp://tesis.bbtk.ull.es/ccppytec/cp181.pdf
python - 標準の巡回セールスマン ソルバーを or-tools のコレクト プライス ソルバーにする方法は?
グラフ内の「1000 個のノードを訪問するための最適なルートは何か」の優れたソルバーをセットアップしました。
しかし、「グラフ内の 1000 個のノードのうち 500 個を訪問するための最短ルートは何か」という質問を解決したいと思います。
どうにかして分離制約を pythonに追加する必要があると思いますRoutingModelが、どうやって？
これは、現在のソルバーの大まかなスケッチです。
optaplanner - 実際の道路距離を持つ TSPTW
OptaPlanner または jsprit を使用して、タイム ウィンドウ(実際の道路距離) で非対称 移動セールスマンの問題を解決することは可能ですか?