《【福州大学公共管理学院物流运输管理03运输路线优化】（PPT103）30355.pptx》由会员分享，可在线阅读，更多相关《【福州大学公共管理学院物流运输管理03运输路线优化】（PPT103）30355.pptx（104页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章运输路线优化3.1 运输路线和时间安排的原则u 运输路线的选择影响到运输设备和人员的利用，正确地确定合理的运输路线可以降低运输成本，因此运输路线的确定是运输决策的一个重要领域。安排运输路线和时间的几个原则如下：1.将相互接近的停留点的货物装在一辆车上运送，以便停留点之间的运行距离最小化；u 车辆的运输路线应将邻近的停留点串起来，以使停留点之间的运输距离最小化，这样也就使总的路线上的运输时间最短。3.1 运输路线和时间安排的原则3.1 运输路线和时间安排的原则2.将集聚在一起的停留点安排同一天送货，要避免不是同一天送货的停留点在运行路线上重叠；3.1 运输路线和时间安排的原则3.运行路线从
2、离仓库最远的停留点开始。u 运行路线从离仓库最远的停留点开始，送货车辆依次装载贴邻这个关键停留点的一些停留点的货物，这辆货车满载后，再安排另一辆货车装载另一个最远的停留点的货物。4.一辆货车顺次途径各停留点的路线不应交叉，要成泪滴状。3.1 运输路线和时间安排的原则5.在多种规格车型的车队中，应优先使用载重量最大的货车。u 在运输货物时，最好是适用一辆载重量大到能将路线上所有停留点所要求运送的货物都装载的货车，这样可以将服务区停留点的总的运行距离或时间最小化。6.提货应混在送货过程中进行，而不要在运行路线结束后再进行。u 提货应尽可能在送货过程种进行，以减少交叉路程量，而在送货结束后再进行提货
3、经常会发生路程交叉。3.1 运输路线和时间安排的原则7.对偏离集聚停留点路线远的单独的停留点可专门安排车辆送货。u 偏离集聚停留点少，特别是那些送货量小的停留点一般要花费大量的时间和费用，因此适用小载重量的车辆专门为这些停留点送货是合理的。8.应当避免停留点工作时间太短的约束。u 停留点工作时间太短会迫使途经停留点的顺序偏离理想状态。3.2 运输路线决策l 尽管路线选择问题种类繁多，但可以归为三种基本类型：起迄点不同的单一问题、多起迄点问题、起迄点重合的问题。1、起迄点不同的单一问题最短路线法：逐点求最短路线【例3】如图所示是一张公路运输网示意图，其中A是起点，J是终点，B、C、D、E、G、H
4、、I 是网络中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点A 到终点J的最短的运输路线。A 起点BEIJ 终点HFC DG8490841383481564813215090601321264812666120【练习】如图所示是一张公路运输网示意图，其中A 是起点，I 是终点，B、C、D、E、G、H 是网络中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点A 到终点I 的最短的运输路线。A 起点BCDEFGHI 终点204060 6030605050505020453080100 2、
5、起迄点重合的问题l 物流管理人员经常遇到的一个路线选择问题是始发点就是终点的路线选择，又常称为“旅行推销员”问题。这类问题通常在运输工具是同一部门所有的情况下发生。对起迄点重合问题，有一种简单有效的方法扫描法 是是开始将所有的停留点位置画在地图上选择最大的车辆装载这个停留点的货物然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。通过仓库位置放置一直尺，直尺指向任何方向均可是 否 超 过 车 辆 容 积 或 体 积的限度是否扫描完所有停留点安排下一辆车装载货物，得到一条运行线路结束继 续 转 动 直 尺，扫 描 到 下 一 个 停 留 点，分 配 该 车 辆装载货物优 化 每 条 运 行
6、路 线 的 停 留 点 顺 序，以 求 运 行 距 离 最 小化否否扫描法扫描法4000100030002000100020002000200020003000200030003、多起迄点问题l 如果有多个货源地可以服务于多个目的地时，那么我们面临的问题是，要指定为各目的地服务的供货地，同时要找到供货地、目的地之间的最佳路径。该问题常发生在多个供应商、工厂或仓库服务于多个客户的情况下。图上作业法l 图上作业法根据交通图的点和线的关系，把各种路线归纳为道路不成圈（无圈）和道路成圈两类。l 道路不成圈，就是没有回路的“树”形路线，包括直线、丁字线、交叉线、分支线等；无圈的流向图只要消灭对流，就是最
7、优流向图。l 道路成圈，就是形成闭合回路的“环”状路线，包括一个圈和多个圈；成圈的流向图要达到既没有对流，又没有迂回的要求才是最优流向图。道路不成圈l 任何一张交通网络图，其线路分布形状可分成圈和不成圈两类，对于不成圈的交通网络图，根据线性规划原理，物资调拨或空车调运线路的确定可依据“就近调空”原则进行。【例4】有一种商品从A 地运出40吨，从B 地运出70吨，从C 地运出30吨，从D 地运出60吨，供给a、b、c 三地的数量分别为70吨、80吨、50吨，应用图上作业法选择该商品的合理运输路线。A B C D调入量a 70b 80c 50调出量40 70 30 60 200运出 地运入地40
8、70 70 80506030B DCa bcA4030302060 20A B C D调入量a 40 30 70b 20 60 80c 20 30 50调出量40 70 30 60 200【例5】设产地甲、乙、丙、丁产量分别为70吨、40吨、90吨、50吨；销地A、B、C、D、E 需求分别为30吨、70吨、50吨、60吨、40吨，试求合理的运输方案。A B C D E产量甲70乙40丙90丁50销量30 70 50 60 40 250销地产地70 30 40 507050乙 丁 甲CBA60 90丙E D4050 30405040 4070乙 甲B10D403010A B C D E产量甲30
9、 40 70乙30 10 40丙50 40 90丁50 50销量30 70 50 60 40 250道路成圈l 对于成圈的交通网络，只要先假设某两点间线路“不通”，将成圈问题化为不成圈问题考虑，这样就可得到一个初始的调运方案。l 然后进一步作优化处理，其原则是：里圈、外圈分别算，要求不过半圈长；如若超过半圈长，应甩运量最小段；反复求算最优方案。【例6】有某商品发送点A、B、C、D 四处，与四个接收点a、b、c、d 成圈状，其距离及供需量如表所示，试求最优运输路线。距离a b c d产量A 65 80 80B 180 220 150C 90 75 170D 60 70 100销量130 100
10、160 110 500接收地发送地150 100CAD17016010011080130Babcd15020100109070100l 根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。l L/2（220+180+65+80+70+60+75+90）/2 420l L内180+65+80+60+90 445L/2l L外75+70 145L/2l L内大于全圈长的一半，不是最优方案，应重新甩段破圈，甩内圈运量最小区段a A，寻找最优方案。150 100CAD17016010011080130Babcd130807090803020l 计算内外圈长：l L/2（220+180+65+8
11、0+70+60+75+90）/2 420l L 内180+80+60+90 410L/2l L 外70+75+220 365L/2l 将上述运输结果填入平衡表：运量a b c d产量A 80 80B 130 20 150C 80 90 170D 70 30 100销量130 100 160 110 500接收地发送地【练习】某地区物资供销情况如图所示，现要求得物资调运的最优方案。3020 502030607010020364523251823ABCDEFGHI3020 5020306070100202020802030304010ABCDEFGHIl 根据图中箭头将内外圈货流里程汇总，检查是否
12、超过全圈长的一半。l L/2（45+23+25+18+23+36）/2 85l L内25+18+23 66L/2l L外23+36 59L/2l 将上述运输结果填入平衡表：距离B C E G I产量A 20 20D 20 20F 10 30 20 40 100H 30 30 60销量30 50 20 70 30 200接收地发送地运量B C E G I产量A 20 20D 20 20F 10 20 70 100H 30 30 60销量30 50 20 70 30 200接收地发送地l 当运输路线有几个圈的情况，应逐圈检查并调整，直到每个圈都能符合要求，此时才能得到物资调拨的最优方案。【练习】2
13、9006002000100057ABCDEFHI900130032001000G15009009007845751327432 57554174J166K290060020001000ABCDEFHI900130032001000G1500900900J150010009009009008005001009001500K距离A C E F G I J K销量B1500 800 900 3200D500 900 600 900 2900H100 1000 900 2000产量1500 1300 900 600 1000 1000 900 900 8100发送地接收地表上作业法l 表上作业法是单纯
14、形法在求解运输问题时的一种简化方法。它包括以下步骤：1.确定初始可行方案。方法比较多，一般希望方法既简单，又尽可能接近最优解，常用最小元素法和伏格尔法。2.最优方案的判别。判别的方法是计算空格的检验数，常用闭回路法和位势法。3.改进方案。常使用闭回路调整法进行调整以得到最优的方案。l【例7】有某公司经销一产品，它下设三个加工厂，每日的产量分别为A1 7吨、A2 4吨，A3 9吨，该公司把这些产品分别运往四个销售点。各个销售点每日销量为B1 3吨，B26吨，B3 5吨，B4 6吨，已知从各工厂到各销售点的单位产品的运价如表所示，问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费最少。
15、B1 B2 B3 B4A1 3 11 3 10A2 1 9 2 8A3 7 4 10 5销地加工厂最小元素法B1 B2 B3 B4产量A1 3 11 3 10 7A2 1 9 2 8 4A3 7 4 10 5 9销量3 6 5 6销地加工厂3 146 33B1 B2 B3 B4A1 4 3A2 3 1A3 6 3销地加工厂l【例8】编制被运输商品的产销平衡表和单位运输价格如下表所示，试用最小费用法求出最优运输方案的初始方案。A B C D E发运量甲3 2 3 5 3 100乙3 3 1 3 4 300丙7 8 4 2 2 600丁5 4 7 7 8 800需求量250 300 350 400
16、 500 1800销地加工厂A B C D E发运量甲3 2 3 5 3 100乙3 3 1 3 4 300丙7 8 4 2 2 600丁5 4 7 7 8 800需求量250 300 350 400 500 1800销地加工厂300100 5005050250 250 300l【练习】1 2 3产量1 5 1 8 122 2 4 1 143 3 6 7 4销量9 10 11销地加工厂1011342伏格尔法l 最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运费。l 伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额，差额越大，说明不能按
17、最小运费调运时，运费增加越多，因而对差额最大处，就应当采用最小运费调运。l【例9】试用伏格尔求运输的最优方案。销地加工厂B1 B2 B3 B4产量A1 3 11 3 10 7A2 1 9 2 8 4A3 7 4 10 5 9销量3 6 5 6销地加工厂B1 B2 B3 B4产量A1 3 11 3 10 7A2 1 9 2 8 4A3 7 4 10 5 9销量3 6 5 60112 5 1 36行差额列差额销地加工厂B1 B2 B3 B4产量A1 3 11 3 10 7A2 1 9 2 8 4A3 7 4 10 5 9销量3 6 5 62 5 1 36行差额列差额0123销地加工厂B1 B2 B
18、3 B4产量A13 11 3 10 7A21 9 2 8 4A37 4 10 5 9销量3 6 5 62 1 26行差额列差额01233销地加工厂B1 B2 B3 B4产量A13 11 3 10 7A21 9 2 8 4A37 4 10 5 9销量3 6 5 61 26行差额列差额76335 21销地加工厂B1 B2 B3 B4产量A17A24A39销量3 6 5 66335 211 2 3 4 5产量1 10 2 3 15 9 252 5 10 15 2 4 303 15 5 14 7 15 204 20 15 13 M 8 30销量20 20 30 10 25l【练习】伏格尔法，M 为任意
19、大正数销地加工厂行差额列差额12255 3 10 5 4251 2 3 4 5产量1 10 2 3 15 9 252 5 10 15 2 4 303 15 5 14 7 15 204 20 15 13 M 8 30销量20 20 30 10 25销地加工厂行差额列差额122510 5 1 5 425201 2 3 4 5产量1 10 2 3 15 9 252 5 10 15 2 4 303 15 5 14 7 15 204 20 15 13 M 8 30销量20 20 30 10 25销地加工厂行差额列差额122510 5 1 5 42520 10 0l（有时在产销平衡表上填入一个运量后，在单
20、位运价表上同时划去一行和一列，这时需要添一个“0”，它的位置可在对应同时划去的那行或列的任一空格处）1 2 3 4 5产量1 10 2 3 15 9 252 5 10 15 2 4 303 15 5 14 7 15 204 20 15 13 M 8 30销量20 20 30 10 25销地加工厂行差额列差额129510 1 72520 102025 5001 2 3 4 5产量1 252 303 204 30销量20 20 30 10 25销地加工厂2520 102025 5002、最优方案的判别位势法2、最优方案的判别位势法l 检验数的计算方法如下：设有运量的格子数最多的行或列的位势0 有运
21、量格子的运价行位势+列位势 空格的检验数运价-（行位势+列位势）l【例10】下面是用最小元素法的得出的运输方案，试用位势法判断是否最优。B1 B2 B3 B4产量A1 3 11 3 10 7A2 1 9 2 8 4A3 7 4 10 5 9销量3 6 5 6销地加工厂3 146 33l【例10】下面是用最小元素法的得出的运输方案，试用位势法判断是否最优。B1 B2 B3 B4行位势A1 3 11 3 10 A2 1 9 2 8A3 7 4 10 5 列位势销地加工厂03 10-1-52 91 21-110 12A B C D E发运量甲3 2 3 5 3 100乙3 3 1 3 4 300丙7
22、 8 4 2 2 600丁5 4 7 7 8 800需求量250 300 350 400 500 1800销地加工厂300100 5005050250 250 300l【练习】下面是用最小元素法的得出的运输方案，试用位势法判断是否最优。A B C D E行位势甲3 2 3 5 3乙3 3 1 3 4丙7 8 4 2 2 丁5 4 7 7 8列位势销地加工厂0547-25-4-570 0-22 3 0 17 9 42 13、改进方案闭合回路调整法 从负检验数所在格子出发找一条闭合回路，用水平或垂直线向前划，每碰到数字格转90度，然后继续前进，直到回到起始空格为止。并从出发格开始依次标上正负号。将
23、所有标有负号的转角格中的最小运量作为调整数。各正号加上调整数，负号减去调整数。l【例11】使用闭合回路法对例10进行调整。B1 B2 B3 B4行位势A1 3 11 3 10 A2 1 9 2 8A3 7 4 10 5 列位势销地加工厂03 10-1-52 91 21-110 12B1 B2 B3 B4产量A1 3 11 3 10 7A2 1 9 2 8 4A3 7 4 10 5 9销量3 6 5 6销地加工厂3 146 33+-152A B C D E行位势甲3 2 3 5 3乙3 3 1 3 4丙7 8 4 2 2 丁5 4 7 7 8列位势销地加工厂0547-25-4-570 0-22
24、3 0 17 9 42 1l【练习】使用闭合回路法对上一个练习题进行调整。A B C D E发运量甲3 2 3 5 3 100乙3 3 1 3 4 300丙7 8 4 2 2 600丁5 4 7 7 8 800需求量250 300 350 400 500 1800销地加工厂300100 5005050250 250 300+-A B C D E发运量甲3 2 3 5 3 100乙3 3 1 3 4 300丙7 8 4 2 2 600丁5 4 7 7 8 800需求量250 300 350 400 500 1800销地加工厂300150 4505050300 250 250+-1 2 3 4供应
25、量A 10 6 7 12 4B 16 10 5 9 9C 5 4 10 10 4销量5 2 4 6销地加工厂费用1 2 3 4供应量A 10 6 7 12 4B 16 10 5 9 9C 5 4 10 10 4销量5 2 4 6销地加工厂费用行差额14列差额2 115 241 2 3 4供应量A 10 6 7 12 4B 16 10 5 9 9C 5 4 10 10 4销量5 2 4 6销地加工厂费用行差额14列差额2 316 4411 2 3 4供应量A 10 6 7 12 4B 16 10 5 9 9C 5 4 10 10 4销量5 2 4 6销地加工厂费用行差额14列差额2 3 4414
26、1 2 3 4供应量A 10 6 7 12 4B 16 10 5 9 9C 5 4 10 10 4销量5 2 4 6销地加工厂费用行差额61列差额2 3 44142 151 2 3 4行位势A 10 6 7 12B 16 10 5 9C 5 4 10 10列位势销地加工厂费用4142 15010 6 12-3-58-19 73 7 31 2 3 4行位势A 10 6 7 12B 16 10 5 9C 5 4 10 10列位势销地加工厂费用4142 15+-+-13 61 2 3 4行位势A 10 6 7 12B 16 10 5 9C 5 4 10 10列位势销地加工厂费用41 213 6010
27、 6 7-2-51118 63 8 41 2 3 4行位势ABC列位势销地加工厂运量41 213 6l 最优运输方案如下l【练习】试用伏格尔法求，并检验，得出最优运输方案。1 2 3 4供应量A 15 18 19 13 50B 20 14 15 17 30C 25 12 17 22 70销量30 60 20 40 150销地加工厂费用1 2 3 4供应量A 15 18 19 13 50B 20 14 15 17 30C 25 12 17 22 70销量30 60 20 40 150销地加工厂费用行差额215列差额5 2 2 4601 2 3 4供应量A 15 18 19 13 50B 20 1
28、4 15 17 30C 25 12 17 22 70销量30 60 20 40 150销地加工厂费用行差额225列差额5 2 2 460301 2 3 4供应量A 15 18 19 13 50B 20 14 15 17 30C 25 12 17 22 70销量30 60 20 40 150销地加工厂费用行差额625列差额5 2 2 46030201 2 3 4供应量A 15 18 19 13 50B 20 14 15 17 30C 25 12 17 22 70销量30 60 20 40 150销地加工厂费用行差额25列差额2 560302020 10101 2 3 4行位势A 15 18 19
29、 13 B 20 14 15 17 C 25 12 17 22列位势销地加工厂费用015 134116612 81 4431 2 3 4供应量A 50B 30C 70销量30 60 20 40 150销地加工厂运量60302020 1010l 最优运输方案如下1 2 3供应量A 5 1 3 12B 2 4 1 14C 3 6 7 4销量9 10 11销地加工厂费用1 2 3供应量A 5 1 3 12B 2 4 1 14C 3 6 7 4销量9 10 11销地加工厂费用1011 3421 2 3行位势A 5 1 3B 2 4 1C 3 6 7列位势销地加工厂费用1011 3420523-4-1-
30、1671 2 3行位势A 5 1 3B 2 4 1C 3 6 7列位势销地加工厂费用1011 342+-+-1 2 3行位势A 5 1 3B 2 4 1C 3 6 7列位势销地加工厂费用109 54+-+-21 2 3行位势A 5 1 3B 2 4 1C 3 6 7列位势销地加工厂费用109 54201 3-24-1156 51 2 3行位势ABC列位势销地加工厂运量109 542l 最优运输方案如下供求不均衡运输l 在运输的实际工作中，由于经济活动和市场环境的多变性，经常会存在供求不平衡的现象，此时应对上述的方法进行一定的修正。l 修正的基本思路是：化不均衡为均衡，如果出现供求不平衡，则设一
31、个虚销点或虚发点，得出最优方案后再去掉虚设的点。l【例12】1 2 3 4供应量A 15 18 19 13 50B 20 14 15 17 55C 25 12 17 22 70销量30 60 20 40销地加工厂费用l【例12】1 2 3 4 5供应量A 15 18 19 13 0 50B 20 14 15 17 0 55C 25 12 17 22 0 70销量30 60 20 40 25销地加工厂费用l 解决供求不均衡问题时，可使用西北角法来求得初始可行方案。30 2040 155 40 25l【例12】1 2 3 4 5行位势A 15 18 19 13 0B 20 14 15 17 0C
32、25 12 17 22 0列位势销地加工厂费用30 2040 155 40 2500 22 17-2162130-9-29-312-42l【例12】1 2 3 4 5行位势A 15 18 19 13 0B 20 14 15 17 0C 25 12 17 22 0列位势销地加工厂费用30 2040 155 40 2500 22 17-216213+-+-+-l【例12】1 2 3 4 5行位势A 15 18 19 13 0B 20 14 15 17 0C 25 12 17 22 0列位势销地加工厂费用30 55520 25 2500 22 17-216213+-+-+-15l【例12】1 2 3
33、 4 5行位势A 15 18 19 13 0B 20 14 15 17 0C 25 12 17 22 0列位势销地加工厂费用302010206020 15l【练习】1 2 3 4供应量A 15 18 19 13 50B 20 14 15 17 30C 25 12 17 22 70销量30 60 45 40销地加工厂费用谢谢观看/欢迎下载BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES.BY FAITH I BY FAITH