基于节约算法和改进节约算法的配送路线优化

王芳

摘 要：运用节约算法对山东某葡萄酒配送中心的配送实例进行配送路线的优化，优化的过程中总结出传统的节约算法的不足之处，通过分割配送对节约算法进行改进，用改进的节约算法来优化相同案例，证明改进的节约算法能有效提高车辆装载率、减少所需车辆数、节约里程数。

关键词：配送路线；节约算法；改进节约算法；分割配送

一、节约算法原理

车辆路径优化技术对加快配送速度，提高服务质量，降低配送成本都具有重大意义[1]。节约算法是用来解决运输车辆数目不确定的VRP问题最有名的启发式算法，其核心思想是将运输问题中的两个回路合并成一个回路，若合并后的总运输距离减少，则称节约了运输距离[2]。

二、节约算法步骤

1、计算各地区间最短距离，列出最短距离表；

2、计算两地区连接后的节约里程，按从大到小的顺序排列，得节约里程表；

3、根据节约里程顺序表和车辆载重约束确定较优配送线路。若在合并的过程中超过车辆载重，则取消合并。

三、节约算法优化配送实例

某葡萄酒配送中心P0位于烟台，需对13个地区P1-P13进行配送，现有载重为2t、4t、6t、8t、10t的车辆进行单点往返配送。

（一）确定各地区间最短距离（单位：公里），数据来自高德地图

（二）用传统节约算法得到配送路线

配送路线为：P0-P11-P0，P0-P13-P0，P0-P12-P0，P0-P4-P0，P0-P9-P0，P0-P1-P5-P0，P0-P2-P3-P8-P0，P0-P6-P10-P7-P0。所用车辆：10t、10t、10t、8t、8t、10t、10t、10t。配送量：9.8、8.3、8.8、7、6.8、10、8.3、8.5。配送路程：1192、746、1092、696、500、702、1135、1583。

节约法在求解小规模运输配送路线，优化车辆调度问题方面有其独特的优势[3]。传统节约算法不允许客户的货物分批配送，所有客户必须一次性完成配送，因而非满载的现象比较严重。

四、改进节约算法步骤

1、计算各地区间最短距离，得最短距离表；

2、计算两地连接后的节约里程，按从大到小的顺序排列，编制节约里程表；

3、根据节约里程顺序表来确定较优的配送线路。在貨物总量超过车辆载重的时候，将该客户并入到配送路径中，并使车辆刚好满载，该客户尚未配送完的货物由另一辆车配送。

五、用改进节约算法优化上述实例

（一）利用改进节约算法得到配送路线

配送路线：P0-P10-P11-P0、P0-P6-P11-P7-P12-P0、P0-P8-P12-P0、P0-P13-P8-P3-P9-P0、P0-P13-P2-P0、P0-P2-P4-P0、P0-P1-P5-P0。所用车辆：10t、10t、10t、10t、10t、8t、10t。配送量：10、10、10、10、10、7.5、10。配送路程：1404、1596、1111、1109、788、718、702。

（二）单点往返配送、传统节约算法和改进节约算法得到的配送路线比较

相对于单点往返配送，传统节约算法所得的配送路线大大减少了车辆数、里程数，同时也提高了装载率。而通过改进的节约算法得到的配送路线在车辆的装载率上有更大的提升，同时也进一步减少了所需的配送车辆数和配送的里程数。传统的节约方法在配送路线的选择上有一定的实用性，改进的节约算法能更大程度的提高车辆利用率、降低配送成本，从而提高配送中心的运营效益。

六、结束语

传统节约算法所得的配送路线和配送方式相对于单点往返配送有着很大的进步，而改进节约算法将分割配送和传统节约算法相结合，进一步地优化了传统节约算法，车辆装载率有明显的提升。然而改进节约算法也存在不足之处，其一，由于部分订单的分割，使得接收订单的对象要多次接收订单，增加了收货的复杂性；其二，订单分割导致遗留下来需要配送的货物大大减少，有时为了一点点的货物需要再次前往某处进行配送，这样的做法是否经济也有待考虑。虽然通过分割配送改进的节约算法存在着不足的地方，但在实际应用上仍然具有一定的现实意义。（作者单位：南京农业大学工学院）

参考文献：

[1] 周大帅，李岚，刘文科.一种解决物流配送问题的算法研究[J].佳木斯大学学报（自然科版），2006，03：417-419.

[2] 黄博，金志扬.基于节约法的海南某公司物流配送路径优化[J].物流技术，2015，21：124-126.

[3] 崔天宇.基于节约算法的配送路线优化研究[J].东方企业文化，2013，15：144.