5.3 旅行商与车辆路径问题

5.3 旅行商与车辆路径问题

本节摘要：旅行商问题（TSP）要求访问全部城市再回起点的最短环游，是 NP 难的标志性问题。本节从组合爆炸算起，搭建"近邻构造 + 2-opt 局部搜索"的启发式流水线，讲解模拟退火如何跳出局部最优，再扩展到带容量与多车辆的车辆路径问题（VRP）与选址的分层配合。

三十个仓库，一辆巡检车

区域巡检车要从配送中心出发，逐一检查 30 个仓库再返回，油费按里程结算。路线怎么排？这是 TSP 的标准身形：n 个点的哈密顿回路最短化。第 2 章算过账：30 个点有 29!/2 条路线，任何精确枚举都是妄念。分支定界与割平面在几十个点的规模上尚可一战（专业求解器借助 Held-Karp 下界与小平面切割能解到数千点的特例），但工程日常靠的是另一套兵法：启发式构造 + 局部搜索精修。

两级流水线：先搭后修

第一级，构造。近邻法从起点出发，每次跳到最近的未访问点，最后回到起点。它是 O(n²) 的粗坯——快，但会犯"贪心扎进死胡同"的毛病：早期顺手的选择常常把大片区域留到最后，产生漫长交叉的回头路。第二级，精修。2-opt 是局部搜索的最经典动作：选环游上的两条边，切断后换另一种方式重接，若总长变短就接受。反复执行直到没有 2-opt 改进可做，路线就落入"2-opt 局部最优"——没有任意两条边的交换能再改进。

import numpy as np

def tour_length(tour, D):
    return sum(D[tour[i], tour[(i + 1) % len(tour)]] for i in range(len(tour)))

def nearest_neighbor(n, D, start=0):
    tour, unvisited = [start], set(range(n)) - {start}
    while unvisited:
        cur = tour[-1]
        nxt = min(unvisited, key=lambda j: D[cur, j])
        tour.append(nxt); unvisited.remove(nxt)
    return tour

def two_opt(tour, D):
    n, improved = len(tour), True
    while improved:
        improved = False
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                new = tour[:i] + tour[i:j + 1][::-1] + tour[j + 1:]
                if tour_length(new, D) < tour_length(tour, D) - 1e-10:
                    tour, improved = new, True
    return tour

rng = np.random.default_rng(42)
pts = rng.uniform(0, 100, (30, 2))
D = np.linalg.norm(pts[:, None, :] - pts[None, :, :], axis=2)

t1 = nearest_neighbor(30, D)
t2 = two_opt(t1, D)
print(f"近邻构造: {tour_length(t1, D):.1f}")
print(f"2-opt 精修: {tour_length(t2, D):.1f}")   # 通常改进 15%-25%
​

在均匀随机散点上，近邻解通常比最优长 25% 上下，2-opt 能把差距压到 5% 以内——几行代码换来"接近最优 + 毫秒级速度 + 任何规模可跑"，这是启发式在工业界立足的全部理由。2-opt 的几何含义也值得记：它消除的正是路线交叉，而平面 TSP 的最优解必不自交（交叉可换边变短），所以消交叉的过程就是向最优靠近的过程。

跳坑：模拟退火

2-opt 的天花板是局部最优：所有单步换边都变差的路线，仍可能比最优长 5%。跳出办法是偶尔接受变差的移动——模拟退火借冶金退火的比喻，温度高时容忍大幅变差（鼓励乱撞探索），温度逐渐降低后趋于挑剔（收敛精修）：

def anneal(tour, D, T0=50.0, cool=0.995, iters=20000, seed=1):
    rng = np.random.default_rng(seed)
    tour, best = tour[:], tour[:]
    T = T0
    for _ in range(iters):
        i, j = sorted(rng.integers(1, len(tour), 2))
        cand = tour[:i] + tour[i:j + 1][::-1] + tour[j + 1:]
        delta = tour_length(cand, D) - tour_length(tour, D)
        if delta < 0 or rng.random() < np.exp(-delta / max(T, 1e-9)):
            tour = cand
            if tour_length(tour, D) < tour_length(best, D):
                best = tour[:]
        T *= cool
    return best

t3 = anneal(t2, D)
print(f"退火收尾: {tour_length(t3, D):.1f}")
​

调参经验三条：初始温度设在"典型单步变差量"的量级（本例路线总长几百，单步变差几到几十，T0 取 50 合理）；降温别快于 0.99 每步，快了等于没退火；多跑几个随机种子取最好，退火的本质是带运气管理的随机搜索。这条"构造 + 局部搜索 + 跳坑"的三段式流水线，是遗传算法、蚁群、大邻域搜索等一大家子元启发式的公共骨架，换的只是"怎么生成候选、怎么决定接受"两处零件。

从一辆车到一个车队：VRP

现实配送是车辆路径问题（VRP）：多辆车、每辆有载重上限、每单有需求量，目标常是最少车辆或最短总里程。它在 TSP 之上叠加了装箱约束（哪几单拼一辆车）与排序约束（一辆车内的访问顺序），难度只增不减。工业解法常是"先聚类后路径"的分层：先把客户按地理位置与载重切成簇（对应第 2 章的聚类与选址直觉），簇内再跑 TSP 流水线；更强的做法是自适应大邻域搜索，随机拆掉重插部分客户反复震荡。战略层的选址（建几个仓、建在哪，p-中值模型的最经典形态）与战术层的路径就这样咬合成一个决策体系：仓库位置决定巡回的骨架，巡回成本反过来评估选址好坏，第 9 章会把这两层拼成完整战例。

⚠️ 常见坑：拿随机均匀散点测试出的调参经验，直接搬到真实路网。真实订单有 clusters（商圈密集、郊区稀疏）与时间窗，近邻构造在强聚类数据上表现更差，2-opt 与路由式局部搜索的收益比例都会变化。上线前用真实数据回测，是启发式工程不可省的验收环节。

本节要点回顾

• TSP 是 NP 难试金石：精确解止步于中等规模，工业答案在启发式；
• 构造 + 精修两段式：近邻出粗坯 O(n²)，2-opt 消交叉压差距到个位数百分比；
• 模拟退火管跳坑：温度控制探索与收敛的节奏，多种子取优是标配；
• 元启发式是一家子：公共骨架是候选生成 + 接受准则，换零件不换骨架；
• VRP = TSP + 装箱，先聚类后路径是分层求解的标准姿势，与选址决策上下游咬合。

网络战场收官。至此沙盘上始终只有一个决策者——下一章请入对手与盟友，最优解的定义本身将随博弈改写。