ルート最適化とは、フリートが最短時間・最短距離・最低コストで作業を終えるよう、ストップの順序を決め車両を割り当てる手法です。同じバンと同じストップで、16時に終わる配送ドライバーと19時に終わるドライバーの違いを生むものです。ロジスティクスアプリの「ルート最適化」ボタンの裏では、ソルバーが何百万もの候補順序を計算し、その中から1つを選んでいます。
このガイドでは、ルート最適化とは実際に何か、ソルバーがどうアプローチするか、現実の世界でどこに登場するか、デモと本番を分ける制約と落とし穴について解説します。
ルート最適化の本質
コンピュータサイエンスでは、ルート最適化は2つの古典的な問題に位置します。巡回セールスマン問題（TSP）は「都市のリストと都市間の距離が与えられたとき、すべての都市をちょうど1度訪れて出発地に戻る最短ルートは？」を問います。これは単一車両の問題です。車両ルーティング問題（VRP）はこれをフリートに一般化します。デポ、顧客集合、複数車両が与えられたとき、顧客を車両間でどう分け、各車両がどの順序で訪問すべきか、という問題です。
両問題ともNP困難です。可能な順序の数はストップ数に対して階乗的に増えます。20ストップだけで10の18乗以上のルートになります。厳密アルゴリズムではリアルタイムでこの空間を探索できません。したがって本番環境での最適化は、完璧な答えを見つけることではなく、行動に移せる十分な速さで非常に良い答えを見つけることです。
ソルバーのアプローチ
探索空間が膨大なため、実際のソルバーは複数の技術を組み合わせます。
小規模問題（おおよそ15ストップ未満）では、分枝限定法や整数計画法で数秒以内に証明可能な最適解を返せます。それ以上の規模では厳密法は実用的でなくなり、ヒューリスティクスに切り替わります。
典型的なパイプラインは、最近傍法やClarke-Wrightセービングス法のような構築ヒューリスティクスで初期ルートを生成することから始まります。そのルートはメタヒューリスティクスに渡され、ストップを入れ替え、サブツアーを反転し、ストップを車両間で移動させて目的関数を改善します。シミュレーテッドアニーリング、タブー探索、大規模近傍探索、遺伝的アルゴリズムが最も一般的な選択肢です。いずれも形は同じです。変更を試み、受け入れるか決め、固定時間予算の中で繰り返します。
もう1つの重要な入力は距離マトリクスです。すべてのストップペア間の所要時間と距離の事前計算済みテーブルです。オプティマイザは探索中にマトリクスを数百万回クエリするため、ルーティングエンジンで事前に1度だけ構築し、ソルバー実行中はメモリに保持します。
ルート最適化の活用シーン
ルート最適化は、多くの運用ビジネスを静かに支えています。
- ラストマイル配送: 宅配業者、食料品配達、Eコマースのフルフィルメントは、1日あたり1台のバンに数十から数百のストップを順序付けます
- フィールドサービス: HVAC技術者、通信設置員、訪問医療スタッフが、予約枠とスキル要件を持つ顧客を地域横断で訪問します
- モバイルワークフォース: 公益事業作業員、メーター検針員、検査員が複数のタスクタイプでテリトリーを巡回します
- フードデリバリー: レストランアグリゲーターが、地理が一致するときに複数注文を1人のライダー行程にバッチ化します
- ゴミ収集: 自治体トラックが固定の週次ルートを走り、わずかな順序変更で実際の燃料を節約します
- 営業担当: 1日8〜12アカウントを訪問し、ドライブ時間と商談密度のために順序が重要となるテリトリー計画です
いずれの場合も、ユーザーには正しい順序のストップリストが見えます。仕事はその裏のオプティマイザで行われています。
重要な制約
距離だけを最小化するソルバーはおもちゃです。本番のルーティングは制約によって定義されます。
- 車両容量: 各バンには重量、容積、パレット制限があり、割り当てたストップはそれを超えてはいけません
- 時間枠: 顧客は例えば9時から11時の配送を期待しており、11:05の到着は失敗です
- ドライバーシフト: 最大労働時間、必須休憩、特定デポでの開始・終了
- スキルや車両のマッチング: 冷蔵庫設置には2人組チームが必要、コールドチェーン配送には冷蔵バンが必要
- マルチデポ: 大規模フリートは複数倉庫から配車し、ソルバーがどのデポがどのストップを担当するか決めます
- 拠点復帰: ドライバーが自宅で終わるオープンルートと、デポに戻るクローズドルートがあります
各制約は実行可能ルートの集合を縮小し、紙の上ではやや劣って見えるが実際には実行可能な解の方向にソルバーを押します。
本番環境での落とし穴
ルート最適化はデモは常に動き、ロールアウトはしばしば失敗するカテゴリです。
間違った目的関数の最適化。距離最小化がデフォルトですが、多くのフリートでは、節約したキロ数より売上やサービスレベルの遵守の方が重要です。2km余分に走って1個追加配送するルートは通常勝ちです。
フリーフロー vs 交通対応の所要時間。生の道路速度から構築したマトリクスは、ラッシュアワーの実所要時間が6時間のルートを4時間と教えます。ルートが走る時間帯の交通対応所要時間を公開するルーティングエンジンを使ってください。
リアルタイム再計画なし。ドライバーが予期せぬ渋滞に遭ったり、顧客がキャンセルしたり、新しいストップが入った瞬間に計画は崩れます。運用チームは、午前中の作業を捨てずに残りのストップを再最適化する手段を必要とします。
固定計画の陳腐化。1月に最適だった週次固定ルートが、顧客が移動し、量が変動し、一方通行が増えたため、今では20%劣化しているということがあります。最適化を定期的に再実行し、ドライバーに変更を強制する前に新計画と現行計画を比較してください。
MapAtlasのルート最適化
MapAtlas Optimize Route APIは、運用チームが実際に必要とする制約（容量、時間枠、シフト、スキル、マルチデポ構成）で単一車両およびフリートのルーティング問題を解きます。各車両ごとに、すべてのストップの予測到着・出発時刻を含む順序付き計画を返します。
これはMapAtlasスタックの他の2つのエンドポイントと自然に組み合わさります。Distance Matrix APIはソルバーが消費する所要時間テーブルを構築し、ラッシュアワーでも計画が成り立つ交通対応所要時間を提供します。Directions APIは順序が確定した後、連続するストップ間の実際のターンバイターン道路経路を描き、ドライバーアプリが直線ではなく実際のポリラインを表示できるようにします。
ルート最適化はスライドデッキでは華やかには見えません。ソルバー、マトリクス、制約のリストです。しかしフリートが時間通り予算内で1日を終えるかを決める層であり、これを正しく構築することが、出荷されるルーティング機能と、こっそり停止される機能を分けるのです。
よくある質問
ルート最適化とは何ですか？
ルート最適化とは、複数のストップを訪問する最適な順序を決め、車両が複数ある場合はどの車両がどのストップを担当するかを決定するプロセスです。目標は、車両容量・ドライバーシフト・顧客の時間枠などの実世界の制約を満たしつつ、総ドライブ時間・距離・燃料・コストといった目的関数を最小化することです。コンピュータサイエンスでは、単一車両の場合は巡回セールスマン問題（TSP）、フリートの場合は車両ルーティング問題（VRP）という2つの古典問題に位置づけられます。
ルート計画とルート最適化の違いは何ですか？
ルート計画は「AからBへどう行くか」に答え、2点間の単一経路をターンバイターンの指示付きで返します。ルート最適化は「6台のバンでこれら80のストップをどの順序で訪問し、どのバンがどのストップを担当するか」に答えます。最適化は計画の1つ上の層に位置し、順序と割当を決めてから、ルーティングエンジンを呼び出して各ストップ間の実際の道路経路を描きます。
ルート最適化にはどのアルゴリズムが使われますか？
小規模問題（おおよそ15ストップ未満）では、分枝限定法や整数計画法といった厳密法で証明可能な最適解を見つけられます。それを超えると探索空間が爆発するため、本番システムはヒューリスティクスやメタヒューリスティクスを使います。最近傍法やセービングス法で初期解を作り、局所探索、シミュレーテッドアニーリング、タブー探索、遺伝的アルゴリズムで改善します。商用ソルバーの多くは複数の手法を組み合わせ、証明可能な最適性ではなく固定の時間予算で実行されます。
ルート最適化APIにはどんな入力が必要ですか？
最低限必要なのは、座標付きのストップリスト、開始・終了拠点を持つ車両、すべてのストップペア間の距離または時間マトリクスです。実際には、車両容量、顧客の時間枠、各ストップでのサービス所要時間、ドライバーのシフト時間、ストップごとに必要なスキルや車両タイプ、デポの位置も入力します。マトリクスは最も重い入力で、通常は最適化実行前に別の距離マトリクスAPIで生成します。
