Skip to content
TheChatArchiveThe Chat Archive
o3-2025-04-16· OpenAIHugging Face LMArena Human Preference 140K

TSP旅行商问题目前公认的算法层面的好的解决方法是啥?在实际的工程中如何解决这一问题?

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Qwenqwen3-235b-a22b’s answer.
  1. User

    TSP旅行商问题目前公认的算法层面的好的解决方法是啥?在实际的工程中如何解决这一问题?

  2. Assistant

    下面把“学术界公认的好方法” 与 “工程界实战打法” 分开说,方便查阅。
    如果只想看结论,可先看每段后面的“工程-Tips”。

    ——————————————————
    一、算法层面的“最佳实践”

    1. 精确求解 (Exact)
      ‑ Held-Karp 动态规划:
      • 时空复杂度 O(n²·2ⁿ),n≈20 才可用
      • 工程意义:只用于验证或教学
      工程-Tip:用它给小规模数据做单元测试,确保后面启发式实现无 bug。

      ‑ Branch-and-Cut(分支-割平面)
      • 将 TSP 转为整数规划 (IP),然后不停加入有效割 (Subtour Elimination, Comb, 2-Match 等)
      • Concorde TSP Solver = 业界最强公开实现,可在数小时内给出上万点欧氏 TSP 的最优解(TSPLIB 24,978 节点实例耗时 ≈ 2h)
      工程-Tip:如果 n<5,000 且“必须拿到证明最优”的合同需求,直接调用 Concorde 或商用 IP Solver(Gurobi/CPLEX)+自定义割平面。

    2. 近似算法 (Approximation with guarantee)
      ‑ Christofides (1.5-approx for metric TSP)
      ‑ Euclidean PTAS (Arora/Mitchell):复杂度与 ε 指数相关,学术多于工程
      工程-Tip:当客户只需要“有理论下界”而非最优时,可上 Christofides;代码 200 行即可写完。

    3. 启发式 / 元启发式 (Heuristic / Meta-heuristic)
      (1) Lin-Kernighan 与其改进版 LK-H (K-opt 搜索深度自适应)
      • 几乎被认为是“单目标 TSP 的黄金标准启发式”
      • Keld Helsgaun 的 LKH-2 / LKH-3:百万点欧氏 TSP 在数分钟-数小时内给出 <0.05% Gap 的解
      工程-Tip:n>5k 又要“极好解”但不要求证明最优 → 直接 LKH。
      (2) Local Search:2-opt、3-opt、Or-opt、λ-opt
      (3) 大规模邻域搜索 (LNS / ruin-and-recreate)、ILS、Tabu、Simulated Annealing、Genetic、Ant Colony…
      • 在有时间窗、容量、多车等约束时往往比纯 LKH 更容易扩展
      工程-Tip:复杂约束场景 → 采用 Google OR-Tools 的 Routing Solver(内部是 LNS+局部搜索),然后自己写 callback 计算增量成本。

    ——————————————————
    二、实际工程怎么落地?

    1. 明确需求
      a) 节点规模 n?
      b) 允许的运行时间?
      c) 必须“可证明最优”还是“够好即可”?
      d) 有无额外约束(时间窗、车辆容量、仓中转、异向距离、上/下车等)?
      -> 这直接决定用哪一类算法。

    2. 数据准备
      • 距离/时长矩阵预计算并缓存;
      • 若地图距离可随时间波动 -> 用快照 or 动态查询 API;
      • 非对称 or 有禁行路段时记得生成有向矩阵。
      工程-Tip:n>10k 时距离矩阵 O(n²) 太大,需 online compute + caching + k-d 树近邻剪枝。

    3. 构造初解
      • 最近邻 / Savings / Sweep / MST-based / Greedy insertion …
      • 对 VRP 场景常用 Clarke-Wright Savings 打个底。
      工程-Tip:好初解能让后续局部搜索省 30-50% 时间。

    4. 迭代改进
      3.1 纯 TSP
      • 按规模选:n≤5000 直接 LKH; 5000<n<5e5 用 LK-H + 分块;>5e5 需分区聚类 + 局部拼接。
      3.2 复杂约束 (VRP/TDVRP/TSPTW…)
      • Google OR-Tools (C++/Python) Routing Solver
      • 若想混合求解:先用 OR-Tools 给多车排线,再对单车子路径用 LKH 精修。
      工程-Tip:OR-Tools 的 LNS “启发式链” 可插自定义 Neighborhood,如同时换多条路线的片段。

    5. 并行化 & 工程优化
      • 距离计算 GPU/多线程;
      • 局部搜索阶段可对 disjoint segments 并行;
      • LKH 本身支持 OpenMP;
      • 大规模云端调度可用 Map-Reduce:先地理聚类→各子集单独求解。
      工程-Tip:把“求解核心”与“业务约束/数据 IO”解耦,方便以后换求解器。

    6. 结果验证 & 监控
      • 下界:MST/1-tree、线性松弛、dual-ascent;
      • 记录 Gap、运行时、内存;
      • 线上 AB 实验观察 KPI (油耗、里程、准时率)。

    ——————————————————
    三、常用开源 / 商用工具速查

    场景工具 & 语言亮点规模参考
    精确 TSPConcorde (C)行业标杆≤10k-50k
    精确/整数规划Gurobi / CPLEX强大但收费≤1k-5k
    近似/启发式LKH-3 (C)速度+质量双一流≤1e6
    复杂约束 VRPGoogle OR-Tools (C++/Py/Java)LNS+多车型≤20k
    元启发式框架PyMetaheuristic, OptaPlanner, jsprit易扩展约束视约束
    GPU 并行cuOpt (NVIDIA)交通实时调度10k~100k

    ——————————————————
    四、一个“可抄作业”的最小闭环 Demo

    以 n≈3000 的单车欧氏 TSP 为例:

    # 1. 安装
    git clone https://github.com/kanchana1990/LKH-3
    cd LKH-3 && make
    
    # 2. 准备 TSPLIB 格式
    python to_tsplib.py input.csv > my.tsp
    
    # 3. 配置参数
    echo "PROBLEM_FILE = my.tsp
    TIME_LIMIT    = 600
    MOVE_TYPE     = 5     # Lin-Kernighan
    PATCHING_C    = 3
    PATCHING_A    = 2" > params.par
    
    # 4. 跑!
    ./LKH params.par > log.txt
    # 输出 my.tour, log.txt 内含最优上界&运行时
    

    多车有时间窗:

    from ortools.constraint_solver import pywrapcp, routing_enums_pb2
    
    manager = pywrapcp.RoutingIndexManager(n_nodes, n_vehicles, depot)
    routing = pywrapcp.RoutingModel(manager)
    
    # 回调距离
    def distance_cb(i, j):
        return dist[manager.IndexToNode(i)][manager.IndexToNode(j)]
    routing.SetArcCostEvaluatorOfAllVehicles(distance_cb)
    
    # 加时间窗等约束 ……
    
    search_params = routing.DefaultSearchParameters()
    search_params.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    search_params.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    
    solution = routing.SolveWithParameters(search_params)
    

    ——————————————————
    五、选型归纳(一句话版本)

    • 小规模且要最优 → Concorde / MIP Solver。
    • 中-大规模但可接受极小误差 → 直接 LKH-3。
    • 有时间窗、多车、多仓等业务约束 → OR-Tools(LNS) 或自己写 Meta-heuristic。
    • 超大规模(>10万) → 先聚类分治,再各子集用 LKH/OR-Tools,最后跨簇拼接与局部微调。

    希望能帮你在学术与工程之间找到“最快落地”的那条最短 Hamiltonian 路😉。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.