车辆调度方法

1、车辆调度方法车辆调度方法图上作业法图上作业法物资调拨物资调拨 图上作业法 图上作业法的原则可以归纳为： 流向划右方，对流不应当； 里圈、外圈分别算，要求不能过半圈长； 如若超过半圈长，应去运量最小段； 反复运算可得最优方案。 1运输线路不成圈的图上作业法 对于运输线路不成圈的流向图，只要不出现对流现象，就是最优调运方案。 运输线路不成圈的图上作业法较简单。就是从各端点开始，按“各站供需就近调拨”的原则进行调配。ABCDEFG+10-2-5+3-11+9-4 1运输线路不成圈的图上作业法ABCDEFG+10-2-5+3-11+9-41083654 1运输线路不成圈的图上作业法 2运输线路成圈的图

2、上作业法 运输线路成圈，就是形成闭合回路的“环”形路线，包括一个圈（有三角形、四边形、多边形）和多个圈。成圈的线路流向图要同时达到既无对流现象、又无迂回现象的要求才是最优流向图。 对于成圈运输线路的图上作业法，可按下述三个步骤寻求最优方案，如表所示。表 成圈运输线路的图上作业法的步骤 步骤详 述去段破圈确定初始运输方案 就是在成圈的线路中，先假设某两点间的线路“不通”，去掉这段线路，把成圈线路转化为不成圈的线路，即破圈；按照运输线路不成圈的图上作业法，即可得到初始运输方案。检查有无迂回现象 因为流向箭头都统一画在线路右边，所以圈内圈外都画有一些流向。分别检查每个小圈，如果圈内和圈外流向的总长度

3、都不超过全圈总长度的1/2 ，那么，全圈就没有迂回现象了，这个线路流向图就是最优的，对应的就是最优运输方案。否则转向第三步。重新去段破圈，调整流向 在超过全圈总长1/2 的里（外）圈各段流向线上减去最小运量，然后在相反方向的外（里）圈流向线上和原来没有流向线的各段上，加上减去的最小运量，这样可以得到一个新的线路流向图，然后转到第二步检查有无迂回现象。如此反复，直到得到最优线路流向图为止。 如果全圈存在两个及两个以上的圈，则需分别对各圈进行是否存在迂回线路的检查，如果各圈的里、外圈都不超过全圈总线长的1/2 ，则不存在迂回现象，此方案为最优运输方案。第一步第一步 作出初始方案作出初始方案ABCD

4、EFGHI+20-30-50+20-20+100-70+60-30(36)(23)(13)(29)(25)(23)(45)(18) 2运输线路成圈的图上作业法ABCDEFGHI+20-30-50+20-20+100-70+60-3030208050102060外圈长=45+25+18+23=111公里里圈长=23公里全圈长=45+23+25+18+23+36=170公里半圈长=170/2=85公里ABCDEFGHI+20-30-50+20-20+100-70+60-3020102080303040外圈长=25+18+23=66公里里圈长=23+36=59公里全圈长=45+23+25+18+23

5、+36=170公里半圈长=170/2=85公里调整流向调整流向 3运输线路成两圈的图上作业法甲圈甲圈乙圈乙圈5818324甲圈： 乙圈：半圈长=7+2+3+6+4+3/2=12.5公里 半圈长=4+4+5+8/2=10.5公里外圈长=4公里 外圈长=0公里里圈长=2+3+6+3=14公里 里圈长=4+4+5=13公里初始方案甲圈甲圈乙圈乙圈4716223甲圈： 乙圈：半圈长=7+2+3+6+4+3/2=12.5公里 半圈长=4+4+5+8/2=10.5公里外圈长=4+7=11公里 外圈长=8公里里圈长=2+3+3=8公里 里圈长=4+5=9公里调整方案练习练习最短路径问题最短路径问题例例1 1

6、 多阶段决策法多阶段决策法 下图表示从起点下图表示从起点A A到终点到终点E E之间各点的距离。求之间各点的距离。求A A到到E E的最短路径。的最短路径。BACBDBCDEC412312312322164724838675611064375118讨论：讨论： 1 1、以上求从、以上求从A A到到E E的最短路径问题，可以转化为的最短路径问题，可以转化为四个性质完全相同，但四个性质完全相同，但规模较小的子问题规模较小的子问题，即分别从，即分别从D Di i 、C Ci i、B Bi i、A A到到E E的最短路径问题。的最短路径问题。 最优化原理的应用：从最短路上的每一点到终点的部分道路，也一

7、定是最优化原理的应用：从最短路上的每一点到终点的部分道路，也一定是从该点到终点的最短路。从该点到终点的最短路。 第四阶段：两个始点第四阶段：两个始点D D1 1和和D D2 2，终点只有一个；，终点只有一个； 表表1 1分析得知：从分析得知：从D D1 1和和D D2 2到到E E的最短路径唯一。的最短路径唯一。 阶段阶段4本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策) E D1 D2 10 6 10 6 E E1919 第三阶段：有三个始点第三阶段：有三个始点C1，C2，C3，终点有，终

8、点有D1，D2，对始点和终点进行分析和讨，对始点和终点进行分析和讨论论分别分别求求C1，C2，C3到到D1，D2 的最短路径问题：的最短路径问题： 表表2分析得知：如果经过分析得知：如果经过C1，则最短路为，则最短路为C1-D2-E； 如果经过如果经过C2，则最短路为，则最短路为C2-D2-E； 如果经过如果经过C3，则最短路为，则最短路为C3-D1-E。 阶段阶段3本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策) D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11

9、 6+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D12020第二阶段：有第二阶段：有4个始点个始点B1,B2,B3,B4，终点有，终点有C1,C2,C3。对始点和终点进行。对始点和终点进行分析和讨论分别求分析和讨论分别求B1,B2,B3,B4到到C1,C2,C3 的最短路径问题：的最短路径问题： 表表3 分析得知：如果经过分析得知：如果经过B1，则走，则走B1-C2-D2-E； 如果经过如果经过B2，则走，则走B2-C3-D1-E； 如果经过如果经过B3，则走，则走B3-C3-D1-E； 如果经过如果经过B4，则走，则走B4-C3-D1-E。 阶段阶段2本阶段始点本阶

10、段始点（状态）（状态） 本阶段各终点（决策）本阶段各终点（决策）到到E的最的最短距离短距离本阶段最优终本阶段最优终点（最优决策点（最优决策) C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C32121第一阶段：只有第一阶段：只有1个始点个始点A，终点有，终点有B1,B2,B3,B4 。对始点和终点进行分析和讨论。对始点和终点进行分析和讨论分别求分别求A到到B1,B2,

11、B3,B4的最短路径问题：的最短路径问题： 表表4最后，可以得到：从最后，可以得到：从A到到E的最短路径为的最短路径为A B4 C3 D1 E 阶段阶段1本阶段始本阶段始点点(状态状态) 本阶段各终点（决策）本阶段各终点（决策）到到E的最的最短距离短距离本阶段最优终本阶段最优终点点(最优决策最优决策) B1 B2 B3 B4 A 4+12=16 3+13=163+14=172+12=14 14 C22222 以上计算过程及结果，可用图以上计算过程及结果，可用图2表示，可以看到，以上方法不仅表示，可以看到，以上方法不仅得到了从得到了从A到到D的最短路径，同时，也得到了从图中任一点到的最短路径，同

12、时，也得到了从图中任一点到E的最的最短路径。短路径。 BACBDBCDEC412312312332164724838675161060106121111121314144B127512练习计算V1到V7的最短距离例例2 2 位势法位势法计算CK的最短路1）取VC=0；2）确定与C点相连的结点位势；3）取所有位势中最小者，标注在结点旁，并用箭头连出；ABCDEFHIJKG111066511714411897101094120114）以D为初始结点，计算与之相连的点的位势值；5）从剩余位势中剩余位势中选出最小者，标注箭头和位势值；66）以E为初始结点，计算与之相连的点的位势值；7）从剩余位势中剩余

13、位势中选出最小者，标注箭头和位势值；1211ABCDEFHIJKG1110665117144118971010948）以B为初始结点，计算与之相连的点的位势值；9）从剩余位势中剩余位势中选出最小者，标注箭头和位势值；10）以F为初始结点，计算与之相连的点的位势值；11）从剩余位势中剩余位势中选出最小者，标注箭头和位势值；011612111517ABCDEFHIJKG11106651171441189710109412）以A为初始结点，计算与之相连的点的位势值；13）从剩余位势中剩余位势中选出最小者，标注箭头和位势值；10）以G为初始结点，计算与之相连的点的位势值；11）从剩余位势中剩余位势中选

14、出最小者，标注箭头和位势值；011612111517ABCDEFHIJKG11106651171441189710109424重复计算，可得最优的路线图，如图所示。011612111517ABCDEFHIJKG1110665117144118971010942418313438车辆路线安排3030 车辆路线安排问题（车辆路线安排问题（VRP, Vehicle Routing Problem）是指对物流配送的车辆进行优化调度。该问题一般可以描述如下：对一系列装货点或（和）卸货点，组织适当合理的行车路线，使车辆有序地通过他们，在满足一定的约束条件下（如货物需求量、发送量、交发货时间、车辆容量、数目

15、限制、车辆行驶里程、时间限制等）下，达到一定的目标（如最短路程、最小费用、最短时间、最少车辆等）。该问题涉及了多辆交通工具的服务对象的选择和路径（服务顺序）确定两方面的问题。 VRP问题是组合优化领域著名的NP难题之一，求解方法一般相当复杂，通常的做法是应用相关技术问题分解或者转化为一个或多个已经研究过的基本问题（如旅行商问题、指派问题、最短路问题等），再使用相对比较成熟的基本理论和方法进行求解。3131运用VRP模型对实际问题进行研究时，一般需要考虑以下几个方面的问题：u（1）仓库。仓库的级数，每级仓库的数量、地点和规模。u（2）车辆。车辆的型号和数量，每种车辆的容积和运作费用，出发时间和返

16、回时间，司机休息时间，最大的里程和时间限制。u（3）时间窗口。由于各处的工作时间不同，每个站点每天只允许在特定的时间内取货和/或送货。u（4）顾客。顾客需求，装载、卸载，所处的地理位置，分离需求，优先等级。u（5）道路信息。车流密度，道路交通费用，距离或时间属性。u（6）货物信息。货物的种类多少，兼容性，货物的保鲜。u（7）运输规章。工人每天的工作时间，车辆的周期维护。3232u（1）安排车辆负责相互距离最接近的站点的货物运输。u（2）安排车辆各日途经站点时，应注意使站点群更加紧凑。如果一周内各日服务的站点不同，就应该对一周内每天的路线和时刻表问题分别进行站点群划分。各日站点群的划分应避免重叠

17、。u（3）从距仓库最远的站点开始设计路线u（4）卡车的行车路线应呈水滴状。u（5）尽可能使用最大的车辆进行运送，这样设计出的路线是最有效的。u（6）取货、送货应该混合安排，不应该在完成全部送货任务之后再取货。u（7）对过于遥远而无法归入群落的站点，可以采用其它配送方式。u（8）避免时间窗口过短。简化的原则：简化的原则：33331扫描法扫描法路线设计中的扫描法很简单，即使问题规模很大，也可以通过手工计算得出结果。扫描法可阐述如下：（1 1）在地图或方格图中确定所有站点（含仓库）的位置。）在地图或方格图中确定所有站点（含仓库）的位置。（2 2）自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向

18、旋转）自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该直线直到与某站点相交。考虑：如果在某线路上增加该站点，是否会该直线直到与某站点相交。考虑：如果在某线路上增加该站点，是否会超过车辆的载货能力？如果没有，继续旋转直线，直到与下一个站点相超过车辆的载货能力？如果没有，继续旋转直线，直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力（先使用最大的车交。再次计算累计货运量是否超过车辆的运载能力（先使用最大的车辆）。如果超过，就剔除最后的那个站点，并确定路线。随后，从不包辆）。如果超过，就剔除最后的那个站点，并确定路线。随后，从不包含在上一条路线中的站点开始，继续旋转直线以寻

19、找新路线。继续该过含在上一条路线中的站点开始，继续旋转直线以寻找新路线。继续该过程直到所有的站点都被安排到路线中。程直到所有的站点都被安排到路线中。（3 3）排定各路线上每个站点的顺序使行车距离最短。排序时可以使用）排定各路线上每个站点的顺序使行车距离最短。排序时可以使用“水滴水滴”法或求解法或求解“流动推销员流动推销员”问题的任何算法。问题的任何算法。3434例例 某公司用厢式货车从货主处取货，图某公司用厢式货车从货主处取货，图 (a) (a)是一天的取货量，单位是一天的取货量，单位是件。厢式货车的载货量是是件。厢式货车的载货量是1000010000件。完成所有取货任务需一天时间。件。完成所

20、有取货任务需一天时间。公司需要多少条运输路线（即多少部车），每条路线上应该经过哪些站公司需要多少条运输路线（即多少部车），每条路线上应该经过哪些站点，每条路线上的站点怎样排序。点，每条路线上的站点怎样排序。 首先，向北画一条直线，进行逆时针方向“扫描”。这些都是随机决定的。逆时针旋转该直线，直到装载的货物能装上一辆载重10000件的卡车，同时又不超载。一旦所有的站点都分派有车辆，就可以利用“水滴”法安排经过各站点的顺序，图 (b)是所列出的最终的路线设计。图图 扫描法设计行车路线扫描法设计行车路线汽车站汽车站1000400020003000200020002000100020002000300

21、03000a 停留点提货量数据停留点提货量数据汽车站汽车站100040002000300020002000200010002000200030003000b 扫描法解决方案扫描法解决方案2 2 节约里程法节约里程法分送式配送运输分送式配送运输分送式配送运输是一个供应点对多个用户的共同送货基本条件：所有客户的需求量总和不大于一辆车的额定载重量配送路线确定的原则：成本低、效益高、路线短、准确性高、劳动消耗少、运力合理等配送路线确定的限制条件：用户对货物品种、规格、数量的要求；用户对发到时间的要求；车辆载重量的限制；配送能力的约束等配送路线确定的方法：节约里程法PiPjP0PiPjP0分别送货同时送

22、货图图3-8 配送网络图配送网络图GEDBAFPIJHC5(1.5)(0.4)(1.4)(1.5)(0.8)(0.6)(0.8)52695(0.5)(0.6)(0.7)36875942364107811107464图3-9 配送初始方案EDBAFGPIJHC5(1.5)(0.4)(1.4)(1.5)(0.8)(0.6)(0.8)52695(0.5)(0.6)(0.7)36875942354107811107464表表3-2 配送中心节约里程排序表配送中心节约里程排序表序号序号连接点连接点节约里程节约里程序号序号连接点连接点节约里程节约里程1AB1513FG52AJ1314GH53BC1115H

23、I54CD1016AD45DE1017BI46AI918FH47EF919BE38IJ920DF39AC821GI210BJ822CJ111BD723EG112CE624FI1552695EDBAFGPIJHC(1.5)(0.4)(1.4)(1.5)(0.8)(0.6)(0.8)(0.5)(0.6)(0.7)36875942354107811107464图3-10 第一修正方案EDBAFGPIJHC(1.5)(0.4)(1.4)(1.5)(0.8)(0.6)(0.8)265(0.5)(0.6)(0.7)794354710764图3-11 最优解3、安排车辆运行时间 将所有运输路线首尾相连顺序排

24、列，使车辆的空闲时间最短，就此决定车辆数，并排出配车计划。最优运输计划安排表最优运输计划安排表1 1号线号线1010号线号线6 6号线号线9 9号线号线4 4号线号线5 5号线号线8 8号线号线2 2号线号线7 7号线号线3 3号线号线节约里程法应用案例节约里程法应用案例 由配送中心P向AI等9个用户配送货物。图中连线上的数字表示公路里程（km）。靠近各用户括号内的数字，表示各用户对货物的需求量（t）。配送中心备有2t和4t载重量的汽车，且汽车一次巡回走行里程不能超过35km，设送到时间均符合用户要求，求该配送中心的最优送货方案。ABCDEFGHIP(0.9)(1.2)(1.6)(1.1)(0

25、.9)(0.9)(0.6)(1.7)(0.5)444555556663777891010111214某配送中心配送网络图计算配送中心至各用户以及各用户之间的最短距离，列表得最短距离表： P A B C D E F G H I PABCDEF GHI 11 10 9 6 7 10 10 8 7 5 10 14 18 21 21 13 6 5 9 15 20 20 18 11 4 10 19 19 17 16 6 15 16 14 13 9 17 15 14 14 18 17 12 17 7 由最短距离表，利用节约法计算出各用户之间的节约里程，编制节约里程表： A B C D E F G H I ABCDEF GHI 16 10 3 0 0 0 6 12 14 7 2 0 0 0 6 11 6 0 0 0 0 7 1 0 0 0 8 0 0 0 6 0 0 6 0 8 根据节约里程表中节约里程多少的顺序，由大到小排列，编制节约里程顺序表，以便尽量使节约里程最多的点组合装车配送。顺位号里程节约里程顺位号里程节约里程