物流工程——节约里程法
- 格式：ppt
- 大小：1.33 MB
- 文档页数：29
文档推荐
-
物流工程——节约里程法页数:27
-
物流工程——节约里程法页数:29
-
节约里程法(1)页数:19
-
运输线路优化2---节约里程法页数:28
-
物流节约里程法页数:3
-
运输管理决策--图上作业法与节约里程法.页数:33
-
节约里程法典型实例页数:3
下载文档原格式
合集下载
节约里程法PPT课件
的使用率和周转率。
实施效果
通过节约里程法的应用，共享单 车的调度系统得到了优化，高峰 时段的供不应求问题得到了缓解， 提高了共享单车的服务质量和用
户体验。
06
总结与展望
总结节约里程法的原理与应用
要点一
总结
要点二
应用
节约里程法的原理是基于车辆运输路径优化，通过合理安 排车辆行驶路线，减少车辆空驶和重复行驶的距离，达到 降低运输成本和提高运输效率的目的。在实际应用中，该 方法广泛应用于物流配送、公共交通和共享出行等领域。
节约里程法的应用场景
物流配送路线规划
总结词
节约里程法在物流配送路线规划中，能够优化车辆行驶路径，减少运输成本和 时间。
详细描述
通过计算各需求点之间的距离节约量，选择最佳的配送路线，使得车辆在满足 客户需求的同时，总行驶距离最短，从而达到节约成本和时间的目的。
公共交通路线规划
总结词
节约里程法在公共交通路线规划中， 能够提高线路效率和乘客出行体验。
里程法更注重求解的稳定性。
05
节约里程法的实际案例分 析
某快递公司的配送路线优化
01
02
03
背景介绍
某快递公司面临配送路线 不优化、成本高昂的问题， 需要采用节约里程法进行 配送路线的优化。
解决方案
利用节约里程法，对快递 公司的配送路线进行重新 规划，减少重复行驶和空 驶，提高车辆装载率。
实施效果
低运输成本。
它主要应用于多个发货点之间， 通过合并多个货物装载在同一辆
车上，实现运输效率最大化。
节约里程法的基本思想是通过优 化运输路线，减少车辆空驶和重 复行驶，提高运输效率，降低运
输成本。
适用范围与条件
实施效果
通过节约里程法的应用，共享单 车的调度系统得到了优化，高峰 时段的供不应求问题得到了缓解， 提高了共享单车的服务质量和用
户体验。
06
总结与展望
总结节约里程法的原理与应用
要点一
总结
要点二
应用
节约里程法的原理是基于车辆运输路径优化，通过合理安 排车辆行驶路线，减少车辆空驶和重复行驶的距离，达到 降低运输成本和提高运输效率的目的。在实际应用中，该 方法广泛应用于物流配送、公共交通和共享出行等领域。
节约里程法的应用场景
物流配送路线规划
总结词
节约里程法在物流配送路线规划中，能够优化车辆行驶路径，减少运输成本和 时间。
详细描述
通过计算各需求点之间的距离节约量，选择最佳的配送路线，使得车辆在满足 客户需求的同时，总行驶距离最短，从而达到节约成本和时间的目的。
公共交通路线规划
总结词
节约里程法在公共交通路线规划中， 能够提高线路效率和乘客出行体验。
里程法更注重求解的稳定性。
05
节约里程法的实际案例分 析
某快递公司的配送路线优化
01
02
03
背景介绍
某快递公司面临配送路线 不优化、成本高昂的问题， 需要采用节约里程法进行 配送路线的优化。
解决方案
利用节约里程法，对快递 公司的配送路线进行重新 规划，减少重复行驶和空 驶，提高车辆装载率。
实施效果
低运输成本。
它主要应用于多个发货点之间， 通过合并多个货物装载在同一辆
车上，实现运输效率最大化。
节约里程法的基本思想是通过优 化运输路线，减少车辆空驶和重 复行驶，提高运输效率，降低运
输成本。
适用范围与条件
6.节约里程法用
节约里程表
ABCDEFGHI
A
16 10 3 0 0 0 6 12
B
14 7 2 0 0 0 6
C
11 6 0 0 0 0
D
71 00 0
E
8 00 0
F
60 0
G
60
H
8
I
根据节约里程表中节约里程多少的顺 序，由大到小排列，编制节约里程顺 序表，以便尽量使节约里程最多的点 组合装车配送。
顺位 里程 节约里 顺位 里程 节约里 顺位 里程 节约里
总共节约里程为：362－170=192 或（33+34+16）+（28+21）+（22+18+18）+2=192
例：由配送中心P向A—I等9个用户配送货物。图中 连线上的数字表示公路里程（km）。靠近各用户 括号内的数字，表示各用户对货物的需求量（t）。 配送中心备有2t和4t载重量的汽车，且汽车一次 巡回走行里程不能超过35km，设送到时间均符合 用户要求，求该配送中心的最优送货方案。
根据节约里程排序表和配车（车辆的载重和容积因素）、 车辆行驶里程等约束条件，渐进绘出配送路径：
(0.9)
C
5
(1.2)
4
D
6
B (0.5)
5
(1.6)
E
6
路径A A (1.7)
(1.1)
9 路径B
P
10
F
10
路径C
G
(0.9)
12
7
8
H
6
I (0.6)
(0.9)
• 路径A：4t车，走行32km，载重量3.7t； • 路径B：4t车，走行31km，载重量3.9t； • 路径C：2t车，走行30km，载重量1.8t。
运输的优化求解、运输问题—节约里程法
minz=90x11+70x12+100x13+80x21+65x22+80x23。
1、列运输平衡表
列表时要求表内供销平衡，并将运费标入表内空格。
需
供
B1
B2
B3
A1
x11 90 x12 70 x13 100
供应量 200
A2
x21 80 x22 65 x23 80
250
需求量 100 150
200
250
需求量 100 150
200
450
由于上表中有负检验数，故需继续 进行调整，得新运输方案表。
新运输方案2表
需
供
B1
B2
B3
A1
100 90 100 70
100
A2
80 50 65 200 80
需求量 100
150
200
供应量 200 250 450
对新运输方案表进行检验。
新运输方案2检验表
其需量等于总供量与总需量之差，并设其相应运价为0。这
样，就可以用表上作业法求解产大于销的运输问题。
2、销大于产的运输问题 n m
对于销量大于产量，即 bj ai 的运输问题，必
j 1
i 1
然有一些销地不能得到满足，发生缺货，此时引入虚拟供
应点，并设其相应运价为0。这样，就可以用产销平衡的表
上作业法求解销大于产的运输问题。
450
2、建立初始调运方案
采用最小元素法，即在平衡表中挑取运价最小或
较小的供需点格子尽量优先分配的调运方法。
需
供
B1
A1
0 90
B2
B3
供应量
1、列运输平衡表
列表时要求表内供销平衡，并将运费标入表内空格。
需
供
B1
B2
B3
A1
x11 90 x12 70 x13 100
供应量 200
A2
x21 80 x22 65 x23 80
250
需求量 100 150
200
250
需求量 100 150
200
450
由于上表中有负检验数，故需继续 进行调整，得新运输方案表。
新运输方案2表
需
供
B1
B2
B3
A1
100 90 100 70
100
A2
80 50 65 200 80
需求量 100
150
200
供应量 200 250 450
对新运输方案表进行检验。
新运输方案2检验表
其需量等于总供量与总需量之差，并设其相应运价为0。这
样，就可以用表上作业法求解产大于销的运输问题。
2、销大于产的运输问题 n m
对于销量大于产量，即 bj ai 的运输问题，必
j 1
i 1
然有一些销地不能得到满足，发生缺货，此时引入虚拟供
应点，并设其相应运价为0。这样，就可以用产销平衡的表
上作业法求解销大于产的运输问题。
450
2、建立初始调运方案
采用最小元素法，即在平衡表中挑取运价最小或
较小的供需点格子尽量优先分配的调运方法。
需
供
B1
A1
0 90
B2
B3
供应量
劳动部物流师2级节约里程法
图3-17 配送中心网络图分送式运输是指由一个供应点对多个客户的共同送货。
其基本条件是所有客户的需求量总和不大于一辆车的额定载重量。
送货时，由这一辆车装着所有客户的货物，沿着一条精心选择的最佳线路一次将货物送到各个客户手中，这样既保证按时按量将用户需要的货物及时送到，又节约了车辆，节省了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染。
例：图3-17所示为某配送中心的配送网络，图中P0点为配送中心，P1、P2、P3、P4、P5、P6、P7、P8、P9、P10为配送客户，共10位客户，括号内为配送货物吨数，线路上的数值为道路距离，单位为km。
现配送中心有额定载重量分别为2吨和4吨两种厢式货车可供送货使用，试用节约法设计最佳送货路线。
第一步计算最短距离首先计算网络结点之间的最短距离（可采用最短路求解法）。
计算结果如表3-16所示。
表3-16 最短距离表第二步计算节约里程根据最短距离结果，计算出各客户之间的节约行程，结果见表3-17所示。
表3-17 节约里程表第三步将节约里程进行分类对节约行程按从大到小的顺序排列，如表3-18所示。
表3-18 节约里程排序第四步确定配送线路按节约里程大小顺序，组成线路图。
1、初始方案：如图3-18所示，从配送中心P0分别向各个客户进行配送，对每一客户分别单独派车送货，共有10条配送线路，总行程为148公里，需2吨货车10辆。
2、修正方案1：图3-18 图3-19按照节约行程的由大到小的顺序，连接P1和P2，P1和P10，P2和P3，P3和P4，形成巡回路线P0-P10-P1-P2-P3-P4-P0的配送线路，如图所示，装载货物4吨，这时配送路线总运行距离为109公里，配送线路6条，需4吨货车1辆，需2吨货车5辆，如图3-19所示。
3、修正方案2：按节约里程由大到小的顺序，连接P5和P6，P6和P7，形成巡回路线P0-P5-P6-P7-P0的配送线路，如图所示，装载货物3.5吨，这时配送路线总运行距离为85公里，配送线路4条，需4吨货车2辆， 图3-20 需2吨货车2辆，如图3-20所示。
节约里程法
• 位势法
b
6
c
4
4
2
a
d
3
7 e
第三节 物流配送组织
• 分送式配送是指由一个供应点对多个客户的共同 送货。其基本条件是所有客户的需求量总和不大 于一辆车的额定载质量。送货时，由这一辆车装 着所有客户的货物，沿着一条精心选择的最佳线 路依次将货物送到各个客户手中，这样既保证按 时按量将用户需要的货物及时送到，又节约了文 辆，节省了费用，缓解了交通紧张的压力，并减 少了运输对环境造成的污染。
1
12 0
2
89 0
3
17 8 10 0
4
15 9 8 4 0
5
15 17 9 14 11 0
6
20 23 15 20 16 6 0
7
17 22 13 20 16 5 4 0
8
8 17 9 19 16 11 14 10 0
9
6 18 12 22 20 17 20 16 6 0
10
16 23 14 22 19 9 8 4 8 14 0
第二步，根据最短距离表，利用节约法计算出用
户间的节约里程，并由大到小排列，编制节约里 程顺序表，如表2所示。
ΔL=（La+Lb）－Lab 1—2：L1+L2-L12=12+8-9=11 1—3：L1+L3-L13=12+17-8=21 1—4：L1+L4-L14=12+15-9=18 1—5：L1+L5-L15=12+15-17=10 1—6：L1+L6-L16=12+20-23=9 1—7：L1+L7-L17=12+17-22=7 1—8：L1+L8-L18=12+8-17=3 1—9：L1+L9-L19=12+6-18=0 1—10：L1+L10-L1、10=12+16-23=7 1—11：L1+L11-L1、12=12+21-28=5 1—12：L1+L12-L1、12=12+11-22=1 1—13：L1+L13-L1、13=12+15-27=0
《节约里程法》详解
"节约里程法"英文翻译：节约里程法(Saving Algorithm)内容摘要：节约里程法又称节约算法，是指用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。
什么是节约里程法节约里程法又称节约算法，是指用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。
节约里程法的基本原理节约里程法的基本思路如下图,已知O点为配送中心,它分别向用户A和B送货。
设O点到用户A和用户B的距离分别为a和b。
用户A和用户B之间的距离为c,现有两种送货方案,如图下(a)和(b)所示。
在上图(a)中配送距离为2(a+b)；图上(b)中,配送距离为a+b+c。
对比这两个方案,哪个更合理呢？这就要看哪个配送距离最小,配送距离越小,则说明方案越合理。
由上图(a)中的配送距离,减去图1(b)中的配送距离可得出:2(a+b)－(a+b+c)=(2a+2b)－a－b－c=a+b－c(1)如果把上图(b)看成一个三角形,那么a、b、c则是这个三角形三条边的长度。
由三角形的几何性质可知,三角形中任意两条边的边长之和,大于第三边的边长。
因此,可以认定(1)式中结果是大于零的。
即:a+b－c＞0(2)由(2)式可知,(b)方案优于(a)方案,节约了(a+b-c)的里程,这种分析方案的优劣式的思想,就是节约里程法的基本思想。
、拓展资料：一、节约里程法核心思想节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。
优化过程分为并行方式和串行方式两种。
二、节约里程法示例例:有一配送P具有如图所示的配送网络,其中A-J表示收货站,()内数字表示发送量(吨),路线上的数字表示道路距离(公里)。
问为使行走距离尽量小,应该如何去求配送线路?假设能够利用的车是2吨车(即最大载重量是2吨)和4吨车两种,并限制车辆一次运行的初步距离是30公里。
节约里程法介绍
一、6.车辆的装载技术
车辆合理调度的方法：
经验调度法：在能够保证满载的情况下，优先使用大型车辆，且先 载运大批量的货物。
运输定额比法：车辆的运送能力计算每种车运送不同的定额比。
二、配送路线优化设计方法——节约里程法
二、1.节约里程算法基本原理
• 基本原理是几何学中三角形一边之长必定小于另外两边之和。 • 节约里程法核心思想是依次将运输问题中的两个回路合并为一个回
节约里程法讲解
配送路线设计——节约里程法
一、1.配送路线设计说明
• 随着小批量多批次的及时配送的发展，物流配送费用正在逐年提升， 选择有效的的配送路线，已经成为控制物流成本的主要措施！
• 什么是有效的配送路线？ ✓ 有效的配送路线，实际上是保证货物准时到达客户指定地前提下，尽
可能的减少运输的车次和运输的总路程，在这种思想下，节约里程法 已经成为选择配送路线的主要方法。
二、2.案例分析：
• 例：由配送中心P向A—I等9个用户配送货物。图中连线 上的数字表示公路里程（km）ቤተ መጻሕፍቲ ባይዱ靠近各用户括号内的数 字，表示各用户对货物的需求量（t）。配送中心备有2t 和4t载重量的汽车，且汽车一次巡回走行里程不能超过 35km，设送到时间均符合用户要求，求该配送中心的最 优送货方案。
一、1.配送路线设计说明
通常认为，配送是近距离，小批量，品种比较复杂，按用户需要搭配 品种与数量的服务体系；从配送中心把货物送到所需要的各个用户， 有很多不同的路线选择方案。合理的选择配送路线，对企业和社会具 有很重要的意义： 优化配送路线，可以提高配送效率，对配送车辆做到 物尽其用尽可能的降低配送成本。 可以准时、快速地把货物送到客户的手中，能极大地提高 客 户满意度。 有利于企业提高效益。 对社会而言，它可以节省运输车辆，缓解交通紧张状况，减少噪音、 尾气排放等运输污染，为保护生态平衡、创造美好家园做出贡献。
物流工程节约里程法教学课件讲议
节约里程法
第六步:最终方案的确定。
节约里程法
• 最终修改后的车辆调度结果:
节约里程法
• 通过对比初始方案与最终方案可知,通过优化可节约里程 (1768-1047)=721(公里),节约成本(4476.33384.55)=1091.75(元),仅8家客户的一次配送就节约了物 流配送成本1091.75。
节约里程法
（0.9）
P3
6
（1.4）
P4
7
P0
10
（1.7）
P2
8
8
P5
（2.4）
初始方案: 配送线路5条， 需要车5辆 配送距离=39×2=78KM
P1 (1.5)
节约里程法
• 初始方案: • 配送线路5条， 需要车5辆 • 配送距离: 39×2=78KM
• 优化后的方案: • 2条配送线路，2辆4t车 • 配送距离: 24＋34＝58km
10
16
18
16
12
P5
节约里程法
第2步: 按节约里程公式求得相应的节约里程数
需求量
P0
1.5
8
P1
12
1.7
8
4
13
0.9
6
1
15
1.4
7
0
16
2.4
10
2
如: P0 P1+ P0P2 -
P2
P1P2 =8+8 -12
4
=4
10
P3
9
5
6
8
P4
18
16
12
0
0
5
P5
节约里程法
第 3 步: 将节约里程按从大到小顺序排列
配送路线优化里程节约法
1.满足客户配送需要 2.减少配送车辆使用 3.缓解交通紧张压力
节约里程法(Sa程序法(Vehicle Scheduling Program:VSP) 又称节约算法，是指用来解决运输车辆数目不确定的问题
的最有名的启发式算法。
核心思想: 节约里程法核心思想是依次将运输问题中的两个回路合并
请为百家姓配送中心制定最优的配送方案。
第一步：计算最短距离。根据配送网络中的已知条件， 计算配送中心与客户及客户之间的最短距离，结果见表 11-11。 第二步：计算节约里程sij,结果见表11-12。
第三步：将节约sij,进行分类，按从大到小的顺序排 列，得表11-13
第四步：确定配送线路。从分类表中，按节约里程大小顺序，组成线路图
依次类推： （5-6：8）， （5-4-6：7）， （5-4-3-6：6），最短距离
–配送线路5条， 需要车5辆 求得的最短路径是：1-2-5-4-3-6
距离是：4+2+6=12 图中括号内的数字表示每一家连锁店的需求量（t），线路上的数字表示两节点之间的距离（km）。
–配送距离：39×2=78KM 适用方法——节约里程法
P4
7
P0
10
（1.7）
P2
8
8
P5
（2.4）
初始方案：配送线路5条， 需要车5辆 配送距离=39×2=78KM
P1 (1.5)
第2步：按节约里程公式求得相应的节约里程数 节约行程：a + b－c
节约里程法 例题：已知配送中心P0向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示，配送中心有
3台2t卡车和2台4t两种车辆可供使用。 2、每位客户的送货量都不能满足配送车辆满载。 第四步：确定配送线路。
节约里程法(Sa程序法(Vehicle Scheduling Program:VSP) 又称节约算法，是指用来解决运输车辆数目不确定的问题
的最有名的启发式算法。
核心思想: 节约里程法核心思想是依次将运输问题中的两个回路合并
请为百家姓配送中心制定最优的配送方案。
第一步：计算最短距离。根据配送网络中的已知条件， 计算配送中心与客户及客户之间的最短距离，结果见表 11-11。 第二步：计算节约里程sij,结果见表11-12。
第三步：将节约sij,进行分类，按从大到小的顺序排 列，得表11-13
第四步：确定配送线路。从分类表中，按节约里程大小顺序，组成线路图
依次类推： （5-6：8）， （5-4-6：7）， （5-4-3-6：6），最短距离
–配送线路5条， 需要车5辆 求得的最短路径是：1-2-5-4-3-6
距离是：4+2+6=12 图中括号内的数字表示每一家连锁店的需求量（t），线路上的数字表示两节点之间的距离（km）。
–配送距离：39×2=78KM 适用方法——节约里程法
P4
7
P0
10
（1.7）
P2
8
8
P5
（2.4）
初始方案：配送线路5条， 需要车5辆 配送距离=39×2=78KM
P1 (1.5)
第2步：按节约里程公式求得相应的节约里程数 节约行程：a + b－c
节约里程法 例题：已知配送中心P0向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示，配送中心有
3台2t卡车和2台4t两种车辆可供使用。 2、每位客户的送货量都不能满足配送车辆满载。 第四步：确定配送线路。
节约里程法(Saving Algorithm)
节约里程法(Saving Algorithm)•车辆调度程序法(Vehicle Scheduling Program:VSP)•又称节约算法，是指用来解决运输车辆数目不确定的问题的最有名的启发式算法。
核心思想:•节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。
优化过程分为并行方式和串行方式两种。
节约里程法•利用节约法制定出的配送方案除了使配送总吨公里数最小外，还应满足以下条件：–满足所有用户的需求–不使任何一辆车超载–每辆车每天的总运行时间或行驶里程不超过规定的上限；–用户到货时间要求。
不得超过规定时间。
节约里程法PA（客户）B（客户）ab(配送中心)PA（客户）B（客户）(配送中心)ba c运行距离为：2a+2b运行距离为：a+b+c 节约行程：a + b－c节约里程法例题：已知配送中心P 0向5个用户P j 配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示，配送中心有3台2t卡车和2台4t两种车辆可供使用。
利用节约里程法制定最优的配送方案。
(1.4)P 0P 2P 3P 4P 5P 1( 2.4 )( 0.9 )(1.7）(1.5 )101275124136812168节约里程法•第1 步：作运输里程表，列出配送中心到用户及用户间的最短距离。
需求量P0P11.58P1P21.7812P2P30.96134P3P41.471595P4P52.41016181612P5节约里程法第2步：按节约里程公式求得相应的节约里程数需求量P01.58P11.7812P2 40.96134P3 1101.471595P4 0682.41016181612P5 2005节约里程法第3 步：将节约里程按从大到小顺序排列序号路线节约里程1P2P3102P3P483P2P464P4P555P1P246P1P527P1P318P2P509P3P5010P1P40节约里程法第4步：根据载重量约束与节约里程大小，顺序连接各客户结点,形成二个配送路线.P2P3－P3P4－P2P4－P4P5－P1P2－P1P5－P1P3 －P2P5 －P3P5－P1P4（1.4）P 0P 2P 3P 4P 5P 1（2.4）（0.9）（1.7）(1.5)10768845节约里程法（1.4）P 0P 2P 3P 4P 5P 1（2.4）（0.9）（1.7）(1.5)1078845配送线路1节约里程法（1.4）P 0P 2P 3P 4P 5P 1（2.4）（0.9）（1.7）(1.5)1078845配送线路1配送线路1：运量= 1.7+0.9+1.4= 4t运行距离＝8＋4＋5＋7＝24km用一辆4t 车运送节约距离=18km配送线路2: 运量=2.4+1.5=3.9t<4t 运行距离＝8＋10＋16＝34km 用一辆4t 车运送节约距离=2km节约里程法（1.4）P 0P 2P 3P 4P 5P 1（2.4）（0.9）（1.7）(1.5)107688初始方案：配送线路5条，需要车5辆配送距离=39×2=78KM节约里程法•初始方案：–配送线路5条，需要车5辆–配送距离：39×2=78KM•优化后的方案：–2条配送线路，2辆4t车–配送距离：24＋34＝58km节约里程法案例：•宝洁公司是广州配送中心最大的服务商,为其配送的客户和货量见下表,我们以广州配送中心为例来说明有装载限制的车辆调度的优化方法。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
物流配送——节约里程法(Saving Algorithm)
• 车辆调度程序法(Vehicle Scheduling Program:VSP) • 又称节约算法，是指用来解决运输车辆数目不确定的问题 的最有名的启发式算法。 核心思想: • 节约里程法核心思想是依次将运输问题中的两个回路合并 为一个回路，每次使合并后的总运输距离减小的幅度最大， 直到达到一辆车的装载限制时，再进行下一辆车的优化。 优化过程分为并行方式和串行方式两种。
（0.9）
P3
4
P2
以此类推，如果前面涉及了某些 路线，往后就考虑未涉及的路线 P2P3----P3P4-----P1P5
（1.7）
5
6 8
（1.4）
P4
7
P0
10
8
P5
P1
(1.5)
（2.4）
节约里程法
5
（0.9）
P3
4
P2
（1.7）
配送线路1
（1.4）
P4
8
7
P0
10
8
P5
P1
(1.5)
（2.4）
节约里程法
案例： • 宝洁公司是广州配送中心最大的服务商,为其配送的客户和货量见 下表,我们以广州配送中心为例来说明有装载限制的车辆调度的优 化方法。公司客户分布在全国各地,这里主要以广东省内7家客户 及省外一家特殊客户的一次配送为例。
客户(i) 货运量 (qi) 东莞 江门 4.3 1.8 惠州 0.7 阳江 2.2 汕尾 3.6 揭阳 3.6 汕头 1.6 漳州 2
（2.4）
节约里程法
（0.9）
P3
（1.7）
P2
6 8
（1.4）
P4
7
P0
10
8
P5
P1
(1.5)
（2.4）
初始方案：配送线路5条， 需要车5辆 配送距离=39×2=78KM
节约里程法
• 初始方案： –配送线路5条， 需要车5辆 –配送距离：39×2=78KM • 优化后的方案： –2条配送线路，2辆4t车 –配送距离：24＋34＝58km
P
(配送中心)
b
B（客户）
运行距离为：2a+2b 节约行程：a + b－c
运行距离为：a+b+c
节约里程法
例题：已知配送中心P0向5个用户Pj配送货物，其配送路线网 络、配送中心与用户的距离以及用户之间的距离如下图所 示，配送中心有3台2t卡车和2台4t两种车辆可供使用。利 用节约里程法制定最优的配送方案。 ( 0.9 )
P3
5 6 8 12 4 (1.7）
P2
12 (1.4)P47ຫໍສະໝຸດ P01312
10
8
16
P5
( 2.4 )
P1
(1.5 )
节约里程法
• 第1 步：作运输里程表，列出配送中心到用户 及用户间的最短距离。
需求量 P1 P2 1.5 1.7 0.9 1.4 2.4 P0 8 8 6 7 10 P1 12 13 15 16 P2 4 9 18 P3 5 16 P4 12 P5
练习题
某连锁零售店，下设有一个配送中心P和10个连 锁分店A～J，配送中心和各连锁分店及各连锁分店之 间的位置关系如下图1所示，两点间连线上的数字为
两点间的路线长度（单位：公里）。各连锁分店对某
种商品的需求量见表1，该商品由配送中心统一采购
并进行配送。配送中心备用2t和4t的货车，限定送货
车辆一次巡回距离不超过35公里，设送到时间均符合 用户要求，求配送中心的最优送货方案。
节约里程法
第二步:计算连接城市到同一线路上的距离节约值
节约里程法
第三步:确定初始方案的运输线路及运输费用,现安排4辆2吨、4辆5吨的车给 每个客户送货。运输线路及运输费用见下表所示。
节约里程法
第四步:进行线路第一次优化。
节约里程法
第一次修改后的车辆调度结果：
节约里程法
第五步:继续进行线路优化。
D
C
B
A E
P
J
F
G H
I
图1 配送网络图
表1 各连锁分店需求量
重量单位：吨
分店 A 数量 重量
B
C
D
E
F
G
H
I
J
合计
41
节约里程法
第六步:最终方案的确定。
节约里程法
• 最终修改后的车辆调度结果：
节约里程法
• 通过对比初始方案与最终方案可知,通过优化可节约里程 (1768-1047)=721(公里),节约成本(4476.33384.55)=1091.75(元),仅8家客户的一次配送就节约了物 流配送成本1091.75。
节约里程法
• 利用节约法制定出的配送方案除了使配送总吨公 里数最小外，还应满足以下条件：
– 满足所有用户的需求 –不使任何一辆车超载 –每辆车每天的总运行时间或行驶里程不超过规定的上 限； –用户到货时间要求。不得超过规定时间。
节约里程法
A（客户）
a a c
A（客户）
P
(配送中心) b
B（客户）
第 3 步：将节约里程按从大到小顺序排列 序号 1 路线 P2P3 节约里程 10
2
3
P3P4
P2P4
8
6
4
5 6 7 8 9 10
P4P5
P1P2 P1P5 P1P3 P2P5 P3P5 P1P4
5
4 2 1 0 0 0
节约里程法
第4步：根据载重量约束与节约里程大小，顺序连接各客户 优先考虑节约里程最大的路线， 结点,形成二个配送路线 .
节约里程法
5
（1.4）
P4
（0.9）
P3
4
P2
（1.7）
配送线路1
7
8
P0
10
8
P5
P1
(1.5)
配送线路2: 配送线路1： 运量=2.4+1.5=3.9t<4t 运量 = 1.7+0.9+1.4= 4t 运行距离＝8＋4＋5＋7＝24km 运行距离＝8＋10＋16＝34km 用一辆 4t车运送 用一辆 4t车运送 节约距离 =18km（即2*21-24） 节约距离=2km（即2*18-34）
节约里程法
第二次修改后的车辆调度结果：
节约里程法
节约里程法
• 从表中可以看出,广州-惠州-揭阳-汕头-漳州路线上的 总货运量达到7.9吨,再连接任何一个城市都将使货运量超 过最高限制(8吨),则不能继续配载,所以可以首先确定的 是这一条线路。然后在剩下的东莞、江门、阳江和汕尾重 复以上的优化步骤。得到最终配送计划。
节约里程法
• 广州配送中心为这次配送提供了三种车型,载重量分别为2 吨、5吨和8吨,不同车型的运输单价不一样,具体见运输单 价表。配送中心的配送是由外协商提供车辆,因此汽车的 数量没有限制 • 车辆载重 • 运价(元/公里) 2T 2.4 5T 2.7 8T 3.65
节约里程法
2.步骤 第一步:各城市之间的距离：
P3
P4 P5
节约里程法
第2步：按节约里程公式求得相应的节约里程数
需求量
1.5 1.7
P0
8 8 P1 12 4 13 1 P2 4 10
如：P0 P1+ P0P2 -P1P2 =8+8 -12 =4 P3 5
8 16
0.9 1.4
2.4
6 7
10
15
0 16
9
6 18
P4
12 P5
2
0
0
5
节约里程法
• 车辆调度程序法(Vehicle Scheduling Program:VSP) • 又称节约算法，是指用来解决运输车辆数目不确定的问题 的最有名的启发式算法。 核心思想: • 节约里程法核心思想是依次将运输问题中的两个回路合并 为一个回路，每次使合并后的总运输距离减小的幅度最大， 直到达到一辆车的装载限制时，再进行下一辆车的优化。 优化过程分为并行方式和串行方式两种。
（0.9）
P3
4
P2
以此类推，如果前面涉及了某些 路线，往后就考虑未涉及的路线 P2P3----P3P4-----P1P5
（1.7）
5
6 8
（1.4）
P4
7
P0
10
8
P5
P1
(1.5)
（2.4）
节约里程法
5
（0.9）
P3
4
P2
（1.7）
配送线路1
（1.4）
P4
8
7
P0
10
8
P5
P1
(1.5)
（2.4）
节约里程法
案例： • 宝洁公司是广州配送中心最大的服务商,为其配送的客户和货量见 下表,我们以广州配送中心为例来说明有装载限制的车辆调度的优 化方法。公司客户分布在全国各地,这里主要以广东省内7家客户 及省外一家特殊客户的一次配送为例。
客户(i) 货运量 (qi) 东莞 江门 4.3 1.8 惠州 0.7 阳江 2.2 汕尾 3.6 揭阳 3.6 汕头 1.6 漳州 2
（2.4）
节约里程法
（0.9）
P3
（1.7）
P2
6 8
（1.4）
P4
7
P0
10
8
P5
P1
(1.5)
（2.4）
初始方案：配送线路5条， 需要车5辆 配送距离=39×2=78KM
节约里程法
• 初始方案： –配送线路5条， 需要车5辆 –配送距离：39×2=78KM • 优化后的方案： –2条配送线路，2辆4t车 –配送距离：24＋34＝58km
P
(配送中心)
b
B（客户）
运行距离为：2a+2b 节约行程：a + b－c
运行距离为：a+b+c
节约里程法
例题：已知配送中心P0向5个用户Pj配送货物，其配送路线网 络、配送中心与用户的距离以及用户之间的距离如下图所 示，配送中心有3台2t卡车和2台4t两种车辆可供使用。利 用节约里程法制定最优的配送方案。 ( 0.9 )
P3
5 6 8 12 4 (1.7）
P2
12 (1.4)P47ຫໍສະໝຸດ P01312
10
8
16
P5
( 2.4 )
P1
(1.5 )
节约里程法
• 第1 步：作运输里程表，列出配送中心到用户 及用户间的最短距离。
需求量 P1 P2 1.5 1.7 0.9 1.4 2.4 P0 8 8 6 7 10 P1 12 13 15 16 P2 4 9 18 P3 5 16 P4 12 P5
练习题
某连锁零售店，下设有一个配送中心P和10个连 锁分店A～J，配送中心和各连锁分店及各连锁分店之 间的位置关系如下图1所示，两点间连线上的数字为
两点间的路线长度（单位：公里）。各连锁分店对某
种商品的需求量见表1，该商品由配送中心统一采购
并进行配送。配送中心备用2t和4t的货车，限定送货
车辆一次巡回距离不超过35公里，设送到时间均符合 用户要求，求配送中心的最优送货方案。
节约里程法
第二步:计算连接城市到同一线路上的距离节约值
节约里程法
第三步:确定初始方案的运输线路及运输费用,现安排4辆2吨、4辆5吨的车给 每个客户送货。运输线路及运输费用见下表所示。
节约里程法
第四步:进行线路第一次优化。
节约里程法
第一次修改后的车辆调度结果：
节约里程法
第五步:继续进行线路优化。
D
C
B
A E
P
J
F
G H
I
图1 配送网络图
表1 各连锁分店需求量
重量单位：吨
分店 A 数量 重量
B
C
D
E
F
G
H
I
J
合计
41
节约里程法
第六步:最终方案的确定。
节约里程法
• 最终修改后的车辆调度结果：
节约里程法
• 通过对比初始方案与最终方案可知,通过优化可节约里程 (1768-1047)=721(公里),节约成本(4476.33384.55)=1091.75(元),仅8家客户的一次配送就节约了物 流配送成本1091.75。
节约里程法
• 利用节约法制定出的配送方案除了使配送总吨公 里数最小外，还应满足以下条件：
– 满足所有用户的需求 –不使任何一辆车超载 –每辆车每天的总运行时间或行驶里程不超过规定的上 限； –用户到货时间要求。不得超过规定时间。
节约里程法
A（客户）
a a c
A（客户）
P
(配送中心) b
B（客户）
第 3 步：将节约里程按从大到小顺序排列 序号 1 路线 P2P3 节约里程 10
2
3
P3P4
P2P4
8
6
4
5 6 7 8 9 10
P4P5
P1P2 P1P5 P1P3 P2P5 P3P5 P1P4
5
4 2 1 0 0 0
节约里程法
第4步：根据载重量约束与节约里程大小，顺序连接各客户 优先考虑节约里程最大的路线， 结点,形成二个配送路线 .
节约里程法
5
（1.4）
P4
（0.9）
P3
4
P2
（1.7）
配送线路1
7
8
P0
10
8
P5
P1
(1.5)
配送线路2: 配送线路1： 运量=2.4+1.5=3.9t<4t 运量 = 1.7+0.9+1.4= 4t 运行距离＝8＋4＋5＋7＝24km 运行距离＝8＋10＋16＝34km 用一辆 4t车运送 用一辆 4t车运送 节约距离 =18km（即2*21-24） 节约距离=2km（即2*18-34）
节约里程法
第二次修改后的车辆调度结果：
节约里程法
节约里程法
• 从表中可以看出,广州-惠州-揭阳-汕头-漳州路线上的 总货运量达到7.9吨,再连接任何一个城市都将使货运量超 过最高限制(8吨),则不能继续配载,所以可以首先确定的 是这一条线路。然后在剩下的东莞、江门、阳江和汕尾重 复以上的优化步骤。得到最终配送计划。
节约里程法
• 广州配送中心为这次配送提供了三种车型,载重量分别为2 吨、5吨和8吨,不同车型的运输单价不一样,具体见运输单 价表。配送中心的配送是由外协商提供车辆,因此汽车的 数量没有限制 • 车辆载重 • 运价(元/公里) 2T 2.4 5T 2.7 8T 3.65
节约里程法
2.步骤 第一步:各城市之间的距离：
P3
P4 P5
节约里程法
第2步：按节约里程公式求得相应的节约里程数
需求量
1.5 1.7
P0
8 8 P1 12 4 13 1 P2 4 10
如：P0 P1+ P0P2 -P1P2 =8+8 -12 =4 P3 5
8 16
0.9 1.4
2.4
6 7
10
15
0 16
9
6 18
P4
12 P5
2
0
0
5
节约里程法