车辆调度方法
首先,向北画一条直线,进行逆时针方向“扫描”。这些都是随机 决定的。逆时针旋转该直线,直到装载的货物能装上一辆载重10000件 的卡车,同时又不超载。一旦所有的站点都分派有车辆,就可以利用 “水滴”法安排经过各站点的顺序,图 (b)是所列出的最终的路线设计。
34 图 扫描法设计行车路线
1000
4000
车辆调度方法
图上作业法
——物资调拨
图上作业法
图上作业法的原则可以归纳为: 流向划右方,对流不应当; 里圈、外圈分别算,要求不能过半圈长; 如若超过半圈长,应去运量最小段; 反复运算可得最优方案。
1.运输线路不成圈的图上作业法
对于运输线路不成圈的流向图,只要不出现对流现象,就
是最优调运方案。
2.运输线路成圈的图上作业法
第一步 作出初始方案
A (36) B (23)
C (13)
D
+20 -30
-50
+20
(18)
E
(45)
F
-20
G (29)
I (23) H
(25)
+100
-70
-30
+60
A
B 30
C 20
D
+20 -30
-50
+20
60
E
20
80 F
-20
I 10 -30
H
G
+60 50
9
4
K
0C
8)以B为初始结点,计算与之
相连的点的位势值;
11
6
11 B
9)从剩余位势中选出最小者,
10
D6
标注箭头和位势值;
5
12
6
11 E 14
G
7 17 A
8
4 11
9
11 F 15 10)以F为初始结点,计算与之
相连的点的位势值;
H
10
7
I
10
11)从剩余位势中选出最小者,
标注箭头和位势值; J
调整方案 1 4
甲圈 3
2
乙圈
2
6 7
甲圈: 半圈长=7+2+3+6+4+3/2=12.5公里 外圈长=4+7=11公里 里圈长=2+3+3=8公里
乙圈: 半圈长=4+4+5+8/2=10.5公里 外圈长=8公里 里圈长=4+5=9公里
练习
最短路径问题
例1 多阶段决策法
下图表示从起点A到终点E之间各点的距离。求A到E的 最短路径。
(3)排定各路线上每个站点的顺序使行车距离最短。排序时可以使用 “水滴”法或求解“流动推销员”问题的任何算法。
33
例 某公司用厢式货车从货主处取货,图 (a)是一天的取货量,单位是 件。厢式货车的载货量是10000件。完成所有取货任务需一天时间。公 司需要多少条运输路线(即多少部车),每条路线上应该经过哪些站点, 每条路线上的站点怎样排序。
在超过全圈总长1/2 的里(外)圈各段流向线上减去最小运 量,然后在相反方向的外(里)圈流向线上和原来没有流向线 的各段上,加上减去的最小运量,这样可以得到一个新的线路 流向图,然后转到第二步检查有无迂回现象。如此反复,直到 得到最优线路流向图为止。
如果全圈存在两个及两个以上的圈,则需分别对各圈进行是 否存在迂回线路的检查,如果各圈的里、外圈都不超过全圈总 线长的1/2 ,则不存在迂回现象,此方案为最优运输方案。
19
第二阶段:有4个始点B1,B2,B3,B4,终点有C1,C2,C3。对始点和终点进行 分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题:
表3 阶段2
本阶段始点
本阶段各终点(决策)
(状态)
C1
C2
C3
B1
2+12=14 1+11=12 6+11=17
B2
4+12=16 7+11=18 2+11=13
2
48 B3 3 14
75 1
B4 12
12
C1 8 6
11 7
C
2
5
1
C3 6 11
10
D1 10
0
E
D2 6 6
22
练习
计算V1到V7的最短距离
例2 位势法
C
计算C——K的最短路
11
6
1)取VC=0;
B 6
10
D
2)确定与C点相连的结点位势;
5
12
E 14
G
7
4
11
11
A
F
8
9
H
10
7
I
10
本阶段始点 (状态)
C1 C2 C3
阶段3
本阶段各终点(决策)
D1 8+10=18
D2 6+6=12
7+10=17
5+6=11
1+10=11
6+6=12
到E的最短距离
12 11 11
本阶段最优终点 (最优决策)
D2 D2 D1
分析得知:如果经过C1,则最短路为C1-D2-E; 如果经过C2,则最短路为C2-D2-E; 如果经过C3,则最短路为C3-D1-E。
4
A
3
3 2
2 B1
1 6
4 B2 7
2
48 B3 3
75 1
4
C1
8
6
7 C2 5
1 6
C3
D1
10
E
D2
6
讨论:
1、以上求从A到E的最短路径问题,可以转化为四个性质完全相同,但规 模较小的子问题,即分别从Di 、Ci、Bi、A到E的最短路径问题。 最优化原理的应用:从最短路上的每一点到终点的部分道路,也一定是 从该点到终点的最短路。
31
简化的原则:
(1)安排车辆负责相互距离最接近的站点的货物运输。
(2)安排车辆各日途经站点时,应注意使站点群更加紧凑。如果一周 内各日服务的站点不同,就应该对一周内每天的路线和时刻表问题分别 进行站点群划分。各日站点群的划分应避免重叠。
(3)从距仓库最远的站点开始设计路线
(4)卡车的行车路线应呈水滴状。
里圈长=23+36=59公里
全圈长=45+23+25+18+23+36=170公里
半圈长=170/2=85公里
3.运输线路成两圈的图上作业法
初始方案 5
甲圈 4
8
1
2
3
乙圈
8
甲圈: 半圈长=7+2+3+6+4+3/2=12.5公里 外圈长=4公里 里圈长=2+3+6+3=14公里
乙圈: 半圈长=4+4+5+8/2=10.5公里 外圈长=0公里 里圈长=4+4+5=13公里
扫描法可阐述如下:
(1)在地图或方格图中确定所有站点(含仓库)的位置。
(2)自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转 该直线直到与某站点相交。考虑:如果在某线路上增加该站点,是否会 超过车辆的载货能力?如果没有,继续旋转直线,直到与下一个站点相 交。再次计算累计货运量是否超过车辆的运载能力(先使用最大的车 辆)。如果超过,就剔除最后的那个站点,并确定路线。随后,从不包 含在上一条路线中的站点开始,继续旋转直线以寻找新路线。继续该过 程直到所有的站点都被安排到路线中。
和返回时间,司机休息时间,最大的里程和时间限制。
(3)时间窗口。由于各处的工作时间不同,每个站点每天只允许在特定 的时间内取货和/或送货。
(4)顾客。顾客需求,装载、卸载,所处的地理位置,分离需求,优先 等级。
(5)道路信息。车流密度,道路交通费用,距离或时间属性。 (6)货物信息。货物的种类多少,兼容性,货物的保鲜。 (7)运输规章。工人每天的工作时间,车辆的周期维护。
9
4
K
0C
12)以A为初始结点,计算与之
相连的点的位势值;
11
6
11 B
13)从剩余位势中选出最小者,
10
D6
标注箭头和位势值;
5
12
6
11 E 14
G
7 17 A
8
4 11
9
11 F 15 10)以G为初始结点,计算与之
相连的点的位势值;
24 H
7 I
10 10
11)从剩余位势中选出最小者,
标注箭头和位势值; J
VRP问题是组合优化领域著名的NP难题之一,求解方法一般相当 复杂,通常的做法是应用相关技术问题分解或者转化为一个或多个已经 研究过的基本问题(如旅行商问题、指派问题、最短路问题等),再使 用相对比较成熟的基本理论和方法进行求解。
30
运用VRP模型对实际问题进行研究时,一般需要考虑以下几个方面的问题: (1)仓库。仓库的级数,每级仓库的数量、地点和规模。 (2)车辆。车辆的型号和数量,每种车辆的容积和运作费用,出发时间
B3
4+12=16 8+11=19 3+11=14
B4
7+12=19 5+11=16 1+11=12
分析得知:如果经过B1,则走B1-C2-D2-E;
如果经过B2,则走B2-C3-D1-E;
如果经过B3,则走B3-C3-D1-E;
如果经过B4,则走B4-C3-D1-E。
到E的最 短距离
12 13 14 12