解决需求可拆分车辆路径问题的先聚类后路径方法

A clustering first and routing later-based approach for split delivery vehicle routing problem

介绍了求解需求可拆分车辆路径问题的"先聚类后路径"的方法,其目标是使用最少车辆获得最小总行驶距离。基于该方法,提出了三阶段算法:首先,根据使用最少车辆的原则,利用最大最小距离聚类,将所有客户点按物理位置分成若干组;然后,采用"推出"和"拉入"操作,调整各组的负荷量,形成重量平衡的聚类组;最后,优化上述组内路径。两案例组7个实例的执行验证了该算法的可行性和有效性;结果表明,该算法在总行驶距离和计算所用时间方面性能优于带有效不等式的两阶段算法、k-means聚类算法、拆分阈值聚类算法和扫描算法等。