如何用动态规划求解15城选9个的固定起终点A的非对称TSP问题

你遇到的本质是城市选择+路径规划联合优化的非对称闭环TSP，完全不需要拆分“先选9个城市、再跑TSP”的两步流程，只要对标准TSP模型做小幅适配，就能单次运行同时输出选点结果和最优路径。

先对齐约束，避免建模踩坑 #

先把问题的硬规则理清楚，保证后续求解的可行性不偏离要求：

• 节点全集是15个城市A-O，距离矩阵是非对称的：d(u,v)对应u出发到v的距离，方向不可互换（比如A到F是9，F到A是5，两个值独立计算）
• 硬约束：
  • 路径是闭环，起点终点都是A
  • 不重复访问城市，整个路径总共覆盖9个不同城市（也就是除A外，需要从剩下14个城市里挑8个纳入路径）
• 优化目标：最小化闭环总行驶距离

方案1：ILP精确求解（单次出全局最优） #

如果你习惯用TSP配套的ILP求解工具，只要在原有非对称TSP的模型基础上加几行选点约束就行，不需要拆分流程：

• 变量定义：
  • 二元边变量x_uv：路径里如果有u到v的直接路段就取1，否则0，覆盖所有u≠v的城市对
  • 二元选点变量y_v：城市v被纳入访问集就取1，否则0
  • 辅助顺序变量u_v：给非A的城市定义，用来消除子回路
• 核心约束：
  • 强制A必选：y_A = 1
  • 满足访问规模：所有y_v加起来等于9，凑够要求的城市数量
  • 度平衡：对所有被选中的城市，恰好有一段进路、一段出路（入度和=1，出度和=1）
  • 子回路消除：用最通用的MTZ约束，固定A的顺序为0，对任意非A的u、v对，设置u_v - u_u + 9*x_uv ≤ 8，防止绕开A形成独立小环
• 目标函数：最小化所有边的距离加权和，即min sum(d(u,v)*x_uv)

把距离矩阵和上述约束输进求解器，单次运行就会同时输出：哪8个城市被选中、对应的最短行驶路径是什么，完全匹配你要单次跑的需求。

方案2：适配元启发式TSP算法（适合熟悉遗传、蚁群这类传统求解框架的场景） #

不用改算法的核心逻辑，只要调整编码规则，就能在原有框架下直接跑：

• 染色体编码：固定第一个位置是A，剩下8个位置从除A外的14个城市里挑不重复的元素，整个染色体就是9个城市的排列
• 适应度计算：按照非对称距离矩阵，算从A出发依次经过8个选中城市、最后开回A的总距离，总距离越短，适应度越高
• 操作适配：交叉的时候保留固定的A位置，只对非A的片段做部分匹配交叉；变异的时候随机把某个非A位置的城市，换成其他不在当前染色体里的城市，保证每一代个体都满足“无重复、共9个城市、A当起点”的要求

这种方式的搜索空间一开始就限定在可行解范围内，没有无效计算，单次运行就能直接拿到联合优化的结果。

容易踩的坑 #

• 所有距离取值严格按“行是出发、列是到达”的规则来，别把非对称矩阵对称化处理，不然结果会不准
• 这个问题的解空间规模并不大，不管是精确求解还是元启发式算法，都能很快收敛

内容的提问来源于stack exchange，提问作者PanZemiak