TSP 与 VRP 问题的启发式与元启发式求解

一、直观理解：巡回所有点，或派多辆车送完货

TSP（旅行商问题）：从仓库出发，访问每个城市恰好一次并返回，使总路程最短。点稍多就是经典 NP-hard 组合难题。

VRP（车辆路径问题）：有多辆容量有限的车，服务一批客户需求，使总路程/车数等目标最优。还可加时间窗（VRPTW）、取送货、多仓库等。

精确算法（分支定界、整数规划）在中小规模可行；赛题大规模实例通常需要：

1. 构造启发式快速给可行解（最近邻、节约法）；
2. 改进启发式局部搜索（2-opt、relocate）；
3. 元启发式在全局探索（SA、GA、TS、ALNS）。

原则：先有可行与下界/精确小例，再上智能优化，并报告 gap。

二、适用场景与优缺点

类型	说明
适用场景	配送、巡检、电路板钻孔、旅游线路；客户数十到数百；需要可实施路线而非仅理论最优证明。
核心优点	可处理真实约束；时间可控；解可画可执行。
局限与缺点	不保证全局最优；参数敏感；随机性需多种子；易被质疑“调参故事”，需基线与消融。

三、核心原理

1. TSP 建模（MTZ 示意）

$x_{ij}\in\{0,1\}$ 是否走弧 $(i,j)$，

$$\min\sum_{i\neq j}c_{ij}x_{ij}$$

度约束 + 消子环约束。小 $n$ 可用 intlinprog。

2. 经典启发式

• 最近邻：每次去最近未访点——快但可能差；
• 2-opt：打断两条边重连，消交叉；
• Clarke–Wright 节约法（VRP）：合并回路节省路程；
• 插入法：按最小增量插入客户。

3. 元启发式要点

• 解的编码（排列、路径分割）；
• 邻域（swap、2-opt、relocate、exchange）；
• 接受准则（SA 的 Metropolis、TS 禁忌）；
• 约束处理（罚函数或只在可行邻域动）。

4. 评价

• 与 MST 下界（TSP）、与 LP/精确小例比；
• 多种子均值与最优；
• 时间—质量曲线。

四、关键决策

1. 何时精确何时启发式

$n\le 15\sim20$ 可尝试精确 TSP；$n$ 更大先启发式。VRP 有容量时更难。

2. 目标

总距、最大完工、车数优先——目标不同解不同，需与题目一致。

3. 随机种子

至少 10 次，报告最好与平均。

4. 可复现

固定参数表与种子，避免只报一次奇迹解。

五、MATLAB 示例

rng(27);
% ---- 欧氏 TSP：最近邻 + 2-opt ----
n = 25;
XY = rand(n, 2)*100;
C = squareform(pdist(XY));

% 最近邻
function tour = nearest_neighbor(C)
    n = size(C,1);
    un = true(1,n); tour = zeros(1,n);
    u = 1; tour(1)=u; un(u)=false;
    for k = 2:n
        cand = find(un);
        [~,i] = min(C(u,cand));
        u = cand(i); tour(k)=u; un(u)=false;
    end
end

function L = tour_length(tour, C)
    L = 0; n = numel(tour);
    for i = 1:n-1, L = L + C(tour(i), tour(i+1)); end
    L = L + C(tour(end), tour(1));
end

function tour = two_opt(tour, C)
    n = numel(tour); improved = true;
    while improved
        improved = false;
        for i = 1:n-2
            for k = i+1:n-1
                a = tour(i); b = tour(i+1);
                c = tour(k); d = tour(mod(k,n)+1);
                delta = C(a,c)+C(b,d) - C(a,b)-C(c,d);
                if delta < -1e-9
                    tour(i+1:k) = tour(k:-1:i+1);
                    improved = true;
                end
            end
        end
    end
end

tour0 = nearest_neighbor(C);
L0 = tour_length(tour0, C);
tour1 = two_opt(tour0, C);
L1 = tour_length(tour1, C);
fprintf("NN=%.2f, NN+2opt=%.2f\n", L0, L1);

% MST 下界（TSP 下界之一）
G = graph(C);
% 完整图边
[s,t] = find(triu(ones(n),1));
w = C(sub2ind([n n], s, t));
Gg = graph(s, t, w);
T = minspantree(Gg);
fprintf("MST 下界=%.2f (TSP 最优 ≥ 此)\n", sum(T.Edges.Weight));

figure;
plot(XY(tour1([1:end 1]),1), XY(tour1([1:end 1]),2), "-o");
title(sprintf("TSP 路径长度 %.1f", L1)); axis equal; grid on;

% ---- 简易 CVRP：节约法思想（示意）----
% 1 号为仓库，需求 demand，容量 Cap
nC = 12; % 客户
XY2 = [50 50; rand(nC,2)*100];
dem = [0; randi([5 20], nC, 1)];
Cap = 50;
C2 = squareform(pdist(XY2));
% 初始：一客户一回路
routes = num2cell((2:nC+1)');
% 节约 s_ij = c_0i + c_0j - c_ij
sav = [];
for i = 2:nC+1
    for j = i+1:nC+1
        sav = [sav; i j C2(1,i)+C2(1,j)-C2(i,j)]; %#ok<AGROW>
    end
end
sav = sortrows(sav, -3);
% 极简合并（仅演示结构）
for e = 1:size(sav,1)
    i = sav(e,1); j = sav(e,2);
    % 找包含 i,j 的路线端点才合并（略化：跳过严格实现）
end
fprintf("CVRP 数据已生成：客户=%d, 总需=%d, 容量=%d\n", nC, sum(dem), Cap);
fprintf("完整节约法/ALNS 可在此数据上扩展；报告需含容量可行性检查。\n");

六、如何解释结果

1. 问题类型（TSP/CVRP/…）与目标、约束；
2. 数据规模与距离定义；
3. 算法流程与参数；
4. 最优可行目标值、路径图；
5. 与下界/基线（NN、CW）的 gap；
6. 多种子统计；
7. 未满足的真实约束声明。

七、常见误区

1. 一上来遗传算法却无可行基线

难以证明方法有用。

2. 路径交叉仍声称近似最优

至少做 2-opt。

3. VRP 忘记容量/时间窗检查

不可行解无效。

4. 只报一次随机结果

不可复现。

5. 把启发式当精确证书

没有下界就不要说“已最优”。

八、小结

TSP/VRP 的核心建模步骤是：

明确目标与约束 → 小规模精确/下界 → 构造可行解 → 局部改进 →（必要时）元启发式 → 多种子与 gap 报告。

启发式不是“随便搜”，而是可解释的邻域设计与可验证的工程流程。写清可行性与对照，比堆砌算法名称更重要。