运输线路优化3-图上作业法.ppt

《运输线路优化3-图上作业法.ppt》由会员分享，可在线阅读，更多相关《运输线路优化3-图上作业法.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线线路路优优化化-图图上作上作业业法法第四章第四章 运运输输管理管理本本课课程程教教学学的的组组织织任务五 运输线路优化知识目标明确优化物流运输线路与运输线路开发是不同的。掌握多起点多终点的物流运输线路类型及其特点。掌握运输线路选择的优化方法-图上作业法能力目标养成严谨的工作作风，培养团队协作能力。能够利用物流运输线路优化方法解决实际工作中存在问题。任务描述任务描述 任务五 运输线路优化 案例放送案例放送任务五 运输线路优化A1A2A4A3B2B3B5B4B1（36）+20（45）（23）（18）（25）（23）（29）（127）（13）+60+100+20-30-30-50-70-20图图4

2、-1 4-1 康鑫全药业集团公司特效药品交通线路图康鑫全药业集团公司特效药品交通线路图 相关理论知识相关理论知识任务五 运输线路优化v 物流运输线路，从起点到终点，常见的有物流运输线路，从起点到终点，常见的有不成圈的直线、丁字线、交叉线和分支线，不成圈的直线、丁字线、交叉线和分支线，还有形成闭合回路的环形线路，环形线路包还有形成闭合回路的环形线路，环形线路包括有一个圈和多个圈的。案例中涉及的路线括有一个圈和多个圈的。案例中涉及的路线类型为类型为多起点、多终点问题的物流运输线路多起点、多终点问题的物流运输线路问题问题一、物流运输线路的类型一、物流运输线路的类型v 多起点、多终点问题的物流运输线路

3、，在物流多起点、多终点问题的物流运输线路，在物流运输实践中，经常存在。如多个供应商供应给多个运输实践中，经常存在。如多个供应商供应给多个工厂的情况，或者把不同工厂生产的同一产品分配工厂的情况，或者把不同工厂生产的同一产品分配到不同用户的问题。在这些问题中，起点和终点都到不同用户的问题。在这些问题中，起点和终点都不是单一的。在这类问题中，各供应点的供应量往不是单一的。在这类问题中，各供应点的供应量往往也有限制。往也有限制。v 在多个货源地服务于多个目的地时，物流运输线在多个货源地服务于多个目的地时，物流运输线路存在两种情况：运输线路成圈的和不成圈的。路存在两种情况：运输线路成圈的和不成圈的。一、

4、物流运输线路的类型一、物流运输线路的类型二、物流运输线路的选择优化二、物流运输线路的选择优化有多个货源地服务于多个目的地时，物流运输有多个货源地服务于多个目的地时，物流运输线路选择优化的任务是要指定为各目的地服务线路选择优化的任务是要指定为各目的地服务的供货地，同时要找到供货地、目的地之间的的供货地，同时要找到供货地、目的地之间的最佳路径。解决这类问题可以运用一类特殊的最佳路径。解决这类问题可以运用一类特殊的线性规划方法即物资调运问题线性规划方法即物资调运问题图上作业法图上作业法进行进行求解。求解。二、物流运输线路的选择优化二、物流运输线路的选择优化v图上作业法图上作业法是在运输图上求解线性规

5、划运输模型是在运输图上求解线性规划运输模型的方法。交通运输以及类似的线性规划问题，都的方法。交通运输以及类似的线性规划问题，都可以可以首先画出流向图，然后根据有关规则进行必首先画出流向图，然后根据有关规则进行必要调整，直至求出最小运输费用或最大运输效率要调整，直至求出最小运输费用或最大运输效率的解的解。这种求解方法，就是图上作业法。这种求解方法，就是图上作业法。v适用适用于交通线路呈树状、圈状，而且对产销地点于交通线路呈树状、圈状，而且对产销地点的数量没有严格限制的情况。的数量没有严格限制的情况。v图上作业法的求解规则可以归纳为：图上作业法的求解规则可以归纳为：流向流向划右方，对流不应当；里圈

6、、外圈分别算，划右方，对流不应当；里圈、外圈分别算，要求不能过半圈长；若超过半圈长，应去要求不能过半圈长；若超过半圈长，应去运量最小段；运量最小段；反复运算可得最优方案。反复运算可得最优方案。v图上作业法包括运输线路不成圈的图上作图上作业法包括运输线路不成圈的图上作业法和运输线路成圈的图上作业法。业法和运输线路成圈的图上作业法。二、物流运输线路的选择优化二、物流运输线路的选择优化1.1.运输线路不成圈的图上作业法运输线路不成圈的图上作业法v对于线路不成圈的货物运输，即是不构成回路的运对于线路不成圈的货物运输，即是不构成回路的运输线路，包括直线、丁字线、交叉线和分支线等。输线路，包括直线、丁字线

7、、交叉线和分支线等。只要不出现对流和迂回现象，就是最优调运方案。只要不出现对流和迂回现象，就是最优调运方案。v运输线路不成圈的图上作业法较简单。就是从各端点运输线路不成圈的图上作业法较简单。就是从各端点开始，按开始，按“各站供需就近调拨各站供需就近调拨”的原则进行调配。的原则进行调配。二、物流运输线路的选择优化二、物流运输线路的选择优化图图3-1 3-1 运输线路不成圈的调运方案运输线路不成圈的调运方案585-8-77248-8+8+7-2+4+62.2.运输线路成圈的图上作业法运输线路成圈的图上作业法v 对于成圈运输线路的图上作业法，可以按照如下对于成圈运输线路的图上作业法，可以按照如下三个

8、步骤求解，直到寻求到最优方案。成圈的线路三个步骤求解，直到寻求到最优方案。成圈的线路流向图要同时达到既无对流现象，又无迂回现象的流向图要同时达到既无对流现象，又无迂回现象的要求才是最优流向图，所对应的方案为最优运输方要求才是最优流向图，所对应的方案为最优运输方案。案。v 第第1步步 去段破圈，确定初始运去段破圈，确定初始运输输方案。在成方案。在成圈的圈的线线路中，先假路中，先假设设某两点某两点间间的的线线路路“不通不通”，去掉去掉这这段段线线路，把成圈路，把成圈线线路路转转化化为为不成圈的不成圈的线线路，即破圈；然后按照运路，即破圈；然后按照运输线输线路不成圈的路不成圈的图图上上作作业业法，即

9、可得到初始运法，即可得到初始运输输方案。方案。（1 1）工作过程）工作过程v 第第2步步 检查检查有无迂回有无迂回现现象。因象。因为为流向箭流向箭头头都都统统一画在一画在线线路右路右边边，所以圈内圈外都画有一些流向。分，所以圈内圈外都画有一些流向。分别检查别检查每个小圈，如果内圈和外圈流向的每个小圈，如果内圈和外圈流向的总长总长度都不超度都不超过过全全圈圈总长总长度的度的1/2，那么，全圈就没有迂回，那么，全圈就没有迂回现现象，象，这这个个线线路流向路流向图图就是最就是最优优的，的，对应对应的方案就是最的方案就是最优优运运输输方案。方案。否否则则，转转向第三步。向第三步。v 第第3 3步步 重

10、新去段破圈，调整流向。在超过全圈总长重新去段破圈，调整流向。在超过全圈总长1/21/2的里（外）圈各段流向线上减去最小运量，然后在的里（外）圈各段流向线上减去最小运量，然后在相反方向的外（里）圈流向线上和原来没有流向线的相反方向的外（里）圈流向线上和原来没有流向线的各段上，加上所减去的最小运量，这样可以得到一个各段上，加上所减去的最小运量，这样可以得到一个新的线路流向图，然后转到第二步检查有无迂回现象。新的线路流向图，然后转到第二步检查有无迂回现象。如此反复，直至得到最优线路流向图为止。如此反复，直至得到最优线路流向图为止。v 注：注：如果线路图存在两个及两个以上的圈，则如果线路图存在两个及两

11、个以上的圈，则需分别对各圈进行是否存在迂回线路的检查，如果需分别对各圈进行是否存在迂回线路的检查，如果各圈的里、外圈都不超过全圈总线长的各圈的里、外圈都不超过全圈总线长的1/21/2，则不，则不存在迂回现象，此方案为最优运输方案。存在迂回现象，此方案为最优运输方案。（2 2）解决【案例）解决【案例4.54.5】所涉及问题】所涉及问题第一步：去段破圈，形成初始方案v第二步：检查有无迂回现象。由图看出，不存在对流现第二步：检查有无迂回现象。由图看出，不存在对流现象，但是要检查里、外圈流向线长，看是否超过全圈总象，但是要检查里、外圈流向线长，看是否超过全圈总长的长的1/2。全圈总长全圈总长=（45+

12、23+25+18+23+36）km=170km半圈总长半圈总长=170/2km=85km外圈流向线长外圈流向线长=（45+25+18+23）km=111km里圈流向线长里圈流向线长=23km，v从计算结果看出，里圈流向线长从计算结果看出，里圈流向线长=23km，小于全圈总长，小于全圈总长的的1/2（85km），没有迂回现象。而外圈流向线长），没有迂回现象。而外圈流向线长111km，超过了全圈总长，超过了全圈总长1/2的的85km，可以断定，初始运输流向，可以断定，初始运输流向线路存在迂回现象，所对应的运输方案不是最优方案，必线路存在迂回现象，所对应的运输方案不是最优方案，必须进行优化调整。须进

13、行优化调整。v第三步第三步 调整初始方案调整初始方案v 初始运输中，外圈流向线路中运量最小的是初始运输中，外圈流向线路中运量最小的是A1A1至至B1B1的的“20”20”，所以，去掉，所以，去掉A1A1到到B1B1的线路，并在外圈各段流向线的线路，并在外圈各段流向线路上减去最小运量路上减去最小运量“20”20”，同时在里圈各段流向线上和原，同时在里圈各段流向线上和原来没有流向线的来没有流向线的A1A1到到B2B2上，各加上最小运量上，各加上最小运量“20”20”，这样，这样可以得到一个新的线路流向图可以得到一个新的线路流向图v检查新运输线路图的里、外圈流向线长，看是检查新运输线路图的里、外圈流

14、向线长，看是否超过全圈（封闭回路线）总长的否超过全圈（封闭回路线）总长的1/2。新的。新的流向线路图相关情况是：流向线路图相关情况是：v外圈流向总长外圈流向总长=（25+18+23）km=66kmv里圈流向总长里圈流向总长=（23+36）km=59kmv两者均没有超过全圈总的两者均没有超过全圈总的1/2，即，即85km，所以，所以调整后的新线路流向图所对应的方案为最优运调整后的新线路流向图所对应的方案为最优运输方案。输方案。v之所以说调整后的新线路流向图所对应的方案为最优之所以说调整后的新线路流向图所对应的方案为最优运输方案，可以将它与初始运输方案进行对比：运输方案，可以将它与初始运输方案进行

15、对比：按调整后的新方案组织运输，运力消耗为按调整后的新方案组织运输，运力消耗为（2036+1023+2013+3023+3025+4018+8029+20127）tkm=8230tkm按初始方案组织运输的运力消耗为按初始方案组织运输的运力消耗为（2045+1023+5025+8029+20127+2013+3023+6018）tkm=9270tkm任务实施任务实施 寻求最优运输方案寻求最优运输方案 图图3-2是一个单位的运输是一个单位的运输线路图。图中，线路图。图中，、是产地，是产地，、是销地。是销地。起运站（目的地）之间线起运站（目的地）之间线路旁括号内标注的数字表路旁括号内标注的数字表示两点之间的距离。示两点之间的距离。如何如何找到最优运输方案？找到最优运输方案？技能训练技能训练图图3-23-2成圈的运输线路成圈的运输线路考核与评价考核与评价v一、小组抢答（一、小组抢答（1个个/公司）公司）v二、参考答案（教师总结）二、参考答案（教师总结）v三、评价及奖励结果公布三、评价及奖励结果公布v四、学习收获一句话及下次课预告四、学习收获一句话及下次课预告