李华峰，黄樟灿，张 蔷，湛 航，谈 庆

（武汉理工大学理学院，武汉 430073）

0 引言

车辆路径问题（Vehicle Routing Problem，VRP）最早于1959 年由Dantzig 等［1］提出。该问题可描述为：在一个物流系统中，存在若干个配送中心、若干个客户和若干辆运输车，假设客户的需求量不超过车辆的最大载重量，要求设计合理的车辆行驶路线，在不违背车辆容量限制、不超出车辆最远运输距离等约束条件下，完成所有客户的配送任务。但在实际配送过程中，客户的需求量大于车辆载重量的情况会经常发生，为了解决该问题，Dror 等［2］提出了需求可拆分的车辆路径问题（Split Delivery VRP，SDVRP）。

SDVRP 自提出以来就受到广泛的关注，很多学者也对该问题进行了深入的研究。由于SDVRP 是NP（Nondeterministic Polynomial）-hard 问题［3-4］，精确算法［5-6］求解比较困难，所以主要采用聚类算法［7-8］和启发式算法［9-12］相结合的两阶段思想对该问题进行求解。刘旺盛等［7］分别采用了先分组后路径和先路径后分组两种思想求解了该问题，从不同角度论述了两种思想的优越性；刘旺盛等［8］结合了K-means聚类与模拟退火算法的优点，实验结果表明，算法效果优于其他算法；闵嘉宁等［13］在传统K-means 聚类中加入了“推出”“拉入”操作，平衡了各类的需求量，优化了算法的性能；向婷等［14］通过设置拆分阈值对客户进行聚类，然后采用蚁群算法优化各类的线路，从而提高了求解精度；姜婷［15］分析了SDVRP 解的特点，先求解旅行商问题，然后对其进行切割拆分成单个路径，最后通过删除和最小代价插入操作采用人工蜂群算法求解该问题。

以上两阶段求解算法主要采用K-means 聚类算法，先对客户进行分组，然后运用智能优化算法优化路径。……