物流运输规划.ppt

《物流运输规划.ppt》由会员分享，可在线阅读，更多相关《物流运输规划.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 物流运输规划物流运输规划第一节第一节 合理选择运输方式合理选择运输方式第二节第二节 运输问题及线型规划运输问题及线型规划第三节第三节 旅行路线问题与动态规划旅行路线问题与动态规划第四节第四节 图论方法的应用图论方法的应用第五节第五节 小结与案例小结与案例第一节第一节 合理选择运输方式合理选择运输方式一、铁路运输的特点一、铁路运输的特点（一）铁路运输的优点（一）铁路运输的优点1.运行速度快，时速可达运行速度快，时速可达80120公里公里2.运输能力较大，可满足大量货物一次高效率运输运输能力较大，可满足大量货物一次高效率运输3.运输连续性强，由于运输过程受气候条件限制较小，运输连续性

2、强，由于运输过程受气候条件限制较小，所以可提供全天候的运行所以可提供全天候的运行4.轨道运输的安全性能高，运行较平稳轨道运输的安全性能高，运行较平稳5.通用性能好，可以运送各类不同的货物通用性能好，可以运送各类不同的货物6.运输成本较低、能耗低运输成本较低、能耗低2第一节第一节 合理选择运输方式合理选择运输方式（二）铁路运输的缺点（二）铁路运输的缺点1.灵活性差，只能在固定线路上实现运输灵活性差，只能在固定线路上实现运输2.需要以其他运输手段配合和衔接需要以其他运输手段配合和衔接3.设备和站台等限制使得铁路运输的固定成本高，建设备和站台等限制使得铁路运输的固定成本高，建设周期较长，占用土地较多

3、设周期较长，占用土地较多4.铁路运输的固定成本很高，但变动成本相对较低，铁路运输的固定成本很高，但变动成本相对较低，使得近距离的运费较高使得近距离的运费较高5.长距离运输情况下，由于需要进行货车配车，其中长距离运输情况下，由于需要进行货车配车，其中途停留时间较长途停留时间较长6.铁路运输由于装卸次数较多，通常货物错损事故比铁路运输由于装卸次数较多，通常货物错损事故比较多较多3第一节第一节 合理选择运输方式合理选择运输方式（三）铁路运输适用的作业领域（三）铁路运输适用的作业领域一一般般来来说说，铁铁路路运运输输适适用用于于大大宗宗低低值值货货物物的的中中、长长距距离离运运输输，也也较较适适合合散

4、散装装、灌灌装装货货物物运运输输。对对于于运运费费负负担担能能力力小小、货货物物批批量量大大、运运输输距距离离长长的的货货物物来来说说，运运费费比比较较便便宜宜。其其运输的经济里程一般在运输的经济里程一般在200公里以上。公里以上。4第一节第一节 合理选择运输方式合理选择运输方式二、公路运输特点二、公路运输特点（一）公路运输的优点（一）公路运输的优点公公路路运运输输主主要要优优点点是是灵灵活活性性强强，对对收收到到站站设设施施要要求求不不高高。可可以以采采取取“门门到到门门”运运输输形形式式，即即从从发发货货者者门门口口直直到到收收货货者者门门口口，而而不不需需转转运运或或反反复复装装卸卸搬搬

5、运运。公公路路运运输输也也可可作作为为其其他他运运输输方方式式的的衔衔接接手手段段。可可以以选选择择不不同同的的行行车车路路线线，灵灵活活制制定定营营运运时时间间表表，所所以以服服务务便便利利，市市场场覆覆盖盖率率高。高。1.运输速度较快运输速度较快2.可靠性比较高，对产品损伤较少可靠性比较高，对产品损伤较少3.投资少，经济效益高投资少，经济效益高4.操作人员容易培训操作人员容易培训5第一节第一节 合理选择运输方式合理选择运输方式（二）公路运输的缺点（二）公路运输的缺点1.变动成本相对较高变动成本相对较高2.运输能力小，受容积限制，使它不能像铁路运输一样运输能力小，受容积限制，使它不能像铁路运

6、输一样运送大量不同品种和大件的货物运送大量不同品种和大件的货物3.能耗高，环境污染比其他运输方式严重的多，劳动生能耗高，环境污染比其他运输方式严重的多，劳动生产率低产率低4.土地占用较多土地占用较多（三）公路运输使用的作业领域（三）公路运输使用的作业领域1.近距离的独立运输作业近距离的独立运输作业2.补充和衔接其他运输方式，当其他运输方式担负主要补充和衔接其他运输方式，当其他运输方式担负主要运输时，由汽车担负起点和终点处的短途集散运输运输时，由汽车担负起点和终点处的短途集散运输3.完成其他运输方式到达不了的地区的运输任务完成其他运输方式到达不了的地区的运输任务6第一节第一节 合理选择运输方式合

7、理选择运输方式三、水路运输特点三、水路运输特点（一）水路运输的优点（一）水路运输的优点1.运能大，能够运输数量巨大的货物运能大，能够运输数量巨大的货物2.通用性较强，客货两宜通用性较强，客货两宜3.越洋运输大宗货品，连接被海洋所隔开的大陆，越越洋运输大宗货品，连接被海洋所隔开的大陆，越洋运输始发站国际贸易的强大支柱。洋运输始发站国际贸易的强大支柱。4.运输成本低运输成本低5.劳动生产率高，平均运距长劳动生产率高，平均运距长7第一节第一节 合理选择运输方式合理选择运输方式（二）水路运输的缺点（二）水路运输的缺点1.受自然气象条件因素影响大受自然气象条件因素影响大2.营运范围受到限制营运范围受到限

8、制3.航行风险大，安全性略差航行风险大，安全性略差4.运送速度慢，准时性差，在途货物多，会增加货主运送速度慢，准时性差，在途货物多，会增加货主的流动资金占有量，经营风险增加的流动资金占有量，经营风险增加5.搬运成本与装卸费用高搬运成本与装卸费用高（三）水路运输使用的作业领域（三）水路运输使用的作业领域1.承担大批量货物，特别是集装箱运输承担大批量货物，特别是集装箱运输2.承担原材料、半成品等散货运输承担原材料、半成品等散货运输3.承担外贸运输，远距离、运量大、不要求快速抵达承担外贸运输，远距离、运量大、不要求快速抵达的货物运输的货物运输8第一节第一节 合理选择运输方式合理选择运输方式（四）水运

9、的四种形式（四）水运的四种形式1.沿海运输沿海运输2.近海运输近海运输3.远洋运输远洋运输4.内河运输内河运输9第一节第一节 合理选择运输方式合理选择运输方式四、航空运输的特点四、航空运输的特点（一）航空运输的优点（一）航空运输的优点速度快，不受地形的限制速度快，不受地形的限制货物包装要求低货物包装要求低采用空运，运输时间短，可以使生产企业库存水平降低采用空运，运输时间短，可以使生产企业库存水平降低及时性及时性（二）航空运输的缺点（二）航空运输的缺点受气候条件的限制，在一定程度上影响了运输的准确定受气候条件的限制，在一定程度上影响了运输的准确定和正常性和正常性需要航空港设施，所以可达性差需要航

10、空港设施，所以可达性差设施成本高，维护费用高设施成本高，维护费用高运输能力小，运输能耗高运输能力小，运输能耗高运输技术要求高，人员（飞行员、空勤人员）培训费高运输技术要求高，人员（飞行员、空勤人员）培训费高10第一节第一节 合理选择运输方式合理选择运输方式（三）航空运输适用的作业领域（三）航空运输适用的作业领域1.航空运输是国际运输的重要工具，对于对外开放，航空运输是国际运输的重要工具，对于对外开放，促进国际间技术、经济合作与文化交流有重要作用促进国际间技术、经济合作与文化交流有重要作用2.适用于高附加值、质量低、体积小的物品运输适用于高附加值、质量低、体积小的物品运输3.紧急情况下的物资运输

11、紧急情况下的物资运输4.邮政运输手段邮政运输手段5.它是组建新型快速联运的一种骨干运输方式它是组建新型快速联运的一种骨干运输方式11第一节第一节 合理选择运输方式合理选择运输方式五、管道运输特点五、管道运输特点（一）管道运输的优点（一）管道运输的优点1.由于采用密封设备，在运输过程中可避免散失、丢由于采用密封设备，在运输过程中可避免散失、丢失等损失失等损失2.不存在其他运输设备本身在运输过程中消耗动力所不存在其他运输设备本身在运输过程中消耗动力所形成的无效运输问题形成的无效运输问题3.运输量大，适合于大且连续不断运送的物资运输量大，适合于大且连续不断运送的物资4.建设周期短、费用低、运输费用也

12、低建设周期短、费用低、运输费用也低5.能耗少、成本低、效益好能耗少、成本低、效益好6.安全可靠、运行稳定、不会受恶劣多变的气候条件安全可靠、运行稳定、不会受恶劣多变的气候条件影响影响7.埋于低下，所以占地少，有利于环境保护埋于低下，所以占地少，有利于环境保护8.对所运的商品来说损失的风险很小对所运的商品来说损失的风险很小12第一节第一节 合理选择运输方式合理选择运输方式（二）管道运输的缺点（二）管道运输的缺点1.运输对象受到限制，承运的货物比较单一运输对象受到限制，承运的货物比较单一2.灵活性差，不易随便扩展管道，路线往往完全固定，灵活性差，不易随便扩展管道，路线往往完全固定，服务的地理区域十

13、分有限服务的地理区域十分有限3.设计量是个常量，所以与最高运输量之间协调的难设计量是个常量，所以与最高运输量之间协调的难度较大，且在运输量明显不足时，运输成本会显著度较大，且在运输量明显不足时，运输成本会显著增加增加4.仅提供单向服务仅提供单向服务5.运速较慢运速较慢（三）管道运输适用的作业领域（三）管道运输适用的作业领域管管道道运运输输适适合合于于担担负负单单向向、定定点点、量量大大的的流流体体状货物运输状货物运输13第一节第一节 合理选择运输方式合理选择运输方式六、联合运输与综合运输系统六、联合运输与综合运输系统国国际际多多式式联联运运是是在在集集装装箱箱运运输输的的基基础础上上产产生生和

14、和发发展展起起来来的的，是是指指按按照照多多式式联联运运合合同同，以以至至少少两两种种不不同同的的运运输输方方式式，由由多多式式联联运运经经营营人人将将货货物物从从一一国国境境内内的的接接管管地地点点运运至至另另一一国国境境内内指指定定交交货货的的地地点点。为为履履行行单单一一方方式式货货物物合合同同所所规规定定的的货货物物接接送送业业务务，则则不不应应视视为为国国际多式联运。际多式联运。14第一节第一节 合理选择运输方式合理选择运输方式（一）联运的种类（一）联运的种类联运按其对象，可分为货物联运和旅客联运联运按其对象，可分为货物联运和旅客联运按按各各种种运运输输工工具具的的组组合合，又又可可

15、以以分分为为水水陆陆联联运运，铁公联运，水陆空联运铁公联运，水陆空联运按按地地域域概概念念来来分分类类，可可以以分分为为国国内内联联运运和和国国际际联联运运15第一节第一节 合理选择运输方式合理选择运输方式我我国国在在货货物物联联运运中中，按按照照运运送送凭凭证证通通用用程程度度的的不不同同以以及及组组织织联联运运方方法法的的不不同同，通通常常又又区区分分为为干干线联运和干支线联运。线联运和干支线联运。1.干线联运干线联运干线联运是指按照铁道部、交通部联合颁发的干线联运是指按照铁道部、交通部联合颁发的铁路铁路和水路货物联运规则和水路货物联运规则范围内办理的铁水联运，是大范围内办理的铁水联运，是

16、大宗物资联运的主要通路，它具有批量大、运距长等特宗物资联运的主要通路，它具有批量大、运距长等特点，全国有统一的规则、统一的运价。通过统一的联点，全国有统一的规则、统一的运价。通过统一的联运运单，衔接各运输环节，做到一次托运、一次收费、运运单，衔接各运输环节，做到一次托运、一次收费、一票到底，负责全程运输的联运。一票到底，负责全程运输的联运。2.干支线联运干支线联运干支线联运是指铁水干线与地方公路、水路之间的联干支线联运是指铁水干线与地方公路、水路之间的联运。运。16第一节第一节 合理选择运输方式合理选择运输方式（二）联运的组织形式（二）联运的组织形式1.疏散型疏散型在干支线枢纽地设有联办（或联

17、指），但支线的各县在干支线枢纽地设有联办（或联指），但支线的各县在尚没有联运企业的情况下，由联办与干线运输企业在尚没有联运企业的情况下，由联办与干线运输企业签订疏运合同，与支线各县的货主签订送达合同，负签订疏运合同，与支线各县的货主签订送达合同，负责代办铁、江、海等干线的到达港、站物资，并为货责代办铁、江、海等干线的到达港、站物资，并为货主代办向公路、水路等支线的运输企业托运货到家。主代办向公路、水路等支线的运输企业托运货到家。2.集散型集散型在干支线枢纽地设有联运企业或联办，但在支线经济在干支线枢纽地设有联运企业或联办，但在支线经济吸引范围内各地尚未建立联运企业的情况下，由支线吸引范围内各地

18、尚未建立联运企业的情况下，由支线枢纽城市的联运企业或联办负责为货主代办公、水等枢纽城市的联运企业或联办负责为货主代办公、水等支线运来的货物，并向铁、江、河等干线托运；也代支线运来的货物，并向铁、江、河等干线托运；也代办铁、江、海等干线到达港、站得货物向公、水等支办铁、江、海等干线到达港、站得货物向公、水等支线托运，送货上门。线托运，送货上门。17第一节第一节 合理选择运输方式合理选择运输方式3.线条型线条型在干支线枢纽城市设有联运企业或联办，同时在经济在干支线枢纽城市设有联运企业或联办，同时在经济吸引腹地内直线上的一部分县（市）也有联运企业或吸引腹地内直线上的一部分县（市）也有联运企业或联办的

19、情况下，各联运企业相互沟通联运业务，形成联办的情况下，各联运企业相互沟通联运业务，形成一条联运线。一条联运线。4.网络型网络型在干支线枢纽城市有联运企业，并在其经济吸引范围在干支线枢纽城市有联运企业，并在其经济吸引范围支线上的县（市）普遍设联运企业，联运企业之间相支线上的县（市）普遍设联运企业，联运企业之间相互沟通联运渠道，组成联运服务网络。互沟通联运渠道，组成联运服务网络。18第一节第一节 合理选择运输方式合理选择运输方式（三）综合运输体系（三）综合运输体系1.各种运输方式总体服务水平各种运输方式总体服务水平（1）铁路运输铁路运输：全国铁路能力利用率普遍较高，但从一个侧面：全国铁路能力利用率

20、普遍较高，但从一个侧面说明铁路能力供给不足，整体服务水平不能满足基本需求。说明铁路能力供给不足，整体服务水平不能满足基本需求。（2）公路运输公路运输：主要城市间高速公路客运旅行速度、舒适性、：主要城市间高速公路客运旅行速度、舒适性、安全性有了较大提高，旅客运输服务质量有了较明显改善。但安全性有了较大提高，旅客运输服务质量有了较明显改善。但是，城乡旅客运输和农村旅客运输服务质量和层次较低，与需是，城乡旅客运输和农村旅客运输服务质量和层次较低，与需求存在着较大差距；货运方面，总体服务层次很低。求存在着较大差距；货运方面，总体服务层次很低。（3）水运运输水运运输：水路客运技术设备水平和服务水平总体不

21、高；：水路客运技术设备水平和服务水平总体不高；水路货物运输装备水平相对不高。水路货物运输装备水平相对不高。（4）民航运输民航运输：民航运力储备相对比较充足，服务质量和服务：民航运力储备相对比较充足，服务质量和服务意识虽在不断改进，但仍有较大的改进空间。意识虽在不断改进，但仍有较大的改进空间。（5）管道运输管道运输：已成为正在迅速发展的一种运输方式。：已成为正在迅速发展的一种运输方式。19第一节第一节 合理选择运输方式合理选择运输方式2.我国综合运输体系结构的变化我国综合运输体系结构的变化高速公路使公路运输的中长途客货运输功能得高速公路使公路运输的中长途客货运输功能得到提升到提升铁路大提速巩固了

22、铁路旅客运输份额铁路大提速巩固了铁路旅客运输份额城市经济圈的发展产生了巨大旅客运输需求城市经济圈的发展产生了巨大旅客运输需求支线航空运输将快速发展，将进一步改善旅客支线航空运输将快速发展，将进一步改善旅客出行服务质量出行服务质量汽车保有量的快速增加必然大幅度提高油品供汽车保有量的快速增加必然大幅度提高油品供应需求应需求20第二节第二节 运输问题与线型规划运输问题与线型规划运运输输问问题题是是线线型型规规划划应应用用的的一一个个典典型型案案例例，本本节节先先介介绍绍线线型型规规划划的的基基本本模模型型和和求求解解方方法法，然后介绍运输问题的求解。然后介绍运输问题的求解。21第二节第二节 运输问题

23、与线型规划运输问题与线型规划一、线型规划模型及求解方法一、线型规划模型及求解方法（一）线型规划问题的数学表达式（一）线型规划问题的数学表达式一般形式一般形式目标函数：目标函数：Max（Min）z=c1x1+c2x2+cnxn约束条件：约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amn xn（=,）bm x1，x2，xn022第二节第二节 运输问题与线型规划运输问题与线型规划求求解解之之前前，要要把把线线型型规规划划的的一一般般形形式式转转化成标准型。化成标准型。标准形式标准形式目标函数：目标函数：Maxz

24、=c1x1+c2x2+cnxn约束条件：约束条件：s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bm x1，x2，xn0，bi023可可以以看看出出，线线性性规规划划的的标标准准形形式式有有如如下四个特点：下四个特点：目标最大化目标最大化约束为等式约束为等式决策变量均非负决策变量均非负右端项非负右端项非负24第二节第二节 运输问题与线型规划运输问题与线型规划对对于于各各种种类类 型型 线线性性 规规 划划问问 题题 如如何何 化化 为为标标 准准 形形式式 及及 如如何何 选选 取取初初 始始 变变量量 如如 右右

25、表：表：线性规划模型线性规划模型化为标准形式化为标准形式变变量量约约束束条条件件右端项形式目目标标函函数数极大或极小变量前的系数第二节第二节 运输问题与线型规划运输问题与线型规划例：将以下线性规划问题转化为标准形式例：将以下线性规划问题转化为标准形式Maxf=-2x1+3x2-4x3s.t.3x1+4x2-5x362x1+x38-x1-x2-x3=-9x10,x20,x3无符号限制无符号限制得到标准形式的线性规划问题：得到标准形式的线性规划问题：Minz=-2x1-3x2+4（x3 -x3 ）s.t.-3 x1+4x2-5（x3 -x3 ）+x4 =6-2 x1 +（x3 -x3 ）-x5=8

26、 -x1 +x2 +（x3 -x3 ）=9x1 ，x2，x3 ，x3 ，x4，x5025第二节第二节 运输问题与线型规划运输问题与线型规划26（二）单纯性法的求解步骤（二）单纯性法的求解步骤第二节第二节 运输问题与线型规划运输问题与线型规划应用实例应用实例水泥调运水泥调运1983年年广广东东省省建建材材公公司司运运用用线线型型规规划划安安排排水水泥泥分分配配计计划划，取取得得了了较较好好的的经经济济效效益益。与与1982年年比比较，水泥的运输成本大幅度减少。较，水泥的运输成本大幅度减少。表表2-7是是1983年年广广东东省省水水泥泥调调拨拨的的数数量量和和水水泥泥厂厂到到各各地地、市市的的单单

27、位位运运输输成成本本，也也就就是是线线型型规规划划问问题题中中的的价价值值系系数数。对对于于专专业业运运输输部部门门，例例如如铁铁路路、公公路路运运输输部部门门等等，可可以以用用“吨吨公公里里”数数表表示示运运输输成成本本；而而对对于于物物资资部部门门，特特别别对对运运输输工工具具不不同同、中中转转次次数数较较多多的的物物资资调调运运问问题题，一一般用实际运杂费表示运输成本。般用实际运杂费表示运输成本。27第二节第二节 运输问题与线型规划运输问题与线型规划水泥厂水泥厂用户用户ABCDEF需求量需求量梅县59.0120.062.07290汕头47.179.749.536940潮州53.486.0

28、53.91090惠阳21.830.062.322.213140深圳21.222.021.350.021.66080韶关30.312.630.312780肇庆25.243.046.060.129.213680佛山12.321.051.028.016460江门21.237.051.128.01130珠海21.237.549.029.03800湛江47.112.647.521.012720茂名59.612.560.0335海口50.250.850.225.010830三亚54.370.054.740.05950广州12.612.652.125.022655供应量6152015680188705650

29、275603560016488028第二节第二节 运输问题与线型规划运输问题与线型规划表表2-8水泥调运的最优方案水泥调运的最优方案29A AB BC CD DE EF F需求量需求量梅县梅县7290 7290 0 0 0 0 0 0 0 0 0 0 7290 7290 汕头汕头1340 1340 0 0 0 0 0 0 0 0 35600 35600 3694036940潮州潮州1090 1090 0 0 0 0 0 0 0 0 0 0 10901090惠阳惠阳0 0 0 0 0 0 0 0 13140 13140 0 0 1314013140深圳深圳0 0 2900 2900 0 0 0

30、0 3180 3180 0 0 60806080韶关韶关0 0 12780 12780 0 0 0 0 0 0 0 0 1278012780肇庆肇庆13680 13680 0 0 0 0 0 0 0 0 0 0 1368013680佛山佛山16460 16460 0 0 0 0 0 0 0 0 0 0 1646016460江门江门1130 1130 0 0 0 0 0 0 0 0 0 0 11301130珠海珠海3800 3800 0 0 0 0 0 0 0 0 0 0 38003800湛江湛江7405 7405 0 0 0 0 5315 5315 0 0 0 0 1272012720茂名茂名

31、0 0 0 0 0 0 335 335 0 0 0 0 335335海口海口0 0 0 0 0 0 0 0 10830 10830 0 0 1083010830三亚三亚5540 5540 0 0 0 0 0 0 410 410 0 0 59505950广州广州3785 3785 0 0 18870 18870 0 0 0 0 0 0 2265522655供应量供应量61520 61520 156801568018870188705650565027560275603560035600运输路线规划运输路线规划运运输输路路线线选选择择主主要要是是指指路路线线的的优优化化计计算算问问题题，物流运输界

32、通常将其作以下归类：物流运输界通常将其作以下归类：（1）起讫点不同）起讫点不同最短路径问题最短路径问题常用的最短路径算法，通常不考虑其他运输因素，如常用的最短路径算法，通常不考虑其他运输因素，如路径容量等，步骤如下：路径容量等，步骤如下：第第i次迭代的目标次迭代的目标第第i次迭代的输入值次迭代的输入值第第i个最近节点的候选点个最近节点的候选点第第i个最近节点的计算个最近节点的计算运输路线规划运输路线规划【例例6.1】已已知知起起点点A与与终终点点G之之间间有有节节点点B，C，D，E，F，它它们们共共同同构构成成一一运运输输网网络络，如如图图6.1所所示示，图图中中标标明明了了各各节节点点间间的

33、的距距离离。求求A到到G的的最最短短运运输输路线。路线。运输路线规划运输路线规划解：使用标号法：解：使用标号法：（S，0）（A，50）（A，52）（C，82）（B，83）（B，108）（F，116）运输路线规划运输路线规划（2）起终点相同）起终点相同遍历点问题遍历点问题这类问题主要指从设施点出发访问一定数量顾客后又回到原来这类问题主要指从设施点出发访问一定数量顾客后又回到原来的出发点的线路确定问题，即运筹学中常见的旅行商（的出发点的线路确定问题，即运筹学中常见的旅行商（TSP）问题，其目标是确定回到出发点前服务顾客的次序，使总旅行问题，其目标是确定回到出发点前服务顾客的次序，使总旅行距离最小。

34、通常的数学模型为：距离最小。通常的数学模型为：式中：式中：Cij表示旅行商经过对应路段（表示旅行商经过对应路段（i，j）所花费用；决策变量）所花费用；决策变量Xij表表示如果路段（示如果路段（i，j）在路线上，其值为）在路线上，其值为1，否则为，否则为0。运输路线规划运输路线规划通常采用简单贪婪算法，其步骤如下：通常采用简单贪婪算法，其步骤如下：选择距出发点最近的顾客位置选择距出发点最近的顾客位置再从没有选择的位置中选距离当前已选择的位置最再从没有选择的位置中选距离当前已选择的位置最近的顾客位置近的顾客位置如果所有位置都选了便停止，否则回到第二步如果所有位置都选了便停止，否则回到第二步运输路线

35、规划运输路线规划【例例6.2】一奶厂从站点一奶厂从站点A送奶，服务送奶，服务3个顾客个顾客B，C，D，从站点从站点A到到3个顾客的距离如表个顾客的距离如表6.1所示，确定最优的送奶所示，确定最优的送奶路线。路线。解：解：B距距A最近。最近。C距距B最近。最近。只剩只剩D没选，没选，D即为继即为继C之后的顾客，然后返回之后的顾客，然后返回A。求出的配送顺序为求出的配送顺序为ABCDA。节点节点ABCDA223145B221827C311838D452738运输路线规划运输路线规划（3）起终点相同）起终点相同遍历线问题遍历线问题邮递员问题邮递员问题若若把把它它抽抽象象为为图图的的语语言言，就就是是

36、给给定定一一个个连连通通图图。在在每每边边ei上上赋赋予予一一个个非非负负的的权权w（ei），要要求求一一个个圈圈（未未必必是是简简单单的的），并并使使圈圈的的总总权权数数最最小小。这这个个问问题题是是我我国国的的管管梅梅谷谷同同志志在在1962年提出的，因此在国际上统称为年提出的，因此在国际上统称为中国邮递员问题中国邮递员问题。求解这个问题的方法被称为求解这个问题的方法被称为奇偶点图上作业法奇偶点图上作业法。奇偶点图上作业法算法口诀：奇偶点图上作业法算法口诀：先分奇偶点，奇点对对联；先分奇偶点，奇点对对联；联线不重迭，重迭要改变；联线不重迭，重迭要改变；圈上联线长，不得过半圈圈上联线长，不得

37、过半圈。运输路线规划运输路线规划中中国国邮邮递递员员问问题题也也可可以以表表示示为为：在在一一个个有有奇奇点点的的连连通通图图中中。要要求求增增加加一一些些重重复复边边，使使得得新新的的连连通通图图不不含含有有奇奇点点，并且增加的重复边总权最小。并且增加的重复边总权最小。我我们们把把增增加加重重复复边边后后不不含含奇奇点点的的新新的的连连通通图图叫叫做做邮邮递递路路线线，而总权最小的邮递路线叫做，而总权最小的邮递路线叫做最优邮递路线。最优邮递路线。下下面面我我们们来来介介绍绍初初始始邮邮递递路路线线的的确确定定，改改进进，以以及及一一个个邮邮递递路路线线是是否否是是最最优优路路线线的的判判定定

38、标标准准的的方方法法-图图上上作作业法。业法。运输路线规划运输路线规划（一）初始邮递路线的确定方法（一）初始邮递路线的确定方法由由于于任任何何一一个个图图中中，奇奇点点的的个个数数为为偶偶数数，所所以以如如果果一一个个连连通通图图有有奇奇点点，就就可可以以把把它它们们两两两两配配成成对对，而而每每对对奇奇点点之之间间必必有有一一条条链链（图图是是连连通通的的），我我们们把把这这条条链链的的所所有有边边作作为为重重复复边边追追加加到到图图中中去去，这这样样得得到到的的新新连连通通图图必必无无奇奇点点，这这就给出了初始投递路线。就给出了初始投递路线。例例如如，在在图图1中中，v1是是邮邮局局所所在

39、在地地，并并有有四四个个奇奇点点v2,v4,v6,v8,将它们两两配对，比如将它们两两配对，比如v2和和v4为一对，为一对，v6和和v8为一对。为一对。运输路线规划运输路线规划图图1运输路线规划运输路线规划在在连连接接v2和和v4的的链链中中任任取取一一条条，比比如如链链（v2,v1,v8,v7,v6,v5,v4）,在在 加加 入入 重重 复复 边边v2,v1,v1,v8,v8,v7,v7,v6,v6,v5,v5,v4。同同 样样，任任 取取 连连 接接 v6和和 v8的的 一一 条条 链链(v8,v1,v2,v3,v4,v5,v6),在在加加入入重重复复边边v8,v1,v1,v2,v2,v3

40、,v3,v4,v4,v5,v5,v6.于于是是，得到图得到图2。运输路线规划运输路线规划图 2在连通图2中，没有奇点，故它是欧拉图。对于这条邮递路线，重复边的总长为:2W12+W23+W34+2W45+2W56+W67+W78+2W18=51。运输路线规划运输路线规划（二）改进邮递路线，使重复边的总长不断减少（二）改进邮递路线，使重复边的总长不断减少从从图图2中中可可以以看看出出，在在边边v1,v2旁旁边边有有两两条条重重复复边边，但但是是如如果果把把他他们们都都从从图图中中去去掉掉，所所得得到到的的连连通通图图仍仍然然无无奇奇点点，还还是是一一个个邮邮递递路路线线，而而总总长长度度却却有有所

41、所减减少少。同同理理，在在边边v1,v8,v4,v5,v5,v6旁旁边边的的重重复复边边也也是一样的。是一样的。一一般般地地，在在邮邮递递路路线线上上，如如果果在在边边vi,vj旁旁边边有有两两条条以以上上的的重重复复边边，从从中中去去掉掉偶偶数数条条，那那么么可可以以得得到到一个总长度较少的邮递路线。一个总长度较少的邮递路线。运输路线规划运输路线规划判判定定标标准准1 1：在在最最优优邮邮递递路路线线上上，图图中中的的每每一一条条边边至多有一条重复边。至多有一条重复边。按按此此判判定定标标准准，将将图图2 2改改为为图图3 3，这这时时重重复复边边的的总总权权减少为减少为2121。图 3运输

42、路线规划运输路线规划判判定定标标准准2 2。在在最最优优邮邮递递路路线线上上，图图中中每每一一个个圈圈的的重重复复边边的的总总权权小小于于或或者者等等于于该该圈圈总权的一半。总权的一半。在在图图3中中，圈圈（v2,v3,v4,v9,v2）的的总总权权为为24，但但圈圈上上重重复复边边的的总总权权为为14，大大于于该该圈圈总总权权的的一一半半。因因此此作作一一次次改改进进，在在该该圈圈上上去去掉掉重重复复边边v2,v3,v3,v4,加加上上重重复复边边v2,v9,v9,v4，如如图图4所所示示。这时重复边的总权减少为这时重复边的总权减少为10。图 4运输路线规划运输路线规划在在图图4中中，圈圈(

43、v1,v2,v9,v6,v7,v8,v1)中中重重复复边边总总权权为为13，而而该该圈圈的的总总权权为为24，不不满满足足判判定定标标准准2。再再次次经经过过改改进进后后，得得到到图图5。此此时时，该该圈圈中中重重复复边边的的总总权权为为11，小小于该圈的总权于该圈的总权24。检检查查图图5中中的的每每一一个个圈圈，判判定定标标准准1和和2均均已已满满足足。于于是是，图图中中的的欧欧拉拉圈圈就就是最优邮递路线。是最优邮递路线。图 5运输路线规划运输路线规划（4）多起点、多终点，没有中间点）多起点、多终点，没有中间点运输问题运输问题主要是将多个供应点的供应分配到多个顾客需求点，即运主要是将多个供

44、应点的供应分配到多个顾客需求点，即运筹学中的运输问题。一般通过表上作业法求解。筹学中的运输问题。一般通过表上作业法求解。如果是产销不平如果是产销不平衡问题，转化成衡问题，转化成产销平衡问题。产销平衡问题。运输路线规划运输路线规划一般产销平衡问题的模型为：一般产销平衡问题的模型为：A1、A2、Am表示某物资货物的表示某物资货物的m个产地；个产地；B1、B2、Bn表示某货物的表示某货物的n个销地；个销地；ai表示产地表示产地Ai的产量；的产量；bj表示销地表示销地Bj的销量；的销量；cij表示把货物从产地表示把货物从产地Ai运往销地运往销地Bj的单位运价；的单位运价；设设xij为从产地为从产地Ai

45、运往销地运往销地Bj的运输量。的运输量。运输路线规划运输路线规划【例例】某某部部门门有有3个个生生产产同同类类产产品品的的工工厂厂（产产地地），生生产产的的产产品品由由4个个销销售售点点（销销地地）出出售售，各各工工厂厂的的生生产产量量、各各销销售售点点的的销销售售量量（假假定定单单位位均均为为t）以以及及各各工工厂厂到到各各销销售售点点的的单单位位运运价价（元元/t）如如下下表表所所示示，要要求求研研究究产产品品如何调运才能使总运费最小？如何调运才能使总运费最小？运输路线规划运输路线规划解：解：用最小元素法可以求得初始基本可行解为：用最小元素法可以求得初始基本可行解为：运输路线规划运输路线规

46、划利用位势法进行检验（令利用位势法进行检验（令u1=0）：）：运输路线规划运输路线规划利用闭回路法调整运量：利用闭回路法调整运量：运输路线规划运输路线规划利用位势法进行检验（令利用位势法进行检验（令u1=0）：）：检检验验数数都都非非负负，因因此此该该方方案案为为为为最最优优方方案案，具具体体方方案案为为：A1工工厂厂运运12t到到销销售售点点B3；A1工工厂厂运运4t到到销销售售点点B4；A2工工厂厂运运8t到到销销售售点点B1；A2工工厂厂运运2t到销售点到销售点B4；A3工厂运工厂运14t到销售点到销售点B2；A3工厂运工厂运8t到销售点到销售点B4。最小运费为：最小运费为：124+41

47、1+82+29+145+86=244元。元。运输路线规划运输路线规划由由于于最最优优运运输输方方案案中中x11的的检检验验数数11=0，可可知知此此运运输输问问题题有有多多个个最最优优解解，为为求求得得另另一一个个最最优优解解，只只要要把把作作为为入入基基变变量量，调调整整运运输输方方案，就可得到另一个最优方案：案，就可得到另一个最优方案：具具体体方方案案为为：A1工工厂厂运运4t到到销销售售点点B1；A1工工厂厂运运12t到到销销售售点点B3；A2工工厂厂运运4t到到销销售售点点B1；A2工工厂厂运运6t到到销销售售点点B4；A3工工厂厂运运14t到到销销售售点点B2；A3工厂运工厂运8t到

48、销售点到销售点B4。最小运费为：最小运费为：44+124+42+69+145+86=244元。元。运输路线规划运输路线规划（5）最小连通问题）最小连通问题最小生成树问题最小生成树问题问问题题表表述述：有有N个个点点，他他们们之之间间的的距距离离为为已已知知，如如何何把把各各点点连连接接成成一一个个连连通通图图，使使其其连连线线的的总总长长度度最最短？短？求解步骤：求解步骤：第第一一步步：在在图图的的边边集集合合中中取取一一条条边边e1，其其长长度度是是所所有有边边中长度最小者。中长度最小者。第第二二步步：如如果果选选好好e1，e2，ek，则则再再从从剩剩余余的的边边集合中选取边集合中选取边ek

49、+1，满足：，满足：使使e1，e2，ek，ek+1所组成的图不含圈；所组成的图不含圈；ek+1在剩余的边集合中是长度最短者。在剩余的边集合中是长度最短者。直至选取的边数为直至选取的边数为N-1时为止。时为止。54运输路线规划运输路线规划应用举例应用举例输油管道铺设输油管道铺设东东海海某某海海域域有有8口口油油田田，相相互互之之间间的的距距离离如如表表2-17所所示示。已已知知1号号井井离离海海岸岸最最近近，为为5海海里里。试试问问从从海海岸岸经经1号号井井铺铺设设输输油油管管将将各各油油田田连连接接起起来来，应应如如何何铺铺设设才才能能使使输输油油管管线线长长度度最短？为便于计量和检修，油管只允许在各井位处分叉。最短？为便于计量和检修，油管只允许在各井位处分叉。552345678114209718201529181226231132617251910471615959118661075运输路线规划运输路线规划5687632514