TSP 求解：KDTree + DFJ 算法实现与实践¶

一、核心目标¶

实现一种高效的旅行商问题（TSP）求解方案，通过KDTree近邻稀疏化减少变量规模，结合DFJ（Dantzig-Fulkerson-Johnson）子回路消除算法，在保证解质量的前提下提升大规模TSP问题的求解效率。

二、技术框架与依赖库¶

1. 核心依赖¶

2. 整体架构¶

TSPSolver类（核心求解器）
├── 数据层：read_data() 读取TSP文件，解析坐标与距离类型
├── 预处理层：
│   ├── construct_dist_matrix() 构建距离矩阵（支持EUC_2D/MAN_2D/GEOM）
│   ├── get_k_neighbors_kdtree() KDTree近邻查找，生成稀疏边集
│   └── _adaptive_k() 自适应确定近邻数k
├── 求解层：
│   ├── solve_tsp() 总调度函数
│   ├── DFJ_solver() 整数规划建模+子回路消除
│   ├── _fast_find_subtours() 并查集检测子回路
│   └── _build_route() 从解中构建完整路径
└── 辅助功能：
    ├── validate_solution() 解验证（路径完整性、距离一致性）
    └── plot_tsp_route() 结果可视化

三、关键技术细节¶

1. TSP数据解析（read_data()）¶

• 支持标准TSP文件格式，自动识别EDGE_WEIGHT_TYPE（距离类型）

• 提取NODE_COORD_SECTION中的节点坐标，过滤无效数据

• 输出关键信息：数据量、距离类型、读取耗时

2. 距离矩阵构建（construct_dist_matrix()）¶

• 支持3种主流距离计算：

  • EUC_2D：欧几里得距离（四舍五入保留4位小数）

  • MAN_2D：曼哈顿距离（绝对值和）

  • GEOM：几何距离（欧几里得距离取整）

• 采用向量化计算（numpy广播机制），避免循环，提升效率

3. KDTree近邻稀疏化（get_k_neighbors_kdtree()）¶

核心思想¶

TSP问题的完全图（n个节点有n(n-1)/2条边）变量规模过大，通过只保留每个节点的k个近邻边，大幅减少变量数，加速求解。

实现步骤¶

1. 构建KDTree索引，查询每个节点的k+1个近邻（排除自身）

2. 保证双向近邻：若i是j的近邻，则j也加入i的近邻集

3. 限制近邻数上限（k×2），避免稀疏化过度

4. 输出排序列表形式的近邻矩阵，用于后续变量创建

自适应k值策略（_adaptive_k()）¶

根据节点数量动态调整k，平衡稀疏化率与解质量：

4. DFJ算法求解（DFJ_solver()）¶

整数规划模型构建¶

• 变量：x[(i,j)]（二进制变量），表示边(i,j)是否被选中

• 目标函数：最小化总路程，min ∑x[(i,j)]×dist(i,j)

• 约束条件：

  1. 度约束：每个节点的入度=出度=2（∑x[(i,j)]=2）

  2. 子回路消除约束（懒惰约束）：对每个子回路S，∑x[(i,j)]≤|S|-1

关键优化¶

1. 懒惰约束（Lazy Constraints）：不预先添加所有子回路约束，求解过程中动态检测并添加，减少初始约束数量

2. 并查集子回路检测（ _fast_find_subtours() ）：

   • 路径压缩+按秩合并优化，高效查找连通分量

   • 过滤出长度2≤|S|<n的子回路（完整回路无需约束）

3. 批量添加约束：一次迭代中添加所有检测到的子回路约束，减少求解器调用次数

4. 求解参数调优：

   • 线程数自动分配（Threads=-1）

   • 强预处理（Presolve=2）

   • 时间限制1小时（TimeLimit=3600）

   • 关闭日志输出（Logging=0）

5. 路径构建与验证¶

路径构建（_build_route()）¶

• 从活跃边集（active_edges）出发，验证每个节点度为2

• 多起点尝试（前10个节点），避免单一起点构建失败

• 形成闭合回路（起点=终点），路径长度为n+1（含起点重复）

解验证（validate_solution()）¶

• 路径长度验证：必须为n+1

• 节点覆盖验证：所有节点必须被访问一次

• 距离一致性验证：计算路径实际距离与求解器结果误差≤0.5

6. 可视化（plot_tsp_route()）¶

• 双面板布局：左图展示路径（起点标绿星，节点标红，边标蓝），右图展示关键信息

• 自适应图大小：n>500时扩大画布，避免节点重叠

• 节点标签偏移优化：奇偶节点交替偏移，提升可读性

• 保存高清图片（dpi=600），便于结果存档

四、使用说明¶

1. 环境准备¶

# 安装依赖
pip install coptpy numpy scipy matplotlib

• 注意：coptpy需配合COPT优化器（可申请免费许可证）

2. 数据格式¶

支持标准TSPLIB格式文件，核心段落示例：

EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 41.87500 45.00000
2 39.37500 45.00000
...
EOF

3. 运行方式¶

修改主程序中的test_files列表，添加目标TSP文件路径：

if __name__ == "__main__":
    test_files = [
        "data/ch600.tsp"  # 替换为你的TSP文件路径
    ]
    for filename in test_files:
        solver = TSPSolver(filename)
        model, obj_val, route, active_edges, time_total = solver.solve_tsp()
        # 后续验证与可视化...

五、性能特点¶

优势¶

1. 稀疏化高效：KDTree近邻查找时间复杂度O(n log n)，变量数仅为完全图的5%~30%

2. 解质量有保障：DFJ算法是TSP精确算法，稀疏化仅剔除远邻边（对最优解影响极小）

3. 鲁棒性强：多起点路径构建、双向近邻、自适应k值，适应不同规模数据

4. 结果可追溯：完整的日志输出+高清可视化+解验证，便于结果分析

适用场景¶

• 节点数n≤2000的TSP问题（n=600时求解时间约数十分钟）

• 距离类型为EUC_2D/MAN_2D/GEOM的TSPLIB标准问题

• 对解质量要求高（需精确解或高质量可行解）的场景

性能基准¶

时间复杂度分析¶

空间复杂度分析¶

六、关键输出日志示例¶

求解问题: data/ch600.tsp
读取数据耗时: 0.0004 秒
K值取25
数据处理完成，共有600条数据
自动识别距离类型：EDGE_WEIGHT_TYPE = EUC_2D
构建距离矩阵耗时: 0.0080 秒
KDTree构建邻居矩阵耗时: 0.0062 秒
创建了8373个变量（稀疏化率: 4.7%）

--- 迭代 0 ---
求解状态: 6 (FEASIBLE)
发现 12 个子回路
添加了 12 个子回路约束

--- 迭代 1 ---
求解状态: 6 (FEASIBLE)
发现 8 个子回路
添加了 8 个子回路约束

...

求解状态: 1 (OPTIMAL)
迭代 20: 无子回路，找到可行解
求解成功！最优总路程 = 20448.9516
DFJ算法求解耗时: 123.5356 秒
总求解时间: 123.55秒
验证通过！求解器=20448.9516，计算距离=20448.9516

七、注意事项与改进方向¶

注意事项¶

1. COPT许可证：需提前申请，否则无法调用求解器

2. 内存限制：n>2000时，距离矩阵（n×n）可能占用较多内存，可考虑分块计算

3. 时间限制：n=1000时可能需要数小时求解，可调整TimeLimit参数

改进方向¶

1. 混合启发式：在DFJ之前加入贪心算法（如最近邻）生成初始可行解，加速收敛

2. 动态k值：根据求解进度调整k值（如迭代后期增大k，避免错过最优边）

3. 并行计算：子回路检测部分可并行化，提升大规模问题处理速度

4. 多目标优化：加入路径平滑性、节点优先级等约束

5. 支持更多距离类型：如ATT、CEIL_2D等TSPLIB其他距离类型

6. 证明最优性

八、总结¶

本实现通过KDTree稀疏化+DFJ子回路消除的组合策略，有效平衡了TSP问题的求解效率与解质量。

核心亮点在于：

• 自适应近邻策略，无需手动调整k值

• 向量化与并查集优化，提升关键步骤效率

• 完整的解验证与可视化流程，确保结果可靠性

• 兼容标准TSPLIB格式，通用性强

局限性在于：

1. 绝对最优性：稀疏化可能排除全局最优解（虽概率低）
2. 内存限制：距离矩阵仍需O(n²)内存，超大规模问题需分块
3. 求解器依赖：依赖COPT商业求解器，开源替代有限
4. 确定性问题：TSP是NP-hard，指数级复杂度无法避免

九、完整代码¶

完整的实现代码已保存在 tsp_kdtree_dfj.py 文件中。

代码包含以下主要模块：

• TSPSolver 类：核心求解器，包含数据读取、距离矩阵构建、KDTree 近邻查找、DFJ 求解等方法
• plot_tsp_route 函数：结果可视化，生成在包含路径和统计信息的双面板图表
• validate_solution 函数：解验证，检查路径完整性和距离一致性
• 主程序：演示如何使用求解器进行完整的 TSP 求解流程

使用方法：

1. 将 TSP 文件路径添加到 test_files 列表
2. 运行脚本：python tsp_kdtree_dfj.py
3. 脚本会输出详细的求解过程日志和结果可视化图表

主要类和函数签名：

class TSPSolver:
    __init__(filename) - 初始化求解器
    read_data() - 读取 TSP 文件
    construct_dist_matrix() - 构建距离矩阵
    get_k_neighbors_kdtree(k) - 获取 k 近邻邻接表
    solve_tsp() - 主求解函数
    DFJ_solver(dist, neighbor_matrix) - DFJ 算法求解

def plot_tsp_route(co_dict, route, obj_val, time_total, k) - 绘制结果
def validate_solution(coords, route, obj_val, dist_matrix) - 验证解质量