一种基于可行性的实时混合搜索方法，用于具有质心感知负载平衡的3L-CVRP问题

《IEEE Access》：A Feasibility-Driven Anytime Hybrid Search for the 3L-CVRP with CoM-Aware Load Balancing

　　

摘要：

本文研究了多站点快速消费品配送中存在实际装载约束条件下的3L-CVRP问题。研究考虑了车辆载荷与货箱容量的差异性、货物不可重叠、有旋转限制的正交摆放方式、后进先出的卸货规则、货物易碎性约束以及最小支撑面积要求。所提出的方法采用“先保证可行性”的设计思路，在搜索过程中始终确保装载的可行性，同时通过将重心平衡约束纳入路径规划目标函数来加以考虑。该方法首先在客户位置之间构建最小生成树以指导问题分解，然后通过基于可行性的合并操作形成客户群组，从而尽早避免出现无法卸货的情况。每个可行的客户群组都会经过随时间调整的蚁群优化处理，之后再通过贪婪路径整合和基于重定位的邻域搜索来降低路径成本，同时保持装载的可行性。该算法在两个基准测试集（D1和D2）以及一个针对快速消费品的测试集（D3）上进行了多次测试，测试时固定时间预算，以TS和ALNS-DBLF作为对比算法。在所有测试集中，所提方法均实现了100%的可行性，找到首个可行解的时间更短，运行稳定性更强，且负载均衡效果更好。在D1测试集中，找到首个可行解的时间降至1.77秒，安全车辆比例达到75.81%，相较于共同可行子集中距离最短的方案，路径长度的惩罚系数为9.62%。在D2测试集中，随着问题规模增大，该方法仍能在15秒内保持100%的节点处理成功率。在D3测试集中，它实现了最短的平均路径长度、最少的车辆数量、最高的装载率以及最高的safe-vehicle比例。这些结果表明，对于时间受限的快速消费品配送而言，该算法在路径效率、计算响应速度以及负载均衡质量之间取得了良好的平衡。