複数のドロップを含む複数の車両のルーティングアルゴリズム

Question

複数のバンを管理するために使用できるルーティングアルゴリズムを見つけ出す/作成することを検討しています。

ここで私はルートが迅速かつ効率的な方法で

100 +バン/ 1000 +パッケージ/ 1000 +ドロップオフポイントでした計算されなければならない。..

• を探しています何のラフな仕様です
• 異なるサイズおよび重量かもしれないパッケージは、Oを整理する必要がある各バンは異なるサイズおよび各パッケージ異なる重量制限
• を持つことができ
• を行く1で処理すること路線、重量、サイズの制限を考慮して、公平で経済的な方法でバンに運ばれます。
• バンは、経済的で、できるだけ短くする必要があります（または、両者の設定可能なバランス）。
• バン前にこの種のものを見て誰もが、そうであれば、任意のアイデアなどを持っていくつかのパッケージが配信

のためのタイムスロットを与えてもよい

特定の道路（低橋、幅、高さ及び重量の制限）に制限することができどのようなアルゴリズムを使用してこれを行うことができるか、またはそれをどのように行うことができるかの例を挙げることができる。私はいくつかの大学の論文を見たことがありますが、かなり古い（おそらく現在はかなり非効率的です）とパッケージ管理を扱っていません - 彼らはすべてのバンとパッケージが同じサイズであると仮定します。

ご迷惑をおかけして申し訳ございません。

リッチ

Answer 1

pgRoutingは、ダイヤル・ライド問題のための遺伝的アルゴリズムを実装する新しい機能を持っていますhttp://www.pgrouting.org/docs/1.x/darp.html

これは、PostgreSQL/PostGISの延長だとあなたがこれを使用してアプリケーションを構築することができます。

Answer 2

任意のアルゴリズムこの具体的には、独自になるだろうと、あなたはおそらく何かを購入する必要があります。しかし、これは遺伝的アルゴリズムのインパネレーションで解決できる問題のような疑いがあると思われます。ここで私が見つけたいくつかの研究である：

http://www.ijimt.org/papers/38-M415.pdf

http://www.springerlink.com/content/w3165x33n24v8610/（書籍その問題に焦点を当てたように見える）アルゴリズムが古いので

http://www.computer.org/portal/web/csdl/doi/10.1109/ICCIT.2008.407

だけ、という意味ではありませんが、その効率的ではありません。

Answer 3

私の印象は、このような問題が日常的にオペレーションズ・リサーチで起こり、標準的なアプローチは混合整数計画ソルバーを使用することです。ここではMIPを使った貨物輸送スケジューリングの問題をコード化したan exampleです

MIPの近年の研究では、明らかに15年前の近代的なソルバは、元のものよりも速いです。30,000倍です。

解決策を最初から作成したい場合は、目的と制約が何であるかを把握してから、おおよその分岐と境界検索のような整数プログラミングのアイデアを使用することができます。