経路最適化とは？仕組み・アルゴリズム・主要ソリューションをわかりやすく解説

経路最適化（ルート最適化）とは、複数の訪問先を回るときに、移動距離・所要時間・コストといった指標が最小になるように、回る順序や車両への割り当てを決める技術です。配送の配車計画や営業の訪問ルート設計など、「どの順で回れば一番効率がよいか」を人手や勘ではなく計算で導く場面で使われます。この記事では、経路最適化の数理的な仕組み（TSP・VRP）、実際に使われるアルゴリズムの種類、そして自社開発向けのライブラリからパッケージ型の自動配車サービスまで、主要ソリューションの選び方を整理します。

まとめ：経路最適化のポイント

• 経路最適化は「巡回セールスマン問題（TSP）」と「配送計画問題（VRP）」という組合せ最適化問題として定式化される。実務の配車はほぼVRP。
• 訪問先が増えると経路の組合せは爆発的に増える（NP困難）。そのため大規模な問題は厳密な最短ではなく、良質な近似解を短時間で出すのが基本。
• アルゴリズムは、小規模を厳密に解く「厳密解法（ソルバー）」、初期解を素早く作る「構築法」、それを改善する「メタヒューリスティクス」に大別される。
• ツールは、自社システムに組み込む OR-Tools やクラウドAPI と、地図・動態管理込みで現場がすぐ使えるパッケージ型サービスに分かれる。制約の特殊さと社内人材で選ぶ。
• 精度を左右するのはアルゴリズムより入力データ（住所・所要時間・制約条件）の整備。ここが甘いとどんな最適化も現場で使われない。

経路最適化とは：定義と数理モデル

経路最適化は、数学的には「組合せ最適化問題」の一種です。地点の集合と地点間の移動コスト（距離や時間）が与えられたとき、あらかじめ決めた目的（総移動距離の最小化など）を満たす訪問経路を、膨大な組合せの中から探し出します。目的関数・制約条件・決定変数として問題を記述する考え方は数理最適化の基本で、詳しくは決定変数とは？目的関数・制約条件との違いと決め方【数理最適化の基本】で整理しています。

経路最適化の基礎となる2つの問題：TSPとVRP

経路最適化は、代表的な2つの問題として理解すると全体像がつかめます。

• 巡回セールスマン問題（TSP）：1台（1人）がすべての地点をちょうど1回ずつ訪問して出発地に戻る、最短の巡回経路を求める問題。経路最適化の最も基本的な形。
• 配送計画問題（VRP：Vehicle Routing Problem）：TSPを一般化した問題で、1959年にDantzigとRamserが定式化しました。複数の車両、積載量の上限、配達時間の指定（時間枠）といった制約のもとで、全車両の総移動コストを最小化します。現実の「配送ルートを組む」業務はほぼこのVRPにあたります。

つまり、営業担当が1人で回る訪問順を決めるのはTSP寄り、トラックが複数台で荷物を分担して配るのはVRP寄り、と押さえておくと使い分けが明確になります。

経路最適化が必要とされる背景

配送・物流ではドライバー不足と燃料費の上昇が続き、1台あたりの走行距離や積載効率がそのままコストに直結します。営業でも、1日に回れる訪問件数は移動時間に強く縛られます。こうした計画を担当者の経験と勘で組むと、属人化して品質が安定せず、担当交代のたびに効率が落ちます。経路最適化を使うと、走行距離・残業時間・CO2排出を定量的に削り、計画づくりを標準化できるのが導入の狙いです。

最適解の導出が難しい理由：組合せ爆発とNP困難

訪問先が増えると、回り方の組合せは急激に増えます。n地点のTSPでは巡回経路の総数はおおよそ (n-1)!/2 通りで、20地点でも天文学的な数になり、すべてを試して比較するのは現実的に不可能です。TSPやVRPはNP困難に分類され、地点数が増えると厳密に最短を求める計算時間が指数的に膨らみます。

そのため実務では、小規模な問題だけを厳密に解き、大規模な問題は「最短に近い良質な解を短時間で出す」近似解法を使います。ここは誤解されやすい点ですが、「最適化」を掲げるツールの多くが返すのは近似解であり、常に100%の最短を保証するわけではありません。求めるのは理論上の最短ではなく、実用上十分に良く、計算時間が現場の運用に収まる解です。

経路最適化の主要アルゴリズム

経路最適化のアルゴリズムは、問題をそのまま厳密に解く「厳密解法」、解の骨格を素早く作る「構築法」、その解を反復改善する「メタヒューリスティクス」に大別できます。実務のソルバーはこれらを組み合わせて使います。

厳密解法と数理最適化ソルバー

分枝限定法や分枝カット法を使い、問題を整数計画（MIP）として定式化して数理最適化ソルバーに解かせる方法です。理論上は真の最適解が得られますが、計算量の壁があるため、実用的に厳密解を出せるのは数十〜せいぜい数百地点程度が目安です。代表的なソルバーには商用のGurobiやオープンソースのSCIP・CBCがあり、制約が明確で規模が小さい問題に向きます。

構築法：初期解を素早く作る

大規模な問題では、まず「そこそこ良い経路」を高速に作る構築法から始めます。

• 最近傍法（Nearest Neighbor法）：現在地から最も近い未訪問地点へ順に進む方法。実装が簡単で高速ですが、最後に遠い地点が残りやすく、解の質は粗めです。
• セービング法（Clarke-Wright法）：1964年に提案されたVRPの定番手法。個別に配送していた2地点をまとめたときのコスト削減量（セービング値）が大きいペアから経路を統合していきます。VRPの初期解生成として今も広く使われます。

局所探索とメタヒューリスティクス

構築法で作った初期解を、経路の一部を入れ替えて改善するのが局所探索です。2つの辺を繋ぎ替える2-optや、配送順を移動させるOr-optが基本操作になります。ただし局所探索だけでは、それ以上改善できない「局所最適解」で止まってしまいます。

そこから抜け出すために使うのがメタヒューリスティクスです。焼きなまし法（Simulated Annealing）、タブーサーチ、遺伝的アルゴリズム（GA）、蟻コロニー最適化（ACO）、大規模近傍探索（LNS／ALNS）などがあり、あえて一時的に悪い解も許容しながら探索範囲を広げ、現実的な時間で良質な近似解にたどり着きます。市販・OSSの経路最適化エンジンの多くは、構築法とメタヒューリスティクスの組合せで動いています。

アルゴリズムの選び方

選定の順序は、アルゴリズムありきではありません。まず問題の規模（地点数）と制約（時間枠・積載量・車両ごとの対応可否）を洗い出し、それに合わせて手法を決めます。地点数が少なく制約が単純なら厳密解法で最短を狙い、地点数が多い・制約が複雑なら構築法とメタヒューリスティクスの組合せが現実的です。自作するより既存エンジンを使うことがほとんどなので、実務では「どのソルバー／サービスがこの制約を扱えるか」で選ぶことになります。

経路最適化ソリューションの選び方と主要ツール

経路最適化を実現する手段は、自社システムに組み込むライブラリ・APIと、現場がそのまま使えるパッケージ型サービスに分かれます。配送ルート最適化ソフトウェア（「トラフィック最適化ソリューション」と呼ばれることもあります）を比較検討するときは、この2系統のどちらが自社に合うかから考えると迷いません。

自社開発向け：ライブラリ・API・エンジン

• Google OR-Tools：Googleが提供する無料のオープンソース最適化ライブラリ。TSP・VRP・時間枠・積載制約に標準対応し、自社システムへ組み込んで使えます。使い方はGoogle OR-Toolsとは？できること・インストール・実装例をわかりやすく解説で解説しています。
• Google Maps Platform Route Optimization API：ドライバー数や配達指定時間、交通状況を加味して配送ルートを算出するクラウドAPI。従量課金で、地図データと組み合わせて使えます。
• NVIDIA cuOpt：GPUで大規模な経路最適化を高速に解くエンジン。数千地点規模のVRPを短時間で扱う用途に向きます。

ソルバーやライブラリを横断して比較したい場合は、ORツールとは？主要6ツールの比較と選び方【ライセンス・費用・得意問題】も参考になります。

パッケージ型の自動配車サービス

アルゴリズムを意識せず、地図・動態管理・帳票までまとめて使えるのがパッケージ型のサービスです。国内では、VRPの研究を背景に持つLoogia（オプティマインド）、AIエンジンを搭載したLYNA自動配車クラウド（ライナロジクス）、小規模から使えるODIN配送計画などがあります。海外ではOptimoRouteなどが代表的です。各社は車両台数や走行距離の削減率を公表していますが、削減幅は配送条件によって大きく変わるため、自社の条件に近い事例と最新の料金は公式資料で確認してください。

内製とパッケージの選択基準

判断軸は3つです。第一に地点・車両の規模、第二に制約の特殊さ（自社独自のルールがどれだけあるか）、第三に社内に最適化を扱える人材がいるか。制約が特殊で大規模、かつ基幹システムと密に連携したいならOR-ToolsやAPIによる内製が向きます。逆に、配送内容が定型的で早く始めたいならパッケージ型が確実です。避けたいのは、最適化人材を確保しないまま中途半端に内製することで、初期は動いても制約変更のたびに保守が破綻しやすくなります。まずパッケージで効果を確かめ、限界が見えてから内製に移る進め方が堅実です。

経路最適化の主な適用業務

経路最適化は、複数拠点を効率よく回る必要がある幅広い業務で使われています。

• 物流のラストワンマイル配送：宅配・EC配送で、時間指定と積載量を守りながら配車を最適化。
• ルート配送：食品・飲料・日用品などの定期配送で、固定ルートの見直しに活用。
• 営業の訪問ルート最適化：担当者が1日に回る顧客の訪問順を最短化し、訪問件数を増やす。
• フィールドサービス：設備保守・点検・修理の巡回スケジュール最適化。
• 公共サービス：ゴミ収集や見回りなど、決まったエリアを漏れなく回る計画。

導入でつまずかないための実務ポイント

経路最適化プロジェクトが失敗する原因は、アルゴリズムの性能不足よりも運用設計にあることがほとんどです。導入前に次の3点を押さえておくと、現場で使われる仕組みになります。

• 入力データの整備が精度の大半を決める：住所のジオコーディング精度、地点間の実際の所要時間、荷量などの元データが不正確だと、どんなに高度なアルゴリズムでも現実離れした経路が出ます。マスタデータの整備を最優先にします。
• 制約条件を最初に定義する：時間枠、車両ごとの積載・対応可否、休憩、進入禁止などの現場ルールを最初に洗い出さないと、計算上は最適でも現場が使えない計画になります。
• 現場が結果を上書きできる余地を残す：最適化結果を絶対視せず、ドライバーの土地勘や当日の事情で微修正できるようにしておくと定着します。完全自動化を急ぐと反発を招きがちです。

よくある質問

経路最適化とは何ですか？

複数の訪問先を回る際に、移動距離・時間・コストが最小になる訪問順序や車両割り当てを計算で求める技術です。数学的には巡回セールスマン問題（TSP）や配送計画問題（VRP）という組合せ最適化問題として扱われます。

経路最適化にはどんな技術・アルゴリズムが使われますか？

小規模を厳密に解く分枝限定法などの厳密解法、初期解を作る最近傍法・セービング法、それを改善する2-optやメタヒューリスティクス（焼きなまし法・遺伝的アルゴリズム・タブーサーチなど）を組み合わせて使います。

無料で経路最適化はできますか？

自社開発なら、GoogleのオープンソースライブラリOR-Toolsを無料で使えます。少数地点であればGoogleマップの経路案内でも簡易な最適化は可能です。多数地点や時間指定など制約が多い業務では、専用サービスの利用が現実的です。

営業ルートの最適化にも使えますか？

使えます。1人が複数の顧客を回る訪問順の最適化はTSPに近く、経路最適化の得意分野です。訪問件数の増加や移動時間の短縮に直結します。

なぜ最短ルートが一瞬で出ないのですか？

訪問先が増えると経路の組合せが指数的に増える（NP困難）ためです。厳密に最短を求めるのは小規模に限られ、大規模では良質な近似解を短時間で出す方式が使われます。

関連記事

• Google OR-Toolsとは？できること・インストール・実装例をわかりやすく解説
• ORツールとは？主要6ツールの比較と選び方【ライセンス・費用・得意問題】
• 決定変数とは？目的関数・制約条件との違いと決め方【数理最適化の基本】
• Gurobiとは？Pythonでの使い方・インストール・価格を解説
• 実務で役立つPythonの最適化関数（SciPy）：効率的な利用シーンと事例紹介