基于节约里程法的物流配送路线优化

基于节约里程法的物流配送路线优化

摘要：物流配送是物流中的一个重要环节，为了提高配送效率，降低物流成本，提高服务质量，必然要选择优化配送方案。文中介绍了节约里程法在实际中的应用，得出配送路线优化方案，并通过一次实际配送验证了其可行性。 关键词：节约里程法；物流配送；路线优化

Route Optimization of Logistics Distribution

Based on Saving Algorithm

Zhang Wen-hua

(School of Logistics Engineering, Wuhan University of Technology, Wuhan, 430063) Abstract：Logistics distribution is an important part of logistics. It is necessary to choose route optimization in order to improve distribution efficiency, reduce the cost and improve the quality of service. The paper introduces the practical application of saving algorithm and obtains a method of route optimization and proves its feasibility though an actual distribution. Keywords：saving algorithm; logistics distribution; route optimization

1 导言

随着经济的飞速发展和社会分工的不断细化，物流业快速崛起，但物流成本却居高不下。因此，在物流成本中占很大比重的配送成本日益受到重视。为了满足客户满意度和减少配送时间、降低配送成本、提高配送效率，文中在车辆载重限制、时间限制[1]、客户需求量限制和指定地点的条件下，通过节约里程法对配送路线进行了分析和优化。基于节约里程法的物流配送力求以最少的车辆、最短的行驶里程、最少的中间环节、最低的费用高效合理地完成物流网络中所有需求点的货物配送[2]。因此，文中选择了节约里程法作为物流配送路线优化的分析方法。

对比这两种方案，可得出，方案①的配送路线为：A—B—A—C—A，配送距离为：L1=2a+2b；方案②的配送路线为：A—B—C—A，配送距离为：L2=a+b+c。显然，由几何性质可得，方案②优于方案①，S=a+b-c，其中S为节约里程量。

c C c B B

a b a b

A A

图1 节约里程法理解图

C

2.2 节约里程法的步骤

基于节约里程法的基本思路，在配送网络中尽量使运输车辆多载，尽量节约总配送时间和总配送里程。具体步骤如下：

（1）计算各配送点间最短路径，一般可以通过Dijkstra算法得到。

（2）进行节约里程的计算。即两个配送点之间的里程节约里程为这两个配送点分别到配送中心的最短路径之和减去两个配送点之间的距离。

（3）对节约里程进行排序。一般按照节约里程大小的降序排列，得出排序表。

2 节约里程法概述

2.1 节约里程法的基本思路

节约里程法的基本思路如图1，设A为配送中心，B和C为配送点（即客户），A到B或C的距离分别为a、b，两个配送点之间的距离为c。现有两种送货方案，即A向B、C分别送货和A向B、C同时送货。

[3]

（4）形成初始解。在满足车辆限载、客户需求量大小、时间限制等所有条件下，根据第一步所得的最短路径对配送点进行一对一直达式配送，得到所需车辆和行程。

5 E

6 6 7 F 4 G 4 9 H

（5）进行回路的合并[4]

，得出方案优化。从节约里程排序表找出产生该节约里程的两个配送点i、j，再判断连接i、j的回路是否存在合并的可能性。如果一个回路以（p，i）开始，一个回路以（j，p）结束，且满足需求量和车载量等约束条件，则该回路可以合并，并进行下面的合并操作：删除两个回路中的部分路径（i，p）和(p，j)，然后引入新的连接（i，j），得到新的回路（p，…，i，j…，p），。重复此过程，直至没有可以合并的回路，从而得出优化方案。

（6）确定最优方案。重复上一步，并对得出的优化方案进行比较，得出最终优化方案。

3 实例分析

SJ快运有限公司是一家主要从事公路零担货物运输、兼营快递和航空代理服务的民营企业。它以高速公路和国家高等级公路为依托，根据客户需求，发展建成了以上海、天津、广州、武汉、杭州、西安、成都等地为中枢，遍布全国的信息化货运网络，拥有网点1100多个，运输车辆3000多台，其中95%以上是标准箱式货车，长途车约1200余辆、市内配送货车辆1800辆，另外拥有可调配的其它车辆1500余台。

SJ旗下的南昌物流配送中心及各个配送支点如下图2所示，图中数值为各点相距的公里数，一次配送中，要由配送中心A点向其他配送支点进行配送，现有2t和5t的货车可以使用，在这次配送中，B、C、D、E、F、G、H各点的需求量分别是1.9t、2.4t、1.8t、2.2t、2.4t、2.3t、1.9t。具体配送方案如下：

（1）利用最短路径算法，求出各配送节点间的最短距离，计算结果如表一(单位：公里)。

（2）根据表一，计算各配送节点的节约里程，结果见表二(单位：公里)。

D 5 9 C 4 10 12 B 12

6

A 图2 各配送点位置图 表一 各节点间最短距离 A B 6 B C 10 4 C D 12 9 5 D E 16 10 6 5 E F 15 9 7 11 6 F G 15 9 11 15 10 4 G H 12 10 14 19 14 8 4 表二 各节点间节约里程

B C 12 C D 9 17 D E 12 20 23 E F 12 18 16 25 F G 12 14 12 21 26 G H 8 8 5 14 19 23 （3）对节约里程按大小顺序进行降序排列，结果见表三(单位：公里)。

（4）确定初始配送方案，由配送中心按最短路线向各个配送节点分别送货，需要2t车辆3辆和5t车辆4辆，总里程为172公里。

（5）确定优化方案，按照节约里程的大小顺序，连接F—G，由于配载的限制，不能再纳入其他节点，节约26公里；同理，连接D—E，节约23公里；连接B—C，节约12公里；H单独配送，节约0公里。综上，共需2t车辆1辆，5t车辆3辆，共节约里程61公里。

表三 节约里程排序表 序号 连接 节约 序号 连接 节约 1 F--G 26 12 E--H 14 2 E--F 25 13 B--C 12 3 D--E 23 14 B--E 12 4 G--H 23 15 B--F 12 5 E--G 21 16 B--G 12 6 C--E 20 17 D--G 12 7 F--H 19 18 B--D 9 8 C--F 18 19 B--H 8 9 C--D 17 20 C--H 8 10 D--F 16 21 D--H 5 11 C--G 14 （6）再次优化方案，与上一步骤同理，先连接E—F，得出共需2t车辆1辆，5t车辆3辆，共节约里程65公里。

（7）确定最终方案，与上一步骤同理，可得出多组方案，其中65公里为最大节约里程。最终配送路线如图3所示： E

F G

H

D C B

A 图3 最终配送路线图

最终配送路线方案如下：

路线1：A—B—C—E—F—B—A，节约里程25公里；

路线2 ：A—B—G—H—A，节约里程23公里；

路线3：A—B—C—D—A，节约里程

17公里；

路线4：A—B—A，节约里程0公里。 共节约里程65公里，是总里程的37.8%，需要2t的车1辆，5t的车3辆。

4 小结

一方面，文中SJ旗下的南昌物流配送中心一次配送中共节约了总配送里程的37.8%，减少了配送车辆3辆，大大提高了配送效率，降低了物流成本；另一方面，文中的南昌物流配送中心是在周边的，向着同一端进行配送，突破了传统的物流配送中心在最中心的局限，使得节约里程法在实际配送中得到了推广。

参考文献：

[1] 王荣花. 基于节约里程法的快递企业配送线路优化[J]. 管理学家, 2011(05):345-346.

[2] 陈文佳. 节约里程法在生产企业物流配送中的应用[J]. 商业文化（下半月）, 2011(11): 66-66.

[3] 李如姣. “节约里程法”在某物流公司配送中心的实际应用[J]. 科技资讯, 2008(28): 156-158.

[4] 张颖敏. 基于节约里程法的物流配送线路优化与改进研究[J]. 物流科技, 2011(4):

113-115.