物流配送路径规划：A*与退火遗传的双层求解及在线重规划

简介：这份完整项目开发文档面向计算机、软件工程等专业开展课程设计、项目实训或毕业设计的学生，也可供希望了解物流配送路径规划系统开发流程的初学者参考。文档围绕物流配送最优路径规划模拟系统展开，覆盖需求规格说明、设计规格说明、系统实现说明与测试报告等完整环节，涉及录入、状态显示、地图模拟等功能模块划分，基于MFC的架构与数据库表设计，以及A*算法、模拟退火和遗传算法在最短路径、巡回路线规划中的应用，并包含测试计划、测试用例与结果分析，能够帮助读者梳理从需求分析到编码实现、测试总结的文档组织方式。资源包内为1个doc文档，约2.59MB，查阅和二次整理较为方便。已有1064人学习下载，适合对照课程项目文档结构、功能模块描述和算法方案说明进行参考。

1. 一张只有 71 个点的地图，为什么值得拆开看

物流配送最优路径规划最反直觉的一点是：真正决定程序跑不跑得动的，不是"算出最短的那条线"这个直觉动作，而是你有没有勇气把问题拆成两层。这套模拟系统在一张 71 个节点、75 条道路的窗口地图上做配送：仓库和客户随机标注，堵车路段可以随手画，车沿着结果一路走一路报里程和成本。规模小到肉眼能看穿，但正因为小，每一层的输入输出都能被逐字核对——它是理解路径规划底层机制最干净的样本。很多人做这类课程设计栽在同一个地方：把"图上两点最短路"和"客户访问顺序"揉进一个搜索里，最后既算不准也跑不动。

2. 两层求解：为什么 A* 只管两点，巡回序交给另一套算法

路径规划这个词容易被当成一个动作，实际上是两个：路由（routing）解决"从甲到乙怎么走"，排序（sequencing）解决"这些点按什么次序串起来"。这套系统的做法是把前者交给 A*，后者交给退火遗传，中间用一张距离矩阵接缝。这个分界线划在哪里、为什么必须划，是整套设计里最值得掰开的一处。

2.1 A* 的 f = g + h：估价函数凭什么既剪枝又不剪错

A* 的核心就是一个评价函数f(n) = g(n) + h(n)。g(n)是从起点到当前节点已经走过的真实代价，h(n)是从当前节点到终点的估计代价。g是确定的，h是编的——所有关于 A* 的争论都在这半个h上。

关键的约束叫可采纳性（admissible）：h(n)永远不能大于从 n 到终点的真实最短距离。满足这条，第一次从 open 表里弹出终点时得到的就是最优解，不需要继续搜索。这条性质不是巧合，因为如果h高估了某条路径的剩余代价，那条真正的最优路径可能在队列里被排到后面，还没被展开就已经被"看起来更短"的劣质路径抢先弹出终点。

这套系统里h取的是欧氏距离，因为地图是横平竖直加斜线的路网，两点直线距离不会超过实际绕行距离，天然满足可采纳性。如果h恒等于 0，A* 就退化成了 Dijkstra，会在整张图上摊大饼式扩展；如果把h乘个 1.2 的系数，搜索会快很多，但最优性就丢了。这是路径规划里最经典的一次取舍，很多引擎给h加权重就是为了用最优性换速度，但在物流场景里每公里都是成本，那点速度买不回里程。

源码层面，这套系统的 A* 用得相当朴素：

// 全程用像素做代价单位，只在状态栏输出时乘 (1.0/30) 换成公里 double gCost[72]; // id 直接当下标，0 号位留空，71 号位给最后一个标注点 int father[72]; // 回溯用 bool closed[72]; double H(int a, int b) { // 可采纳的估价：欧氏距离不会高估实际路程 double dx = nd[a].x - nd[b].x; double dy = nd[a].y - nd[b].y; // 设备坐标 y 轴向下，平方后方向无影响 return sqrt(dx * dx + dy * dy); } bool AStar(int src, int dst, int* seq, int& len) { for (int i = 0; i <= 71; ++i) { gCost[i] = 1e18; closed[i] = false; father[i] = 0; } gCost[src] = 0.0; // open 表用线性扫描取最小 f，节点总数只有 71，堆的维护成本反而是负担 for (;;) { int cur = -1; double bestF = 1e18; for (int i = 1; i <= 71; ++i) if (!closed[i] && gCost[i] < 1e17 && gCost[i] + H(i, dst) < bestF) { bestF = gCost[i] + H(i, dst); cur = i; } if (cur == -1) return false; // open 表空，两点不连通 if (cur == dst) break; // 第一次弹出终点即为最优，h 可采纳才有这个性质 closed[cur] = true; for (int k = 0; k < nd[cur].degree; ++k) { int nb = nd[cur].aroundid[k]; // 邻接点 id double w = Dist(cur, nb); // 该条道路的像素长度 if (gCost[cur] + w < gCost[nb]) { // 松弛 gCost[nb] = gCost[cur] + w; father[nb] = cur; } } } // 沿 father 回溯，反序写入 seq，len = 路径节点数 ... }

这段代码里有两个细节值得单独说。第一个是单位：gCost全程用像素，比例尺 30 像素 = 1 公里只在状态栏刷新那一刻换算。如果在 A* 内部就开始换算成公里，代价数值会缩到 0.03 量级，浮点比较时的误差阈值就变得难以拿捏，而且频繁乘除带来的舍入误差会在 20 次矩阵构造后累积。第二个是 open 表的实现方式：Node总数只有 71，用线性扫描找最小f的复杂度是 O(V)，整体 O(V² + E)，实际耗时在毫秒以下；上一个二叉堆反而是负优化，因为堆的常数因子在这个规模下压不倒朴素扫描。

还有一个容易忽略的约束：closed一旦置位就不再更新。这在h可采纳的前提下是安全的，因为节点第一次被弹出时的g已经是它的最优值。但只要你给h加了权重，这个前提就崩了，同一节点可能需要被重新打开——这是加权 A* 最常见的翻车点。

2.2 如果让 A* 直接排客户顺序，状态空间会怎样炸掉

最直觉的想法是：把"已访问集合"塞进 A* 的搜索状态，让它同时决定路线和顺序，一次搜完。20 个客户加一个仓库，状态数是2^20 × 21 ≈ 2.2 × 10^7。这个量级看起来还行，Held-Karp 动态规划就是这么干的。但问题卡在h上。

状态一旦包含集合，从"当前点 + 已访问集合"到终点的真实剩余代价，需要求解一个规模为剩余点数的子 TSP——这本身就是原问题。也就是说，h要么取 0（A* 退化成 Dijkstra，在 2^20 个状态上做无信息搜索），要么你得编一个下界，比如"剩余点到最近未访问点的距离和"，这个下界弱到几乎剪不掉任何分支，因为最小生成树下界、分配问题下界这些强下界本身的求解成本又上去了。

更实际的问题是这个系统的性能指标写得明明白白：短路径 30 秒内出结果，长路径不超过 90 秒。VC++6.0 单线程、32 位进程，2^20 × 21 个状态每个存 8 字节代价加 4 字节父指针，光数组就接近 250 MB，还没有算每步 21 次转移的开销。这条线在实测里基本走不通。

分层的价值就在这里：A* 的h只在"两点之间"有意义，那就只让它解决两点之间的事；顺序那部分另外找一个不吃h的算法。这不是妥协，是运筹学里做了几十年的标准套路，路由和排序本就不该共享同一套搜索结构。

2.3 距离矩阵：把 71 点的路网折叠成 21×21 的完全图

分层之间的接缝是一张矩阵。把仓库和所有标注客户当作一个点集（最多 21 个），两两跑 A*，得到一张对称矩阵，之后 TSP 那层完全不关心底下路网长什么样，只认矩阵里的数字。

const int K = 21; // 仓库 1 个 + 客户最多 20 个 double dist[K][K]; void BuildMatrix(const int* pts, int k) { for (int i = 0; i < k; ++i) { dist[i][i] = 0.0; for (int j = i + 1; j < k; ++j) { int seq[72], len = 0; if (!AStar(pts[i], pts[j], seq, len)) { dist[i][j] = dist[j][i] = 1e9; // 不可达用大数占位，退火里会被自然淘汰 continue; } // A* 结束时 dst 的 gCost 就是最短路长度，不用再从 seq 累加一遍 dist[i][j] = dist[j][i] = gCost[pts[j]]; } } }

k(k-1)/2次 A*，21 个点就是 210 次，单次在几十微秒到毫秒量级，总耗时远低于 30 秒指标。这里有个副作用值得注意：矩阵是对称的，所以只需要算一半，但如果路网里有单行道或者方向相关的拥堵（Road.traffic只对某个方向有效），对称假设就会失效，必须改成两个方向各算一次。这套系统没有单行道，所以对称成立——依赖一个假设之前，先确认这个假设在数据里真的成立，这类地方最容易在后面埋坑。

矩阵还有一层额外价值：它是动态重规划的天然输入。后面的第 4 章会看到，当用户在车行进途中标注堵车时，重算的只是矩阵里的一部分元素，而不是从零开始。

3. 退火与遗传缝合：20 个客户的巡回序怎么在 30 秒内定下来

矩阵到手的下一步是求解旅行商问题：从仓库出发，遍历所有客户各一次，最后返回仓库，求总里程最短的访问次序。20 个客户时可能的巡回数是(20-1)!/2 ≈ 6 × 10^16，精确解在这个规模上不现实。这套系统用的是"改进的模拟退火算法与遗传算法相结合"，这个说法在文献里有好几种落地方式，下面拆的是最常见的实现思路。

3.1 Metropolis 准则：为什么允许暂时走一条更差的路

模拟退火的核心不是"退火"这个词，而是那个允许走坏路的概率。对当前解做一次邻域扰动，得到候选解，两者的代价差记作 Δ = C(候选) - C(当前)。如果 Δ ≤ 0，候选更优，无条件接受；如果 Δ > 0，按概率exp(-Δ/T)接受，T 是当前温度。

这个公式的作用是把"坏的程度"按温度压缩成一个概率。T 很高时，exp(-Δ/T)接近 1，几乎什么改动都接受，搜索在解空间里大步游走；T 逐渐降低，坏变更难被接受，搜索收缩到局部最优附近。如果一开始就不允许坏变更，搜索会卡在离起点最近的那个局部极小上再也不动——TSP 的 2-opt 邻域里这种局部极小遍地都是，血泪经验。

温度调度是这套算法里最玄学的部分，没有普适参数，只有经验区间：

初温取"初始解邻域平均 Δ"这个做法的好处是自适应：不管地图比例尺怎么变、像素代价的量级怎么变，T0都能自动缩放到合适的区间。如果硬写一个常数，换一张分辨率不同的地图就全乱了。

邻域扰动用的是 2-opt：随机选两个位置，把这两点之间的片段整体反转。对 TSP 来说这个算子性价比极高，因为它直接改变了两条边（断开两条旧边、连上两条新边），一次扰动就能跳出局部结构，而且不会产生非法解。

3.2 序表示下的交叉与变异：二进制编码在这里为什么翻车

遗传算法负责的是全局跳跃。这里第一个决策就是编码方式。如果用二进制编码，一个客户排列要先编码成比特串，交叉后大概率得到非法的排列（同一个客户出现两次、另一个客户缺席），必须写一个修复函数把非法个体拉回可行域。这个修复过程本身就是随机的，等于在交叉之后又加了一层扰动，遗传的信息传递被稀释掉了。

序表示（path representation）没有这个问题：染色体就是一个客户下标的排列，天然合法。代价是交叉算子要重新设计，因为单点交叉会破坏排列的完整性。这套系统用的应该是 OX（有序交叉，Order Crossover）：随机选两个切点，父本 A 的中间片段整段复制给子代，其余位置按父本 B 里的相对顺序依次填充。

// 染色体就是客户在 pts[] 里的下标排列，仓库固定在下标 0，不参与变异 double Cost(const int* p, int k) { double s = dist[0][p[0]]; // 仓库 -> 第一个客户 for (int i = 0; i + 1 < k; ++i) s += dist[p[i]][p[i + 1]]; return s + dist[p[k - 1]][0]; // 最后一个客户 -> 仓库 } // OX 有序交叉：切点之间的片段整段继承，其余位置按另一父本的相对顺序补齐 void OrderCrossover(const int* a, const int* b, int k, int* child) { int l = rand() % k, r = rand() % k; if (l > r) swap(l, r); bool used[K] = {false}; for (int i = l; i <= r; ++i) { child[i] = a[i]; used[a[i]] = true; } int pos = (r + 1) % k; for (int i = 1; i <= k; ++i) { // 从 b 的 r+1 处开始绕一圈 int cand = b[(r + i) % k]; if (!used[cand]) { child[pos] = cand; used[cand] = true; pos = (pos + 1) % k; } } } // 逆转变异正好等价于 TSP 里的 2-opt 邻域，是这类问题性价比最高的算子 void ReverseMutate(int* p, int k) { int i = rand() % k, j = rand() % k; if (i > j) swap(i, j); while (i < j) { swap(p[i], p[j]); ++i; --j; } }

OrderCrossover的逻辑说明：切点区间[l, r]内的基因来自父本a，这是"继承"的部分；剩下的位置由父本b按它自身的相对顺序填补，跳过已经被继承的基因。参数k是客户数（不含仓库），child是输出缓冲区，长度必须为k。这样交叉出来的子代一定是合法排列，而且保留了双亲的边结构信息——这是 OX 相比随机修复的最大优势。

变异用逆转变异，从解空间角度看就是一次 2-opt 移动，和退火的邻域算子完全一致。这种一致性不是巧合：把退火的接受准则套在遗传的变异结果上，就是所谓"退火遗传混合"最常见的缝合点。

// 子代不直接替换父代，而是先过一遍 Metropolis 准则 bool Accept(double cur, double cand, double T) { if (cand <= cur) return true; // 更优，无条件接受 double p = exp((cur - cand) / T); // 更差，按概率接受 return (rand() / (double)RAND_MAX) < p; }

cur是父代代价，cand是子代（经过交叉加变异）的代价，T是当前退火温度。这个函数返回 true 才让子代进入下一代种群。加上这一层之后，遗传算法不再只依赖"适者生存"的硬筛选，种群里的劣质个体也有机会留下，多样性维持得更久，早熟收敛的概率明显下降。

还有一个细节：仓库固定在下标 0，不参与交叉和变异。这是为了把巡回问题固定成"从 0 出发、回 0"的闭环，避免在染色体里反复定位仓库位置带来的额外分支。

3.3 收敛重找与非收敛重找：同一颗按钮的两种语义

这套系统有个很特别的设计：重找按钮有两种模式。文档里的描述是"收敛重找"结果一定比上一次短，"非收敛重找"每次结果是经过一次算法后的随机值。

收敛重找的实现在于两件事：第一，把上一次的最优解当作本次退火的初始解，而不是重新构造一个最近邻解；第二，初温设为上次终止温度的一半左右，让搜索在已有解附近做精修。更关键的是必须维护一个bestRoute快照，只有新解严格优于快照时才替换，否则丢弃。没有这个快照，退火的随机性会让用户连点几次看到里程数忽高忽低，那用户对这套系统的信任就崩了。

非收敛重找则相反：每次用新的随机种子重新构造初始解，初温复位到 T0，接受结果不设保护。它的用途是观察算法的波动性——对同一个客户集合跑十次，里程数的方差有多大，直接反映了参数调得好不好。这在调参阶段非常有价值，但在实际调度场景里就是灾难。

这两颗按钮背后是同一套算子，差别只在初值和历史保护，但它把"能不能重复得到更好结果"这个原本隐含在算法里的性质，变成了用户可见、可验证的接口。用课程设计的话说，这叫把需求、设计、实现三段式在交互层闭合了——用户不需要看代码，点两下就知道算法稳不稳。

4. 在线重规划：堵车标注之后，为什么不用推倒重算整条路线

静态规划只是开始。这套系统真正的动态部分是这样的场景：车已经出发了，走到一半，用户在界面上把前方某条路段标成拥堵，车停下，用户点启动，系统得绕开这条路重新找路线。文档里把这段叫"动态规划"，但从机制上看，它其实是在线重规划（online replanning），和 Bellman 方程那个动态规划不是一回事。这个术语偏差值得点出来，因为搞混了会导致对算法复杂度的错误预期。

4.1 子集划分：把"当前路段端点 + 剩余客户"重新拼成一张小图

重规划的关键洞察是：已经配送完的客户不需要再考虑，车当前所在的位置是新的起点，剩下的客户加上仓库构成一个新的、更小的 TSP 实例。

文档里的活动图写得很清楚：行进中遇到堵车路段，判断是否将当前路段的端点和剩余配送点划分为子集 A，然后调用 A* 求两两最短路线，再调用退火求子集 A 的巡回最短路线，返回后继续。这个流程和初始化时的求解完全一样，只是输入的点集变小了。

这个"变小"是整套动态机制能在 5 秒响应指标内完成的根本原因。刚出发时可能有 20 个客户待配送，跑第一次矩阵要 210 次 A*；配送掉 8 个客户之后遇到堵车，只剩 12 个点，矩阵只有 66 次 A*，退火的解空间也从 19! 掉到 11! 的量级。越到后面重规划越快，这是一个天然的、免费的加速结构。

但这套机制里有个必须处理的细节：新起点是当前路段的前方端点，不是车当前所在的位置。车可能正走在一条路段的中间，如果以车的精确位置为起点，那么 A* 的输入就多了一个不在节点表里的临时点，需要临时插入节点、重算邻接关系，代价很高。取前方端点是一种近似，会多算半条路段的距离，但换来的是所有算法都能复用现成的节点表。这种近似在物流场景里完全可以接受，因为路段长度相对总里程很小。

4.2 从定时器到 Route 链表：一次重规划的完整时序

这套系统用 MFC 的定时器驱动车辆沿路线移动。定时器的周期决定了动画的流畅度，也决定了重规划逻辑必须放在哪个位置，否则很容易把界面卡死。

完整时序是这样的：OnTimer被周期性触发，每次把车辆坐标沿当前Route链表推进一小段；推进到一条新路段时检查Road.traffic，如果被标成拥堵，就把状态切成暂停，等待用户操作；用户点"启动"按钮，LogicController::RefindRoute()被调用，做子集划分、重建矩阵、跑退火、重写Route链表；算完之后重新启动定时器，车辆沿新链表继续走。

void CLogicController::RefindRoute() { KillTimer(m_hWnd, TIMER_MOVE); // 先停推进，避免边算边改 Route int startPt = curRoad.frontNode; // 车已驶入的这条路段，取前方端点作新起点 int subset[K], k = 0; subset[k++] = startPt; for (int i = 0; i < markedCount; ++i) if (!nd[marked[i]].been) // 关键：已配送的点必须剔除 subset[k++] = marked[i]; subset[k++] = warehouseId; // 终点固定回仓库 BuildMatrix(subset, k); // k 随配送推进而变小，越到后面越快 double best = AnnealTSP(k, path); // 返回 k 个点的巡回序，写入 path[] BuildRouteList(subset, path, k); // 重写 Route 链表，前半段已走的部分不动 SetTimer(m_hWnd, TIMER_MOVE, 50, NULL); // 继续推进 }

几个参数的说明：curRoad是车辆当前所在路段的Road对象，frontNode是它朝向车辆前进方向的那个端点；marked[]是用户标注过的所有配送点 id 数组；nd[i].been是配送完成标志，由定时器在车辆抵达客户节点时置位；TIMER_MOVE是动画定时器的句柄，周期 50 毫秒左右。AnnealTSP返回的是子集内部的访问序，BuildRouteList负责把它翻译成从当前路段出发的完整链表，前半段已经走过的节点不重新生成，因为历史轨迹还要留给"手动测试"功能复核。

注意KillTimer和SetTimer的位置。寻路期间如果把定时器留着，OnTimer还会继续触发，可能在Route链表被改写的中途读到半成品状态，出现车辆瞬移或者路径断裂。这种问题在调试时极难定位，因为出错的概率取决于定时器周期和寻路耗时的相对关系，机器快慢不同表现完全不一样。

4.3 四个实体类怎么承载状态：Node、Road、Route、Astar

这套系统的数据模型很精简，四个实体类各自负责一块，边界清晰。

Node存节点信息：x、y是 Window 设备坐标，aroundid[]是邻接节点 id 数组，roadid[]是对应的道路 id 数组，id是节点编号，choose记录标注类型（仓库、客户还是未标注），father是 A* 回溯用，running和been分别表示"车是否正在此节点"和"是否已配送完成"。这个类同时被寻路、动画和状态判断复用，是典型的以数据换简单。

Road存道路信息：id、traffic（拥堵标志）、running（车是否正在这条路上）、then（方向或连接关系）。traffic是动态规划的唯一触发条件，用户标注就是改这个字段。

Route是一个单链表，节点只有id和next，表示配送的先后顺序。之所以手写链表而不用 MFC 的CArray，是因为重规划时需要整条替换、频繁在头部插入，链表没有元素搬移的成本。

Astar是 A* 专用的表节点：id、center（父节点）、g（已走代价）、price（f 值），next串成 open/closed 表。把它和Node分开，是为了避免每次寻路都污染业务数据。

这套划分有一个隐含的好处：Node和Road是静态拓扑加少量动态标志，Route和Astar是每次计算重新生成的临时结构。这种"静态-动态"分离让整个系统的状态管理变得可推理，也是后来排查问题时能快速定位层次的基础。

5. 排查手册：坐标、编号、定时器里最容易翻车的几处

这一章记录的是这套系统在实现阶段最容易踩的几类坑，每一条都按"现象—原因—解决"写清楚。这些问题不是编出来的理论难点，而是只要用 MFC 手写这类系统就大概率会撞上的东西。

5.1 编号断层与坐标系：两个最容易算错 30 倍的地方

坑一：节点编号不连续导致寻路时新标注的点"消失"。

现象：用户在地图上标注了一个新客户，界面上小旗子正常显示，但点击寻路后状态栏给出的路线完全不经过这个客户，手动双击测试也走过去不停。

原因：这套系统的节点编号是分段的——1 到 49 是道路交叉口，51 到 71 是可以被标注的客户和仓库节点，50 号是空的。如果代码里写Node nd[71]然后直接用 id 当数组下标，71 号节点就越界了；如果写的是Node nd[49]，所有标注点在访问时都会被静默丢弃，因为越界访问在某些编译模式下不报错，只是读到垃圾数据。

解决：数组上界开到 72，0号位留空不用，这样 id 和下标一对一；所有按 id 访问节点的地方统一走GetNode(id)封装，禁止在业务代码里直接写nd[id]。这个封装看起来多余，但它是唯一能防止后续再加节点时重蹈覆辙的办法。

坑二：比例尺换算位置放错，里程数差 30 倍。

现象：状态栏显示的配送总里程是手算结果的 30 倍，或者反过来只有三十分之一。用户手动测算一段距离得到 10 公里，系统报 300 公里。

原因：地图定义 30 像素对应 1 公里。如果 A* 内部就已经把像素换算成公里，代价数值会缩到小数点后两位，浮点比较时的容差阈值就不适用了，可能出现两条等长路径判不相等、退火代价函数抖动；如果输出时忘了换算，报出来就是像素数。

解决：约定一条硬规则——算法层全程用像素，只在状态栏刷新的那一处乘1.0/30。这条规则要写进命名规范里，比如所有变量名带Px后缀的就是像素单位，一眼能看出有没有漏换算。文档里提到变量用骆驼命名、函数用帕斯卡命名，这种命名规则的真正价值不在于好看，而在于让单位这种容易出错的信息附着在名字上。

5.2 重规划的状态污染：已经配送过的点又被塞回子集

坑三：重找路线之后车辆往回开，重复配送同一个客户。

现象：车配送到第 6 个客户后遇到堵车，用户点重找，结果车掉头开回已经配送过的第 3 个客户。

原因：子集划分时用的是"所有被标注的客户"，没有减掉been == true的点。这在第一次寻路时没问题（所有点都没配送），但在重规划时就是错的。

解决：划分前先过滤nd[marked[i]].been，同时把当前路段的前方端点强制放在子集第一个位置。这个"强制放第一位"也很重要，因为退火求出来的是闭环巡回序，起点在哪不影响总里程，但会让Route链表的拼接逻辑找不到断点。

坑四：连点几次重找，里程数忽高忽低。

现象：点击收敛重找按钮，结果第一次 42.3 公里，第二次 45.1 公里，第三次 41.8 公里，没有任何单调性。

原因：把"本次退火的返回结果"直接覆盖了"当前路线"，而没有和历史上的最优值比较。退火是随机算法，同一个初值再跑一遍也可能给出更差的解——这是算法的正常行为，不是 bug。用户看到的是不正常的，因为按钮上写的是"收敛"。

解决：维护一份bestRoute快照和bestCost，新解严格更优才替换，否则丢弃但保留退火的温度状态供下次精修。快照必须是完整拷贝，不能存指针——链表指针在下次重写时会被原地修改，快照跟着一起变，等于没存。

5.3 时间预算：5 秒响应指标是怎么被一次寻路撑爆的

坑五：一点寻路，窗口假死，鼠标变成转圈，超过 5 秒响应指标。

现象：客户数量拉到 18 个以上时，点击寻路按钮后整个窗口无响应，标题栏显示"未响应"，等十几秒才恢复。

原因：A* 加退火是同步计算，全部跑在 UI 线程里。MFC 的消息泵在这个函数返回之前不会继续分发消息，重绘、鼠标、键盘全部阻塞。文档里写的响应时间指标是"不多于 5 秒"，而 18 个客户的矩阵构造加退火总耗时在低配机器上很容易突破这个数。

解决：分两步。第一，寻路和重规划只在按钮响应里做一次，OnTimer永远不调用寻路函数，定时器只负责按已算好的Route推进坐标；第二，进入寻路前先KillTimer，算完再SetTimer，并且在状态栏打一行"正在计算"并强制UpdateWindow()刷一次，让用户看到反应。更彻底的做法是把寻路拆成多段，每个温度迭代之后就PeekMessage一次，但在这个规模下没必要，前面那两步已经足够把体感拉回来。

坑六（附带）：输入区的需求量一直是默认值。

现象：用户在输入区填了 8 吨，状态栏算出来的推荐车型和平均速度还是按默认吨数算的。

原因：用了 MFC 的 DDX 机制绑定控件变量，但读取之前没有调用UpdateData(TRUE)，成员变量还是上次UpdateData(FALSE)时的值。

解决：在所有读取输入区参数的函数入口统一调用UpdateData(TRUE)，在写入结果的地方调用UpdateData(FALSE)。这个成对出现的规则要写进代码注释里，因为它出错的时候没有任何编译期提示，只能靠现象反推。

6. 取舍：把"能解释"放在"跑得快"前面，值不值

这套系统的算法选型其实是有更"正确"的答案的。比如全源最短路加 Held-Karp 精确 DP 能给出严格最优的巡回序，20 个客户时的状态数是2^20 × 21，理论上可行。但实测下来，VC++6.0 单线程、32 位进程，光状态数组就吃掉 250 MB，还没算每步 21 次转移的开销，跑完轻松几十秒起步，直接撞穿 30 秒的性能指标。更麻烦的是它没有"中途停下来看看"的能力——用户点重找，只能从头再来一遍。

选第二行的理由不是"简单"，而是可验证。这套系统提供了一条人工复核链路：用户手动双击路段驱动路径行进，状态栏的里程、成本、时长同步更新，走完之后和系统算出来的路线对比，短了就是算法没收敛好，长了就是算法算对了。这种把算法正确性外包给用户肉眼验证的设计，在工业系统里是荒唐的，在教学和二次开发场景里却是最有价值的部分——它让每一个中间结果都暴露在外面，而不是藏在一个不可观测的黑匣子里。

实际验证时我一般会跑三件事。第一，把dist矩阵里的几个值用尺子在图上量一遍，乘 30 除 1000，看是否一致，这一步能同时抓出比例尺换算和坐标方向两个错误。第二，连点十次收敛重找，记录里程序列，如果出现上升就说明快照没生效。第三，把客户数从 5 逐步加到 20，每次记录矩阵构造和退火的耗时，画出增长曲线，正常应该是指数级的——如果某一段突然变平，多半是缓存或者子集过滤写错了。

这套架构的代价也很清楚：近似解没有最优性保证，退火的参数需要针对每张地图重新调，20 个客户以上性能会断崖式下跌。文档里把客户数上限定在 20 个不是随意写的，那是"退火在秒级能给出可接受解"的经验边界，超过这个数，要么加算子（比如 3-opt），要么换算法。这个边界值本身就是设计的一部分，比任何参数说明都更能说明这套系统的适用范围。

从那以后我每次接这类"先规划后模拟"的活儿，都会先把两层的输入输出固定成一张表——路由层只吐距离矩阵，排序层只吃距离矩阵，中间不允许有任何隐式依赖——再动第一行代码。这套系统最值钱的地方不是 A* 也不是退火，是它把这条分界线画得足够干净，干净到二十年后再看，每一层的职责还是清清楚楚。希望帮到你。

本文还有配套的精品资源，点击获取