algo-sc-routing

Compare original and translation side by side

🇺🇸

Original

English

🇨🇳

Translation

Chinese

Vehicle Routing Problem (VRP)

车辆路径规划问题（VRP）

Overview

概述

VRP determines optimal routes for a fleet of vehicles to serve a set of customers from a depot, minimizing total distance or cost. NP-hard — exact solutions only feasible for small instances (< 25 nodes). Practical solutions use heuristics (Clarke-Wright savings, sweep) or metaheuristics (simulated annealing, genetic algorithm).

VRP用于为车队确定从仓库出发服务所有客户的最优路线，以最小化总行驶距离或成本。该问题属于NP难问题——仅在小规模场景（<25个节点）下可求得精确解。实际场景中通常使用启发式算法（如Clarke-Wright节约算法、扫描算法）或元启发式算法（如模拟退火、遗传算法）来求解。

When to Use

适用场景

Trigger conditions:

Planning daily delivery routes for a fleet of vehicles
Minimizing total travel distance/time under capacity constraints
Optimizing route assignments across multiple vehicles

When NOT to use:

For single-vehicle route optimization (use TSP solvers)
For real-time dynamic routing with continuous order arrivals (use online algorithms)

触发条件：

为车队规划每日配送路线
在容量约束下最小化总行驶距离/时间
优化多车辆间的路线分配

不适用场景：

单车辆路线优化（请使用TSP求解器）
存在连续订单到达的实时动态路径规划（请使用在线算法）

Algorithm

算法

IRON LAW: VRP Is NP-Hard — Exact Solutions Don't Scale
For n customers, the solution space grows factorially. Exact methods
(branch and bound) work for n < 25. For real-world problems (50-1000+
customers), heuristics are REQUIRED. A good heuristic solution within
5% of optimal is far more valuable than an optimal solution that takes
hours to compute.

铁律：VRP是NP难问题——精确解决方案不具备可扩展性
对于n个客户，解空间呈阶乘级增长。精确方法（如分支定界法）仅适用于n<25的场景。对于真实世界的问题（50-1000+个客户），必须使用启发式算法。一个与最优解误差在5%以内的优质启发式解，远比对计算耗时数小时的最优解更有价值。

Phase 1: Input Validation

阶段1：输入验证

Collect: depot location, customer locations and demands, vehicle capacity, number of vehicles, time windows (if applicable), distance/time matrix. Gate: All locations geocoded, demand doesn't exceed vehicle capacity per customer.

收集信息：仓库位置、客户位置与需求、车辆容量、车辆数量、时间窗（若适用）、距离/时间矩阵。 校验门限： 所有位置已完成地理编码，单个客户的需求不超过车辆容量。

Phase 2: Core Algorithm

阶段2：核心算法

Clarke-Wright Savings Heuristic:

Start with each customer on its own route (depot → customer → depot)
Compute savings for merging route pairs: s(i,j) = d(depot,i) + d(depot,j) - d(i,j)
Sort savings descending
Merge routes greedily if capacity constraint allows
Improve with 2-opt (swap edges within routes) and or-opt (move customers between routes)

Clarke-Wright节约启发式算法：

初始状态为每个客户单独一条路线（仓库→客户→仓库）
计算合并路线对的节约值：s(i,j) = d(仓库,i) + d(仓库,j) - d(i,j)
按节约值降序排序
在容量约束允许的情况下，贪婪地合并路线
使用2-opt（交换路线内的边）和or-opt（在路线间移动客户）算法进行优化

Phase 3: Verification

阶段3：验证

Check: all customers visited exactly once, no vehicle exceeds capacity, all routes start and end at depot. Compare total distance against lower bound. Gate: All constraints satisfied, solution within 10% of lower bound.

检查：所有客户均被访问且仅访问一次，无车辆超出容量限制，所有路线均从仓库出发并返回仓库。将总距离与下界进行对比。 校验门限： 所有约束均被满足，解与下界的误差在10%以内。

Phase 4: Output

阶段4：输出

Return routes with sequence, distance, and load.

返回包含路线顺序、距离和负载的结果。

Output Format

输出格式

json

{
  "routes": [{"vehicle": 1, "sequence": ["depot", "C3", "C7", "C1", "depot"], "distance_km": 45, "load": 850, "capacity": 1000}],
  "summary": {"total_distance_km": 180, "vehicles_used": 4, "utilization_avg": 0.82},
  "metadata": {"customers": 30, "method": "clarke_wright_2opt", "computation_ms": 150}
}

json

{
  "routes": [{"vehicle": 1, "sequence": ["depot", "C3", "C7", "C1", "depot"], "distance_km": 45, "load": 850, "capacity": 1000}],
  "summary": {"total_distance_km": 180, "vehicles_used": 4, "utilization_avg": 0.82},
  "metadata": {"customers": 30, "method": "clarke_wright_2opt", "computation_ms": 150}
}

Examples

示例

Sample I/O

输入输出样例

Input: 10 customers, 2 vehicles (cap=500), depot at center Expected: 2 routes, each serving ~5 customers, total distance minimized by geographic clustering.

输入： 10个客户，2辆车辆（容量=500），仓库位于中心位置 预期输出： 2条路线，每条路线服务约5个客户，通过地理聚类最小化总行驶距离。

Edge Cases

边缘情况

Input	Expected	Why
One customer demand > capacity	Infeasible or split delivery	Need split delivery VRP variant
All customers co-located	Minimal routing, capacity-limited trips	Distance is trivial, trips determined by load
Tight time windows	More vehicles needed	Time constraints may prevent full-capacity routes

输入	预期输出	原因
单个客户需求超过车辆容量	不可行或拆分配送	需要使用支持拆分配送的VRP变体
所有客户位置重合	最小化路径规划，按容量限制安排运输次数	行驶距离可忽略，运输次数由负载决定
严格的时间窗约束	需要更多车辆	时间约束可能导致无法充分利用车辆容量

Gotchas

注意事项

Distance matrix quality: Road distance ≠ Euclidean distance. Use actual road network distances (Google Maps, OSRM) for practical routing.
Time windows add complexity: VRPTW (VRP with Time Windows) is significantly harder. Customers requiring specific delivery windows fragment routes.
Dynamic vs static: Real-world routing has cancellations, additions, and traffic. Plan static routes but allow dynamic re-optimization.
Driver constraints: Maximum driving hours, break requirements, and overtime costs add practical constraints not in the basic model.
Return to depot: Standard VRP assumes routes return to depot. Open VRP (routes end at last customer) needs different formulation.

距离矩阵质量： 道路距离≠欧氏距离。实际路径规划中请使用真实道路网络距离（如Google Maps、OSRM）。
时间窗增加复杂度： 带时间窗的VRP（VRPTW）难度显著更高。有特定配送时间要求的客户会导致路线碎片化。
动态vs静态： 真实场景中的路径规划会涉及订单取消、新增以及交通状况。先规划静态路线，但需支持动态重新优化。
驾驶员约束： 最长驾驶时长、休息要求以及加班成本等实际约束未包含在基础模型中。
是否返回仓库： 标准VRP假设路线需返回仓库。开放式VRP（路线结束于最后一个客户）需要不同的模型 formulation。

References

参考资料

For Clarke-Wright algorithm implementation, see
```
references/clarke-wright.md
```
For metaheuristic approaches (SA, GA), see
```
references/metaheuristics.md
```

关于Clarke-Wright算法的实现，请参见
```
references/clarke-wright.md
```
关于元启发式算法（SA、GA）的实现，请参见
```
references/metaheuristics.md
```