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

邓芳敏

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

【关键词】路径优化；节约算法；集送货一体化；时间窗约束

一、背景

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

二、研究现状

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

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

三、研究方法

（一）节约算法

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

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

（二）改进的节约算法

对配送量和集货量有如下改进：各节点配送量和集货量）表示在节点j加入路线后可以留出的空间效益，把差值越大的节点放在运输路线的前面部分，并考虑车辆的载重限制。因此对节约算法进行一定的修正。即。

对于时间窗约束有：设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均与基点相邻。

（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。其各地点的距离以及它们的需求量和配送量如上表所示：

四、优化方案

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

五、总结

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

参考文献

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