最短の輸送順序ルートを見つけるためのグラフアルゴリズム

Question

私は交通会社情報システムをモデル化している簡単なweb-appを持っています。私は指定された注文の最短ルートの自動計算の機能を実装したいと思います。

new order form

注文は貨物の集合で表現され、それらのそれぞれは、出発/到着ポイントを持っています。私はデータベース内の各ペア間の都市と距離を保存します。問題は、これらすべての貨物を輸送することを可能にする最短ルートを見つけることです。スタートとフィニッシュの都市は重要ではありませんが、唯一興味深い点は、すべての船積みの積み降ろしを含む最短経路です。

このような問題を解決するのに適したグラフアルゴリズムはありますか？

Answer 1

アイテムの数が比較的少ない場合（あなたのコメントが示唆しているように）、問題を​​に減らすことができます。

最初に、各都市の間に最短距離がない場合は、Floyd-Warshall algorithmを使用して見つけることができます。各都市の距離が既にある場合は、この手順を省略できます。

ここで、あなたはブルートフォースを使用している都市の数が少ない場合や、より複雑な動的プログラミングソリューションで簡単に解決できるTSPの問題があります。

私があなただったら、簡単な解決策から始めましょう。十分でない場合は、より複雑なものを実装してください。
都市の数が大きくなると、より洗練されたTSPアルゴリズムが必要になり、問題の性質上、最適ではない解決策を見つける必要があります。それは、あなたがほんの少数の都市の領域にいる間に、既存のソリューションがそのトリックを行うべきだと言いました。