基于节约算法的集送货车辆路径优化研究

邓芳敏南京农业大学工学院 江苏南京 210031

基于节约算法的集送货车辆路径优化研究

邓芳敏
南京农业大学工学院 江苏南京 210031

车辆路径问题是物流系统调度中的关键环节,它可以使物流经济效益化,实现物流运作科学化和高效化。而集送货一体化把配送和集货两个目标结合在一起,统筹安排,能更好达到成本最小化和效益最大化的根本目的,因此本文针对有集送货双重需求，有时间窗约束的车辆路径优化问题，通过改进后的节约算法实现了路径优化，同时对案例进行了分析，给出了路径优化方案。

路径优化；节约算法；集送货一体化；时间窗约束

一、背景

在物流运输过程中，运输成本占了60％，部分产品的运输成本甚至高于产品的生产成本，因此对配送进行优化成为公司降低物流成本，实现自身利益最大化的一个重要方面。而运输车辆的行车路线是配送优化的核心问题，在配送的同时回收货物是现代物流的发展方向，因此，一体化集货与配送的车辆路径问题（Vehicle Routing Problem with Back-hauls，VRPB)得到了广泛重视。

二、研究现状

目前国内对于带集货送货车辆路径规划的研究主要有霍佳震，张磊把上述问题分解为两个阶段进行求解:第一阶段对每一项任务内部的集货点与送货点进行内部安排行车路线；第二阶段再对各项任务之间进行外部安排行车路线，以此简化问题。钟石泉，贺国光提出一种改进的禁忌算法来解决这类问题。李华建立多目标优化模型，用混合遗传算法进行仿真求解。

本文重点讨论通过简单节约算法进行修正得到的改进型节约算法，对有集送货双重需求，有硬时间窗约束的车辆路径进行优化，并对某案例进行分析，给出优化方案。

三、研究方法

（一）节约算法

节约算法的基本步骤是先将各客户点分别与配送中心相连形成初始路线，然后将任意两客户点（即i，j）相连并计算节约值越大，节约的费用越多。S(i,j)按由大到小排序后，按照S(i,j)排序顺序依次连接各点。若连接过程中出现该路线运货总量超过车辆载重，则不连接这两点，考虑后面两点的连接。

本案例增加了集送货任务以及硬时间窗要求，要首先判断各点集送货量之和有无超过车辆载重Q，如果超出，需要在满足Q的情况下对该点单独集送货，而超出Q的部分再参与计算。

（二）改进的节约算法

对于时间窗约束有：设Si为完成任务i所需的时间，Ti为装货或卸货所需的时间，ETi为i的允许最早开始时间，LTi为i的允许最迟开始时间，则Si需满足：ETi≤Si≤LTi, S0=0令ti,j为车辆由点i行驶到点j的时间，则到达j点时间的推迟（或提前）量EFj可表示为，则有：EFj<0，提前到达；EFj>0，推迟到达。定义参数分别为j点的到达时间最大可提前量和最大允许推迟量，则有

其具体步骤如下：(1)形成一个初始解。采取单点配送构成各车辆配送点集令(2)计算各客户点间的距离节约值S(i,j)及S'(i,j)；(3)按S(i,j)值的上述顺序，逐个考察其端点i和j，若满足以下条件，则转下步，否则，不连接。条件是：1)点i和点j不在一条线路上；2)点i和点j均与基点相邻。

表1　各点之间的最短距离 （单位：km）

表2　每个点的配送量和集货量表(单位：kg )

表3　距离节约值S＇(i,j)（单位：km）

(4)考察点i和点j连接后线路上的总配送量要小于车载量且集货量之和要小于车载量减去总配送量,则转下步，否则不连接。(5)计算EFj，若满足弧(i,j)插入到线路中，否则，不连接。(6)计算连接点i和点j后车辆到达各项任务的新时间，返回步骤(3),直至考察完所有的弧为止。

（三）节约算法具体应用

1、案例分析

本文在符合客户可接受送达时间的前提下，不考虑运送次序对客户满意度和运输成本的影响，以赣州YQ农产品配送中心为实例并优化该配送中心的物流配送路径，赣州YQ农产品配送中心主要给赣州市区的15个大客户运送农产品，每天一定的时间段进行配送，配送中心目前有4辆车，核定载重量为10吨。每天运输的速度为50km/h，由配送中心负责配送和集货。A值取0.6。在此情况下为使配送中心自身运输成本最低，合理规划其路径。本案例取配送中心附近的8个点，配送中心为0点，其他赣州国光超市为1、天虹商场2、铁龙大酒店3、汇康大酒店4、赣州格兰云天国际酒店5、江西理工大学6、赣南医学院7、江西环境工程学院8。其各地点的距离以及它们的需求量和配送量如上表所示：

根据节约算法的步骤可以得到表3;

四、优化方案

赣州YQ农产品配送中心的在日常的配送过程中，其农产品配送路线计划主要是依据驾驶员的配送经验来安排，当配送客户点较少时，此类方法才有一定可行性，但在配送客户点很多时，这种方法缺乏科学依据，可操作性不强，同时存在许多不合理的地方，这时候配送成本会增加很多。赣州YQ农产品配送中心，由文献知赣州YQ农产配送中心的原有农产品配送计划和车辆配送对应客户点的实际情况，车辆编号配送线路计划如下：

1 0一5一3一4一7一6一0 22/2（载重量/集货量）502（距离km）

2 0一1一0 3 （载重量/集货量） 64（距离km）

3 0一2一8一0 4 /8（载重量/集货量） 180（距离km）

注:表中的“0”表示赣州YQ农产品配送中心，数字序号1-8指每个客户点

通过应用节约算法进行优化后，最后得出的结果如表4

表4　计算结果表

得出优化方案为：

路径1：农产品配送中心 ---赣州格兰云天国际酒店 ---铁龙大酒店---江西环境工程学院 --- 农产品配送中心

路径2：农产品配送中心---江西理工大学---赣南医学院---农产品配送中心

路径3：农产品配送中心---汇康大酒店---赣州国光超市---天虹商场---农产品配送中心

通过利用节约算法达使得了该配送中心运输成本得以下降，达到了路径优化的效果。

五、总结

本文从改进C一W节约算法入手，对有时间窗约束的VRPSDP式进行了研究，提出了以集货量和送货量共同作为各客户点归并的判断条件，并与其最短距离结合其来在规定的时间将货物送到以及集货。案例表明文中所提出的算法实现了路径优化，并节约了配送中心的运输费用。

邓芳敏，（1994—），女，汉，江西，本科，物流工程。

[1]冯芳媛.B2C电子商务中带逆向物流的车辆路径优化问题研究[D].沈阳师范大学,2012