链上镖师 / Chain Biaoshi
EJOR|多车场容量车辆路径：双目标数学启发式框架
Math-AUGMECON-II用进化搜索引导ε约束求解，在中大型多车场累计容量路径问题上兼顾前沿质量和计算效率
这篇论文把多车场累计容量车辆路径问题扩展为同时最小化客户等待时间和行驶成本的双目标模型，并提出Math-AUGMECON-II框架来提升中大型实例的Pareto前沿求解效果。
- 01：问题对象是多车场、多车辆、容量受限的累计车辆路径，延迟目标对应客户到达时间之和，成本目标对应车辆行驶成本。
- 02：方法把NSGA-II型多目标模因算法得到的近似Pareto前沿，用作AUGMECON-II中ε边界扫描和跳点的引导。
- 03：实验比较NSGA-II、AUGMECON-II和Math-AUGMECON-II，指标包括非支配解数量、hypervolume和set coverage，并覆盖缩减车队规模场景。
研究背景
累计车辆路径问题关注成本沿路线逐步累积的场景。本文聚焦的延迟目标，是所有客户到达时间之和，也就是客户等待时间。该类问题已用于医疗、救援、维护和末端配送等任务，真实网络中车辆常常从多个车场发出，单车场假设难以覆盖这些运营结构。
来源：Fig. 1。多车场累计容量车辆路径问题示例，图中同时呈现车辆路线、客户等待和行驶成本，虚线回车场弧用于完整展示路线。
论文把客户侧的及时服务和运营侧的成本控制放进同一个模型。客户希望更快、更可靠地收到服务，物流企业需要降低距离、车队使用和运行成本。作者因此把MDCCVRP扩展为bi-MDCCVRP，同时最小化累计延迟和总行驶成本。
核心问题
bi-MDCCVRP要求从多个车场派出容量受限车辆，覆盖所有客户需求，每个客户只访问一次，并同时优化两个目标。第一目标是路线延迟之和，第二目标是车辆移动产生的总行驶成本。两个目标都和访问顺序、车场选择、车辆容量约束紧密相连。
这篇论文的关键挑战在于：更快服务客户通常会推高行驶成本，更省成本的线路安排又会让部分客户等待更久，求解器需要给出一组可选择的Pareto解，而非单一线路方案。
01建模层面：把多车场、容量限制和累计等待时间放入同一整数规划结构。
02求解层面：在Pareto前沿上同时控制解集质量、覆盖范围和计算时间。
03实验层面：比较小、中、大实例以及缩减车队规模下三类方法的表现。
方法框架
作者先用多层网络表示访问顺序。网络中包含车场、客户和辅助节点，并把节点复制到不同层级；一条路径从上层车场出发，沿层级向下连接客户，起始层级反映该车辆访问的客户数量。这个结构支撑后续目标函数和容量约束表达。
来源：Fig. 2。bi-MDCCVRP的多层网络表示，用于把车辆访问顺序转化为整数规划中的节点和边变量。
1建立bi-MDCCVRP双目标模型，目标分别为累计延迟和总行驶成本。
2用NSGA-II型多目标模因算法生成近似Pareto前沿。
3把近似前沿拆分为两个子集，分别引导两轮ε约束扫描。
4在AUGMECON-II子问题中利用松弛量跳过冗余边界，并更新非支配解集。
来源：Algorithm 4。Math-AUGMECON-II matheuristic framework，用NSGA-II近似前沿引导ε约束扫描并减少冗余求解。
来源：Fig. 3。基于两座车场、八个客户和四辆车的交叉算子示例，用于说明进化搜索如何重组车辆路线。
案例或实验设置
实验使用已有MDCCVRP基准实例，并覆盖不同规模。论文分别评估NSGA-II、AUGMECON-II和Math-AUGMECON-II，比较指标包括非支配解数量、hypervolume和set coverage，这些指标分别对应解集规模、前沿覆盖质量和算法之间的支配覆盖关系。
来源：Algorithm 1。AUGMECON-II求解流程，是Math-AUGMECON-II中ε约束扫描机制的基准参照。
在AUGMECON-II中，论文保留累计延迟目标作为主优化目标，把行驶成本目标放入ε约束。作者说明，这一选择延续了原MDCCVRP以延迟最小化为核心的建模传统，并在预实验中表现出更稳定、更高效的求解过程。
结果分析
摘要给出的主结论是：AUGMECON-II适合小规模实例，Math-AUGMECON-II更适合中等和大型实例，并能处理缩减车队规模的情形。原因在于混合框架保留ε约束求解的前沿校正能力，同时用启发式前沿减少需要探索的边界。
来源：Table 4。三类算法在不同实例规模上的HV比较，用于判断Pareto前沿覆盖质量。
来源：Fig. 4。不同算法在随机实例中的Pareto前沿分布，展示延迟和行驶成本之间的解集形态。
来源：Fig. 5。NSGA-II与Math-AUGMECON-II在不同实例上的HV箱线图，用于观察多次运行下的稳定性。
来源：Table 8。缩减车队规模条件下的HV比较，反映资源约束收紧后不同方法的前沿覆盖质量。
管理启示
这篇论文对运营决策的价值，在于把服务速度和运输成本的取舍显式呈现为一组Pareto方案。管理者可以从前沿中选择偏向低等待、偏向低成本或居中折中的路线方案，并用同一套目标口径比较车场、车辆和访问顺序调整的后果。
来源：Table 11。缩减车队规模条件下延迟目标与行驶成本目标的权衡分析，把极端方案之间的变化转化为百分比。
论文的实验结论说明，若目标是快速获得小实例的精确前沿，AUGMECON-II是合适选择；若任务扩展到中大型多车场配送或车队资源受限场景，Math-AUGMECON-II更适合作为前沿生成工具。
✓面向时效敏感配送，可用延迟目标筛选更快服务方案。
✓面向成本控制，可查看低行驶成本方案带来的等待时间变化。
✓面向车队收缩评估，可用缩减车队实验观察前沿覆盖质量和服务成本权衡。
论文：A matheuristic augmented ε-constraint framework for a bi-objective Multi-Depot Cumulative Capacitated Vehicle Routing Problem
作者：Eduardo Segredo，Samuel Nucamendi-Guillén，Gara Miranda，Eduardo Lalla-Ruiz
期刊：European Journal of Operational Research
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
