Upgrade to Pro — share decks privately, control downloads, hide ads and more …

オンデマンド交通のための車両ルーティング問題

Avatar for GO Inc. dev GO Inc. dev
July 07, 2025
28

 オンデマンド交通のための車両ルーティング問題

社内勉強会で使用した資料です。
オンデマンド交通のための車両ルーティング問題についてまとめました。

Avatar for GO Inc. dev

GO Inc. dev

July 07, 2025
Tweet

Transcript

  1. AI ▪ 目的関数 ▪ x ij : 地点iから地点jへの道を通る場合は1, 通らない場合は0 ▪

    c ij : 地点iから地点jへ移動するのにかかるコスト VRP ▪ 制約 ▪ 各顧客は必ず1回だけ訪問される ▪ 車両はある顧客を訪問したら、必ずそこから出発する ▪ 全ての車両はデポ(車庫)から出発し、デポに戻る 目的関数は一つとは限らず「総移動距離を最小化する」だけ でなく「車両台数を最小化する」「全ドライバーの走行距離 を平準化する」など複数の目的を組み合わせることもある 5
  2. AI 最適解ではなく近似解を素早く見つける 構築的ヒューリスティクス (Constructive Heuristics) • 何もない状態からある一定のルールにしたがって逐次 的に解を構築する手法 • 得られる解の質は最適解から大きく劣ることが多い

    改善ヒューリスティクス (Improvement Heuristics) • 構築的ヒューリスティクスなどで得られた初期解を出発 点とし、解に小さな変更(近傍操作)を繰り返し加え、より 良い解へと改善していく手法 メタヒューリスティクス (Metaheuristics) • 構築法や改善法を部品として利用しつつ、局所最適解 から脱出するための探索戦略 • 解空間をより広範に探索し、質の高い解を発見する可 能性が高まる ▪ アルゴリズムの洗練度に応じて階層的に分類できる 7
  3. AI 代表的手法 : 最近傍法 (Nearest Neighbor) ▪ 目的関数を直接計算するのではなく、「最も近いところへ行く」という貪欲 なルールに従って逐次的に変数の値(どの x

    ij を1にするか)を決めていく ▪ 制約を満たす中で最も近いことろを選ぶ ▪ 制約を満たすところがなければデポに戻り、新しいルートを開始する 構築的ヒューリスティクス 8
  4. AI 代表的手法 : 2-opt法 ▪ 既存のルート(x ij の組み合わせ)に対して、より良い解がないかを探す ▪ ルート上にある交差する2つの辺を削除し、交差しないように繋ぎかえる

    ▪ ルートが短くなり、かつ制約を満たす場合に、変更を採用する ▪ 小さな変更しかしないので局所最適解に陥りやすい 改善ヒューリスティクス 9
  5. AI 代表的手法 : 大規模近傍探索(LNS, Large Neighborhood Search) ▪ 構築法・改善法を部品として利用し、局所最適解から脱出するための戦略 メタヒューリスティクス

    破壊 解の一部をランダム or 特定のルールで取り除く 修復 取り除かれたリクエストを、残されたルートに再挿入する(構築的ヒューリスティ クスなどを使う) ▪ 修復によって得られた解が元の解より改善されていれば採用 ▪ 局所最適解からの脱出を促すために一定確率で改悪解も受容する 10
  6. AI ▪ Dial-a-Ride Probrem ▪ 相乗り問題特有の制約を加える ▪ VRP(輸送問題)と異なり、人間を運ぶため人間中心の性質に起因する 特有の制約がある DARP

    乗降ペア・先行制約 リクエストが乗車地点・降車地点のペアで構成され、その順番を守らな ければいけない 容量制約 車両の定員を超えてはいけない time-window制約 乗客が希望する乗車時間・到着時間を守らなければいけない 最大乗車時間制約 乗客が車内で過ごす最大許容時間を超えてはいけない 13
  7. AI Sequential Insertion Heuristics ▪ D-DARPにおける単純で即時的なアプローチ ▪ 既存の計画(解の順番)は変えず、新しいリクエストをその都度最良の位置 に挿入する ▪

    目先の最適な挿入だけを見ているので長期的視点が欠けているが、非常にシ ンプルで高速なため、システム初期によく使われる 逐次挿入ヒューリスティクス 15
  8. AI https://developers.google.com/optimization?hl=ja Googleが提供する最適化のためのライブラリ ▪ ルーティング問題 ▪ LNSベースにさらにヒューリスティクスを加えたGLS(Guided Local Search) が主に使われる

    ▪ GLS ▪ ペナルティを導入して局所最適解から抜け出せるようにしている ▪ 例えば、LNSの探索の中でコストが高い移動が頻繁に登場する場合、局所最適解 に陥っている可能性があるので、その高コストの移動に一時的にペナルティを課 すことで抜け出せるようになる OR-Tools 18
  9. AI ▪ 制約を Dimensions として与える 実装(イメージ) PARALLEL_CHEAPEST_INSERTION : コストが低いものから試す戦略 ▪

    初期解を見つけるための戦略を設定する ▪ 初期解からより良い解を探索するためのメタ ヒューリスティックを設定する ▪ 最適化を実行 Guided Local Search 19
  10. AI ▪ 強化学習の活用 ▪ その都度最適化問題を解くのではなく、長期的な価値が最大になるような行動方針を学 習する ▪ 一度学習すれば意思決定が高速になる ▪ ヒューリスティクスの学習

    ▪ LNSなどの手法をより賢くする ▪ Learning-to-Delegate (MIT) ▪ https://news.mit.edu/2021/machine-learning-speeds-vehicle-routing-1210 ▪ どの部分問題を解けば最も解全体の質が向上するかを予測する ▪ GNNの活用 ▪ VRPはグラフ上の問題のため、ノード間の複雑な関係を捉えるために、グラフ構造を直 接扱うことができるGNNの活用が進んでいる ▪ LLMによるヒューリスティクス生成 機械学習の応用 21
  11. AI ▪ 問題設定 ▪ 相乗りにおける最適化問題は乗客中心のサービス品質制約によって定義 されるDARP ▪ 解法 ▪ DARPの複雑性から、厳密解法は非現実的

    ▪ 高度なメタヒューリスティクスを用いる ▪ 実装ツール ▪ OR-Tools ▪ アーキテクチャ ▪ D-DARPに対しては、静的ソルバを中核に据えたローリングホライズン まとめ 22