車両ルート決定

最も一般的な最適化タスクの 1 つに、車両ルーティングがあります。これは、一連の場所を訪れる一連の車両にとって、最適なルートを見つけることを目標としています。通常、「最適」とは、合計距離または料金が最も少ないルートを指します。 ルーティングに関する問題の例としては、次のようなものが挙げられます。

• ある荷物配送会社が、ドライバーが配達するルートを割り当てたいと考えています。
• ケーブルテレビ会社が、技術者が住宅サービス通話を行うルートを割り当てることを検討しています。
• ライドシェアリング会社が、乗客が乗り降りするルートをドライバーに割り当てたいと考えています。

最も有名なルート選択の問題は、出張販売担当者問題（TSP）です。さまざまな場所の顧客を訪問し、出発地に戻る必要がある営業担当者にとって、最短ルートを見つけます。TSP はグラフで表すことができます。このグラフのノードはロケーションに対応し、エッジ（アーク）はロケーション間の直接移動を示します。たとえば、以下のグラフは、A、B、C、D というラベルが付いた 4 つのロケーションのみを持つ TSP を示しています。2 つの地点間の距離は、それらの地点を結ぶエッジの横にある数字で示されます。

考えられるすべてのルートの距離を計算すると、最短ルートは ACDBA で、合計距離は 35 + 30 + 15 + 10 = 90 になります。

ロケーションの数が増えると、問題が難しくなります。上記の例では、ルートは 6 つだけです。ただし、10 のロケーション（始点をカウントせず）がある場合、ルートの数は 362,880 になります。20 地域の場合、数値は 2432902008176640000 にジャンプします。 考えられるすべてのルートを網羅的に検索すると最短のルートが見つかりますが、これは、少数のロケーション セットを除き、計算処理の難易度が高くなります。より大きな問題の場合、解空間をインテリジェントに検索し、最適な（またはほぼ最適）の解決策を見つけるために最適化手法が必要になります。

TSP のより一般的なバージョンは、車両ルート選択の問題（VRP）です。この問題には、複数の車両が関係します。ほとんどの場合、VRP には制約があります。たとえば、車両に運搬できるアイテムの最大重量や積載量に上限がある場合や、顧客が要求する特定の時間枠内に運転手が店舗を訪問しなければならない場合があります。

OR-Tools は、次のような多くのタイプの VRP を解決できます。

• 巡回営業担当者問題。車両が 1 台だけ存在するような従来のルート選択問題です。
• 車両ルーティングの問題。複数の車両に関する TSP を一般化したものです。
• 収容力の制約がある VRP: 車両で運べる品物に対して最大容量を確保します。
• 時間枠を使用した VRP: 車両は指定された時間間隔で場所を訪問する必要があります。
• リソースの制約がある VRP。デポ（ルートの出発点）で車両を積み下ろすためのスペースや人員など。
• 訪問中断を伴う VRP。車両はすべての場所を訪問する必要はありませんが、訪問ごとにペナルティを支払う必要があります。

車両ルート選択の問題を解決する制限

車両のルーティングの問題は、本質的に対処不可能です。解決に要する時間は、問題の大きさに応じて指数関数的に増大します。非常に大きな問題の場合、最適なソリューションを見つけるのに OR-Tools（またはその他のルーティング ソフトウェア）で数年かかることがあります。その結果、OR-Tools によって、良いが最適ではない解決策が返されることがあります。より適切な解答を見つけるには、解法の検索オプションを変更します。例については、検索戦略の変更をご覧ください。