経路探索の定式化

車両ルート計画に関するドメイン概念。APIやインターフェースの詳細については、ここでは扱いません。

経路計画とは

TSP：車両1台で、すべての場所を1回ずつ訪問する（例：最短巡回）。
VRP：複数の車両、積載量および／または時間制限あり。車両に注文を割り当て、停車順を決定する。
PDP：集荷・配送ペア。対応する配送先を訪問する前に、集荷先を訪問しなければならない。

必要な質問（問題とデータ）

以下の点が明確でない場合は、確認してください：

問題の種類— TSP、VRP、またはPDPか？
地点数— いくつありますか？拠点（デポ）はありますか？ペア間のコストまたは距離（行列形式または導出値）？
注文／タスク— どの地点を訪問する必要があるか？各停車地点ごとの需要またはサービス量は？
車両— 車両数、車両あたりの積載量（複数次元の場合は各次元ごとの積載量）、出発地・到着地は？
制約条件— 時間枠（最速／最遅到着時刻）、サービス所要時間、順序関係（AをBより先に処理）？

代表的なデータ

コストまたは距離行列（あるいは移動時間行列）。
注文の場所、およびVRPの場合は注文ごとの需要。
車両の積載量、および車両と注文ごとのオプションの時間枠。

GitHubで見る

---
name: cuopt-routing-formulation
description: Defines vehicle routing problem types (TSP, VRP, PDP) and the data requirements needed to formulate them, without covering any API or interface details.
license: Apache-2.0
---


# Routing Formulation

Domain concepts for vehicle routing. No API or interface details here.

## What is routing

- **TSP**: Single vehicle, visit all locations once (e.g. shortest tour).
- **VRP**: Multiple vehicles, capacity and/or time limits; assign orders to vehicles and sequence stops.
- **PDP**: Pickup and delivery pairs; pickup must be visited before the corresponding delivery.

## Required questions (problem and data)

Ask these if not already clear:

1. **Problem type** — TSP, VRP, or PDP?
2. **Locations** — How many? Depot(s)? Cost or distance between pairs (matrix or derived)?
3. **Orders / tasks** — Which locations must be visited? Demand or service per stop?
4. **Fleet** — Number of vehicles, capacity per vehicle (and per dimension if multiple), start/end locations?
5. **Constraints** — Time windows (earliest/latest arrival), service times, precedence (order A before B)?

## Typical data

- Cost or distance matrix (or travel-time matrix).
- Order locations and, for VRP, demand per order.
- Vehicle capacities and optional time windows for vehicles and orders.