天津理工大学中环信息学院2014届本科毕业论文
第四章 海南新伟物流有限公司车辆运输路线优化
4.1 运输路线线路优化方法
4.1.1 节约里程法
1.节约里程法基本思想
节约里程法是知名的启发式算法[3]，用来解决运输配送车辆等数目不确定的问题。节约算法和节约法也是节约里程法的另一种称呼，节约里程法的运用是以配送中心运输情况和配送中心去到每个用户以及每个用户间距离来制定方案，使得总的运输车辆运输的载货吨数和运输公里数最小的配送方案。另外还得去满足如下条件：（1）所有用户需要要求；（2）不能使得任何得一辆车发生超载；（3）用户收到货物时间上的要求；（4）每一辆车每天的运行总时间或者行驶的里程不能超过规定要求的上限。
2.节约里程法应用的步骤
节约里程法应用步骤的基本思路如图4.1，假设A为运输配送中心，B以及C为需要的配送点( 客户) ，A到B或到C的距离分别是a、b。c为B和C两配送点之间距离。现在，可以看出送货方案可以为两种，第一种是A向B向C分别进行送货服务，第二种是A向B向C一起送货。根据这两种方案，做出对比。方案（1）A—B—A—C—A为第一种配送路线方案，计算配送距离是: L1=2a+2b；方案（2）A—B—C—A为第二种配送路线方案，L2=a+b+c是计算配送距离。根据三角形几何性质分析，方案（2）的配送路线优于方案(1)的配送路线，节约的里程量为S,S=a+b-c。如图4.1所示：
BcCBcCbaabA
图4.1 节约里程法理解图
A
Fig.4.1 Saving mileage method to understand chart
15
天津理工大学中环信息学院2014届本科毕业论文
3.节约里程法在运输配送路线优化中应用的步骤
在节约里程法的思路分析上，运用到关于配送的网络上时，以合理的车辆调度，选择线路最短，不超过车辆标准载重尽可能多载重，最优化的节约运输配送时间和里程。步骤如下所示:（1）通过狄克斯特拉(Dijkstra) 算法用来计算最短路径，在每个配送点之间计算。（2）然后开始节约里程法应用计算，计算配送中心分别到两配送地点路径最短的那条路线之和来减去它两之间配送地点最短距离。（3）分析整理节约的里程，然后按数值大到数值小降序，进行排序。（4）得到最初的值，也就是解。最后根据运输配送中心要求、车辆的情况、客户需求、客户所在地等等需要满足的条件，接着根据前面所求出的路径最短来为配送地点直达配送，分析得到需要的车辆、行驶里程进行配送的数据。（5）配送方案优化，合并回路，获得多个优化方案。查看里程排序表，找出i，j这两个产生配送节约里程点，判断i，j连接的回路，是否存在可能合并性。假如一个回路以(p，i) 开始，一个回路以(j，p) 结束，并且满足需求量和车载量等等约束的条件，说明该回路可合并。继续以下合并操作：对这两个回路部分路径(i，p) 、( p，j)进行删掉 ，引入(i，j)这个新的连接 ，得到(p，?，i，j?，p)新回路 。反复上述的操作过程，直至找不到能够和并的回路。得到优化的配送方案。（6）用同样的方式反复之前合并过程，进而得到多个解决的优化方案，得出的优化方案进行详细的分析，在比较后得出最终的最好的优化方案。
4.1.2 对海南新伟物流有限公司进行分析
海南新伟物流有限公司主要在公路中从事货物运输的民营企业。它是在高速公路上或者是国家公路为基础依托，根据客户需求，发展建成了以深圳、广州、湛江、三亚、海口、陵水、琼海等地为中枢的信息化货运网络，公司拥有约1500余辆长途运输车，城市内1200辆配送货车，其它可调配的车辆300多台，公司为客户本着以科学的现代化的优质的运营管理提供运输配送服务。本公司海口物流配送中心配送点的位置如下图4.2 所示，配送图中各点相距的距离数值单位均以公里计。公司运输配送任务中，由运输配送中心海口点（以A点表示）向需要货物的配送支点进行运输配送服务。配送任务中配送中心使用5吨和2吨的货车，运输车辆充分。以下是公司运输配送点：澄迈支点（以B点表示)、屯昌点（以C点表示）、琼海支点（以D点表示）、琼中支点（以E点表示)、白沙支点(以F点表示）、儋州支点（以G点表示）、临高支点（以H点表示），图中距离以公里为单位计，各支点的需求量分别为1.9吨、2.4吨、1.8吨、2.2吨、2.4吨、2.3吨、1.9吨。对于本次配送中现有的配送方案如图4.2，图4.3所示:
16
天津理工大学中环信息学院2014届本科毕业论文
图4.2 配送支点位置图 Fig.4.2 Distribution pivot location map
A（海口）120H(临高)601004090G（儋州）9040706060E(琼中)50C（屯昌）50D（琼海）40120B（澄迈）F(白沙)
图4.3 配送支点配送路线图
Fig.4.3 Delivery fulcrum delivery roadmap
17
天津理工大学中环信息学院2014届本科毕业论文
1.海南新伟物流公司原先运输配送计划
海南新伟物流有限公司此次运输配送中安排的配送方案为由配送中心A点（海口）向其余各个配送点分别送货，需要2吨的车辆3辆，5吨的车辆4辆，总共的配送里程是1720公里。
2.根据运输配送现状运用节约里程法进行计算分析
(1)首先第一步根据运输配送中心与配送支点的实际情况进行分析，然后对通过各节点间的最短距离进行分析( 单位: 公里)，得出各节点的最短距离表如表4.1所示：
表4.1 各节点间最短距离
Table 4.1 Delivery fulcrum delivery roadmap
B C D E F G H
A 60 100 120 160 150 150 120
B 40 90 100 90 90 100
C 50 60 70 110 140
D 50 110 150 190
E 60 100 140
F 40 80
G 40
(2)对各节点的节约里程进行计算( 单位: 公里)，如表4.2所示：
表4.2 各节点约里程表
Table 4.2 Odometer savings between nodes
C D E F G H
B 120 90 120 120 120 80
C 170 200 180 140 80
D 230 160 120 50
18
E 250 210 140
F 260 190
G 230
天津理工大学中环信息学院2014届本科毕业论文
(3)参照表4.2，按节约里程数值大小从大到小排列节约里程数( 单位:公里)如下表4.3所示：
表4.3 节约里程排序表
Table 4.3 Saving Mileage sort table 序号 1 2 3 4 5 6 7 8 9 10 11
连接 F--G E--F D--E G--H E--G C--E F--H C--F C--D D--F C--G 节约 260 250 230 230 210 200 190 180 170 160 140 序号 12 13 14 15 16 17 18 19 20 21 连接 E--H B--C B--E B--F B--G D--G B--D B--H C--H D--H 节约 140 120 120 120 120 120 90 80 80 50 (4)运输配送方案初始确定，由配送中心A点（海口）按照最短的路径分别向配送支点进行运输配送服务，算出需要载重量为5吨的车辆4辆，还需要载重量为2吨的车辆3辆，算出总共需要1720公里配送里程。
(5)对回路进行合并，进行配送优化方案的确定。参照表节约里程排序表，从F点连接到G点，需载重5吨的车辆要1辆，涉及到载重的限制，其他配送支点不能纳入，构成A—B—F—G—B—A的回路，此回路节约里程260公里 ；从D点连接到E点，构成A—B—C—E—D—A回路，需载重5吨的车辆要1辆，此回路节约里程230公里；从B点连接到C点，构成A—B—C—B—A回路，需载重为5吨的车辆要1辆，节约里程120公里；H进行单独的配送，需载重为2吨的车辆要1辆，节约里程0公里。综上，共需2吨车辆1辆，5吨车辆3辆，共节约里程610 公里。
(6)再次进行优化，优化方案同理以上步骤，先连接E点到F点，计算出实际需要载重为2吨车辆要1辆，载重为5吨车辆要3辆，总共节约了650公里里程。
4.2 新伟物流运输配送运输路径优化改进
优化后的方案选择，同理以上步骤，计算出多组优化方案，从中可以看出最大的节约里程为650公里。因而确定运输配送方案最终路线方案为以下三条:第一条路线为:A—B—C—E—F—B—A，里程节约了250公里；第二条路线为:A—B—G—H—A，里程节约了230公里；第三条路线为:A—B—C—D—A，里程节约170公里。共节约里程650公里，
19