OpenStreetMapで配送ルート最適化デモを作ってみた

「複数の配送先を効率よく回るには、どの順番がベストなのか」

物流に関わる方なら一度は考えたことがある問題ではないでしょうか。これは数学的には「巡回セールスマン問題（TSP）」として有名で、配送先が増えるほど組み合わせが爆発的に増加するため、最適解を求めるのが難しいことで知られています。

今回、オープンソースの地図データとルーティングAPIを使って、この問題を体験できるデモを作ってみました。

まずは触ってみてください

プリセットから「東京都心（10箇所）」を選択するか、住所検索や地図クリックで配送先を追加して、「最適化を実行」ボタンを押してみてください。

オレンジ色が「入力順に回った場合」のルート、青色が「最適化後のルート」です。どれだけ距離と時間が削減されるか、視覚的に確認できます。

使っている技術について

OpenStreetMap

OpenStreetMapは、世界中のボランティアによって作成・更新されているオープンな地図データベースです。Google Mapsとは異なり、データの利用制限が少なく、商用利用も含めて自由に活用できるのが特徴です。

地図の表示には、OpenStreetMapが提供している公開タイルサーバーを使用しています。

OSRM（ルーティングエンジン）

OSRM（Open Source Routing Machine）は、OpenStreetMapのデータを使ってルート計算を行うオープンソースのルーティングエンジンです。

このデモでは主に2つのAPIを使っています：

• Table API: 複数地点間の距離行列を一括で取得
• Route API: 指定した地点を結ぶ、実際の道路に沿ったルートを取得

今回はOSRMのデモサーバーを使用していますが、自社サーバーにOSRMを構築すれば、API制限を気にせず利用できます。

ルート最適化のアルゴリズム

配送先が10箇所あると、すべての順番を試す場合は約360万通り。20箇所なら天文学的な数字になります。すべてを計算するのは現実的ではありません。

そこで今回は、広く知られている近似アルゴリズムを組み合わせて使用しました：

1. 最近傍法（Nearest Neighbor）: 今いる場所から一番近い未訪問の配送先を選んでいく方法。シンプルで高速ですが、必ずしも最適な結果にはなりません

2. 2-opt改善法: 上記で得たルートを改善する手法。ルートの一部を入れ替えて、総距離が短くなるなら採用する、という操作を繰り返します

どちらも古くから使われている定番の手法です。厳密な最適解ではありませんが、実用的な時間内でそれなりに良い結果が得られます。

地図UI（Leaflet + React）

地図の表示にはLeafletを使用し、react-leafletでReactコンポーネントとして統合しています。Leafletは軽量でカスタマイズしやすく、OpenStreetMapとの組み合わせでよく使われるライブラリです。

実際の物流システムとの違い

今回のデモは最もシンプルな形のTSPです。実際の物流業務では、もっと多くの制約が加わります：

• 時間枠制約: 「10時〜12時の間に届けてほしい」といった指定
• 車両容量制約: トラックの積載量に収まるよう割り当てる
• 複数車両への分配: 複数台で手分けして効率よく配送する

こうした制約を含む問題は「車両配送問題（VRP）」と呼ばれ、Google OR-ToolsやOptaPlannerといった専用のソルバーを使って解くのが一般的です。

まとめ

OpenStreetMapとOSRMというオープンソースの組み合わせで、配送ルート最適化の仕組みをここまで再現できました。

商用の地図APIやルーティングサービスを使わなくても、オープンソースだけでこうしたデモが作れるのは面白いですね。物流のデジタル化に興味がある方は、ぜひ触ってみてください。