摘要：两级车辆路径问题（2E-VRP）旨在使用两种不同类型的车队完成对客户的配送。第一级网络的车辆从配送中心取货并将其运送到卫星点。在卫星点，货物被转移到第二级网络的车辆上，再由其进行最终配送。本研究考虑城市物流的实际情况，加入客户点时间窗约束、第一级网络车辆和第二
摘要： 两级车辆路径问题（2E-VRP）旨在使用两种不同类型的车队完成对客户的配送。第一级网络的车辆从配送中心取货并将其运送到卫星点。在卫星点，货物被转移到第二级网络的车辆上，再由其进行最终配送。本研究考虑城市物流的实际情况，加入客户点时间窗约束、第一级网络车辆和第二级网络车辆在卫星点的同步约束，并允许第二级网络车辆多次往返交接点，提出一种2E-VRP的变体，即带有同步和时间窗约束且多行程的两级车辆路径优化问题 (2E-MTVRP-SS)，设计了一种自适应大邻域搜索算法（ALNS）来解决该问题。最后在带有时间窗的VRP数据集上进行数值实验。
关键词：路径优化、2E-VRP、同步、城市物流、自适应大邻域搜索算法
两级车辆路径问题（2E-VRP）旨在通过一组中间站点将货物从中央仓库运送到客户手中。中央仓库是一个称为配送中心（DC）的多式联运物流站点，具有一定的存储能力，允许货物整合。中间站点通常称为卫星站，存储能力很小甚至没有，但它们位于靠近客户的位置。该问题涉及两种类型的车辆：第一级网络的车辆将货物从DC运送到卫星站，第二级网络的车辆则将货物从卫星站运送到客户。通常情况下，第一级网络的车辆容量远大于第二级网络。
城市货运中，为减少交通拥堵、环境污染以及运输卡车装载率低下等问题，多级网络配送系统，尤其是二级配送网络被广泛使用。本研究考虑到，在实际物流配送中，（i）由于客户需求或城市法规的限制，需要考虑客户的允许配送时间；（ii）由于第二级网络的车辆容量较小，它们即使满载也无法完成一天的配送量，需要多次往返交接点；（iii）由于劳动力成本和高昂的租金，在城市中运营一个卫星站费用昂贵，越来越多的城市允许运输公司使用专用或现有的基础设施（如专用停车位、公交车站）来进行卸货，这些地点通常不提供存储能力，需要两级网络车辆的配送同步。考虑上述三点，本研究提出一种2E-VRP问题的变体，即带有同步和时间窗约束且多行程的两级车辆路径优化问题（2E-MTVRP-SS），并设计一种自适应的大邻域搜索算法求解，最后作者在经过修改的带有时间窗的车辆路径问题数据集上进行广泛的数值实验。
目标函数（1）为最小化运输成本与车辆使用成本的和。约束（2）表示每辆车都必须从车场出发并回到车场；约束（3）是流平衡约束；约束（4）表示每个客户点都被服务；约束（5）表示对于每个送货请求只使用一个卫星点；约束（6）表示每个客户点都被一辆一级网络车和一辆二级网络车访问；约束（7）表示二级网络车辆从卫星点出发服务客户；约束（8）表示若两点被相同车辆连续访问的行驶时间计算；约束（9）处理没有先前结点的特例；约束（10）确保在允许时间窗内访问每位顾客；约束（11）表示每辆车的运行时长不超过其最大服务时间；约束（12）和（15）是车辆的容量约束；约束（13）表示第二级网络车辆容量随着访问路径的变化；约束（14）表示每次二级网络车辆访问卫星点时都是空的；约束（16）是对决策变量的限制。
本文采用ALNS算法求解2E-MTVRP-SS，如算法1所示。ALNS算法由Ropke and Pisinger (2006)首次提出，并已用于2E-VRP的求解(Hemmelmayr et al., 2012)。
该算法中，采用two-phase constructive alogorithm获得初始解，首先，使用最佳插入算法为多行程多站点问题设计二级网络的路径，在此启发式方法中，可能插入的客户是现有行程中的所有插入，以及通过创建新行程进行的所有插入。然后，根据之前创建的二级网络路径构造一级网络路径来满足卫星站的需求。“破坏”指从当前解中移除p个请求，作者在文献(Azi et al., 2014)的基础上设计破坏方法，分别基于工作日、路径和顾客级别移除请求。“修复”指在解中插入计划外的请求，作者首先介绍了将顾客插入现有第二级网络路径的3种插入算子，包括向现有行程插入顾客、通过创建新行程插入、按行程拆分插入（如图2所示）；其次介绍限制插入算子邻域数量的方法，该方法在保证解质量的情况下将速度提升2.3倍；之后介绍了两种修复方法，包括最佳插入法和K-遗憾法；最后指出当插入算子产生卫星站时，需要考虑偏差成本。
本文判断修复是否可行的方法来自对PDPT可行性算法的改编(Masson et al., 2013b)。
在 2E-MTVRP-SS 中，若将一个请求插入到二级车辆 A 的行程中，它可能会在下一次与一级车辆交接时延迟到达，一级车辆将此延迟传播到与之同步的下一个二级车辆B，最终可能导致与A并不直接关联的B违反客户时间窗，这被称为相互依赖问题（interdependence problem）。
本文在Solomon数据集的基础上设计了新的算例，在CDC和卫星站位置、客户时间窗和车辆容量方面做了改动，以1结尾的算例偏向时间约束，以2结尾的算例偏向容量约束。由于本问题的车辆数量无限制，因此第一阶段以最小化车辆数目为目标，在此最小车辆数上，第二阶段以成本最小为目标。在每个算例上实验10次，结果如下：
（1）对于初始解的构建，比较最佳插入法和两阶段最佳插入方法。单独使用后者会产生更糟糕的结果，但它可作为减少车辆数目的更好起点，如表2所示。
（2）比较FTS 扩展的算法和增量 PERT 的算法的运行时间。由表3可见， FTS 方法是减少计算工作量的关键，采用FTS使得我们的算法快了91.9%。
（3）基于表4的结果，本文选择了邻域4（使用customer first和exsiting stops算子，在为一级车辆创建新卫星点时，将探索的卫星数量限制为三个）
（4）在自定义的销毁和修复方法对成本优化阶段的影响方面，使用偏差成本和基于同步的移除不会对解的质量产生重大影响，但它们使本方法更加稳定。
（5）对于类型 2（即容量受限）的 实例，二级网络的平均行程数量更多，并且在具有集群的实例中使用了更多的卫星站。
最后，作者进一步分析了去掉时间窗以及将同步约束改为优先约束，对二级网络车辆使用数量和成本的影响，如表7所示。可见，改为优先约束后影响不大，更加现实的场景是设置车辆在卫星点的最大等待时间，并增加等待站点；去掉时间窗后影响较大。
本文扩展了 2E-VRP，以考虑城市物流中出现的约束（时间窗口、同步约束和某些车辆的多次行程），作者设计了一种 ALNS 来解决 2E-MTVRP-SS，该方法具有自定义销毁和修复启发式方法，以及检查插入是否可行的有效方法，它可以在合理的时间内找到好的解。数值实验表明，客户时间窗对解成本的影响大于精确同步。在未来的工作中，该算法可以应用于其他具有同步约束的 VRP问题。
[1] Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455–472.
[2] Hemmelmayr, V. C., Cordeau, J.-F., & Crainic, T. G. (2012). An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & Operations Research, 39(12), 3215–3228.
[3] Azi, N., Gendreau, M., & Potvin, J.-Y. (2014). An adaptive large neighborhood search for a vehicle routing problem with multiple routes. Computers & Operations Research, 41, 167–173.
[4] Masson, R., Lehuédé, F., & Péton, O. (2013b). Efficient feasibility testing for request insertion in the pickup and delivery problem with transfers. Operations Research Letters, 41(3), 211–215.
来源：夏琳说科技