魏远晗

(重庆交通大学 重庆 400074)

一、引言

众所周知，车辆路径问题(VRP)是一个NP-hard问题，为了有效地解决VRP问题，过去开展了大量的研究[1-3]。Novoa和Storer[4]从再优化的角度提出了需求随机的单车辆路径问题的近似动态规划方法。Fuellerer等[5]在前人研究的基础上，进一步研究了具有装载能力的三维车辆路径问题，并利用蚁群算法解决了该问题。Marinakis等[6]提出了一种混合粒子群优化算法来解决车辆路径问题，并在较短的计算时间内取得了非常满意的结果。在大型物流网络中，VRP的成功实施应包括客户聚类和车辆路径优化[7]。然而，近二十年来，传统的车辆路径问题的客户聚类优化过程很少涉及客户和产品的特点。近年来，逆向物流和冷链物流研究的兴起促进了集群客户和产品研究的深入。每个客户的特点可以用周边交通条件、地理环境、需求要求、货物相容性等来表征。然而，这些特性中有一部分是不能直接用数字测量的。分区交付基于异构客户特点,有必要将这些特征作为输入，然后进行车辆路径优化,再结合运输成本寻找最优路线。

综上所述，上述VRP的变化反映了客户的实际交付要求。例如，许多零售商为顾客提供退货服务，顾客可能会选择将自己不满意的商品退货。这也被称为逆向物流。在这种情况下，每个客户的交货和取货活动可以同时进行，从而使车辆路径优化问题变得更加困难。另一个例子是送货上门，送货人员需要配送客户的顺序，客户货物的体积大小，合理安排车辆的装箱方案，优化配送路径。……