任务五_优化运输路线

1、配货管理配货管理本课程教学的组织本课程教学的组织任务五 配送运输的线路优化任务描述任务描述 任务五 优化物流运输的线路 案例放送案例放送A1A2A4A3B2B3B5B4B1（36）+20（45）（23）（18）（25）（23）（29）（127）（13）+60+100+20-30-30-50-70-20图图4-1 4-1 康鑫全药业集团公司特效药品交通线路图康鑫全药业集团公司特效药品交通线路图案例研讨案例研讨 优化物流运输线路与运输线路开发有区别，它是优化物流运输线路与运输线路开发有区别，它是在已知货物名称及数量、货源地和目的地的情况下，在已知货物名称及数量、货源地和目的地的情况下，根据运输合理

2、化原则对运输线路的选择与优化。根据运输合理化原则对运输线路的选择与优化。 物流运输合理化要求以最佳的运输线路、最快的物流运输合理化要求以最佳的运输线路、最快的运输速度和最低的运输费用等将物品从原产地运送到运输速度和最低的运输费用等将物品从原产地运送到目的地，案例中康鑫全集团的目的地，案例中康鑫全集团的4 4个生产供应点，个生产供应点，5 5个批个批发配送点，线路图中有成圈的，有不成圈的，属于相发配送点，线路图中有成圈的，有不成圈的，属于相对复杂的情况。应该如何安排，才能达到路程最近和对复杂的情况。应该如何安排，才能达到路程最近和时间及费用最省？经过本单元以下内容的学习，可以时间及费用最省？经过

3、本单元以下内容的学习，可以找到解决问题的办法找到解决问题的办法。任务五 优化物流运输的线路 相关知识相关知识任务五 优化物流运输的线路v 物流运输线路，从起点到终点，常见的有物流运输线路，从起点到终点，常见的有不成圈的直线、丁字线、交叉线和分支线，不成圈的直线、丁字线、交叉线和分支线，还有形成闭合回路的环形线路，环形线路包还有形成闭合回路的环形线路，环形线路包括有一个圈和多个圈的。尽管线路的类型颇括有一个圈和多个圈的。尽管线路的类型颇多，但是可以将其归纳为以下多，但是可以将其归纳为以下三个基本类型三个基本类型一、物流运输线路的类型一、物流运输线路的类型（一）单一装货地和单一卸货地的物流运输线（

4、一）单一装货地和单一卸货地的物流运输线路路v 如图如图4-2是路路通运输公司签订了的一项运是路路通运输公司签订了的一项运输合同，要把输合同，要把A城的一批化肥运送到城的一批化肥运送到J城，路城，路路通公司根据这两个城市之间可选择的行车路通公司根据这两个城市之间可选择的行车线路绘制的公路网络。其中线路绘制的公路网络。其中A点表示装货地点表示装货地，J点是卸货地。此类运输线路的特点是点是卸货地。此类运输线路的特点是A点点和和J点是两个点，不重合。这是运输活动中的点是两个点，不重合。这是运输活动中的一种情况。一种情况。 B CA DG E H J I8012874741161161405011238

5、122110381463388056 F图图4-24-2公路网络示意图公路网络示意图（二）起点与终点为同一地点的物流运输线路（二）起点与终点为同一地点的物流运输线路v 在运输生产实践中，自有车辆运输时，车辆往往在运输生产实践中，自有车辆运输时，车辆往往要回到起点。或者是某物流中心送货到配送中心然要回到起点。或者是某物流中心送货到配送中心然后返回物流中心的线路；或某配送中心送货上门后后返回物流中心的线路；或某配送中心送货上门后返回，这就是属于起点与终点为同一地点的情况。返回，这就是属于起点与终点为同一地点的情况。如图如图4-3（a）中，从）中，从V1经过经过V2、V3、V4、V5和和V6回到回到

6、V1，V1既是起点，也是终点。始发点和终点既是起点，也是终点。始发点和终点相重合的线路选择问题通常被称为相重合的线路选择问题通常被称为“旅行推销员旅行推销员”问题、货郎担问题或者中国邮递员邮路问题问题、货郎担问题或者中国邮递员邮路问题。（a a）不合理的运输路线）不合理的运输路线（b b）合理的运输路线）合理的运输路线V3V2V1V6V4V5V2V4V5V6V1V3图图4-34-3运输线路示意图运输线路示意图（三）多起点、多终点问题的物流运输线路（三）多起点、多终点问题的物流运输线路v 多起点、多终点问题的物流运输线路，在物多起点、多终点问题的物流运输线路，在物流运输实践中，经常存在。如多个供

7、应商供应流运输实践中，经常存在。如多个供应商供应给多个工厂的情况，或者把不同工厂生产的同给多个工厂的情况，或者把不同工厂生产的同一产品分配到不同用户的问题。在这些问题中一产品分配到不同用户的问题。在这些问题中，起点和终点都不是单一的。在这类问题中，起点和终点都不是单一的。在这类问题中，各供应点的供应量往往也有限制。各供应点的供应量往往也有限制。v 在多个货源地服务于多个目的地时，物流运在多个货源地服务于多个目的地时，物流运输线路存在两种情况：运输线路成圈的和不成输线路存在两种情况：运输线路成圈的和不成圈的。圈的。v 案例广西康鑫全药业集团公司案例广西康鑫全药业集团公司“护肝王护肝王”特效药的生

8、产和销售的交通线路（特效药的生产和销售的交通线路（图图4-14-1），），从公路运输线路看，从公路运输线路看，A1-B2-B3-B4-A2-B1A1-B2-B3-B4-A2-B1构成构成一个圈，其余的不成圈。一个圈，其余的不成圈。二、物流运输线路的选择优化二、物流运输线路的选择优化v（一）单一装货地和单一卸货地的物流运输线（一）单一装货地和单一卸货地的物流运输线路的选择优化路的选择优化最短路径法最短路径法 在图在图4-2中，路路通运输公司要在装货地中，路路通运输公司要在装货地A点，满载点，满载货物到货物到J点卸货。点卸货。B、C、D、E、F、G、H、和、和I是是网络中的站点，站点之间以线路连接

9、，线路上标明网络中的站点，站点之间以线路连接，线路上标明了两个站点之间的距离。从图了两个站点之间的距离。从图2-可以看出，从可以看出，从A地地到到J地，有很多条线路可以选择，然而，运输线路地，有很多条线路可以选择，然而，运输线路选择优化的任务就是要找出使总路程的长度最短的选择优化的任务就是要找出使总路程的长度最短的线路。这就是运输规划中的最短线路问题，通常称线路。这就是运输规划中的最短线路问题，通常称为最短路径法，或者称最短路线方法。即是列出最为最短路径法，或者称最短路线方法。即是列出最短运输线路计算表（如表短运输线路计算表（如表1-1），分步骤地计算。），分步骤地计算。通过比较，选择走近路。

10、通过比较，选择走近路。表表1-1 最短运输线路计算表最短运输线路计算表表表1-1最短运输线路计算表（续）最短运输线路计算表（续）v步骤步骤1：在图：在图4-1可以看出，装货地可以看出，装货地A即是起点，即是起点，是第一个已解的节点。与是第一个已解的节点。与A点直接连接的未解的点直接连接的未解的节点有节点有B、C和和D点。点。B到到A的距离最短，所以是的距离最短，所以是唯一的选择，成为已解的节点。唯一的选择，成为已解的节点。v步骤步骤2 2：是找出距离已解：是找出距离已解A A点和点和B B点最近的未解节点最近的未解节点。只要列出距各个已解节点最近的连接点，点。只要列出距各个已解节点最近的连接点

11、，则有则有A-CA-C，B-CB-C。注意从起点通过已解节点到某注意从起点通过已解节点到某一节点所需的路程应该等于到达这个已解节点一节点所需的路程应该等于到达这个已解节点的最短路程加上已解节点与未解节点之间的路的最短路程加上已解节点与未解节点之间的路程。程。即从即从A A经过经过B B到达到达C C的距离为的距离为80+56=13680+56=136公里，公里，而从而从A A直达直达C C的距离为的距离为128128公里。现在公里。现在C C点也成为点也成为已解节点。已解节点。v步骤步骤3：要找出与各已解节点直接连接的最近的未：要找出与各已解节点直接连接的最近的未解节点。在图解节点。在图4-1

12、5上可见，在与已解节点上可见，在与已解节点A、B、C直接连接的有直接连接的有D、E、F三个点，自起点到三个候三个点，自起点到三个候选点的路程分别是选点的路程分别是338、154、208公里，其中连公里，其中连接接BE的路程最短，为的路程最短，为154公里。因此，公里。因此，E点为所选点为所选。v重复上述过程，直至到达终点重复上述过程，直至到达终点J J，即步骤，即步骤8 8。由此。由此得到最优线路为得到最优线路为A-B-E-I-JA-B-E-I-J，最短的路程的，最短的路程的344344公公里。里。v 最短路径法可以利用计算机进行求解。把最短路径法可以利用计算机进行求解。把运输网络中的线路（有

13、的称为链）和节点的资运输网络中的线路（有的称为链）和节点的资料都存入数据库中，选好起点和终点后，计算料都存入数据库中，选好起点和终点后，计算机可以很快就算出最短路径。机可以很快就算出最短路径。v 此计算的结果，称为单纯的最短距离路径，此计算的结果，称为单纯的最短距离路径，并未考虑各条线路的运行质量。不能说明穿越并未考虑各条线路的运行质量。不能说明穿越网络的最短时间。因此，对运行时间和距离都网络的最短时间。因此，对运行时间和距离都设定权数就可以得出比较具有实际意义的线路。设定权数就可以得出比较具有实际意义的线路。案例案例 单一装货地和单一卸货地的物流运输线路的选择优单一装货地和单一卸货地的物流运

14、输线路的选择优化化 某连锁超市的配送中心位于城市边缘的郊区，但超市某连锁超市的配送中心位于城市边缘的郊区，但超市的一家门店位于繁华的城市中心区，因此负责送货路线规的一家门店位于繁华的城市中心区，因此负责送货路线规划的计划调度员要规划出配送中心到这个门店的送货成本划的计划调度员要规划出配送中心到这个门店的送货成本最低的路线。最初按交通图所示里程最短的线路进行送货最低的路线。最初按交通图所示里程最短的线路进行送货，见下图，见下图4-4： 任务实施任务实施1 1OAV4V2V3V1235223396图图4-4中中O代表配送中心，代表配送中心，A代表门店，代表门店，V1V4代代表要经过的关键节点（如主

15、要道路的交叉路口、表要经过的关键节点（如主要道路的交叉路口、立体交叉互通枢纽等），连线边上的数值代表每立体交叉互通枢纽等），连线边上的数值代表每一路段的里程，图中绿线连接的一路段的里程，图中绿线连接的O-V1-V4-A为里为里程最短线路。程最短线路。但但很快发现里程最短并不意味着成本最低，因为里程最短很快发现里程最短并不意味着成本最低，因为里程最短这条路有一条新建的大桥（图中这条路有一条新建的大桥（图中V4点与点与A点之间黑色加粗点之间黑色加粗部分）来回都要收取通行费，这条路是城区主干道且建成部分）来回都要收取通行费，这条路是城区主干道且建成时间较长通行条件较差，越往城中心走道路拥堵越严重，时

16、间较长通行条件较差，越往城中心走道路拥堵越严重，每趟送货产生的油耗、车辆送货时间占用、送货人员工作每趟送货产生的油耗、车辆送货时间占用、送货人员工作时间等综合成本超出了正常水平，并且多次发生没按门店时间等综合成本超出了正常水平，并且多次发生没按门店的要求时间送达的情况。因此计划调度员对每一条能从的要求时间送达的情况。因此计划调度员对每一条能从O到到A的线路都进行了实地勘察记录，并综合考虑每条送货的线路都进行了实地勘察记录，并综合考虑每条送货线路的里程、时间、车辆耗损，得出了每条线路每一个路线路的里程、时间、车辆耗损，得出了每条线路每一个路段的送货运行成本，汇总出了一张从配送中心到此门店的段的送

17、货运行成本，汇总出了一张从配送中心到此门店的送货路径数据图。现在计划调度员要依据此图，找出配送送货路径数据图。现在计划调度员要依据此图，找出配送中心与该门店之间送货成本最低路径。中心与该门店之间送货成本最低路径。OAV4V2V3送中心与位于城中心门店之间的网络路线图，图配送中心与位于城中心门店之间的网络路线图，图4-5中中O代表配送中心，代表配送中心，A代表门店，代表门店，V1V4代表要经过的关键节代表要经过的关键节点（如主要道路的交叉路口、立体交叉互通枢纽等），连点（如主要道路的交叉路口、立体交叉互通枢纽等），连线边上的数值代表每一路段送货运行的最低成本值。线边上的

18、数值代表每一路段送货运行的最低成本值。v一、小组抢答（一、小组抢答（1个个/公司）公司）v二、参考答案（教师总结）二、参考答案（教师总结）v三、评价及奖励结果公布三、评价及奖励结果公布v四、学习收获一句话及下次课预告四、学习收获一句话及下次课预告教师总结教师总结第一步：第一步：O点是原始已解节点，从配送中心O点出发，可以走V1、V2两个节点，由于OV13、OV211，因此选择走OV1线路，V1成为已解节点，见下图。OAV4V2V3二步：第二步： 与O、V1两个已解节点相连的未解节点有V2、V3、V4，可选择的送货路线为：O-V1-V4、O-V1-V3、O-V2，相应的

19、送货成本值为： O-V1-V43+14O-V1-V33+710O-V211O-V1-V4线路的成本最少，因此V4成为已解节点，见下图。OAV4V2V3三步：第三步： 与O、V1、V4三个已解节点相连的未解节点有V2、V3、A，可选择的送货路线为：O-V1-V4-A、O-V1-V4-V3、O-V1-V3、O-V2，相应的送货成本值为：O-V1-V4-A3+1+812O-V1-V4-V33+1+37O-V1-V33+710O-V211O-V1-V4-V3线路的成本最少，因此V3成为已解节点，见下图。OAV4V2V3四步：第四步：与O、V1、V4、

20、V3四个已解节点相连的未解节点有V2、 A，可选择的送货路线为：O-V1-V4-V3-A、O-V1-V4-V3-V2、O-V1-V3-A、O-V1-V3-V2、O-V2，相应的送货成本值为：O-V1-V4-V3-A3+1+3+411O-V1-V4-V3-V23+1+3+18O-V1-V3-A3+7+414O-V1-V3-V23+7+111O-V211O-V1-V4-V3-V2线路的成本最少，因此V2成为已解节点，见下图。OAV4V2V3五步：第五步：与O、V1、V4、V3、V2五个已解节点相连的未解节点只有A，可选择的送货路线为：O-V1-V4-V3-A、O-V1-V

21、4-V3-V2-A、O-V1-V3-A、O-V1-V3-V2-A、O-V2-A、O-V1-V4-A，相应的送货成本值为：O-V1-V4-V3-A3+1+3+411O-V1-V4-V3-V2-A3+1+3+1+210O-V1-V3-A3+7+414O-V1-V3-V2-A3+7+1+213O-V2-A11+213O-V1-V4-A3+1+812O-V1-V4-V3-V2-A线路的成本最少，因此这条线路是配送中心与该门店之间成本最低的送货线路，线路的送货成本数值为10，见下图。OAV4V2V3论：结论：最后通过与实训情境中里程最短路线O-V1-V4-A的成本比较一下，里程

22、最短路线的成本为12，成本最小路线O-V1-V4-V3-V2-A的成本为10。（二）起点与终点为同一地点的物流运输线（二）起点与终点为同一地点的物流运输线路的选择优化路的选择优化v 起点与终点为同一地点（起迄点重合）的物流运起点与终点为同一地点（起迄点重合）的物流运输线路的选择优化，目标是找到一个可以走遍所有输线路的选择优化，目标是找到一个可以走遍所有地点的最佳顺序，使运输车辆必须经过所有站点并地点的最佳顺序，使运输车辆必须经过所有站点并且总距离或运输时间最短。可以分为两种情况：且总距离或运输时间最短。可以分为两种情况：v1.1.规模很大规模很大 规模很大，即是包含站点很多。某次运输在很多规模

23、很大，即是包含站点很多。某次运输在很多个站点的规模中找到最优路径，是不切合实际的。个站点的规模中找到最优路径，是不切合实际的。此情况不是我们讨论的范围。此情况不是我们讨论的范围。 2.2.规模比较小规模比较小 对于规模相对比较小的情况，可以应用经验试探对于规模相对比较小的情况，可以应用经验试探法加以解决。其步骤是：法加以解决。其步骤是： （1）掌握来自实践的经验。）掌握来自实践的经验。经验经验是：合理的经停是：合理的经停线路中各条线路之间是不交叉的，并且只要有可线路中各条线路之间是不交叉的，并且只要有可能路径就会呈凸形或水滴状。能路径就会呈凸形或水滴状。 （2）根据经验作出判断。按照）根据经验

24、作出判断。按照“线路不交叉线路不交叉”和和“凸形或水滴状凸形或水滴状”的两条原则，画出线路规划图的两条原则，画出线路规划图，如图，如图4-3所示。图所示。图4-3所示的是通过各点的运行线所示的是通过各点的运行线路示意图，都是经过所有站点，但是先后次序不路示意图，都是经过所有站点，但是先后次序不同，即线路不同。其中同，即线路不同。其中A是不合理的运行线路，是不合理的运行线路，B是合理的运行线路。是合理的运行线路。(1)(1)节约里程法假设条件节约里程法假设条件节约里程法节约里程法(2)(2)节约里程法原理节约里程法原理 已知已知P P点为配送中心，它分别向用户点为配送中心，它分别向用户A A和和

25、B B送货，送货，P P到到A A和和B B的距离分别为的距离分别为a a、b b，A A和和B B之间的距离为之间的距离为c c，送货方案只有以，送货方案只有以下两种：下两种：ABPABP方案方案从上图可以得知：方案从上图可以得知：方案的配送距离为：的配送距离为：2a+2b2a+2b 方案方案的配送距离为：的配送距离为：a+b+ca+b+c 显然：显然： 2a+2b2a+2ba+b+c a+b+c （为什么？）（为什么？） 例：某连锁零售店，下设有一个配送中心例：某连锁零售店，下设有一个配送中心P P和和1010个连锁个连锁分店分店A AJ J，配送中心和各连锁分店及各连锁分店之间的位，配送

26、中心和各连锁分店及各连锁分店之间的位置关系如下图所示，两点间连线上的数字为两点间的路置关系如下图所示，两点间连线上的数字为两点间的路线长度（单位：公里），括号内的数字为各连锁分店对线长度（单位：公里），括号内的数字为各连锁分店对某种商品的需求量（单位：某种商品的需求量（单位：t t）。该商品由配送中心统一）。该商品由配送中心统一采购并进行配送。配送中心备用采购并进行配送。配送中心备用2t2t和和4t4t的货车，限定送的货车，限定送货车辆一次巡回距离不超过货车辆一次巡回距离不超过3030公里，设送到时间均符合公里，设送到时间均符合用户要求，求配送中心的最优送货方案。用户要求，求配送中心的最优送货

27、方案。BFEPGDCAIJH第一步：计算各点之间的最短距离第一步：计算各点之间的最短距离IJGHEFCDAPAPBCDEIGHFJB第二步：计算分店之间的节约里程第二步：计算分店之间的节约里程CGHIJEFDABACBEDGFIHJ第三步：将上述所得的节约里程按从大到小排序第三步：将上述所得的节约里程按从大到小排序EF69121196BJCEBDACIJAB146423DEAICDBCAJ顺序排位连接线BE9319867892222222119CJFIEGGIDF11123顺序排位15131091013111616161313节约里程FG5BIFHADHIGH44455连接线节约里程第四步：确

28、定配送线路第四步：确定配送线路（1 1）初始方案：对每个客户分别单独派车送货）初始方案：对每个客户分别单独派车送货BFEPGDCAIJH883410710978配送距离：148km配送车辆：2t10(2)(2)修正方案修正方案1 1：按节约里程大小顺序，连接：按节约里程大小顺序，连接A A和和B B，A A和和J J，B B和和C C配送线路：7条配送距离：109km配送车辆：2t6+ 4t1BFEPGDCAIJH883471057844（3 3）修正方案）修正方案2 2：连接：连接D D和和E E形成一个新的线路形成一个新的线路BFEPGDCAIJH8834710578446配送线路：6条配

29、送距离：99km配送车辆：2t5+ 4t1（4 4）修正方案）修正方案3 3：将：将F F并入线路并入线路BFEPGDCAIJH7834710578446配送线路：5条配送距离：90km配送车辆：2t3+ 4t2（5 5）修正方案）修正方案4 4：将：将G G点并入线路点并入线路BFEPGDCAIJH7834710576446配送线路：4条配送距离：85km配送车辆：2t2+ 4t2（6 6）最终方案：将）最终方案：将H H和和I I连接形成新的线路连接形成新的线路BFEPGDCAIJH7834710576446配送线路：3条配送距离：80km配送车辆：2t1+ 4t2 任务实施任务实施2 2

30、212066991212241019v一、团队抢答（一、团队抢答（1个个/公司）公司）v二、参考答案（教师总结）二、参考答案（教师总结）v三、评价及奖励结果公布三、评价及奖励结果公布v四、学习收获一句话及下次课预告四、学习收获一句话及下次课预告教师总结教师总结第一步：第一步：根据根据“配送中心到各门店及两两门店之间成本最低线路的数配送中心到各门店及两两门店之间成本最低线路的数值表（见上表）值表（见上表）”和节约法的基本原理，计算出两两门店之和节约法的基本原理，计算出两两门店之间的最小成本值及节约成本。计算方法是：间的最小成本值及节约成本。计算方法是：i,j是任意相邻两是任意相邻两门店节点门店节

31、点Oi=a，OJ=b，ij=c，则，则 ij节约的成本为：节约的成本为：a+b-c 。计算结果填入下表中。计算结果填入下表中。第二步：第二步：根据上表中的出两两门店之间的节约成本计算结果，按节约成本大小顺序排列到下表中。第三步：方案调整第三步：方案调整EG节约里程最大，从表3-2中得知，它们的配送货物量是：175 + 115 =29 t，在货车载重限度内，可以入选。FG的配送货物量11 t，正好可以与29 t拼装为一辆4 t货车的载运量，它们相互衔接成为一条路线AEGFA。全程为20 + 1 + 6 + 24 = 51 km。因4 t货车已装满，所以应考虑第二条配送路线。C，D配送货物量是10

32、 + 07 = 17 t，在货车载重限度内，可以将B点的08 t货物集中在一起，拼装为一辆25 t货车的载运量，形成第二条配送路线ABCDA或ADCBA，全程为9 + 9 + 10 + 12 = 40 km。 此案例的配送路线优化后确定为二条，即AEGFA和ABCDA（ADCBA），总行程为51 + 40 = 91 km，使用4 t和25 t的货车各一辆。结论 使用4 t和25 t的货车各一辆 总节约里程: (9+12+12+24+20+21)*2-91=105B=2.5tA=4t 案例放送案例放送A1A2A4A3B2B3B5B4B1（36）+20（45）（23）（18）（25）（23）（29

33、）（127）（13）+60+100+20-30-30-50-70-20图图4-1 4-1 康鑫全药业集团公司特效药品交通线路图康鑫全药业集团公司特效药品交通线路图（三）多起点、多终点的物流运输线路的选（三）多起点、多终点的物流运输线路的选择优化择优化v 有多个货源地服务于多个目的地时，物流运输线路选择优化有多个货源地服务于多个目的地时，物流运输线路选择优化的任务是要指定为各目的地服务的供货地，同时要找到供货的任务是要指定为各目的地服务的供货地，同时要找到供货地、目的地之间的最佳路径。解决这类问题可以运用一类特地、目的地之间的最佳路径。解决这类问题可以运用一类特殊的线性规划方法即物资调运问题殊的

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

35、严格限制的情况。v图上作业法的求解规则可以归纳为：图上作业法的求解规则可以归纳为：流向划右流向划右方，对流不应当；里圈、外圈分别算，要求不方，对流不应当；里圈、外圈分别算，要求不能过半圈长；若超过半圈长，应去运量最小段；能过半圈长；若超过半圈长，应去运量最小段；反复运算可得最优方案。反复运算可得最优方案。v图上作业法包括运输线路不成圈的图上作业法图上作业法包括运输线路不成圈的图上作业法和运输线路成圈的图上作业法。和运输线路成圈的图上作业法。1.1.运输线路不成圈的图上作业法运输线路不成圈的图上作业法v 对于线路不成圈的货物运输，即是不构成回路的运输对于线路不成圈的货物运输，即是不构成回路的运输

36、线路，包括直线、丁字线、交叉线和分支线等。只要线路，包括直线、丁字线、交叉线和分支线等。只要不出现对流和迂回现象，就是最优调运方案。不出现对流和迂回现象，就是最优调运方案。v 运输线路不成圈的图上作业法较简单。就是从各端运输线路不成圈的图上作业法较简单。就是从各端点开始，按点开始，按“各站供需就近调拨各站供需就近调拨”的原则进行调配。的原则进行调配。v 如图如图3-13-1是某地区的物资供应网络，有是某地区的物资供应网络，有4 4个起运站个起运站、，供应量分别为，供应量分别为+7+7、+8+8、+6+6、+4+4单位（为单位（为了便于识别，供应量记了便于识别，供应量记“+ +”，需求量记，需求

37、量记“- -”）；另）；另有有4 4个目的地个目的地、，需求量分别为，需求量分别为-2-2、-8-8、-7-7、-8-8。为了便于检查对流现象，把流向箭头统一画。为了便于检查对流现象，把流向箭头统一画在右侧。箭头旁标注的数字表示调运量。在右侧。箭头旁标注的数字表示调运量。图图3-1 3-1 运输线路不成圈的调运方案运输线路不成圈的调运方案58-85-77248-8+8+7-2+4+6v具体调运方案是：具体调运方案是：v 从站点从站点开始，把开始，把7 7个单位的物资供应给个单位的物资供应给，剩余剩余5 5个单位，供应给个单位，供应给；站点；站点的的8 8个单位由个单位由供应；供应；剩余的剩余的

38、5 5个单位供应给个单位供应给，尚缺少尚缺少2 2单位由单位由提供。提供。的的4 4个单位经过个单位经过，连，连原有原有的的4 4单位合计单位合计8 8单位供给单位供给。这样就得出一个最优。这样就得出一个最优调运方案。调运方案。2.2.运输线路成圈的图上作业法运输线路成圈的图上作业法v 运输线路成圈，就是形成闭合回路的环形线路，包括一个运输线路成圈，就是形成闭合回路的环形线路，包括一个圈和多个圈。在图圈和多个圈。在图3-2中，包含有两个圈，一是由中，包含有两个圈，一是由、组成的圈；另一是由组成的圈；另一是由、组组成的圈。圈可以是三角形、四边形和多边形。图成的圈。圈可以是三角形、四边形和多边形。

39、图3-6中的两中的两个圈都是多边形。起运站（目的地）之间线路旁括号内标注个圈都是多边形。起运站（目的地）之间线路旁括号内标注的数字表示两点之间的距离。的数字表示两点之间的距离。v 对于成圈运输线路的图上作业法，可以按照如下三个步对于成圈运输线路的图上作业法，可以按照如下三个步骤求解，直到寻求到最优方案。成圈的线路流向图要同时达骤求解，直到寻求到最优方案。成圈的线路流向图要同时达到既无对流现象，又无迂回现象的要求才是最优流向图，所到既无对流现象，又无迂回现象的要求才是最优流向图，所对应的方案为最优运输方案。对应的方案为最优运输方案。 图图3-23-2运输线路成圈的调运方案运输线路成圈的调运方案v

40、 第第1步步 去段破圈，确定初始运输方案。在成圈的线路去段破圈，确定初始运输方案。在成圈的线路中，先假设某两点间的线路中，先假设某两点间的线路“不通不通”，去掉这段线路，去掉这段线路，把成圈线路转化为不成圈的线路，即破圈；然后按照运把成圈线路转化为不成圈的线路，即破圈；然后按照运输线路不成圈的图上作业法，即可得到初始运输方案。输线路不成圈的图上作业法，即可得到初始运输方案。v 第第2 2步步 检查有无迂回现象。因为流向箭头都统一画检查有无迂回现象。因为流向箭头都统一画在线路右边，所以圈内圈外都画有一些流向。分别检查在线路右边，所以圈内圈外都画有一些流向。分别检查每个小圈，如果内圈和外圈流向的总

41、长度都不超过全圈每个小圈，如果内圈和外圈流向的总长度都不超过全圈总长度的总长度的1/21/2，那么，全圈就没有迂回现象，这个线路流，那么，全圈就没有迂回现象，这个线路流向图就是最优的，对应的方案就是最优运输方案。否则，向图就是最优的，对应的方案就是最优运输方案。否则，转向第三步。转向第三步。v 第第3 3步步 重新去段破圈，调整流向。在超过全圈总长重新去段破圈，调整流向。在超过全圈总长1/21/2的里（外）圈各段流向线上减去最小运量，然后在相的里（外）圈各段流向线上减去最小运量，然后在相反方向的外（里）圈流向线上和原来没有流向线的各段上，反方向的外（里）圈流向线上和原来没有流向线的各段上，加上

42、所减去的最小运量，这样可以得到一个新的线路流向加上所减去的最小运量，这样可以得到一个新的线路流向图，然后转到第二步检查有无迂回现象。如此反复，直至图，然后转到第二步检查有无迂回现象。如此反复，直至得到最优线路流向图为止。得到最优线路流向图为止。v 如果线路图存在两个及两个以上的圈，则需分别对各如果线路图存在两个及两个以上的圈，则需分别对各圈进行是否存在迂回线路的检查，如果各圈的里、外圈都圈进行是否存在迂回线路的检查，如果各圈的里、外圈都不超过全圈总线长的不超过全圈总线长的1/21/2，则不存在迂回现象，此方案为，则不存在迂回现象，此方案为最优运输方案。最优运输方案。 现在，解决【案例现在，解决

43、【案例4.34.3】所涉及问题。】所涉及问题。v （1）去段破圈，确定初始运输方案。在图）去段破圈，确定初始运输方案。在图4-1中，中，A1（南宁）（南宁）-B2（合山）（合山）-B3（宜州）（宜州）-B4（河池）（河池）-A2（巴马）（巴马）-B1（平果）组成的圈，去掉（平果）组成的圈，去掉A1至至B2的线路，然后根据的线路，然后根据“各站供需就近调拨各站供需就近调拨”的原则进的原则进行调运，即可得到初始运输流向线路图，如图行调运，即可得到初始运输流向线路图，如图1.4-6所示。所示。v（2）检查有无迂回现象。由图）检查有无迂回现象。由图1.4-6看出，不存看出，不存在对流现象，但是要检查里

44、、外圈流向线长，看在对流现象，但是要检查里、外圈流向线长，看是否超过全圈总长的是否超过全圈总长的1/2。 全圈总长全圈总长=（45+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，可以断定，初始运输流向，

45、可以断定，初始运输流向线路存在迂回现象，所对应的运输方案不是最优方案，线路存在迂回现象，所对应的运输方案不是最优方案，必须进行优化调整。必须进行优化调整。v （3 3）重新去段破圈，调整流向。）重新去段破圈，调整流向。v 初始运输中，外圈流向线路中运量最小的是初始运输中，外圈流向线路中运量最小的是A1A1至至B1B1的的“20”20”，所以，去掉，所以，去掉A1A1到到B1B1的线路，并在外圈各段流的线路，并在外圈各段流向线路上减去最小运量向线路上减去最小运量“20”20”，同时在里圈各段流向线，同时在里圈各段流向线上和原来没有流向线的上和原来没有流向线的A1A1到到B2B2上，各加上最小运量

46、上，各加上最小运量“20”20”，这样可以得到一个新的线路流向图，如图，这样可以得到一个新的线路流向图，如图1.3-71.3-7所示。所示。v检查新运输线路图的里、外圈流向线长，看是检查新运输线路图的里、外圈流向线长，看是否超过全圈（封闭回路线）总长的否超过全圈（封闭回路线）总长的1/2。新的。新的流向线路图相关情况是：流向线路图相关情况是：v外圈流向总长外圈流向总长=（25+18+23）km=66kmv里圈流向总长里圈流向总长=（23+36）km=59kmv两者均没有超过全圈总的两者均没有超过全圈总的1/2，即，即85km，所以，所以调整后的新线路流向图所对应的方案为最优运调整后的新线路流向

47、图所对应的方案为最优运输方案。输方案。v之所以说调整后的新线路流向图所对应的方案为最优之所以说调整后的新线路流向图所对应的方案为最优运输方案，可以将它与初始运输方案进行对比：运输方案，可以将它与初始运输方案进行对比： 按调整后的新方案组织运输，运力消耗为按调整后的新方案组织运输，运力消耗为（2036+1023+2013+3023+3025+4018+8029+20127）tkm=8230tkm 按初始方案组织运输的运力消耗为按初始方案组织运输的运力消耗为（2045+1023+5025+8029+20127+2013+3023+6018）tkm =9270tkmv可见，调整后的运输方案比初始运输

48、方案节约运可见，调整后的运输方案比初始运输方案节约运力力1040tkm，当然是最优运输方案。，当然是最优运输方案。v多起点、多终点的物流运输线路的选择优化方法多起点、多终点的物流运输线路的选择优化方法，还有表上作业法等，限于篇幅，此处暂时不加，还有表上作业法等，限于篇幅，此处暂时不加以介绍。以介绍。项目项目 寻求最优运输方案寻求最优运输方案 图图3-2是一个单位的运输是一个单位的运输线路图。图中，线路图。图中，、 、 、 是产地，是产地， 、 、 、是销地。起运站是销地。起运站（目的地）之间线路旁括（目的地）之间线路旁括号内标注的数字表示两点号内标注的数字表示两点之间的距离。之间的距离。如何找

49、到最如何找到最优运输方案？优运输方案？ 技能训练技能训练图图1-71-7成圈的运输线路成圈的运输线路v一、各公司提供答案（一、各公司提供答案（1个个/公司）公司）v二、参考答案（见给你提个醒）二、参考答案（见给你提个醒）v三、评价及奖励结果公布三、评价及奖励结果公布v四、学习收获一句话及下次课预告四、学习收获一句话及下次课预告给你提个醒给你提个醒v 如果运输线路全图存在两个及两个以上的圈，则需分别如果运输线路全图存在两个及两个以上的圈，则需分别对各圈进行是否存在迂回线路的检查，如果各圈的里、对各圈进行是否存在迂回线路的检查，如果各圈的里、外圈都不超过全圈总线长的外圈都不超过全圈总线长的1/2，

50、则不存在迂回现象，则，则不存在迂回现象，则此方案为最优运输方案。此方案为最优运输方案。 v 1.1.分别破圈。对于由分别破圈。对于由、组成的圈，组成的圈，去掉去掉至至的线路；在由的线路；在由、组成的圈组成的圈中，去掉中，去掉到到的线路，便得到不成圈的线路，从各端的线路，便得到不成圈的线路，从各端点开始，按点开始，按“各站供需就近调拨各站供需就近调拨”的原则进行调配，得的原则进行调配，得出调运方案，如图出调运方案，如图1-81-8。图中线路旁括号内的数字表示两。图中线路旁括号内的数字表示两点之间的距离，箭头线旁不带括号的数字表示调运量。点之间的距离，箭头线旁不带括号的数字表示调运量。v 1 去段

51、破圈，确定初始运输方案。在成圈的线路中，去段破圈，确定初始运输方案。在成圈的线路中，先假设某两点间的线路先假设某两点间的线路“不通不通”，去掉这段线路，把成，去掉这段线路，把成圈线路转化为不成圈的线路，即破圈；然后按照运输线圈线路转化为不成圈的线路，即破圈；然后按照运输线路不成圈的图上作业法，即可得到初始运输方案。路不成圈的图上作业法，即可得到初始运输方案。+8-7-8(50)(90)55246(50)+71238457-2+4+6-8(50)(200)(90)(30)(50)(100)788v 2.检查。在图检查。在图1-8上部的圈中，总长度为上部的圈中，总长度为580，调运方案，调运方案外

52、圈总长度为外圈总长度为50+50+90+100=290，内圈总长度为，内圈总长度为90，均不超过圈总长度的一半。而在图下部的圈中，总长度均不超过圈总长度的一半。而在图下部的圈中，总长度为为310，外圈总长度为，外圈总长度为50+90+50=190，大于圈总长度的，大于圈总长度的一半。所以，此方案不是最优方案，应当进行调整。一半。所以，此方案不是最优方案，应当进行调整。v 3.3.调整。办法是：去掉调整。办法是：去掉至至、至至的线路（因为的线路（因为至至是是、组成的圈中外圈各段流向线组成的圈中外圈各段流向线上的最小运量），运输线路就不成圈了。按照前述办法，上的最小运量），运输线路就不成圈了。按照

53、前述办法，做出调运方案如图做出调运方案如图1-91-9。图图1-91-9运输线路成圈的初始调运方案运输线路成圈的初始调运方案v 4.再检查。在图再检查。在图1-9上部的圈中，总长度的上部的圈中，总长度的1/2为为290，调，调运方案外圈总长度为运方案外圈总长度为50+50+90+100=290，内圈总长度，内圈总长度为为0，均不超过圈总长度的一半。在图，均不超过圈总长度的一半。在图1-9下部的圈中，下部的圈中，总长度的总长度的1/2为为155，外圈总长度为，外圈总长度为50+50=100，内圈总，内圈总长度为长度为30+90=120，外、内圈总长度均不超过全圈总长，外、内圈总长度均不超过全圈总

54、长度的一半（度的一半（155）。所以，图）。所以，图1-9方案是最优方案。方案是最优方案。课后自我检测课后自我检测v在给定的运输线路图在给定的运输线路图( (图图1-101-10) )上，运用图上作上，运用图上作业法，求出最优运输线路图。业法，求出最优运输线路图。A2A1A3A3图图1-101-10某集团公司物资供应交通线路图某集团公司物资供应交通线路图B1B5B7B3（78）-1500（75）（32）（109）（132）（74）（57）（13）+2000+2900-1000+3200-1300-600B8-900（55）B6B2B4-900-900（74）（45）（41）-1000v问题：优

55、化物流运输线路与运输线路开发问题：优化物流运输线路与运输线路开发“不是一码事不是一码事”主要区别是：优化物流运输线路是在已知货物主要区别是：优化物流运输线路是在已知货物名称及数量、货源地和目的地的情况下，根据名称及数量、货源地和目的地的情况下，根据运输合理化原则对运输线路的选择与优化，而运输合理化原则对运输线路的选择与优化，而运输线路的开发主要是根据当前物流市场环境运输线路的开发主要是根据当前物流市场环境、货源数量情况、政府规定等对运输线路的选、货源数量情况、政府规定等对运输线路的选择确定，两者在目的、市场环境等多方面不同择确定，两者在目的、市场环境等多方面不同，因此不是一码事。，因此不是一码

56、事。配送运输配送运输表上作业法表上作业法 例例1 1：有四个用户：有四个用户B1B1、B2B2、B3B3、B4B4所需的某种物品可由所需的某种物品可由三个配送中心三个配送中心A1A1、A2A2、A3A3供应，各配送中心的可供给量供应，各配送中心的可供给量和各用户的需求量以及各配送中心运送单位物品到各用和各用户的需求量以及各配送中心运送单位物品到各用户的运价（单位：百元户的运价（单位：百元/ /吨）见下表，求使总运费最小的吨）见下表，求使总运费最小的调运方案。调运方案。 9192第一步：确定初始方案第一步：确定初始方案最小元素法最小元素法 基本思想是按照运价的大小决定供应的先后，优先满足单位运价最小基本思想是按照运价的大小决定供应的先后，优先满足单位运价最小者的供需要求者的供需要求 40 1 5 3 6 3 7 2 3 5 4 4 2 70 50 301093 从上图可知，初始方案对应的总运费为：从上图可知，初始方案对应的总运费为： 70 702+302+303+503+504+404+401+101+102=4902=490（元）（元）94 第二步：用位势法（第二步：用位势法（霍撒克方法