做同城配送项目那年我手上已经有一套解TSP旅行商问题的求解器几百个点算起来也很快。但客户的需求一出来我就知道之前的东西得推翻重来——对方说我们有五辆车覆盖全市八十个客户点要求总行驶里程尽量短每辆车走几条回路全部当天上午完成。这不是一个旅行商问题而是经典的多旅行商问题MTSP。它和单旅行商问题的差别远不止“多辆车”这么简单。当时被“多车版本”坑过几次后我才把这类问题的公式和求解过程系统梳理了一遍。这篇文章就写给正在做路径规划、运筹优化、算法课程设计或者需要在项目里落地多车辆调度方案的朋友。我从问题定义、数学模型、常用降维技巧、精确解与启发式解法、实际编码路线以及我真实踩过的坑这几个方向来展开保证你读完既能看懂公式也能动手复现一套方案。1. 一辆车变成多辆车之后TSP那套数学定义就不够用了单旅行商问题的定义很干净一名销售员从仓库出发遍历所有客户点各一次最后回到仓库目标是让总路径最短。数学上就是在一个加权完全图上找一个经过所有节点且权重之和最小的哈密顿回路。但换成多旅行商问题问题结构立刻复杂了。mTSP 严格说是有 m 个销售员、一个或多个仓库所有客户点都必须被某个销售员访问且只访问一次每个销售员从仓库出发最后返回仓库闭合式或者不返回开放式。目标通常是最小化所有销售员的总路程也可能是最小化最长的单条路径后者就是负载均衡的考虑。初看似乎想当然觉得“那就把客户点按区域分给每辆车然后每一辆车单独解一个TSP不就行了”我在早期方案里真这么干过效果不好。原因很简单分组和排序是耦合的。某个客户点到底由哪辆车服务会影响这条路径的长度而路径的长度又反过来决定最优分组。直接按地理位置硬切可能导致一辆车跨越整个城市去服务一个孤立点另一辆车却闲得只跑两三个点。所以 mTSP 本质上是两个子问题的叠加任务分配assignment和路径排序routing。这比单纯一个TSP要难不少。另外实际项目里遇到的 mTSP 很少是教科书经典版通常带各种限制按仓库数量分单仓库 mTSP 和 多仓库 mTSP。多仓库意味着每辆车从不同地点出发公式和约束都得改。按是否返回分闭合式closed和开放式open。外卖配送、无人机巡检很多是开放式——车或无人机不用回到起点。按能力限制分带容量约束的 CVRP带时间窗的 VRPTW带最大路径长度限制的 mTSP。按是否强制全部车辆运作有的场景是“最多5辆车”但最优解只用3辆这时要在数学模型中加可选车辆的判断。我常和同学、同事说一句话mTSP 是通往 VRP车辆路径问题的第一道门槛。你如果把 mTSP 的公式和求解思路搞透后面理解带约束的 VRP、带时间窗的 VRPTW会顺很多。因为它们共用的底层结构是同一个——多个回路、每个回路对应一个资源载具、节点只能被覆盖一次。2. MTSP的数学模型目标函数、流约束和子回路消除mTSP 的数学建模我用的是最经典的整数线性规划ILP形式。刚开始对着论文里的公式觉得每个符号都认识但不知道为什么要这样写。直到自己动手实现求解器又在实际数据上翻车才明白每一个约束都有它存在的原因。2.1 决策变量与目标函数假设有 n 个客户节点编号 1 到 n仓库节点编号 0一共有 m 辆车。定义决策变量$$x_{ij}^{k} \in {0, 1}$$如果车辆 k 从节点 i 直接行驶到节点 j那么 $x_{ij}^{k} 1$否则为 0。注意 i 和 j 可以取仓库节点也可以取客户节点但 i 不等于 j。这里 k 从 1 到 m。目标函数一般是总距离最短$$\min \sum_{k1}^{m} \sum_{i \in N} \sum_{j \in N, j \neq i} c_{ij} x_{ij}^{k}$$其中 $c_{ij}$ 是节点 i 到节点 j 的行驶距离或成本N 包括仓库和所有客户点。这个公式是最常见的形式。如果业务要求负载均衡目标函数换成最小化最长单条路径形式就变成$$\min \sum_{k1}^{m} L_k, \quad \text{s.t.} \quad L_k \ge \sum_{i \in N} \sum_{j \in N} c_{ij} x_{ij}^{k}, \ \forall k$$也就是说用一组辅助变量 $L_k$ 把每辆车的总路径长度控制住然后最小化所有 $L_k$ 的和或最小化它们的最大值 $L_{\max}$。实测下来当各片区的客户密度差异很大时这种方式生成的路径明显更均衡不会出现一辆车跑二百公里、另一辆车只跑五十公里的情况。2.2 核心约束为什么每条都必须写第一类约束是“每个客户点只能被访问一次”$$\sum_{k1}^{m} \sum_{i \in N, i \neq j} x_{ij}^{k} 1, \quad \forall j \in {1, \dots, n}$$意思是每个客户点 j 必须恰好有一辆车从某个节点 i 开进来。这个约束保证了覆盖也保证了不重复。第二类约束是流量守恒。车辆进入一个客户点之后也必须从该客户点离开$$\sum_{i \in N, i \neq h} x_{ih}^{k} \sum_{j \in N, j \neq h} x_{hj}^{k}, \quad \forall h \in {1, \dots, n}, \forall k$$如果这个约束不写就可能出现某个客户点被访问了但没有后续出走的路路径在中间崩掉。第三类约束是仓库节点对每辆车进出各一次$$\sum_{j1}^{n} x_{0j}^{k} 1, \quad \sum_{i1}^{n} x_{i0}^{k} 1, \quad \forall k$$这是单仓库闭合式 mTSP 的条件。每辆车必须从仓库出发一次最后再回到仓库一次。如果改成开放式就把“返回仓库”的那个约束去掉或者在距离矩阵里把回程距离设成 0。如果带容量约束即每个客户点 j 有需求 $q_j$每辆车 k 的容量是 $Q_k$还要加$$\sum_{j1}^{n} q_j \sum_{i \in N} x_{ij}^{k} \le Q_k, \quad \forall k$$这个约束就是 CVRP 与 mTSP 的差别。很多论文把 CVRP 描述成“带容量约束的多旅行商问题”从公式上看确实是一回事。第四类约束是子回路消除。这是我在实际建模中踩过最深的坑值得单独拿出来讲。2.3 子回路消除MTZ 与 DFJ 两条路如果不加任何子回路消除约束求解器会给你一个小循环。比如有一辆车从仓库出发到客户 1再回仓库这条路径没问题但同时还可能出现另外一条客户 2 → 客户 3 → 客户 2完全没接上仓库。这在数学上满足前面所有“覆盖一次”和“流量守恒”的约束但对实际配送毫无意义。解决子回路问题有两条经典路线。第一条是 Miller-Tucker-ZemlinMTZ约束$$u_i - u_j n \cdot x_{ij}^{k} \le n - 1, \quad \forall i, j \in {1, \dots, n}, i \neq j, \forall k$$这里的 $u_i$ 是辅助变量表示客户 i 在一条回路中的访问顺序位置。如果你从仓库出发沿路径依次给节点编号那么每经过一条边 $i \to j$后续编号都必须递增这样自然不会出现脱离仓库的闭合小环。MTZ 的优点是约束数量是多项式级别好实现直接写进 Gurobi 或 CPLEX 就行。缺点是线性松弛比较弱分支定界树往往更大节点数稍多就容易慢。第二条是 Dantzig-Fulkerson-JohnsonDFJ约束$$\sum_{i \in S} \sum_{j \in S} x_{ij}^{k} \le |S| - 1, \quad \forall S \subseteq {1, \dots, n}, 2 \le |S| \le n-1, \forall k$$这个约束说任意客户点子集 S 内部连边数不能超过 |S|-1否则就成环了。问题在于 S 的个数是 2 的 n 次方不可能一次性全部写进去。实际做法是 branch-and-cut先用没有 DFJ 约束的模型求解解出来之后检查有没有子回路发现一个就加一条对应的割平面约束然后重新求解。迭代几轮后子回路会被逐渐消灭。从我自己的测试来看n 在 50 以内时MTZ 更省事直接写约束解下去没问题n 超过 100 以后如果还想用精确解DFJ 配合割平面通常比 MTZ 快不少。但 DFJ 需要自己写分离子回路的代码实现成本略高。下面的表格是我在模型选型时常用的判断依据方便你们直接参考问题类型子回路消除方式适用规模说明小规模 mTSPn ≤ 60MTZn ≤ 60实现简单直接塞进任意 ILP 求解器中等规模精确解n ≤ 150DFJ 割平面n ≤ 150需要迭代加约束写回调大规模场景启发式/元启发式n 150一般放弃精确解用 OR-Tools 或遗传算法带容量限制 VRPCVRP 专用约束 启发式视实例而定精确法通常只在小规模上有优势这个表不是绝对的分界线但方向上基本靠谱。3. 最实用的降维技巧把 mTSP 改写成标准 TSP 去求解在引入 OR-Tools 和 LKH 之前有一个非常实用而且优雅的技巧把 m 个销售员的问题改写成单个销售员的问题。这个方法我很早以前是在一篇关于 LKH 求解器的文档里看到的后来发现它也是很多论文里做 mTSP 基准测试的默认手段。3.1 单仓库闭合式 mTSP 的改写方法做法是把仓库节点复制 m 份每个副本对应一个销售员。原来的 n 个客户节点保持不变所有销售员副本之间不存在合法连接距离设为无穷大或一个非常大的数 M。这样形成的单 TSP 实例中最优哈密顿回路由于副本之间不能直连必然会在某些时刻穿过每个仓库副本。整个回路就可以从仓库副本处剪开变成 m 条闭合回路每条回路分配给一个销售员。公式上原问题有节点集合 $N {0, 1, \dots, n}$仓库是 0。改造后的节点集合是 $N {0_1, 0_2, \dots, 0_m, 1, 2, \dots, n}$。新距离矩阵满足$$c(0_p, 0_q) M, \quad \forall p \neq q$$$$c(0_p, j) c(0, j), \quad c(j, 0_p) c(j, 0), \quad \forall j \in {1, \dots, n}$$这样做的最大好处是可以直接用 LKH、Concorde 这些为单 TSP 做了大量优化的顶级求解器。LKH 在标准单 TSP 上能轻松处理上万节点比很多通用 MILP 求解器强太多。虽然 mTSP 比单 TSP 多了一层分组约束但通过这种变换其实把大部分复杂度交给了成熟求解器去处理。3.2 切割回路时容易踩的坑等 LKH 输出一个巡游序列后你需要找到仓库副本的位置依次把它们切成独立回路。我看网上一些实现版本在这里经常出问题主要有两个一是切割顺序搞反。正确的逻辑是对于一个巡游序列[0_1, a, b, c, 0_2, d, e, 0_3, f]你需要在每个0_k位置切一刀得到三段0_1-a-b-c-0_1、0_2-d-e-0_2、0_3-f-0_3然后按原仓库距离计算真实成本。别把距离矩阵里的 M 当真实距离算进去否则你最后统计的总距离会大得离谱。二是有些非对称问题的距离矩阵不是对称的。原始 mTSP 如果方向不同距离不同变成单 TSP 后也要用非对称 TSP 的求解器。LKH 有一个专门的 ATSP 处理版本或者你把非对称矩阵扩展成对称矩阵也能解但计算量会明显上升。我遇到过的最稳方案是直接用 TSPLIB 格式中的 ATSP 实例配合 LKH 的对应参数。3.3 多仓库或开放式怎么变多仓库 mTSP 也能用类似的思路但更麻烦一些。一个常用技巧是加一个“超级仓库”节点把这个超级节点到各个真实仓库之间的距离设为 0从真实仓库到超级仓库距离也设为 0但真实仓库之间保持大 M。这样通过超级仓库中转单 TSP 求解器又能跑起来。开放式的话更简单在距离矩阵中把每辆车返回仓库的距离设为 0就能骗过求解器让回程不产生成本。这个方法在 OR-Tools 里也适用本质上是同样的思路。我非常推荐在做小规模验证时先试试这个变换。你不需要自己写复杂的车辆约束就能快速得到一个质量不错的解再用它作为后续算法的初始解或对标底线。4. 精确解法到底能扛多大规模分支定界与LKH的实测感受很多人以为只要公式写对了扔给 Gurobi 或 CPLEX 就能出结果。第一次做 mTSP 的时候我也这么想结果跑一个 n120、m8 的实例等了半个小时还在 gap 3% 徘徊最后只能放弃。这里的关键是理解精确求解器对这类问题的真实杀伤范围。4.1 整数规划求解器的瓶颈在哪里mTSP 的整数变量数量是 m × n × n也就是说车辆数增加一倍变量数量直接翻倍。更糟的是问题具有很强的对称性车辆 A 走路线甲、车辆 B 走路线乙和车辆 B 走路线甲、车辆 A 走路线乙对总成本来说是完全一样的。这种对称性会让分支定界树里出现大量等价节点浪费大量搜索时间。针对对称性的常用办法是对称破缺symmetry breaking。最简单的做法是给车辆编号加约束比如车辆 1 必须访问编号最小的那个客户节点或者要求车辆按路径长度排序$L_1 \ge L_2 \ge \dots \ge L_m$。这样做能在某些实例上明显减少搜索时间但也不是万能药。我实测的经验数字大概是这样在 Gurobi 中用 MTZ 子回路消除n50、m5 左右的 mTSP通常几秒到几十秒内能找到最优解n100、m10 时一般问题要几分钟甚至更久n150 时基本不指望精确解在合理时间内收敛。当然如果距离矩阵结构特别好比如所有节点分布均匀时间会好一些。4.2 用 LKH 做快速评估LKH 是专门为 TSP 设计的启发式求解器它在 TSPLIB 的实例上几乎都能找到最优解或非常接近最优的解。通过上一节的变换把 mTSP 转成单 TSP再交给 LKH我在实际数据上测过n200、m10 的实例LKH 一般几十秒内就能返回一个质量很高的解和大规模精确解之间也就差 1% 到 3%。这带来一个实战策略如果你不确定一个规模适中的实例的最优解是多少先用 LKH 跑一版再拿小规模实例去跟精确解对比。如果误差在可接受范围内就大胆把 LKH 结果当基准用。4.3 混合策略精确解做小、启发式做大我现在做实践项目时的路线基本是如果实例小n ≤ 60直接上 Gurobi 写 MTZ 约束解精确最优顺便检验模型的正确性。如果实例中等60 n ≤ 300用 LKH 转换加求解必要时加一轮 2-opt 局部搜索。如果实例超过 300 或者带复杂约束直接上 OR-Tools 或遗传算法配合问题特定的局部搜索。这套组合拳在实际项目里性价比很高既保证小规模能拿到最优解又保证大规模能快速产出可落地的路线。5. 从公式到代码OR-Tools建模与遗传算法编码两条路线光谈公式不写代码总差一口气。这里给出两条我实际用过的落地路线一条适合快速验证和产品落地另一条适合需要定制化约束的时候。5.1 OR-Tools十分钟跑出一个多车辆路径方案OR-Tools 是 Google 开源的运筹优化库对 VRP 族问题支持非常完善。它内部封装了局部搜索和元启发式算法接口设计对新手友好。我最早用它来做 mTSP 时基本没看文档照着示例改就行。核心代码框架如下from ortools.constraint_solver import routing_enums_pb2, pywrapcp def solve_mtsp(distance_matrix: list, num_vehicles: int, depot: int 0): manager pywrapcp.RoutingIndexManager( len(distance_matrix), 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 int(distance_matrix[from_node][to_node]) transit_callback_index routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # 添加一个距离维度让模型感知每辆车的累计距离 dimension_name Distance routing.AddDimension( transit_callback_index, 0, # slack 容量这里不等待 1000000, # 单辆车的最大行驶距离按需调整 True, # 允许从0开始累计 dimension_name, ) distance_dimension routing.GetDimensionOrDie(dimension_name) # 让所有车辆的总距离在目标中占权重可以缓解车辆距离悬殊的问题 distance_dimension.SetGlobalSpanCostCoefficient(100) 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 10 solution routing.SolveWithParameters(search_parameters) if solution is None: return None routes [] for vehicle_id in range(num_vehicles): index routing.Start(vehicle_id) route [] while not routing.IsEnd(index): route.append(manager.IndexToNode(index)) index solution.Value(routing.NextVar(index)) routes.append(route) return routes有几个点值得注意。SetArcCostEvaluatorOfAllVehicles是告诉求解器每条边的成本函数AddDimension会为每辆车维护一个累计行驶距离的“维度”后面如果你想加时间窗或容量约束逻辑类似。PATH_CHEAPEST_ARC作为 first solution strategy 对中小规模实例效果好GUIDED_LOCAL_SEARCH适合后续局部搜索。我自己在真实项目里经常改两个地方一是把距离回调里的 float 乘一个系数转成 int避免精度损失二是根据业务规模调整时间限制不要默认 10 秒小型实例 5 秒足够大型实例给 60 秒更稳妥。5.2 遗传算法灵活但需要一个好编码如果需要处理自定义约束比如某些客户点必须在某个时间段内完成服务或者某些车辆不能进入某些区域OR-Tools 也能做但调试成本会上升。这时候自己写遗传算法更有掌控感。遗传算法的关键是编码和解码。我常用的编码是两段式一段是客户点的巡游排列另一段是断点位置。举个例子假设 8 个客户点3 辆车排列是[3, 6, 1, 2, 8, 5, 4, 7]断点是[2, 5]。那么三辆车分别服务车13, 6车21, 2, 8车35, 4, 7每条车辆路径再按给定顺序服务。这个编码的好处是每个巡游排列天然满足“客户点不重复”的约束遗传交叉算子不需要额外修复重复基因。适应度函数按照断点把排列切分然后分别计算每辆车的路径总距离加权求和。如果带容量约束就在目标函数中加入一个超容量惩罚项。伪代码大致是function fitness(chromosome): order chromosome.order cut_points chromosome.cuts total_cost 0 for each segment in split(order, cut_points): route_cost distance(depot, segment[0]) for i in 1 to len(segment)-1: route_cost distance(segment[i-1], segment[i]) route_cost distance(segment[-1], depot) total_cost route_cost return 1 / (total_cost capacity_penalty)但我必须说一句光靠遗传算法的交叉变异在 mTSP 上基本打不过 OR-Tools。原因是 GA 全局搜索强、局部精修弱。所以我自己写的 GA 都会在交叉变异之后加一个 2-opt 局部搜索对每条车辆路径做内部反转优化。这一步能把解的质量提升不少实测收敛速度和最终结果都明显变好。如果你刚开始接触 GA建议先用 OR-Tools 跑一版结果作为 baseline然后写一个 GA 对照这样你才知道自己的实现有没有 bug改进有没有效果。5.3 两种路线的对比与选择把两个方案放在一起对比维度OR-Tools遗传算法上手成本低官方有大量示例中高需要设计编码和算子定制约束支持但复杂灵活可自行改目标函数求解质量通常较好依赖局部搜索调参多可解释性黑盒多一些完全透明适合场景标准 VRP、快速原型、产品化教学、研习、特殊约束我最常用的判断标准是能不能接受默认指标OR-Tools 处理 mTSP 和 CVRP 很成熟我会默认先试它。只有遇到非常奇怪的约束或者要给学生讲算法原理时才会回到 GA。6. 参数、初始化与目标函数里的细节都是会让结果崩掉的坑最后这部分我写几个真实项目中踩过的、有点隐蔽的坑。每个问题都对应一个“看起来合情合理但结果不对”的场景希望能帮你们少走弯路。6.1 距离矩阵取整导致路径变“怪”OR-Tools 的 distance callback 要求返回整数。很多时候算法拿到的距离是浮点数如果直接int()强转会丢掉小数点后的信息。当两个候选路径的浮点距离本身差距很小而强转后变成同一个整数时求解器会认为它们等价最终选出来的一条路线可能在浮点意义下更差。我的处理方式是把浮点距离统一乘一个系数比如 1000再做取整。输出路径时总成本再除以 1000。这样做既满足接口要求又不损失有效精度。6.2 车辆“必须全用”和“可选车辆”是两套目标很多 mTSP 示例代码默认所有车辆都得从仓库出发并且都必须用。这在真实场景里经常不符合需求你有 10 辆车但今天订单量少最优方案可能只用 3 辆。如果强制全用会造出很多绕路的幽灵路径。数学上这个差异体现在仓库节点约束上强制全用是把等于 1改成“每辆车必须进出一次”可选车辆则是在目标函数里加一个“启用车辆”的固定成本或者把进出仓库的条件放宽成“至少 0 次”。OR-Tools 里没有特别直接的开关但可以通过在仓库节点之间设置大 M 距离让多余的车辆走一个零成本空转路径或者用AddDisjunction机制处理。6.3 全局跨度成本系数不是越大越好OR-Tools 的SetGlobalSpanCostCoefficient是我见过最容易被误用的参数。它把“所有车辆累计距离的最大值与最小值之差”加入目标函数用来防止车辆路线长度过于悬殊。系数设得高车辆均衡性会好但总行驶距离可能上升系数设得太低均衡约束等于摆设。我的经验是先跑一组系数扫描比如 0、50、100、200、500看总距离和最长路径的折中曲线。一般取 100-300 之间属于比较稳的范围具体要看问题规模。6.4 初始解的作用比想象中大尤其是在 GA 里随机初始化一组种群往往要上百代才能收敛到一个好解。如果改成用最近邻算法构造几条初始路径或者先用 K-Means 把客户点聚成 m 类再让每辆车在各自聚类内部跑 TSP得到的初始种群质量会高很多。这里顺便提一个我常用的招如果客户点在地图上分布比较偏圆形可以先把所有点按相对仓库的极角排序然后按角度均匀切成 m 段。这样构造的初始路径在配送场景里通常不差而且计算复杂度极低。这个技巧在路径规划博客里很少看到系统性讲解但实际效果很扎实。6.5 子回路消除约束加错了解出来永远是错的如果你是用 Gurobi 写 MILP有一个非常隐蔽的问题MTZ 约束如果没有给对 n 的范围或者 u 变量没有设定上限模型可能在整数解里出现“绕开仓库的环”依然合法的情况。原因是 u 的约束只是相对顺序没有限定“起点必须是仓库”。所以要在公式里补充对每个客户点 i都有 $1 \le u_i \le n$而且仓库节点的 u 值固定为 0。否则子回路里的编号可以自洽但整个回路根本不接仓库。DFJ 割平面也有对应问题迭代加约束时如果子回路检测代码只检测一条最大连通分量可能漏掉多条小环导致加约束后仍然继续出错。我当时吃了大亏后来干脆在分离代码里把所有连通分量全找出来一次性把所有违反约束都加进去迭代次数瞬间减少很多。6.6 距离矩阵非对称时的特别提醒外卖场景里有单行道山路场景上下坡速度不同这些都会导致 c_ij ≠ c_ji。遇到这种非对称距离矩阵mTSP 模型本身没有本质变化但 LKH 这类基于对称 TSP 的工具要换用 ATSP 模式OR-Tools 的 callback 也要对应改成从from_index和to_index取矩阵行值而不是对称取值。我在一个小规模实验里吃过亏对称矩阵直接套用能秒出解换成非对称数据后我忘了改 LKH 配置结果跑了半小时还在原地转后来才意识到是工具把非对称问题当对称问题处理了。这些小细节单个拿出来都不是大事但在完整方案里任何一个出错最终输出的路径都不可用。我自己现在做这类问题时基本流程是先用小规模实例验证模型正确性再用 LKH 或 OR-Tools 跑大规模最后针对业务输出做人工抽查。每次踩坑就记录一条积攒下来后面做类似优化项目时真的能省很多时间。希望这篇文章也能成为你的“排坑清单”让你在 mTSP 的公式与求解路上少走几段弯路。