车辆路径规划：建模比算法难
摘要
本文针对带时间窗的车辆路径问题设计了一套求解系统。问题本身定义简短，难点集中于建模与算子配置。本文讨论三处关键设计：符号定义中三维下标与虚拟节点的处理、目标函数中”早到不计惩罚”的设定理由，以及破坏与修复算子的互补配置；并指出执行跟踪模块的长期价值，以及静态成本矩阵假设带来的局限。
1 引言
问题描述为：设有单一配送中心与若干客户需求点，每客户具有需求量与服务时间窗，配送中心拥有多台容量相同的车辆；需为每台车规划一条自配送中心出发、访问若干客户并返回的路径，在满足容量与时间窗约束下使总行驶成本最低。此即带时间窗的车辆路径问题（VRPTW）。
定义虽只有几句话，真正动手时第一处麻烦落在建模上。
2 建模中的两处难点
2.1 符号定义
有三处细节容易在实现时出错。其一，配送中心应作为虚拟节点 0 处理，而非”第 0 个客户”；其二，服务时长与时间窗上下界是三件不同的事，混用将导致到达时间计算错误；其三，路径决策变量的下标为三维，车辆维度不可省略。
2.2 早到不应计惩罚
目标函数由三项加权构成：总行驶成本、时间窗惩罚成本与车辆使用成本。
其中时间窗一项仅惩罚晚到，早到则记为等待而不计惩罚。这一设定值得说明：现实中早到并不产生额外开支，司机等候即可；但若将早到也计入惩罚，算法将倾向于令车辆压着时间窗抵达，反而抬高了迟到风险。因此此处仅对晚到施罚。
三项权重由运营方按业务偏好设定——外卖与家电配送对时间窗的容忍度截然不同，该判断不宜固化于算法之中。
3 求解算法设计
3.1 破坏与修复算子的错开配置
精确方法在客户数量与时间窗约束下无法在可接受时间内求解，故采用自适应大邻域搜索（ALNS），以”破坏—修复”交替迭代在解空间内跳跃。
破坏算子配置四种：随机移除、最远移除、时间窗移除与最坏移除。四类算子的探索方向是我刻意错开的——仅保留随机移除会退化为随机重排，仅保留最坏移除则始终在同一局部结构内打转。
3.2 贪婪插入与 regret 插入的互补
修复算子配两种：贪婪插入选取插入代价最小的位置，regret 插入则优先插入 regret 值最大的客户。
前者着眼即时代价最小，后者以当前多花一点换取后续不至于无位可选。二者并用，恰好互补。
3.3 “自适应”来自何处
ALNS 的自适应体现在两处：以模拟退火准则接受劣解，接受概率随温度衰减下降；按算子近期获得最优解的次数更新其被选概率。
这两者缺一不可。没有劣解接受机制，算法将困于局部最优；没有权重更新，则退化为固定算子的普通邻域搜索。这一点我在调试过程中印象很深。
4 系统实现：执行跟踪的价值
系统的功能模块包含订单管理、路网建模、求解引擎、结果可视化与执行跟踪五项。
其中执行跟踪是最容易被忽略、而我认为长期价值最高的一个模块：它将车辆实际到达时间与规划时间窗比对，使偏差数据回流用于后续算例的参数校准。换言之，系统不只在编排计划，还在以真实执行数据修正自身假设。
5 已知局限与后续方向
有两点局限须说明。其一，行驶成本矩阵为静态给定，未考虑实时交通的影响。城市配送的成本矩阵在高峰与平峰完全是两套数字，静态矩阵意味着方案系按平均路况编排，实际偏差最终汇入执行跟踪模块记录。其二，需求量与时间窗均取确定值，未覆盖随机需求场景。
这也是我在这个项目里最想继续做的一块：把执行偏差反过来修正成本矩阵，让下一次排出来的方案更贴近现实。
此外，方案可视化、收敛曲线与成本对比三张图中的数值目前为示意数据，用于说明评估维度与呈现方式，真实结果尚待标准算例库运行后回填。
6 结论
本文的工作表明，该类问题的关键不在算法选型，而在建模细节与算子配置：虚拟节点与三维下标的处理决定实现正确性，早到不计惩罚决定解的可用性，算子的错开与互补决定搜索质量。而执行跟踪所积累的偏差数据，是系统从”排一次计划”走向”持续修正假设”的基础。
附件
