你要给 15 个客户送货，用 1 辆车。请问有多少种可能的路线？
答案是：15! ≈ 1.3 × 10¹²，也就是 1.3 万亿种。如果再用 2 辆车，你不仅要决定每辆车访问哪些客户，还要决定各自的顺序——这个数量级会把任何蛮力穷举踢出局。
这就是车辆路径问题面临的“组合爆炸”。而现实中的物流公司，面对的是上百辆车、上千个配送点、加上时间窗、车型限制、道路拥堵——复杂度可以说是天文数字。
01 问题的数学本质：一个带约束的组合优化
我们用精确但不枯燥的方式，定义这个问题。
容量约束车辆路径问题可以形式化为：
目标：找到一组总代价最小的回路（每辆车从仓库出发并返回），使得：
每个客户被恰好访问一次；
每辆车访问的客户总需求不超过容量 Q。
这个问题的决策变量是二元的：Xij(k)=1 当且仅当车辆 k直接从 i 行驶到 j。约束条件包含流量守恒、容量约束和子回路消除（subtour elimination）。完整写出整数规划模型需要相当篇幅，但核心思想就是：在满足所有结构约束的前提下，最小化总行驶代价。
这是一个 NP-hard 问题。精确算法（分支定界、分支切割）在小规模（约 50 个客户以内）可以拿到全局最优；大规模则依赖于启发式和元启发式——而 Google OR-Tools 把这些都封装好了。
02 为什么不用遗传算法从头写？
收敛性不稳定：参数调不好，解的质量波动极大。
约束处理很麻烦：容量约束和子回路消除需要专门设计编码和修复算子。
没有最优性 gap：你不知道当前找到的解离全局最优还有多远。
OR-Tools 的 VRP 求解器底层混合使用了局部搜索（Local Search）和元启发式（Guided Local Search、Tabu Search、Simulated Annealing）。它的核心思路是：先通过一个贪心启发式（PATH_CHEAPEST_ARC）构建初始可行解，然后通过一系列邻域操作（2-opt、Or-opt、Relocate、Exchange、Cross）不断改进，同时用 Guided Local Search 惩罚重复出现的“好边”来逃离局部最优。
03 从代码到求解：模型的三个关键组件
在 OR-Tools 中建模一个 CVRP，本质上就是定义三个东西：
① 距离回调函数（Distance Callback）
这个函数返回任意两个节点之间的代价。我们用欧几里得距离并转换成整数：
def distance_callback(from_index, to_index): from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return distance_matrix[from_node][to_node]
需要整数是因为 OR-Tools 内部用整数运算避免浮点误差。我们乘以 1000 保留三位小数精度。
② 需求回调函数（Demand Callback）+ 容量约束维度
维度（Dimension）是 OR-Tools 中传递约束的核心机制。一个维度沿路线累积一个量（这里是从仓库出发的累计载货量），并施加上下界约束：
routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # 松弛变量，允许超载时为正值 [vehicle_capacity] * num_vehicles, # 每辆车的容量上界 True, # 从起点开始累加 'Capacity')
这里 松弛变量设为 0 意味着硬约束：绝对不允许超载。如果你需要软约束（允许超载但有惩罚），可以给松弛变量一个正的上界，并在目标函数中加入惩罚项。
③ 搜索策略
PATH_CHEAPEST_ARC 是构建初始解的启发式：从仓库出发，每次选择未访问且代价最小的弧连接，直到所有点被访问。当一辆车装满，就启动下一辆。后续的局部搜索会在此基础上迭代改进。GUIDED_LOCAL_SEARCH 是一种元启发式，它会给当前解中经常出现的高代价边加上“惩罚”，迫使搜索跳出局部最优。
04 完整实现：15 个客户，2 辆车，容量约束
import randomimport numpy as npimport matplotlib.pyplot as pltfrom ortools.constraint_solver import pywrapcp, routing_enums_pb2# ==================== 1. 数据生成 ====================random.seed(42)np.random.seed(42)num_customers = 15num_vehicles = 2depot = 0vehicle_capacity = 15# 坐标：仓库在原点，客户在[-10, 10]范围内均匀分布points = [(0, 0)] + [(random.uniform(-10, 10), random.uniform(-10, 10)) for _ in range(num_customers)]# 需求量：1~4 均匀分布，仓库为0demands = [0] + [random.randint(1, 4) for _ in range(num_customers)]# ==================== 2. 距离矩阵 ====================def compute_distance_matrix(points): """欧几里得距离矩阵，乘以1000保留整数精度""" size = len(points) matrix = np.zeros((size, size), dtype=int) for i in range(size): for j in range(size): if i != j: dx = points[i][0] - points[j][0] dy = points[i][1] - points[j][1] matrix[i][j] = int(np.hypot(dx, dy) * 1000) return matrixdistance_matrix = compute_distance_matrix(points)# ==================== 3. OR-Tools 建模 ====================# RoutingIndexManager：管理节点索引与求解器内部索引的映射manager = pywrapcp.RoutingIndexManager(len(points), num_vehicles, 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 distance_matrix[from_node][to_node]transit_callback_index = routing.RegisterTransitCallback(distance_callback)routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)# 需求回调 → 容量约束维度def demand_callback(from_index): from_node = manager.IndexToNode(from_index) return demands[from_node]demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # 不允许超载的硬约束 [vehicle_capacity] * num_vehicles, True, 'Capacity')# 搜索参数：贪心初始解 + 引导式局部搜索search_parameters = pywrapcp.DefaultRoutingSearchParameters()search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)search_parameters.local_search_metaheuristic = ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)search_parameters.time_limit.seconds = 5# ==================== 4. 求解并输出 ====================solution = routing.SolveWithParameters(search_parameters)if solution: print(f'最优解目标值: {solution.ObjectiveValue()/1000:.2f} (总距离)') routes = [] for vehicle_id in range(num_vehicles): route = [] index = routing.Start(vehicle_id) while not routing.IsEnd(index): node = manager.IndexToNode(index) route.append(node) index = solution.Value(routing.NextVar(index)) route.append(depot) routes.append(route) load = sum(demands[node] for node in route if node != depot) dist = sum(distance_matrix[route[i]][route[i+1]] for i in range(len(route)-1)) / 1000 print(f'车辆 {vehicle_id+1} | 路线: {route} | 载重: {load}/{vehicle_capacity} | 距离: {dist:.2f}')else: print('未找到可行解。请检查约束或增大容量。') exit()# ==================== 5. 可视化 ====================plt.style.use('dark_background')fig, ax = plt.subplots(figsize=(12, 10), facecolor='#1a1a2e')ax.set_facecolor('#1a1a2e')palette = ['#00f5ff', '#ff6ec7', '#f5ff00', '#00ff7f', '#ffa500', '#af7ac5']for vid, route in enumerate(routes): color = palette[vid % len(palette)] xs = [points[n][0] for n in route] ys = [points[n][1] for n in route] # 三次样条平滑 t = np.arange(len(xs)) t_dense = np.linspace(0, len(xs) - 1, 500) xs_smooth = np.interp(t_dense, t, xs) ys_smooth = np.interp(t_dense, t, ys) ax.plot(xs_smooth, ys_smooth, color=color, linewidth=2.5, alpha=0.85, zorder=2) mid = len(route) // 2 ax.annotate(f'车辆{vid+1}', (xs[mid], ys[mid]), color=color, fontsize=12, fontweight='bold', bbox=dict(boxstyle='round,pad=0.3', facecolor='#1a1a2e', edgecolor=color, alpha=0.9))# 客户点 (大小 ∝ 需求量)for i in range(1, len(points)): d = demands[i] ax.scatter(points[i][0], points[i][1], s=d*80, c='white', edgecolors='#00f5ff', linewidths=1.5, zorder=5) ax.annotate(f'{d}', (points[i][0], points[i][1]), textcoords="offset points", xytext=(0, 8), ha='center', color='white', fontsize=9, fontweight='bold')# 仓库ax.scatter(points[0][0], points[0][1], s=350, c='#ff073a', marker='s', edgecolors='white', linewidths=2, zorder=10, label='仓库 (Depot)')# 装饰ax.legend(loc='upper left', frameon=True, facecolor='#2d2d44', edgecolor='white', fontsize=10)ax.grid(True, linestyle='--', linewidth=0.3, alpha=0.4, color='white')for spine in ax.spines.values(): spine.set_edgecolor('#444466')ax.tick_params(colors='#cccccc')ax.set_xlabel('X', color='white', fontsize=12)ax.set_ylabel('Y', color='white', fontsize=12)ax.set_title('CVRP 优化结果 · 2 辆车 · 容量 Q=15', color='white', fontsize=18, fontweight='bold', pad=20)plt.tight_layout()plt.savefig('cvrp_solution.png', dpi=200, bbox_inches='tight', facecolor='#1a1a2e')plt.show()
10个月宝宝每天需要喝多少奶粉？
