节约里程算法在车辆路径优化中的应用研究

齐建强

【摘 要】 高效地配送会使物流系统的顺利运行得到保障，对配送车辆的路径优化，可以节省配送时间，提高配送的效率，进而提高整个企业的经济效益和社会效益。本文从企业配送货物时，配送车辆存在空载率高、迂回运输现象严重和配送时间长等问题的角度出发，采用节约里程法对车辆路径进行优化。进而提高物流服务水平。

【关键词】 配送路线 车辆路径问题 节约里程法

1 引言

随着我国经济的高速发展，各种工业制造型企业不断发展壮大，市场竞争日趋激烈。企业为了降低成本，提高竞争力，越来越重视物流的发展，物流领域也成为继降低人工、材料费用和扩大销售之后，企业的“第三利润源泉”。在这种大背景的情况下，企业想提高收益，降低物流成本成为企业获取利润的必选之路。对配送线路进行优化对企业乃至对社会都有重大意义，

2 节约里程算法概述

节约里程算法的核心思想是将运输问题中存在的两个回路合并成为一个回路。在上面的合并操作中，整个运输的总运输距离会发生变化，如果变化后总运输距离下降，则节省了运输距离。相应的变化值，叫做节约距离， 如式子所示：。

已知条件：需求点集={1，2，……n}，各个点的需求量为，各点之间的最短距离为。第一步形成一个初始解。确定各车辆配送点集，，……令={j}，j=1，2，……n（先采取单点配送）。第二步，进行节约度的计算，计算所有点对的节约度，然后对计算结果进行升序排列。第三步，进行回路的合并。从升序排列的节约度序列中的最上面的值开始，直到节约里程的序列空为止，重复下列步骤。按照节约里程队列从大到小的顺序，分析客户和之间合并的可能性将，连接起来，如果不是这样，则从节约里程队列中去除当前的节约里程，分析下一个网点。

3 算法实现

3.1 A公司配送现状

本文以A公司为例研究节约里程算法在车辆路径优化问题中的应用，A公司是一家电子商务公司，每天需要给客户配送货物，本文以该公司的配送中心为研究对象。经过调查，该配送中心需要向固定的9个网点配送货物，通过合理布局和摆放可发现，该类型货车最多可装载30个周转箱。已知1-9号网点周转箱的数量分别为10、11、8、10、11、12、8、10、7个。

同时得到原有的配送路线和配送车辆情况，该公司由四辆车和四名司机进行配送，配送的总运输里程为134.2公里。

3.2 基于节约里程法路径优化

节约里程数是由公式，0，1，2…，9计算得出，其中0代表该企业的配送中心，1-9代表该企业各个配送网点。由各个网点之间的距离可求的，将从大到小排列可以得到如下分析。

a）=25.8為最大值，所以我们首先从最大值开始考虑，表示各个网点配送量中周转箱的个数。=11+11=22<30，所以可以选择这条路线进行配送。

b）=22.9，是余下的最大值，所以我们把网点7考虑到回路当中，++=11+11+8=30，所以可以把网点7放入到回路当中，配送路线为0-2-5-7，由于该车辆已经满载，所以可得出0-2-5-7-0为一条完整的回路。

c）在余下的节约里程数中选择最大的节约里程数，由于网点2、5、7已经形成了完整的配送回路，所以中含有2、5、7的不在考虑。为最大值，由于=8+10=18<30，所以0-3-8可以构成回路。

d）为符合节约里程算法中满足条件的最大值，所以我们把网点1考虑到配送回路当中=8+10+10=28<30，所以可以把网点1放入当回路当中，配送路线为0-3-8-1，由于所剩空间只能容纳两个周转箱，不满足任意网点配送所需周转箱的个数，所以可得出0-3-8-1-0为一条完整的回路。

e）在余下的节约里程数中，只有网点4、6、9没有形成闭合的配送回路，所以余下的节约里程数当中，我们只考虑含有4、6、9的节约里程数，为最大值，由于=10+12=22<30，所以0-4-6可以构成回路。

f）将网点9插入到该配送回路当中，发现+为29，所以可以把网点9插入到该回路当中，0-4-6-9-0为一条完整的配送回路，并且符合节约里程算法的要求。

因此用节约里程算法对A企业配送线路的优化。最后得到的优化结果为，第一条配送路线为0-2-5-7-0，运输距离为42.1公里，周转箱有30个，装载率为100%；第二条配送路线为0-3-8-1-0，运输距离为27.7公里，周转箱有28个，装载率为93.3%；最后一条配送路线为0-4-6-9-0，运输距离为36.1公里，周转箱个数为29个，装载率为96.7%。

4 结论

用节约里程法对原有配送路线进行优化，配送车辆由原来的四辆车变成了三辆，由原来的需要四名司机变成现在的三名司机进行配送，降低了人工成本，同时也减少了配送车辆的数量，使车辆的装载率得到提高，充分利用了车辆的空间。节约了里程数28.3公里，节约了油耗3.4升，人工成本和燃油成本每天共节省费用173元。用节约里程算法对车辆路径进行优化，可以明显减少企业的配送成本，降低劳动力，提高车辆的装载率，与之前相比，大大提高了物流的配送效率。同时，降低了燃油排放，对社会效益也有很大的帮助。所以，节约里程算法在求解车辆路径优化问题上是一种良好且实用的解决方法，对企业经济效益和社会效益都有所帮助。

【参考文献】

[1] 张颖敏.基于节约里程法的物流配送线路优化与改进研究.物流科技，2011（04）：113～115

[2] 张敏.基于中国邮递员问题的图书配送线路优化.物流技术，2012（12）：320～322

[3] 尚文芳.电子商务环境下基于B2C的物流配送路径优化.物流技术，2014（07）：100～103