cuopt-routing-formulation

ルーティングの定式化

車両ルーティングに関するドメイン概念です。API やインターフェースの詳細は扱いません。

ルーティングとは

• TSP：単一の車両で、すべての場所を一度ずつ訪問します（例：最短巡回路）。
• VRP：複数の車両を使用し、容量や時間の制限があります。注文を車両に割り当て、立ち寄り先の順序を決めます。
• PDP：集荷と配送の組み合わせです。対応する配送先を訪問する前に、集荷場所を訪問する必要があります。

必要な確認事項（問題とデータ）

すでに明らかでない場合は、以下を確認してください。

1. 問題の種類 — TSP、VRP、PDP のどれですか？
2. 場所 — いくつありますか？デポはありますか？場所のペア間のコストまたは距離はどのように求めますか（行列または算出）？
3. 注文／タスク — どの場所を訪問する必要がありますか？各立ち寄り先での需要またはサービス内容は何ですか？
4. 車両群 — 車両の台数、車両ごとの容量（複数の次元がある場合は各次元の容量）、出発地と到着地はどこですか？
5. 制約 — 時間枠（最も早い到着時刻／最も遅い到着時刻）、サービス時間、先行制約（注文 A を注文 B より先に行う）などはありますか？

典型的なデータ

• コストまたは距離の行列（または移動時間の行列）。
• 注文の場所と、VRP の場合は注文ごとの需要。
• 車両の容量、および車両と注文に設定する任意の時間枠。