城市大件物流运输车辆路径优化问题研究

魏远晗

(重庆交通大学 重庆 400074)

一、引言

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

综上所述，上述VRP的变化反映了客户的实际交付要求。例如，许多零售商为顾客提供退货服务，顾客可能会选择将自己不满意的商品退货。这也被称为逆向物流。在这种情况下，每个客户的交货和取货活动可以同时进行，从而使车辆路径优化问题变得更加困难。另一个例子是送货上门，送货人员需要配送客户的顺序，客户货物的体积大小，合理安排车辆的装箱方案，优化配送路径。以上例子说明带时间窗的城市大件物流车辆路径优化问题应该考虑不同顾客的相同类型的需求，并把它们装载在车辆的同一个区域，这样就会提高装载率，减少车辆数，降低配送成本。

二、案例分析

在本文中，我们用的是智能启发式算法，为了验证算法的有效性，本文选取重庆部分地区的30个客户，他们的经纬度坐标和需求如表1所示。

(一)案例相关数据

车厢的大小为420*180*200，每个区域的大小分别为：第1个区域大小为120*30*200，在这个区域里放置的是第一种类型的货物，货物的大小为120*30*50，每个货物的重量为40kg；第2个区域大小为150*120*200，在这个区域里放置的是第2种类型的货物，货物的大小为120*50*100，每个货物的重量为70kg；第3个区域大小为300*30*200，在这个区域里放置的是第3种类型的货物，货物的大小为150*30*65，每个货物的重量为60kg；第4个区域大小为300*150*200，在这个区域里放置的是第4种类型的货物，货物的大小为150*75*185，每个货物的重量为80kg。

车辆的额定载重是1300kg，配送车辆车厢里最多容纳的第1种类型货物的个数为4个，货车最多容纳的第2种类型货物的个数为6个，货车最多容纳的第3种类型货物的个数为4个，货车最多容纳的第4种类型货物的个数为4个。车子的配送速度为40km/h，配送中心拥有的车子的数目为6辆，每一辆车子的固定配送费用为100元，车辆单位运输成本为10元，早到的惩罚成本是5元/小时，晚到的惩罚成本为10元/小时。

表1 客户及其具体的需求

(二)优化结果分析

本文采用智能启发式算法来求解优化带有时间窗的城市大件物流车辆路径优化问题。优化结果如下所示：

第1条路线的配送顺序是：22,17,7,16,25,12，装载重量是1040kg，车厢里固定区域装载的货物的情况分别是：第1个区域里装载的第1种类型的货物的个数为3个，第2个区域里装载的第2种类型的货物的个数为6个，第3个区域里装载的第3种类型的货物的个数为3个，第4个区域里装载的第4种类型的货物的个数为4个。路线总长度为34.70km。

第2条路线的配送顺序是：18,15，装载重量是520kg，车厢里固定区域装载的货物的情况分别是：第1个区域里装载的第1种类型的货物的个数为0个，第2个区域里装载的第2种类型的货物的个数为0个，第3个区域里装载的第3种类型的货物的个数为6个，第4个区域里装载的第4种类型的货物的个数为2个。路线总长度为16.26km。

第3条路线的配送顺序是：10,20,6,14,13,11，装载重量是1070kg，车厢里固定区域装载的货物的情况分别是：第1个区域里装载的第1种类型的货物的个数为3个，第2个区域里装载的第2种类型的货物的个数为5个，第3个区域里装载的第3种类型的货物的个数为6个，第4个区域里装载的第4种类型的货物的个数为3个。路线总长度为45.74km。

第4条路线的配送顺序是：1,4,19,9,26,28，装载重量是900kg，车厢里固定区域装载的货物的情况分别是：第1个区域里装载的第1种类型的货物的个数为4个，第2个区域里装载的第2种类型的货物的个数为2个，第3个区域里装载的第3种类型的货物的个数为6个，第4个区域里装载的第4种类型的货物的个数为3个。路线总长度为29.70km。

第5条路线的配送顺序是：24,3,5,29,27，装载重量是1180kg，车厢里固定区域装载的货物的情况分别是：第1个区域里装载的第1种类型的货物的个数为2个，第2个区域里装载的第2种类型的货物的个数为6个，第3个区域里装载的第3种类型的货物的个数为6个，第4个区域里装载的第4种类型的货物的个数为4个。路线总长度为26.32km。

第6条路线的配送顺序是：8,30,23,21,2，装载重量是1120kg，车厢里固定区域装载的货物的情况分别是：第1个区域里装载的第1种类型的货物的个数为4个，第2个区域里装载的第2种类型的货物的个数为4个，第3个区域里装载的第3种类型的货物的个数为6个，第4个区域里装载的第4种类型的货物的个数为4个。路线总长度为32.27km。

经计算，总的配送成本为2833.98元。

本文首先介绍了车辆路径问题，根据阅读文献，发现车辆路径研究的变化反映了客户的实际交付要求。所以引出在带时间窗的城市大件物流的配送上，送货人员需要考虑配送客户的顺序，客户货物的体积大小，合理安排车辆的装箱方案，优化配送路径。接着本文选取了重庆某地区的30个客户点，基于它们的需求运用智能启发式算法进行求解，结果证明了该算法的有效性。希望对相关的研究有一定的参考意义。