第三章-运输路线优化

第三章运输路线优化3.1运输路线和时间安排的原则运输路线的选择影响到运输设备和人员的利用，正确地确定合理的运输路线可以降低运输成本，因此运输路线的确定是运输决策的一个重要领域。安排运输路线和时间的几个原则如下：1.将相互接近的停留点的货物装在一辆车上运送，以便停留点之间的运行距离最小化；车辆的运输路线应将邻近的停留点串起来，以使停留点之间的运输距离最小化，这样也就使总的路线上的运输时间最短。3.1运输路线和时间安排的原则3.1运输路线和时间安排的原则2.将集聚在一起的停留点安排同一天送货，要避免不是同一天送货的停留点在运行路线上重叠；3.1运输路线和时间安排的原则3.运行路线从离仓库最远的停留点开始。运行路线从离仓库最远的停留点开始，送货车辆依次装载贴邻这个关键停留点的一些停留点的货物，这辆货车满载后，再安排另一辆货车装载另一个最远的停留点的货物。4.一辆货车顺次途径各停留点的路线不应交叉，要成泪滴状。●●●●●●●●●●●●3.1运输路线和时间安排的原则5.在多种规格车型的车队中，应优先使用载重量最大的货车。在运输货物时，最好是适用一辆载重量大到能将路线上所有停留点所要求运送的货物都装载的货车，这样可以将服务区停留点的总的运行距离或时间最小化。6.提货应混在送货过程中进行，而不要在运行路线结束后再进行。提货应尽可能在送货过程种进行，以减少交叉路程量，而在送货结束后再进行提货经常会发生路程交叉。3.1运输路线和时间安排的原则7.对偏离集聚停留点路线远的单独的停留点可专门安排车辆送货。偏离集聚停留点少，特别是那些送货量小的停留点一般要花费大量的时间和费用，因此适用小载重量的车辆专门为这些停留点送货是合理的。8.应当避免停留点工作时间太短的约束。停留点工作时间太短会迫使途经停留点的顺序偏离理想状态。3.2运输路线决策尽管路线选择问题种类繁多，但可以归为三种基本类型：起迄点不同的单一问题、多起迄点问题、起迄点重合的问题。1、起迄点不同的单一问题最短路线法：逐点求最短路线【例3】如图所示是一张公路运输网示意图，其中A是起点，J是终点，B、C、D、E、G、H、I是网络中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点A到终点J的最短的运输路线。●●●●●●●●●●A起点BEIJ终点HFCDG84908413834815648132150906013212648126●●●●●●●●●66120【练习】如图所示是一张公路运输网示意图，其中A是起点，I是终点，B、C、D、E、G、H是网络中的结点，结点与结点之间以线路连接，线路上标明了两个结点的距离，以运行时间（分）表示。要求确定一条从起点A到终点I的最短的运输路线。●●●●●●●●●A起点BCDEFGHI终点2040606030605050505020453080100●●●●●●●●●2、起迄点重合的问题物流管理人员经常遇到的一个路线选择问题是始发点就是终点的路线选择，又常称为“旅行推销员”问题。这类问题通常在运输工具是同一部门所有的情况下发生。对起迄点重合问题，有一种简单有效的方法—扫描法是是开始将所有的停留点位置画在地图上选择最大的车辆装载这个停留点的货物然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。通过仓库位置放置一直尺，直尺指向任何方向均可是否超过车辆容积或体积的限度是否扫描完所有停留点安排下一辆车装载货物，得到一条运行线路结束继续转动直尺，扫描到下一个停留点，分配该车辆装载货物优化每条运行路线的停留点顺序，以求运行距离最小化否否扫描法【例】某公司从其所属的仓库用送货车辆到各客户点提货，然后将客户的货物运回仓库，以便集运成大的批量再进行远程运输。全天的提货量见下图，提货量以件为单位。送货车每次可运载1万件，完成一次运行路线一般需要一天时间。该公司要求确定：需多少条路线（即多少辆送货车）；每条路线上有哪几个客户点；送货车辆途经有关客户点的顺序。扫描法4000100030002000100020002000200020003000200030003、多起迄点问题如果有多个货源地可以服务于多个目的地时，那么我们面临的问题是，要指定为各目的地服务的供货地，同时要找到供货地、目的地之间的最佳路径。该问题常发生在多个供应商、工厂或仓库服务于多个客户的情况下。图上作业法图上作业法根据交通图的点和线的关系，把各种路线归纳为道路不成圈（无圈）和道路成圈两类。道路不成圈，就是没有回路的“树”形路线，包括直线、丁字线、交叉线、分支线等；无圈的流向图只要消灭对流，就是最优流向图。道路成圈，就是形成闭合回路的“环”状路线，包括一个圈和多个圈；成圈的流向图要达到既没有对流，又没有迂回的要求才是最优流向图。道路不成圈任何一张交通网络图，其线路分布形状可分成圈和不成圈两类，对于不成圈的交通网络图，根据线性规划原理，物资调拨或空车调运线路的确定可依据“就近调空”原则进行。【例4】有一种商品从A地运出40吨，从B地运出70吨，从C地运出30吨，从D地运出60吨，供给a、b、c三地的数量分别为70吨、80吨、50吨，应用图上作业法选择该商品的合理运输路线。ABCD调入量a70b80c50调出量40703060200运出地运入地40707080506030BDCabcA403030206020ABCD调入量a403070b206080c203050调出量40703060200【例5】设产地甲、乙、丙、丁产量分别为70吨、40吨、90吨、50吨；销地A、B、C、D、E需求分别为30吨、70吨、50吨、60吨、40吨，试求合理的运输方案。ABCDE产量甲70乙40丙90丁50销量3070506040250销地产地703040507050乙丁甲CBA6090丙ED4050304050404070乙甲B10D403010ABCDE产量甲304070乙301040丙504090丁5050销量3070506040250道路成圈对于成圈的交通网络，只要先假设某两点间线路“不通”，将成圈问题化为不成圈问题考虑，这样就可得到一个初始的调运方案。然后进一步作优化处理，其原则是：里圈、外圈分别算，要求不过半圈长；如若超过半圈长，应甩运量最小段；反复求算最优方案。【例6】有某商品发送点A、B、C、D四处，与四个接收点a、b、c、d成圈状，其距离及供需量如表所示，试求最优运输路线。距离abcd产量A658080B180220150C9075170D6070100销量130100160110500接收地发送地150100CAD17016010011080130Babcd15020100109070100根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。L/2＝（220+180+65+80+70+60+75+90）/2＝420L内＝180+65+80+60+90＝445L/2L外＝75+70＝145L/2L内大于全圈长的一半，不是最优方案，应重新甩段破圈，甩内圈运量最小区段aA，寻找最优方案。150100CAD17016010011080130Babcd130807090803020计算内外圈长：L/2＝（220+180+65+80+70+60+75+90）/2＝420L内＝180+80+60+90＝410L/2L外＝70+75+220＝365L/2将上述运输结果填入平衡表：运量abcd产量A8080B13020150C8090170D7030100销量130100160110500接收地发送地【练习】某地区物资供销情况如图所示，现要求得物资调运的最优方案。3020502030607010020364523251823ABCDEFGHI30205020306070100202020802030304010ABCDEFGHI根据图中箭头将内外圈货流里程汇总，检查是否超过全圈长的一半。L/2＝（45+23+25+18+23+36）/2＝85L内＝25+18+23＝66L/2L外＝23+36＝59L/2将上述运输结果填入平衡表：距离BCEGI产量A2020D2020F10302040100H303060销量3050207030200接收地发送地运量BCEGI产量A2020D2020F102070100H303060销量3050207030200接收地发送地当运输路线有几个圈的情况，应逐圈检查并调整，直到每个圈都能符合要求，此时才能得到物资调拨的最优方案。【练习】29006002000100057ABCDEFHI900130032001000G1500900900784575132743257554174J166K290060020001000ABCDEFHI900130032001000G1500900900J150010009009009008005001009001500K距离ACEFGIJK销量B15008009003200D5009006009002900H10010009002000产量15001300900600100010009009008100发送地接收地表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法。它包括以下步骤：1.确定初始可行方案。方法比较多，一般希望方法既简单，又尽可能接近最优解，常用最小元素法和伏格尔法。2.最优方案的判别。判别的方法是计算空格的检验数，常用闭回路法和位势法。3.改进方案。常使用闭回路调整法进行调整以得到最优的方案。【例7】有某公司经销一产品，它下设三个加工厂，每日的产量分别为A1＝7吨、A2＝4吨，A3＝9吨，该公司把这些产品分别运往四个销售点。各个销售点每日销量为B1＝3吨，B2＝6吨，B3＝5吨，B4＝6吨，已知从各工厂到各销售点的单位产品的运价如表所示，问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费最少。B1B2B3B4A1311310A21928A374105销地加工厂最小元素法B1B2B3B4产量A13113107A219284A3741059销量3656销地加工厂314633B1B2B3B4A143A231A363销地加工厂【例8】编制被运输商品的产销平衡表和单位运输价格如下表所示，试用最小费用法求出最优运输方案的初始方案。ABCDE发运量甲32353100乙33134300丙78422600丁54778800需求量2503003504005001800销地加工厂ABCDE发运量甲32353100乙33134300丙78422600丁54778800需求量2503003504005001800销地加工厂3001005005050250250300【练习】123产量15181222411433674销量91011销地加工厂1011342伏格尔法最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就应当采用最小运费调运。【例9】试用伏格尔求运输的最优方案。销地加工厂B1B2B3B4产量A13113107A219284A3741059销量3656销地加工厂B1B2B3B4产量A13113107A219284A3741059销量365601125136行差额列差额销地加工厂B1B2B3B4产量A13113107A219284A3741059销量365625136行差额列差额0123销地加工厂B1B2B3B4产量A13113107A219284A3741059销量36562126行差额列差额01233销地加工厂B1B2B3B4产量A13113107A219284A3741059销量3656126行差额列差额7633521销地加工厂B1B2B3B4产量A17A24A39销量365663352112345产量110231592