带约束的非完全图旅行商问题（TSP）建模与求解咨询

这个问题本质是非完全图上的最短哈密顿回路问题——因为所有连通边的权重都是1，最优解就是恰好经过每个节点一次的回路（如果图存在哈密顿回路的话），总权重等于节点总数。下面从建模、求解（包括适配Concorde）、多最优解处理三个方面给你梳理具体方案：

一、建模方法 #

1. 转化为标准TSP格式 #

把非完全图补全为完全图，通过权重区分有效边和无效边：

• 对于原本连通的节点对，边权重设为1；
• 对于原本不连通的节点对，边权重设为一个足够大的常数M（比如M = N + 2，其中N是节点总数）。这样求解器会自动避开这些无效边，因为选任何一条都会让总权重超过最优值（最优总权重为N）。

2. 整数规划建模 #

基于标准TSP的整数规划模型，额外添加无效边的禁用约束：

• 决策变量：x_ij（0-1变量，x_ij=1表示选择节点i到j的边）；
• 目标函数：minimize sum(x_ij * w_ij)，其中w_ij=1（连通边）或w_ij=M（非连通边）；
• 核心约束：
  • 每个节点的入度和出度均为1：sum(x_ij) = 1（对所有i），sum(x_ji) = 1（对所有j）；
  • 消除子回路：添加经典的MTZ约束或割平面约束；
  • 禁用无效边：对所有不连通的i,j，添加x_ij = 0。

二、求解策略 #

1. 适配Concorde求解器 #

你提到Concorde要求边权重为实数，这个问题完全符合要求：

• 按上面的补全图方法，把连通边权重设为1（整数属于实数范畴），非连通边设为M；
• 直接将处理后的权重矩阵输入Concorde即可。如果图存在哈密顿回路，Concorde会返回总权重为N的最优回路；如果不存在，返回的总权重会远大于N，你可以据此判断无解。

2. 其他求解方式 #

• 小规模节点（N≤15）：用回溯法或动态规划（DP）直接枚举。比如DP状态设为dp[mask][u]，mask是已访问节点的二进制集合，u是当前节点，值为到达u的最少边数，最终找dp[full_mask][v] + (v到起点有边则1，否则无穷大)的最小值。
• 中等规模节点：用启发式算法（遗传算法、模拟退火、蚁群算法等）快速找到可行的哈密顿回路，因为所有回路都是最优解，只要找到任意一条即可。

三、多最优解的处理 #

因为所有边权相同，所有哈密顿回路都是最优解，处理多解可以用这些方法：

• 小规模节点：直接用回溯法遍历所有可能的哈密顿回路，枚举全部解；
• 中大规模节点：找到一个最优解后，添加约束排除该解，重新求解。比如已找到回路v1→v2→...→vN→v1，可以添加约束x_{v1,v2} + x_{v2,v3} + ... + x_{vN,v1} ≤ N-1，强制求解器避开这条回路，重复此过程直到返回非最优解；
• 部分扩展工具支持Concorde输出多个最优解，你可以查看官方文档的参数设置，开启多解输出模式。

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