graph-theory - 車両ルーティング アルゴリズム?

Question

私は持っている

• デポ
• それぞれが最大10トンを運ぶことができる輸送船の艦隊
• 数人の顧客。

トランスポーターの負荷を最大化し、ツアーを最小化するにはどうすればよいですか?

これまでのところ、トランスポーターをグループ化するために 1Dビン パッキングを使用し、ツアーを短縮するためにアリ コロニーの最適化を使用していますが、それは適切ではありません。ナップサック アルゴリズムについて読んだことがありますか? 私はもっ​​とうまくやれるだろうか？

Answer 1

あなたの問題に対する完璧な解決策はないと思います。私が正しく理解できれば、あなたの問題はパレート最適です。ルート、負荷、または必要なフリートカーの数を最適化できます (サイド制約の毎日の作業時間も問題になる可能性があります)。より重要なこと、たとえば、燃料費のために短いルート、車の数が少ないなど、自分自身を評価する必要があります。

私の意見では、各パーティションの積載量が 10 トンを超えないように、顧客を地理的に分割する必要があります。その後、その小さな問題に対して TSP を使用して、完全なルートを計算できます。主な「魔法」はパーティションのステップで行われます。それをうまく解決すれば、問題がなくなる可能性があります。

役に立ったことを願っています

Answer 2

A* 検索 (最大コスト パス用に変更) と最短パス アルゴリズムの組み合わせ (Microsoft Research の論文 http://research.microsoft.com/pubs/154937/soda05.pdfで説明されている) を組み合わせると、検討する価値があるかもしれません。