物流运输优化与决策
《物流运输组织管理》 王长琼 编著
华中科技大学出版社
*
主要内容
预备知识 运输优化与决策的基本理论
第一节 物流运输服务选择决策
第二节 货物运输调配决策
第三节 物流运输线路的优化
第四节 行车路线及时刻表的制订
第五节 运输工具与货载的最优分配
*
预备知识 运输优化与决策的基本理论
一、物流运输组织、规划的基本原理
二、物流运输的质量
三、物流运输的合理化
*
一、物流运输组织、规划的基本原理
（一）规模经济（economy of scale）
随着装运规模的增长，每单位质量的运输成本呈下降趋势。
通过规模运输还可以获得运价折扣，也使单位货物的运输成本下降。
规模经济使得货物的批量运输显得更加合理。
思考：规模经济存在的原因？
有关的固定费用可以按整批货物的质量分摊。
*
一、物流运输组织、规划的基本原理
（二）距离经济（economy of distance）
指每单位距离的运输成本随距离的增加而减少。距离越长，固定费用分摊后的值越小，使得每单位距离支付的费用越小。
距离经济的合理性类似于规模经济，尤其体现在运输装卸费用上的分摊。
*
二、物流运输的质量
（一）货运质量事故分类
1、重大事故：货损金额在3000元以上的运输质量事故，以及经省级有关部门鉴定为珍贵、尖端、保密物品在运输过程中发生灭失、损坏的事故。
2、大事故：货损金额在500-3000元的货运质量事故。
3、一般事故：货损金额在50-500元的货运质量事故。
4、小事故：货损金额在20-50元的货运质量事故。
货损金额在20元以下的货运质量事故，不作为事故统计上报，但企业要作为内部记录和处理。
*
二、物流运输的质量
（二）货运质量事故考核指标
1、重大货运质量事故次数
2、货运质量事故频率:每完成百万吨公里发生货运质量事故的次数。
*
二、物流运输的质量
（二）货运质量事故考核指标
3、货损率：指运输统计报告期内，发生货运质量事故造成货物损失吨数占货运总吨数的比例。
4、货差率：指运输统计报告期内，发生货运质量事故造成货差货物的吨数占总货运吨数的比例。
*
二、物流运输的质量
（二）货运质量事故考核指标
5、货运质量事故赔偿率:指运输统计报告期内，发生货运质量事故所赔偿的金额占货运总收入金额的比例。
6、完成运量及时率:指运输报告期内，按托运要求时间完成的货运量吨数占完成总货运量吨数的比例。
*
三、物流运输的合理化
（一）合理运输的概念
（二）不合理运输的表现形式
（三）运输合理化的措施
*
三、物流运输的合理化
（一）合理运输的概念
合理运输（Reasonable Transportation）：
是指物品从生产地到消费地的运输过程中，从全局利益出发，力求运输距离短、中间转运少、运输能力省、运输费用低、到达速度快、运输质量高，并充分有效地发挥各种运输工具的作用和运输能力。
运输工具
运输距离
运输环节
运输时间
运输费用
*
三、物流运输的合理化
（二）不合理运输的表现形式
对流运输
迂回运输
重复运输
倒流运输
过远运输
运力选择不当
无效运输
*
甲
乙
丙
丁
为发货地
为收货地
为对流运输流向线
1、对流运输
（二）不合理运输的表现形式
*
甲
乙
丙
丁
戊
表示合理运输
表示不合理运输
2、迂回运输
（二）不合理运输的表现形式
*
甲
乙
丙
（二）不合理运输的表现形式
3、重复运输
*
4、倒流运输
甲
乙
丙
（二）不合理运输的表现形式
*
300km
400km
500km
200km
甲
乙
丙
丁
（二）不合理运输的表现形式
5、过远运输
*
石英砂除杂
（二）不合理运输的表现形式
6、无效运输
*
未考虑各种运输工具的经济技术特点而进行不适当的选择造成的不合理。常见的有以下几种形式：
（1）违反水陆分工使用，弃水走陆的运输。
（2）铁路短途运输。
（3）水运的过近运输。
（二）不合理运输的表现形式
7、运力选择不当
*
三、物流运输的合理化
（三）运输合理化的措施
1、合理选择运输方式
2、合理地选择运输工具
3、合理地进行物资调配
4、优化运输线路
5、提高包装的质量
6、提高车辆装载技术
7、通过流通加工，使运输合理化
*
第一节
物流运输服务选择决策
一、物流运输方式选择的原则
二、基于物流总成本比较的运输方式选择
三、承运人的选择与评价
*
一、物流运输方式选择的原则
（一）安全性原则
（二）及时性原则
（三）准确性原则
（四）经济性原则
*
二、基于物流总成本比较的运输方式选择
【例7-1】某公司欲将产品从位置A的工厂运往位置B的公司
自有仓库，年运量D=700000件，年存货成本为产品价格的
30%。公司希望选择使总成本最小的运输方式。据估计，运
输时间每减少一天，平均库存成本可以减少1%。各种运输服
务方式的有关参数见表7-1。
运输方式
费率R(元/件) 时间T(天) 年运送批次 平均存货量Q/2
铁路
21 10 100000
驮背
14 20 46500
公路
5 20 42000
航空
2 40 20250
表7-1 各种运输方式的基本参数
*
二、基于物流总成本比较的运输方式选择
【例7-1】基于运输成本与库存成本的总成本分析方法：
成本类型
计算公式
铁路运输
驮背运输
公路运输
航空运输
运输成本
RD
70 000
105 000
140 000
980 000
在途库存
ICDT/365
362 466
241 644
86 301
34 521
工厂存货
ICQ/2
900 000
418 500
378 000
182 250
仓库存货
I(C+R)Q/2
903 000
420 593
380 520
190 755
总成本
2 235 466
1 185 737
984 821
1387526
表7-2 各种运输方式成本计算结果
*
三、承运人的选择与评价
（一）影响承运人选择的主要因素
1、运输成本
2、运输时间和运输时间的可靠性
3、可到达性
4、服务能力
5、安全性
*
三、承运人的选择与评价
（二）承运人的评价方法
1、综合因素加权求和法
假设一共有N个评价指标。对于某备选承运商来说，客户可通过统计分析、专家打分或其他信息获取途径，得出该承运商的N个指标（取值）得分情况，分别用X1、X2，…..Xn表示。
则，该承运商的综合得分为：
S=K1×X1+K2×X2+K3×X3+…+Kn×Xn
*
表7-3 承运商评估报告示例
承运人：_____ 时期:_____
最高分
评价标准
承运人
分数
备注
13
满足接货时间表
13
13
满足搬运
10
9
运输时间
9
10
运输时间一致性
7
7
费率
5
3
附加费
1
高的住宅搬运
5
运营比率
3
％增长
4
收益性
3
3
索赔频率
3
3
索赔解决
3
10
账单错误
7
9
跟踪能力
7
11
设备可用性
l
无平台装货卡车
100
总分
72
*
第二节 货物运输调配决策
一、多起讫点间的直达运输
二、存在中间转运的物资调配
三、图上作业法
表上作业法
*
一、多起讫点间的直达运输
对于多点间直达运输问题，描述如下：
图7-1 多点之间的物资运输调拨问题示意图
*
一、多起讫点间的直达运输
销地
产地
B1
B2
…
Bn
产量
A1
x11
x12
…
x1n
a1
A2
x21
x22
…
x2n
a2
…
…
…
…
…
…
Am
xm1
xm2
…
xmn
am
销量
b1
b2
…
bn
运输问题变量表
*
一、多起讫点间的直达运输
（一）产销平衡的运输问题（ai= bj）
1．产销平衡运输问题数学模型
m n
min z= cij xij
i=1 j=1
n
. xij = ai i = 1,2,…,m (1)
j =1
m
xij = bj j = 1,2,…,n (2)
i =1
xij ≥ 0 (i=1,2,…,m; j=1,2,…,n)
*
一、多起讫点间的直达运输
（二）运输问题数学模型的特点
【例】某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
*
解：
产销平衡问题：总产量 = 总销量
设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：
一、多起讫点间的直达运输
*
min f = 6x11+4x12+6x13+6x21+5x22+5x23
. x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
xij≥0 (i=1,2；j=1,2,3）
一、多起讫点间的直达运输
（二）运输问题数学模型的特点
*
1 1 1 0 0 0
0 0 0 1 1 1
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
系数矩阵
一、多起讫点间的直达运输
（二）运输问题数学模型的特点
*
模型系数矩阵特征
1.共有m+n行，分别表示各产地和销地；mn列，分别表示各决策变量；
2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。
对于产销平衡问题：
1、所有结构约束条件都是等式约束；
2、各地产量之和等于销量之和。
一、多起讫点间的直达运输
（二）运输问题数学模型的特点
*
1、确定初始基本可行解（初始调运方案）
① 西北角法
② 最小元素法
③ 沃格尔法（vogel）
2、解的最优性检验（判断是否为最优调运方案）
① 闭回路法
② 位势法（对偶变量法）
3、解的改进
4、重复2、3两步，经有限次调整，得到最优解。
一、多起讫点间的直达运输
（三）用表上作业发求解运输问题的基本步骤
*
销地
产地
B1
B2
B3
B4
产量
A1
16
A2
10
A3
22
销量
8
14
12
14
48
4
12
4
3
11
10
2
8
5
11
9
6
1、确定初始基本可行解—西北角法
8
8
6
4
8
14
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
*
销地
产地
B1
B2
B3
B4
产量
A1
16
A2
10
A3
22
销量
8
14
12
14
48
4
12
4
3
11
10
2
8
5
11
9
6
1、西北角法得到的初始调运方案为：
8
8
6
4
8
14
总运输费用为：372（怎么计算？）
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
*
销地
产地
B1
B2
B3
B4
产量
A1
16
A2
10
A3
22
销量
8
14
12
14
48
4
12
4
3
11
10
2
8
5
11
9
6
1、确定初始基本可行解—最小元素法
8
2
10
14
8
6
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
*
销地
产地
B1
B2
B3
B4
产量
A1
16
A2
10
A3
22
销量
8
14
12
14
48
4
12
4
3
11
10
2
8
5
11
9
6
1、最小元素法得到的初始调运方案为：
8
2
10
14
8
6
总运输费用为：
246
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
*
销地
产地
B1
B2
B3
B4
产量
行罚数
A1
16
A2
10
A3
22
销量
8
14
12
14
48
列罚数
4
12
4
3
11
10
2
8
5
11
9
6
1、确定初始基本可行解—沃格尔（Vogel）法
8
12
4
2
8
14
2
5
1
3
0
1
1
2
1
3
0
1
2
2
1
2
0
1
1
2
7
6
2
0
0
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
*
销地
产地
B1
B2
B3
B4
产量
A1
16
A2
10
A3
22
销量
8
14
12
14
48
4
12
4
3
11
10
2
8
5
11
9
6
1、确定初始基本可行解—沃格尔（Vogel）法
8
12
4
2
8
14
总运输费用为：
244
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
*
2、解的最优性检验--闭回路法
销地
产地
B1
B2
B3
B4
产量
A1
16
A2
10
A3
22
销量
8
14
12
14
48
4
12
4
3
11
10
2
8
5
11
9
6
8
2
10
14
8
6
对最小元素法得到的初始可行解进行检验
+1
-1
+1
-1
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
*
2、解的最优性检验—闭回路法
销地
产地
B1
B2
B3
B4
产量
A1
1
2
16
A2
1
- 1
10
A3
10
12
22
销量
8
14
12
14
48
4
12
4
3
11
10
2
8
5
11
9
6
8
2
10
14
8
6
检验数计算结果
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
*
2、解的最优性检验—位势(对偶变量)法
销地
产地
B1
B2
B3
B4
产量
ui
A1
16
u1
A2
10
u2
A3
22
u3
销量
8
14
12
14
48
vj
v1
v2
v3
v4
4
12
4
3
11
10
2
8
5
11
9
6
8
2
10
14
8
6
① 计算位势
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
(0)
(1)
(-4 )
(2)
(9)
(3)
(10)
*
2、解的最优性检验—位势(对偶变量)法
销地
产地
B1
B2
B3
B4
产量
ui
A1
16
u1(1)
A2
10
u2(0)
A3
22
u3 (-4
销量
8
14
12
14
48
vj
v1 (2)
v2 (9)
v3 (3)
v4 (10)
4
12
4
3
11
10
2
8
5
11
9
6
8
2
10
14
8
6
② 计算检验数
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
1
2
1
10
12
-1
*
3、解的改进
销地
产地
B1
B2
B3
B4
产量
A1
16
A2
10
A3
22
销量
8
14
12
14
48
4
12
4
3
11
10
2
8
5
11
9
6
8
2
10
14
8
6
对最小元素法得到的初始可行解进行改进
+2
-2
-2
+2
总运输费用为：
246+2（-1）=244
（三）用表上作业发求解运输问题的基本步骤
一、多起讫点间的直达运输
*
练习：求解如下运输问题
销地
产地
B1
B2
B3
B4
产量
A1
8
A2
5
A3
5
销量
4
3
5
6
3
12
3
5
1
2
11
6
7
4
9
5
要求：用三种方法求出初始方案，用两种方法对最小元素法得到的初始方案进行检验，如果初始方案不是最优，请调整到最优。
*
1．总产量大于总销量：
则增加一个假想的销地Bn+1，其销量为：
2．总销量大于总产量：
则增加一个假想的产地Am+1，其产量为：
（四）产销不平衡问题
一、多起迄点间的直达运输
*
销地
产地
B1
B2
…
Bn
Bn+1(贮存)
产量
A1
x11
x12
x1n
+1
a1
A2
x21
x22
x2n
+1
a2
…
…
Am
xm1
xm2
xmn
+1
am
销量
b1
b2
b3
bn
ai- bj
c11
c12
c1n
c2n
0
cmn
c22
c21
cn1
cn2
0
0
0
（四）产销不平衡问题
一、多起迄点间的直达运输
*
二、存在中间转运的物资调配
（一）问题描述
图7-2 有中间转运的物资运输调拨问题
*
二、存在中间转运的物资调配
目标函数为：
约束条件为：
（1）配送量生产能力的限制： k=1，2，…，f；
（2）流通中心发送能力的限制： i＝1，2，…，m；
（3）满足零售店需求量： j=1，2，…，n；
（4）变量非负：
（二）数学模型
*
二、存在中间转运的物资调配
[例7-2]某公司生产变压器，一个工厂在A市，每天生产能力为150 ，另一个工厂在B市，每天生产能力为200 。需求点C市和D市的需求量均为130。公司还需要两中间转运站E市和F市进行整合运输。各点间运输单位费用见表7-4。试确定从工厂到需求点的最优路线。
A
B
E
F
C
D
A
0
13
4
6
12
14
B
13
0
7
6
13
12
E
4
7
0
3
8
8
F
6
6
3
0
7
8
C
12
13
8
7
0
17
D
14
12
8
8
17
0
（三）求解方法
表7-4 各点间运输单位费用
*
二、存在中间转运的物资调配
（三）求解方法
1、将运输模型转为简单的运输问题
（1）增加一虚拟的行或列来平衡需求
（2）构造一个包括所有城市（起点、终点和中间点）作为供需点的运输表（包括虚拟列）。
（3）根据表7-5的规则，得到最终运输表
转运问题中
点的性质
在运输表中的
供应值
在运输表中的
需求值
供应点
起始供应+总供应
总供应
转运点
总供应
总供应
需求点
总供应
起始需求+总供应
空 点
0
起始供应－起始需求
需求和供应量确定准则
*
表7-6 最终运输表
A
B
E
F
C
D
空列
供应
A
0
13
4
6
12
14
0
500
B
13
0
7
6
13
12
0
550
E
4
7
0
3
8
8
0
350
F
6
6
3
0
7
8
0
350
C
12
13
8
7
0
17
0
350
D
14
12
8
8
17
0
0
350
需求
350
350
350
350
480
480
90
1490
二、存在中间转运的物资调配
（三）求解方法
2、运用求解产销平衡问题的方法求解
*
表7-7 初始调运方案
A
B
E
F
C
D
空列
供应
A
(350)0
13
4
6
(130)12
14
(20)0
500
B
13
(350)0
7
6
13
(130)12
(70)0
550
E
4
7
(350)0
(0)3
8
8
0
350
F
6
6
3
(350)0
(0)7
8
0
350
C
12
13
8
7
(350)0
17
0
350
D
14
12
8
8
17
(350)0
0
350
需求
350
350
350
350
480
480
90
1490
二、存在中间转运的物资调配
（三）求解方法
*
三、图上作业法
利用表上作业法，可以确定物资的调运方向，即物资调运的发点和收点，但实施运输方案时，还会遇到运输路线的选择问题，即找出使用运力最小的方案：
1、消灭对流运输；
2、消灭迂回运输。
（一）图上作业法要解决的问题
*
回顾一下什么是对流运输？
20
30
30
20
2
4
3
(20)
(20)
(30)
(30)
这是对流
20
30
30
20
2
4
3
(20)
(20)
(30)
(30)
(10)
*
20
60
40
40
2
4
6
3
(20)
(20)
(40)
圈长：圈上每一条边的长度之和（记为 l）
l =15
先用“丢边破圈”方法，得到无圈图，再产生一个没有对流的方案。
内圈长 l内=8
外圈长 l外=4
是最优解码？
称为迂回运输
调整方案：对内圈各流量中最小调运量，进行反向调运
(40)
(20)
(20)
准则：内外圈长都小于圈长的一半的无对流的调运方案
为最优方案
什么又是迂回运输呢？
*
三、图上作业法
（二）交通图
1、交通图的符号
发点用“ ”表示，并将发货量记在里面，收点用“ ”表示，并将收货量记在里面。两点间交通线的长度记在交通线旁边。
2、调运物资的流向图
物资调运的方向（流向）用箭线表示，并把
“ ” 按调运方向画在交通线的旁边，把调运物资的数量记在“ ”的旁边并加上括号。
在交通图成圈时，若运输方向沿逆时针方向，则需将流向“ ”画在圈外，称为外圈流向，反之，若运输方向沿顺时针方向，则需将流向“ ”画在圈内，称为内圈流向，
*
三、图上作业法
1、交通图不含圈
没有对流运输即是最优方案。
方法：作一个没有对流的流向图，即由各端点开始，由外向里，逐步进行各收发点之间的收发平衡。
（三）基本步骤
【例】有某物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7（单位：万吨），运往B1，B2，B3，B4，收量分别为8，1，3，5，收发量是平衡的，它的交通路线如图所示，问应如何调运，才能使运输吨·公里最小。
*
5
2
3
7
8
1
3
5
A1
A2
B1
A3
B2
B3
A4
B4
(5)
(7)
(1)
(2)
(1)
(5)
(2)
【例】
该方案是否到达最优？
三、图上作业法
（三）基本步骤
1、交通图不含圈
*
2、交通图含圈
没有迂回运输即为最优方案
第一步：“去线破圈”（一般去掉长度最长的交通线），作一个没有对流的流向图，形成初始方案。
第二步：检查初始方案是否最优（即有无迂回）。
第三步：若无迂回则为最优方案；如有迂回，进行调整。
第四步：重复上述两步，直至得出最优方案。
三、图上作业法
（三）基本步骤
*
【例】某物资7万吨，由A1、A2、A3发出，发量分别为3，3,1万吨，运往B1、B2、B3、B4四个收货地，收货量分别为2、3、1、1万吨，收发货平衡，交通路线图如下，问应如何调运，才使运输吨公里数最小
三、图上作业法
（三）基本步骤
2、交通图含圈
3
1
3
1
1
3
2
A1
A2
B1
A3
B2
B3
B4
7
5
3
4
4
4
3
2
*
3
1
3
1
1
3
2
A1
A2
B1
A3
B2
B3
B4
7
5
3
4
4
4
3
2
L1
L2
(3)
(1)
(2)
(1)
(1)
【例】
检验该方案是否最优？
三、图上作业法
（三）基本步骤
2、交通图含圈
*
调整L1
3
1
3
1
1
3
2
A1
A2
B1
A3
B2
B3
B4
7
5
3
4
4
4
3
2
L1
L2
(3)
(1)
(1)
(1)
(1)
(2)
(2)
(1)
检验调整后的方案达到最优
三、图上作业法
（三）基本步骤
2、交通图含圈
*
销地
产地
B1
B2
B3
B4
产量
A1
2
1
3
A2
2
1
3
A3
1
1
销量
2
3
1
1
7
最优调运方案
三、图上作业法
（三）基本步骤
2、交通图含圈
*
练习：
20
30
A
30
50
20
70
100
20
60
30
B
C
D
E
F
G
H
I
23
45
23
25
18
13
(20)
(10)
(50)
(20)
(80)
(60)
(20)
(30)
判断该方案是否达到最优？
三、图上作业法
（三）基本步骤
2、交通图含圈
*
20
30
A
30
50
20
70
100
20
60
30
B
C
D
E
F
G
H
I
23
45
23
25
18
13
(20)
(10)
(50)
(20)
(80)
(60)
(20)
(30)
调整初始方案
(30)
(40)
(10)
(20)
(30)
三、图上作业法
（三）基本步骤
2、交通图含圈
练习：
*
P
Q
M
N
供应量
A
65
80
800
B
180
220
1500
C
90
75
1700
D
60
70
1000
需求量
1300
1000
1600
1100
5000
练习：设有物料X，发运点有A、B、C、D等四处，接收点P、Q、M、N等四处，其距离及其供需量如下表所示，请用交通图求最优的调运路线（注;调运线路呈圈状）
*
第三节 物流运输线路的优化
一、起迄点不同的单一路线优化
二、起迄点重合的单一路线优化
*
一、起迄点不同的单一路线优化
归结为运筹学中的最短路径问题
图7-3 从起点到终点的运输网络图
A
B1
B2
B3
C1
C2
C3
D1
D2
E
3
5
4
1
5
8
4
6
4
2
4
6
9
7
5
1
2
4
2
*
（一）动态规划法（逆序递推）
图7-4 多阶段划分
一、起迄点不同的单一路线优化
A
B1
B2
B3
C1
C2
C3
D1
D2
E
3
5
4
1
5
8
4
6
4
2
4
6
9
7
5
1
2
n=4
n=3
n=2
n=1
4
2
*
（二）标号法（Dijkstra方法）
[例7-3]
图7-5 运输网络图
一、起迄点不同的单一路线优化
*
表7-8 Dijkstra算法步骤表
步骤
P标号点
与P点直接相连的T标号点
相应的总距离
第n个
最近点
最小总距离
最新连接
1
O
A
2
A
2
OA
2
O
A
C
B
4
2+2=4
C
B
4
4
OC
AB
3
A
B
C
D
E
E
2+7=9
4+3=7
4+4=8
E
7
BE
4
A
B
E
D
D
D
2+7=9
4+4=8
7+1=8
D
D
8
8
BD
ED
5
D
E
T
T
8+5=13
7+7=14
T
13
DT
*
二、起迄点重合的单一路线优化
（一）旅行商问题（TSP）模型
1、问题描述
图7-6 TSP问题示意图
变量矩阵
代价矩阵Cij
0-1整数规划模型
*
二、起迄点重合的单一路线优化
（一）旅行商问题（TSP）模型
2、解决办法
枚举、分支定界、现代优化方法（遗传算法等）启发式算法。
贪婪算法：
① 选择距离出发点最近的顾客位置；
② 再从剩下的位置中选距离已选择的位置最近的顾客位置。
③ 如果所有位置都被选择了，则停止，否则返回②。
*
（二）中国邮递员问题
预备知识：图论的相关概念
“顶点”表示某对象节点（设施地点或企业单位）。
“边”表示对象之间的某种特性（如距离）。
边上的非负数字称为“权”。
以V为顶点的边的数目称为顶点V的“次”。
次为奇数的点，称为奇点；次为偶数的点，称为偶点。
由点、边交替构成的序列称为“链”；起点与终点相同的链就称为“圈”。
二、起迄点重合的单一路线优化
*
（二）中国邮递员问题
预备知识：图论的相关概念
二、起迄点重合的单一路线优化
图7-7 连通网络图（欧拉图）
若一个圈中没有重复的边，这个圈就是欧拉圈；若一个图中含有欧拉圈，此图就是欧拉图。当且仅当图中每一个顶点都是偶点时，一个图才是欧拉图(能一笔画)
*
（二）中国邮递员问题
1．确定可行方案（如果有奇点存在 ）
二、起迄点重合的单一路线优化
图7-8 街道图
图7-9 加重复边后的街道图（可行方案）
*
（二）中国邮递员问题
2．判断最优方案（两条标准）
（1）图的每一边上最多有一条重复边；
（2）图中每个圈上重复边的总权不大于该圈总权的一半。
二、起迄点重合的单一路线优化
（a）调整方案一
（b）调整方案二
（c）调整方案三（最佳方案）
*
第四节 行车路线及时刻表的制定
一、运输路线及时刻表制订的原则
二、行车路线制订的扫描法
三、行车路线制订的节约法
*
一、运输路线及时刻表制订的原则
1．同一车辆服务的客户按距离聚类
图7-11 合理的车辆分派方案
图7-12 不合理的车辆分派方案
*
2．避免行车路线交叉
3．尽可能使用大载重量车辆，减少出车数量
4．取货/送货混合安排
5．从距仓库最远的站点开始设计线路
图7-13 合理与不合理的行车线路
一、运输路线及时刻表制订的原则
*
二、行车路线制订的扫描法
1、基本原理
先以仓库(物流中心)为原点，将所有需求点的极坐标算出，然后依角度大小以逆时针或顺时针方向扫描，若满足车辆装载量即划分为一群，将所有点扫描完毕后在每个群内用最短路径法求出车辆最佳行驶路径。
2、基本步骤
第一步：求出各客户点的极坐标。
第二步：扫描划分客户群。
第三步：确定每辆车的最佳路径（TSP算法 ）。
*
二、行车路线制订的扫描法
【例7-4】某运输公司为其客户企业提供取货服务，货物运回仓库集中后，将以更大的批量进行长途运输。所有取货任务均由载重量为10吨的货车完成。现在有13家客户有取货要求，各客户的去货量、客户的地理位置坐标见表7-10。运输公司仓库的坐标为（，）。要求合理安排车辆，并确定各车辆行驶路线，使总运输里程最短。
客户
1
2
3
4
5
6
7
8
9
10
11
12
13
Di(吨)
2
3
Xi
Yi
表7-10 客户数据信息
*
图7-14 客户位置及扫描法求出的结果
二、行车路线制订的扫描法
*
三、行车路线制订的节约法
基本思想：如果将运输问题中的两个回路合并成一个回路，就可缩短线路总里程（即节约了距离），并减少了一辆卡车。
图7-15 节约法的图形描述
*
【例7-5】某配送中心要为13个客户提供配送服务，配送中心的位置、客户的坐标及客户的订单规模见表7-11。配送中心共有4辆卡车，每辆车的载重量是200件。
由于送货成本与车辆行驶总里程之间密切相关，公司经理希望获得总行驶距离最短的方案。如何分配客户？如何确定车辆行驶路径？
三、行车路线制订的节约法
*
表7-11 客户坐标及订单规模
站点
X坐标
Y坐标
订单规模（件）
配送中心
顾客1
顾客2
顾客3
顾客4
顾客5
顾客6
顾客7
顾客8
顾客9
顾客10
顾客11
顾客12
顾客13
0
0
6
7
9
15
20
17
7
1
15
20
7
2
0
12
5
15
12
3
0
-2
-4
-6
-6
-7
-9
-15
48
36
43
92
57
16
56
30
57
47
91
55
38
三、行车路线制订的节约法
*
1．确定距离方阵
配送
中心
客户
1
客户
2
客户
3
客户
4
客户
5
客户
6
客户
7
客户
8
客户
9
客户
10
客户
11
客户
12
客户
13
客户1
客户2
客户3
客户4
客户5
客户6
客户7
客户8
客户9
客户10
客户11
客户12
客户13
12
8
17
15
15
20
17
8
6
16
21
11
15
0
9
8
9
17
23
22
17
18
23
28
22
27
0
10
8
9
15
13
9
12
14
18
14
20
0
4
14
20
20
19
22
22
26
24
30
0
11
16
16
16
20
19
22
21
28
0
6
5
11
17
9
11
14
22
0
4
14
20
8
7
16
23
0
10
16
4
6
12
20
0
6
8
13
5
12
0
14
19
7
9
0
5
9
16
0
13
20
0
8
0
三、行车路线制订的节约法
表7-12 客户及配送中心之间的距离
*
2．计算节约矩阵
客户
1
客户
2
客户
3
客户
4
客户
5
客户
6
客户
7
客户
8
客户
9
客户
10
客户
11
客户
12
客户
13
客户1
客户2
客户3
客户4
客户5
客户6
客户7
客户8
客户9
客户10
客户11
客户12
客户13
0
11
21
18
10
9
7
3
0
5
5
1
0
0
15
15
14
13
12
7
2
10
11
5
3
0
28
18
17
14
6
1
11
12
4
2
0
19
19
16
7
1
12
14
5
2
0
29
27
12
4
22
25
12
8
0
33
14
6
28
34
15
12
0
15
7
29
32
16
12
0
8
16
16
14
11
0
8
8
10
12
0
32
18
15
0
19
16
0
18
0
三、行车路线制订的节约法
表7-13 第一次计算的节约矩阵
*
3．将客户划归到不同的运输路线
线路
客户
1
客户
2
客户
3
客户
4
客户
5
客户
6
客户
7
客户
8
客户
9
客户
10
客户
11
客户
12
客户
13
客户1
客户2
客户3
客户4
客户5
客户6
客户7
客户8
客户9
客户10
客户11
客户12
客户13
1
2
3
4
5
6
7
8
9
10
6
12
13
0
11
21
18
10
9
7
3
0
5
5
1
0
0
15
15
14
13
12
7
2
10
11
5
3
0
28
18
17
14
6
1
11
12
4
2
0
19
19
16
7
1
12
14
5
2
0
29
27
12
4
22
25
12
8
0
33
14
6
28
34
15
12
0
15
7
29
32
16
12
0
8
16
16
14
11
0
8
8
10
12
0
32
18
15
0
19
16
0
18
0
三、行车路线制订的节约法
表7-14 第一次改进后的节约矩阵
*
表7-15第二次改进后的节约矩阵
线路
客户
1
客户
2
客户
3
客户
4
客户
5
客户
6
客户
7
客户
8
客户
9
客户
10
客户
11
客户
12
客户
13
客户1
客户2
客户3
客户4
客户5
客户6
客户7
客户8
客户9
客户10
客户11
客户12
客户13
1
2
3
4
5
6
6
8
9
10
6
12
13
0
11
21
18
10
9
7
3
0
5
5
1
0
0
15
15
14
13
12
7
2
10
11
5
3
0
28
18
17
14
6
1
11
12
4
2
0
19
19
16
7
1
12
14
5
2
0
29
27
12
4
22
25
12
8
0
33
14
6
28
34
15
12
0
15
7
29
32
16
12
0
8
16
16
14
11
0
8
8
10
12
0
32
18
15
0
19
16
0
18
0
三、行车路线制订的节约法
*
表7-16 第三次改进后的节约矩阵
线路
客户
1
客户
2
客户
3
客户
4
客户
5
客户
6
客户
7
客户
8
客户
9
客户
10
客户
11
客户
12
客户
13
客户1
客户2
客户3
客户4
客户5
客户6
客户7
客户8
客户9
客户10
客户11
客户12
客户13
1
2
3
3
5
6
6
8
9
10
6
12
13
0
11
21
18
10
9
7
3
0
5
5
1
0
0
15
15
14
13
12
7
2
10
11
5
3
0
28
18
17
14
6
1
11
12
4
2
0
19
19
16
7
1
12
14
5
2
0
29
27
12
4
22
25
12
8
0
33
14
6
28
34
15
12
0
15
7
29
32
16
12
0
8
16
16
14
11
0
8
8
10
12
0
32
18
15
0
19
16
0
18
0
三、行车路线制订的节约法
*
图7-16 配送中心送货线路规划方案
三、行车路线制订的节约法
*
第五节 运输工具与货载的最优分配
一、航线配船优化问题
二、多车多品种货载配车优化
*
一、航线配船优化问题
（一）问题概述
设船公司经营n条航线。第j条航线上规划期正向货运量预测为Qj，公司拥有装载能力分别为Ni的m种船型；i型船的船舶艘数为mi，一艘i型船在j航线上规划期可以完成的最大往返航次数为nij；一艘i型船在j航线上完成一个往返航次所花费的全部成本为kij。要求将这些船合理地安排在这几条航线上，使公司的经济效益最好。
*
一、航线配船优化问题
（二）数学模型的建立
1．参数说明
I ——船型编号，i=1,2，…，m；
J ——航线编号，j=1,2，…，n；
Xij ——i型船在j航线上每季度完成的往返航次数，是决策变量；
Yj ——j航线上未被船舶承运的货物量，也是决策变量；
Kij ——每艘i型船在j航线上完成一个往返航次所花费的运营成本；
——j航线上单位货物未被承运产生的费用损失；
——每艘i型船在j航线上每季度可以完成的最大往返航次数；
——i型船的集装箱装载能力；
——i型船的船舶数量；
——j航线的正向运量。
*
一、航线配船优化问题
（二）数学模型的建立
2．目标函数
3．约束条件
*
一、航线配船优化问题
（三）航线配船优化举例
【例7-6】假设某船公司拥有3种吨位的集装箱船舶共30搜，分别是1500TEU的8艘、850TEU的12艘、500TEU的10艘。现开辟班轮航线6条，各航线季度集装箱运输量、船舶在每条航线每季度最多能完成的航次数、每艘船在各航线每往返航次的成本（万元）以及每条航线发现的机会成本（万元/TEU）如表7-17至表7-19所示。求不同航线的船舶最佳配置方案。
*
一、航线配船优化问题
（三）航线配船优化举例
1
2
3
4
5
6
Ⅰ型船（1500TEU），8艘
2
3
2
3
1
2
Ⅱ型船（850TEU），12艘
3
4
3
4
2
3
Ⅲ型船（500TEU），10艘
4
4
4
5
2
1
航线
船型
季节最大航次数
1
2
3
4
5
6
Ⅰ型船（1500TEU），8艘
30
25
28
25
35
32
Ⅱ型船（850TEU），12艘
24
24
25
24
30
28
Ⅲ型船（500TEU），10艘
18
20
23
32
航线
船型
单船单航次成本
（万USD）
表7-17 某船公司船型及航线与航次
表7-18 不同航线和船型的营运成本
*
表7-19不同航线的运量和机会成本
航线
1
2
3
4
5
6
机会成本（万USD/TEU）
运量（TEU）
6000
8000
5000
4500
3000
7000
一、航线配船优化问题
（三）航线配船优化举例
*
解：（1）目标函数：
一、航线配船优化问题
*
解：（2）约束条件：
一、航线配船优化问题
*
解：（3）求解结果
1
2
3
4
5
6
Ⅰ型船（1500TEU），8艘
0
0
3
2
2
4
Ⅱ型船（850TEU），12艘
7
0
0
0
0
1
Ⅲ型船（500TEU），10艘
0
1
1
4
0
0
航线
船型
航次数
一、航线配船优化问题
*
二、多车多品种货载配车优化
（一）问题描述
已知有m辆零担作业车，其载重量和容积分别为G1，G2，…，Gm和V1，V2，…，Vm。现有n批货物H1，H2，…，Hn，其重量和体积分别为g1，g2，…，gn和v1，v2，…，vn。
试确定一个零担货物的装车计划，使各车厢的载重能力和装载空间浪费最少，即如何用最少的车辆完成所要求的货运量。
*
二、多车多品种货载配车优化
（二）模型建立
1．变量及参数说明
i——货物编号，i=1，2，…，n；
j——车连编号，j=1，2，…，m。
xij——0-1变量，当货物i装入车辆j时取值1，否则取值0；
yi——0-1变量，当车辆j装货物时取值1，否则取值0。
Gi——车辆j的载重能力；
Vj——车辆j的有效容积；
gi——货物i的重量；
vi——货物i的体积。
*
二、多车多品种货载配车优化
（二）模型建立
2．目标函数
3．约束条件
（1）每辆车的载重能力限制：
（2）每辆车的容积限制：
（3）每一批货物最多只能装入一辆车：
（4）变量约束：
*
（三）启发式方法求解算例
【例7-7】A物流公司为机电市场采用直送方式送货，现有相同车型的待装车辆5辆，要对14种货物进行配装。每辆车的额定体积为10m3，额定载重为6t，各种货物的体积和重量见表7-21。试确定合理的货物配车方案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vi(m3)
3
2
gi(t)
3
1
2
1
2
1
2
1
二、多车多品种货载配车优化
表7-20 货物信息表
*
（三）启发式方法求解算例
1．其求解思路
根据各种货物的容重比，运用反聚类的思想对货物容重之间距离进行计算，分析货物之间差距大小与车辆容重，比较是否需要对其中某些货物进行组合，看成新的货物集，然后采用启发式算法，先装大件货物，再比较车辆剩余容重与货物容重差距后依次装载货物，从而得到最优方案。
2．求解步骤
第一阶段：货物聚类
（1）将每批货物看成是一类,记做G1,G2,…,Gn。计算其对应货物的容重比ci=vi/gi。
二、多车多品种货载配车优化
*
（三）启发式方法求解算例
（2）确定每批货物之间的距离dij， 。计算出n种货物间容重比距离dij(i,j=1, 2, …, n)，得到货物距离关系表记作 D(0)，见表7-21。
ci
dij
cj
G1
G2
G3
G4
G5
G6
G7
G8
G9
G10
G11
G12
G13
G14
5
4
G1
0
G2
0
G3
0
G4
5
0
G5
0
G6
0
G7
2
0
G8
4
1
0
G9
1
0
G10
3
0
G11
2
0
G12
1
2
0
G13
0
G14
3
2
0
表7-21 货物距离关系表D(0)
*
（三）启发式方法求解算例
（3）比较D(0)中的每个非零元素dij，如果任意dij小于临界值C则停止。如果存在某个dij大于C则继续下一步。
（4）把距离最大的两批货物合并成一个新类，记做Gn+1，取消原来的两个类，若存在多个这样的类，则同时合并。
（5）重新计算各类之间的距离，得到降一阶的新距离矩阵D(1)，见表7-22。
G1
G2
G5
G6
G7
G8
G9
G10
G11
G12
G13
G14
G15
G1
0
G2
0
G5
0
G6
0
G7
2
0
G8
0
G9
1
0
G10
0
G11
2
0
G12
2
0
G13
0
G14
3
2
0
G15(3,4)
1
1
0
表7-22 货物距离关系表D(1)
*
（三）启发式方法求解算例
（6）对D(1)重复步骤（4）-（5），直到所有dij小于临界值C为止。得表7-23所示的货物距离关系表。
G7
G9
G11
G16
G17
G18
G19
G20
G7
0
G9
0
G11
0
G16(8,14)
0
G17(1,2)
0
G18(6,13)
1
0
G19(3,4,5)
0
G20(10,12)
0
表7-23 货物距离关系表D（1）
*
（三）启发式方法求解算例
货物编号
聚类名称
货物品种
vi(m3)
gi(t)
ci
i1
19
3,4,5
i2
17
1,2
6
4
i3
20
10,12
3
i4
18
6,13
3
i5
16
8,14
i6
11
11
i7
9
9
2
i8
7
7
（7）对货物进行聚类分组得到新的待装货物，见表7-24。
表7-24 新待装货物信息表
*
（三）启发式方法求解算例
第二阶段：货物配装
对聚类后的新货物进行装载，得到最终装载方案，如表7-25。
车辆编号
货物编号
聚类名称
货物品种
重量（t）
体积（m3）
1
i1
19
3,4,5
2
i2, i7, i8
17,7,9
1,2,7,9
3
i3, i6
11,20
10,11,12
10
4
i4, i5
16,18
6,13,8,14
表7-25 配装方案表
*
本章小结
一、运输优化与决策的基本理论
物流运输组织、规划的基本原理；物流运输的质量；物流运输的合理化
二、物流运输服务选择决策
运输方式的选择、承运商的选择
三、货物运输调配决策
表上作业法、图上作业发
四、物流运输线路的优化
起讫点不同（动态规划法、标号法）；
起讫点相同（奇偶点图上作业法）
五、行车路线及时刻表的制订（扫描法、节约法）
六、运输工具与载货的最优分配
航线配船、货载配车
LD-CED与Cross-Docking作业
LD-CED and Cross-Docking
1
2
3
4
1
2
3
1
2
3
4
1
1
2
A1
B1
C1
A2
B2
A3
C2
A4
C3
D1
E1
B3
C4
E2
客户1
客户2
客户3
客户4
客户5
制造商1
制造商2
制造商3
商品A,50
商品B,40
商品C,100
商品D,10
商品E,40
制造商送货到配送中心
Delivering to DC
分拣
Sorting
拣选
Picking
送货到客户
Delivering to User
组配
Assembling
商品
按制造商+商品名排序
商品
按客户+商品名排序
对商品按排序关键字
进行交换作业：分拣→拣选
首先，制造商根据配送中心订货将货物送到配送中心，各制造商送到配送中心的货物是按照“制造商名+商品名”排序的，为了将同时送来的大量商品按照“分区分类、货位编号”的原则暂时储存，配送中心需要进行分拣，即将商品按照不同的储存区域和货位分开，以便暂时储存，这是“分”的过程；
其次，客户向配送中心下的订单是以“客户名+商品名”排序的，所以，配送中心首先应该根据各个客户的订单要求，从不同的货位上将不同的商品拣出，以便进行组配和装车，这是“合”的过程。通过这样“一分一合”，就实现了“E”，即“交换”，这个作业时配送中心最具有增值功能的作业，应该尽量提高效率。
*
1、对流运输
是指同类的或可以互相代替的货物的相向运输，它是不合理运输最突出、最普遍的一种。主要有两种表现形式：
（1）明显对流
（2）是隐蔽对流
派生形式：倒流运输，即同一批货物或同批中的一部分货物，由发运站至目的站后，又从目的站往发运站方向运输
不经过最短路径的绕道运输，“近路不走走远路”。
3、重复运输--出现不必要的中转
指同一批货物由产地运抵目的地，没经任何加工和必要的作业，也不是为联运及中转需要，又重新装运到别处的现象。
重复运输是因物流仓库设置不当或计划不周使其在中途卸下，导致增加运输环节、浪费运输设备和装卸搬运能力，延长运输时间的不合理运输方式。
4、倒流运输
指同一批货物或同一批中的部分货物，由始发站运往目的站，又从目的站往始发站方向运输。
5、过远运输
指凡是可以从附近取得所需物资的供应而不去就近组织，相反却从相反的地方运来，从而造成不必要的浪费，即在相同条件下舍近求远的物品运输方式。
6、无效运输
运输货物中含有较多杂质，使运力浪费于不必要物资的运输。
1、提高运输工具的实载率
2、减少动力投人，增加运输能力
3、发展社会化的运输体系
4、开展中短距离铁路公路分流，“以公代铁”的运输
5、尽量发展直达运输
6、配载运输
7、“四就”直拨运输
8、发展特殊运输技术和运输工具
9、通过流通加工，使运输合理化
