Grab流の配送効率をOSSで再現！PythonとOR-Toolsで構築する動的ルート最適化エンジンの実装手順

東南アジアを訪れると、GrabやGojekのバイクが驚くほどスムーズに人や物を運んでいる光景を目にしますよね。彼らの強みは、単なる配車アプリというだけでなく、裏側で動いている極めて高度なルート最適化アルゴリズムにあります。

「うちの物流部門もあんな風に効率化したい」

そう考えて物流DXのソリューションを探し始めると、多くの企業が壁にぶつかります。それは、専用パッケージソフトの導入コストが非常に高いという現実です。数千万円規模の投資が必要だったり、月額費用が車両台数に応じて青天井になったりと、中堅規模の企業が「まずは試してみる」にはハードルが高すぎる傾向にあります。

でも、諦める必要はありません。実は、GrabやGojekが使っているような最適化技術のコア部分は、オープンソースソフトウェア（OSS）とAPIを組み合わせることで、自社でも十分に再現可能です。

今回は、概念論ではなく「手を動かして作る」ことに主眼を置き、Googleが提供する数理最適化ソルバー「OR-Tools」とPythonを使って、自社専用の動的ルーティングエンジンを構築する手順を解説します。エンジニアの方も、DX推進担当の方も、ぜひこの手順を参考に、自社の物流革新への第一歩を踏み出してみてください。

1. Grab/Gojek型「動的ルーティング」の技術的解剖と導入要件

まずは、彼らが何をやっているのか、技術的な視点で分解してみましょう。彼らのシステムが優れているのは、単に「最短距離」を走っているからではありません。VRP（Vehicle Routing Problem：配送計画問題）と呼ばれる複雑な数学的問題を、リアルタイムに近い速度で解き続けている点にあります。

静的計画と動的最適化の決定的な違い

従来の日本の物流現場でよく見られるのは「静的計画」です。前日の夜に配送ルートを決め、当日はその通りに走る。これだと、当日の急な依頼や交通渋滞、ドライバーの体調不良などに対応できません。

一方、Grab型のアプローチは「動的最適化」です。

• リアルタイム入力: 新規注文や交通状況が随時システムに入る
• 再計算: 状況変化に応じてルートを瞬時に引き直す
• 割り当て変更: 最適な車両へタスクを動的に割り振る

これを自社で再現するには、固定されたルート表ではなく、常に計算し続けるエンジンが必要になります。

必要なデータセットの定義

アルゴリズムを動かすには、燃料となるデータが必要です。最低限、以下の3つをデジタル化して用意する必要があります。

1. 位置情報（Coordinates）: 配送先の住所を緯度・経度に変換したもの。
2. 時間枠（Time Windows）: 「午前中」「14時〜16時」といった配送指定時間。
3. 積載量（Capacity）: トラックやバイクに積める荷物の量と、荷物自体のサイズ。

これらがExcelや紙の伝票に散らばっているなら、まずはこれをCSVやデータベースに集約することから始めましょう。

自社再現のための技術スタック選定

「何を使って作るか」ですが、スモールスタートなら以下の構成が一般的です。

• 言語: Python（ライブラリが豊富で実装が早い）
• ソルバー: Google OR-Tools（無料で高性能、VRPに強い）
• 地図データ: Google Maps Platform または OSRM（Open Source Routing Machine）

商用の配送管理システムを購入するのではなく、これらの部品を組み立てるアプローチなら、初期コストを開発工数のみに抑えられます。費用対効果を重視する現場において、非常に現実的な選択肢となります。

2. 事前準備：最適化エンジンのためのデータ構造化と環境構築

実際の構築に向けた準備を進めます。AIやアルゴリズムと聞くと複雑な印象を受けるかもしれませんが、実のところ「データを正しく渡せるか」が成否の大部分を握っています。

配送先データのクレンジングとジオコーディング

「東京都港区...」といった住所文字列のままでは、計算機は距離を算出できません。これを緯度経度（例: 35.6585, 139.7454）に変換するジオコーディングという処理が不可欠です。

Google Maps Geocoding APIなどを活用すれば変換自体は容易ですが、ここで最も注意すべきは精度の確保です。ビル名や階数まで正確に入力されていないと、建物の裏側や入口の反対側に案内されてしまうケースが珍しくありません。実際の物流現場では「トラックを安全に停車できる位置」が正解となるため、可能であれば過去の配送実績から「実際の停車位置の座標」を抽出し、マスタデータとして整備しておくのが理想的です。

車両・ドライバー制約のパラメータ化

次に、現場の制約条件をプログラムが解釈できる形式（JSONなど）で定義します。

{
  "vehicles": [
    {
      "id": "truck_01",
      "capacity": 1000,  // 積載量(kg)
      "start_location": [35.6895, 139.6917], // 車庫の位置
      "time_window": [480, 1080] // 稼働時間 8:00-18:00 (分換算)
    }
  ]
}

このように、現場特有のルールを具体的な数値やフラグに落とし込む作業が求められます。「特定のベテランドライバーは狭い路地でも配送可能」といった、属人化しやすいドライバーのスキル情報も、ここでパラメータ化（例: "skill": ["narrow_road"]）しておくと、最終的なルート最適化の精度が飛躍的に向上します。

開発環境のセットアップ

ベースとなるPython環境を用意し、必要なライブラリをインストールします。今回はGoogleのOR-Toolsをコアとなるソルバーとして利用します。

pip install ortools pandas requests googlemaps

開発環境と本番環境の差異によるトラブルを防ぐため、Dockerを活用して環境をコンテナ化しておく手法が効果的です。チーム開発や将来的なクラウド環境へのデプロイを見据えると、コンテナ技術の導入はほぼ必須の要件と言えます。

ここで環境構築における重要な注意点があります。Docker EngineやDocker Composeの最新バージョンでは、定期的なセキュリティ更新が実施されるとともに、一部の古い機能が廃止されています。GitHub ActionsなどのCI/CDランナー環境でも順次最新版へのアップデートが適用されているため、廃止された機能に依存する既存のワークフローや設定ファイル（Dockerfileやdocker-compose.yml）をそのまま使用すると、思わぬエラーを引き起こす可能性があります。環境を構築・移行する際は、必ず公式ドキュメントの変更履歴（Changelog）を確認し、推奨される最新の記述方法へ設定をアップデートしてください。

また、Docker Desktopを商用利用する場合は、組織の従業員数や売上規模に応じたライセンス形態（有料プランの適用条件）に留意する必要があります。最新の利用規約や正確なインストール手順については、Docker公式サイトで確認してください。Linux環境での無償のDocker Engineの利用も含め、セキュリティ要件と組織のポリシーに合致した環境選定をお勧めします。

これで、最適化エンジンを稼働させるための下準備は完了です。

3. ステップ1：ベースラインとなる配送計画ソルバーの実装

ここからが本番です。まずは「複数の配送先を、総移動距離が最小になるように回るルート」を計算する基本的なエンジンを作ります。

距離行列（Distance Matrix）のAPI連携設定

ルート計算には、地点間の距離と移動時間が不可欠です。出発地点から到着地点への移動コストをまとめた表を距離行列と呼びます。

Google Distance Matrix APIを使うと、リアルタイムの渋滞情報を加味した正確な時間が取れますが、APIコール数に応じた従量課金になります。開発段階では、APIキーを設定し、必要な地点間のデータを取得してローカルに保存（キャッシュ）する仕組みにしておきましょう。毎回APIを呼び出すと、テストだけで多額の費用がかかってしまうこともあります。

VRPソルバーの初期設定コード

OR-Toolsを使って、データをモデルに読み込ませます。イメージとしては以下のような流れです。

1. データモデルの作成: 距離行列、車両数、デポ（出発点）を辞書型データにする。
2. ルーティングインデックスマネージャーの作成: 内部的なノード番号と実際の場所を紐付ける。
3. ルーティングモデルの定義: ここに制約を追加していく。

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

# データ作成（簡略化）
def create_data_model():
    data = {}
    data['distance_matrix'] = [...] # APIから取得した行列
    data['num_vehicles'] = 4
    data['depot'] = 0
    return data

# モデルの初期化
data = create_data_model()
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                       data['num_vehicles'], data['depot'])
routing = pywrapcp.RoutingModel(manager)

基本的なコスト関数（総移動距離最小化）の定義

「何を最適化したいか」を定義します。まずはシンプルに「移動距離」をコストとして設定します。

def distance_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

これで「ソルバーを実行」すれば、数学的に最も距離が短いルートが出力されます。これがGrab流アルゴリズムの第一歩です。

4. ステップ2：実用性を高める制約条件とパラメータチューニング

ステップ1で作ったものは、あくまで「理論上の最短ルート」です。実際の現場では「最短だけど、指定時間に間に合わない」「このトラックには積めない」といった課題が必ず発生します。ここから実用レベルに引き上げていきます。

時間枠指定（Time Windows）の実装設定

配送現場で最も重要なのが「時間指定」です。OR-Toolsでは、Dimension（次元）という概念を使って時間を管理します。

「累積時間」という次元を追加し、各地点での到着時間が「指定された開始時間」と「終了時間」の間に収まるように制約をかけます。

time = 'Time'
routing.AddDimension(
    transit_callback_index,
    30,  # 許容される待機時間（分）
    3000,  # 車両の最大稼働時間
    False,  # 累積をゼロにリセットしない
    time)
time_dimension = routing.GetDimensionOrDie(time)

# 各地点に時間枠を設定
for location_idx, time_window in enumerate(data['time_windows']):
    index = manager.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

これにより、単に近い順に回るのではなく、「14時に特定の地点に行かなければならないから、先に別の地点を回る」といった人間のような判断を自動で行えるようになります。

複数車両・デポ（拠点）の設定

車両ごとに積載量が異なる場合も設定が必要です。これも「Capacity」というDimensionを追加して管理します。

• 軽トラ：積載350kg
• 2tトラック：積載2000kg

これらをリスト化してモデルに渡すと、ソルバーは「大きな荷物は2tトラックのルートに組み込む」といった割り振りを自動計算します。これができれば、配車担当者が頭を悩ませていた「荷物のパズル」から解放されます。

ペナルティ関数の設定による柔軟な割り当て

現実には「どうしても全件回りきれない」日もあります。その時、エラーで止まってしまっては困ります。

そこで、一部の配送先を「回らない（ドロップする）」ことを許容しつつ、その代わりに莫大なペナルティコストを加算する設定にします。こうすると、システムは「基本は全部回るが、どうしても無理な場合は優先度の低い1件だけを外す」という現実的な解を出してくれるようになります。

5. ステップ3：シミュレーション検証と現場導入へのブリッジ

エンジンができたら、いきなり本番投入せず、まずは過去データを使ってシミュレーションを行います。

既存ルートとAI最適化ルートの比較検証（A/Bテスト）

過去1ヶ月分の配送データを用意し、「実際に人間が組んだルート」と「AIが計算したルート」を比較します。

• 総走行距離はどれくらい減ったか？
• 稼働時間は短縮できたか？
• 車両台数を減らせる可能性はあるか？

熟練の配車担当者が組んだルートと比べても、走行距離で10〜15%、計算時間に関しては90%以上の削減が見込める可能性があります。この数値をROI（投資対効果）の根拠として、経営層や現場責任者に提案しましょう。

ドライバー向け出力フォーマットの整備

どんなに優れたルートも、ドライバーに伝わらなければ意味がありません。計算結果のJSONを、見やすい形に変換します。

• Googleマップのリンク付きリスト: スマホでタップすればナビが始まる。
• LINE通知: ルート順序をテキストで送る。

最初は高機能なアプリを作る必要はありません。現場が使い慣れているツールに情報を流し込むだけで十分です。

API化と既存システムへの統合手順

PoCが成功したら、このPythonスクリプトをWeb API（FlaskやFastAPIを使用）としてラップし、サーバー上で常駐させます。そうすれば、既存の受注システムから「配送リスト」をPOSTするだけで、「最適ルート」が返ってくるマイクロサービスの完成です。

6. よくある実装トラブルと解決策

最後に、多くのプロジェクトで直面する可能性のある「落とし穴」とその回避策をお伝えします。

「現実離れしたルート」が出力される原因と対策

「システムがUターン禁止の場所でUターンを指示した」「トラックが入れない細い道を案内された」という意見が出るかもしれません。

これは、使用している地図データの「属性情報」不足が原因です。Google Maps APIの「driving」モードは乗用車基準であることが多いため、トラック特有の規制を考慮できません。

対策: トラック対応のナビゲーションAPI（商用のものや、OSRMのプロファイル設定）を検討するか、あるいは「エリアごとの進入禁止リスト」を自前で持ち、そのエリアを通るルートにはペナルティを課すロジックを追加することで緩和できます。

地図APIコストの爆発を防ぐキャッシュ設計

動的ルーティングを行うと、距離行列の取得回数が膨大になります。Google Maps APIは従量課金なので、何も考えずにループで回すと、月に数十万円の請求が来ることもあります。

対策: 地点間の距離データはそう頻繁に変わりません。「出発地点から到着地点」の距離と時間はデータベースにキャッシュし、有効期限（例: 1ヶ月）内であればAPIを叩かずにキャッシュを使う設計を徹底してください。これだけでコストを大幅に抑えられます。

計算が終わらない時のタイムアウト設定

配送先が100件、200件と増えると、組み合わせの数は天文学的になり、計算が終わらなくなります。

対策: OR-Toolsには「計算時間の上限（Time Limit）」を設定できます。「30秒以内に見つかった中で一番良い解を出す」という設定にしましょう。物流現場では、数学的な厳密解（100点満点）が出るまで1時間待つより、95点の解が30秒で出る方が実用的で価値があります。

まとめ：まずは小さなエリアで「自動化」の手応えを

GrabやGojekのような高度な物流システムも、最初は小さなプログラムから始まっています。今回ご紹介した手順を使えば、高額な投資をしなくても、自社のデータを使ってルート最適化の威力を検証することができます。

まずは特定の営業所や、少数の車両だけでスモールスタート（PoC）してみてください。「本当に計算が一瞬で終わる」「意外と実用的なルートが出る」という手応えが得られるはずです。

ただ、実際に現場へ導入するフェーズになると、「ドライバーごとの休憩時間の考慮」や「リアルタイムの動態管理との連携」など、さらに細かい調整が必要になる可能性があります。もし、「実装してみたけれど精度が上がらない」「自社の特殊な制約をどうコードに落とし込めばいいかわからない」といった課題があれば、専門家に相談することをおすすめします。