物流运输规划.

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. 完成其他运输方式到达不

7、了的地区的运输任务完成其他运输方式到达不了的地区的运输任务6第一节第一节 合理选择运输方式合理选择运输方式三、水路运输特点三、水路运输特点（一）水路运输的优点（一）水路运输的优点1. 运能大，能够运输数量巨大的货物运能大，能够运输数量巨大的货物2. 通用性较强，客货两宜通用性较强，客货两宜3. 越洋运输大宗货品，连接被海洋所隔开的大陆，越越洋运输大宗货品，连接被海洋所隔开的大陆，越洋运输始发站国际贸易的强大支柱。洋运输始发站国际贸易的强大支柱。4. 运输成本低运输成本低5. 劳动生产率高，平均运距长劳动生产率高，平均运距长7第一节第一节 合理选择运输方式合理选择运输方式（二）水路运输的缺点（二

8、）水路运输的缺点1. 受自然气象条件因素影响大受自然气象条件因素影响大2. 营运范围受到限制营运范围受到限制3. 航行风险大，安全性略差航行风险大，安全性略差4. 运送速度慢，准时性差，在途货物多，会增加货主运送速度慢，准时性差，在途货物多，会增加货主的流动资金占有量，经营风险增加的流动资金占有量，经营风险增加5. 搬运成本与装卸费用高搬运成本与装卸费用高（三）水路运输使用的作业领域（三）水路运输使用的作业领域1. 承担大批量货物，特别是集装箱运输承担大批量货物，特别是集装箱运输2. 承担原材料、半成品等散货运输承担原材料、半成品等散货运输3. 承担外贸运输，远距离、运量大、不要求快速抵达承担

9、外贸运输，远距离、运量大、不要求快速抵达的货物运输的货物运输8第一节第一节 合理选择运输方式合理选择运输方式（四）水运的四种形式（四）水运的四种形式1. 沿海运输沿海运输2. 近海运输近海运输3. 远洋运输远洋运输4. 内河运输内河运输9第一节第一节 合理选择运输方式合理选择运输方式四、航空运输的特点四、航空运输的特点（一）航空运输的优点（一）航空运输的优点 速度快，不受地形的限制速度快，不受地形的限制 货物包装要求低货物包装要求低 采用空运，运输时间短，可以使生产企业库存水平降低采用空运，运输时间短，可以使生产企业库存水平降低 及时性及时性（二）航空运输的缺点（二）航空运输的缺点 受气候条件

10、的限制，在一定程度上影响了运输的准确定受气候条件的限制，在一定程度上影响了运输的准确定和正常性和正常性 需要航空港设施，所以可达性差需要航空港设施，所以可达性差 设施成本高，维护费用高设施成本高，维护费用高 运输能力小，运输能耗高运输能力小，运输能耗高 运输技术要求高，人员（飞行员、空勤人员）培训费高运输技术要求高，人员（飞行员、空勤人员）培训费高10第一节第一节 合理选择运输方式合理选择运输方式（三）航空运输适用的作业领域（三）航空运输适用的作业领域1.航空运输是国际运输的重要工具，对于对外开放，航空运输是国际运输的重要工具，对于对外开放，促进国际间技术、经济合作与文化交流有重要作用促进国际

11、间技术、经济合作与文化交流有重要作用2.适用于高附加值、质量低、体积小的物品运输适用于高附加值、质量低、体积小的物品运输3.紧急情况下的物资运输紧急情况下的物资运输4.邮政运输手段邮政运输手段5.它是组建新型快速联运的一种骨干运输方式它是组建新型快速联运的一种骨干运输方式11第一节第一节 合理选择运输方式合理选择运输方式五、管道运输特点五、管道运输特点（一）管道运输的优点（一）管道运输的优点1. 由于采用密封设备，在运输过程中可避免散失、丢由于采用密封设备，在运输过程中可避免散失、丢失等损失失等损失2. 不存在其他运输设备本身在运输过程中消耗动力所不存在其他运输设备本身在运输过程中消耗动力所形

12、成的无效运输问题形成的无效运输问题3. 运输量大，适合于大且连续不断运送的物资运输量大，适合于大且连续不断运送的物资4. 建设周期短、费用低、运输费用也低建设周期短、费用低、运输费用也低5. 能耗少、成本低、效益好能耗少、成本低、效益好6. 安全可靠、运行稳定、不会受恶劣多变的气候条件安全可靠、运行稳定、不会受恶劣多变的气候条件影响影响7. 埋于低下，所以占地少，有利于环境保护埋于低下，所以占地少，有利于环境保护8. 对所运的商品来说损失的风险很小对所运的商品来说损失的风险很小12第一节第一节 合理选择运输方式合理选择运输方式（二）管道运输的缺点（二）管道运输的缺点1. 运输对象受到限制，承运

13、的货物比较单一运输对象受到限制，承运的货物比较单一2. 灵活性差，不易随便扩展管道，路线往往完全固定灵活性差，不易随便扩展管道，路线往往完全固定，服务的地理区域十分有限，服务的地理区域十分有限3. 设计量是个常量，所以与最高运输量之间协调的难设计量是个常量，所以与最高运输量之间协调的难度较大，且在运输量明显不足时，运输成本会显著度较大，且在运输量明显不足时，运输成本会显著增加增加4. 仅提供单向服务仅提供单向服务5. 运速较慢运速较慢（三）管道运输适用的作业领域（三）管道运输适用的作业领域 管道运输适合于担负单向、定点、量大的流体管道运输适合于担负单向、定点、量大的流体状货物运输状货物运输13

14、第一节第一节 合理选择运输方式合理选择运输方式六、联合运输与综合运输系统六、联合运输与综合运输系统 国际多式联运是在集装箱运输的基础上产生国际多式联运是在集装箱运输的基础上产生和发展起来的，是指按照多式联运合同，以和发展起来的，是指按照多式联运合同，以至少两种不同的运输方式，由多式联运经营至少两种不同的运输方式，由多式联运经营人将货物从一国境内的接管地点运至另一国人将货物从一国境内的接管地点运至另一国境内指定交货的地点。为履行单一方式货物境内指定交货的地点。为履行单一方式货物合同所规定的货物接送业务，则不应视为国合同所规定的货物接送业务，则不应视为国际多式联运。际多式联运。14第一节第一节 合

15、理选择运输方式合理选择运输方式（一）联运的种类（一）联运的种类联运按其对象，可分为货物联运和旅客联运联运按其对象，可分为货物联运和旅客联运按各种运输工具的组合，又可以分为水陆联运按各种运输工具的组合，又可以分为水陆联运，铁公联运，水陆空联运，铁公联运，水陆空联运按地域概念来分类，可以分为国内联运和国际按地域概念来分类，可以分为国内联运和国际联运联运15第一节第一节 合理选择运输方式合理选择运输方式我国在货物联运中，按照运送凭证通用程度的我国在货物联运中，按照运送凭证通用程度的不同以及组织联运方法的不同，通常又区分为不同以及组织联运方法的不同，通常又区分为干线联运和干支线联运。干线联运和干支线联

16、运。1. 干线联运干线联运 干线联运是指按照铁道部、交通部联合颁发的干线联运是指按照铁道部、交通部联合颁发的铁路铁路和水路货物联运规则和水路货物联运规则范围内办理的铁水联运，是大范围内办理的铁水联运，是大宗物资联运的主要通路，它具有批量大、运距长等特宗物资联运的主要通路，它具有批量大、运距长等特点，全国有统一的规则、统一的运价。通过统一的联点，全国有统一的规则、统一的运价。通过统一的联运运单，衔接各运输环节，做到一次托运、一次收费运运单，衔接各运输环节，做到一次托运、一次收费、一票到底，负责全程运输的联运。、一票到底，负责全程运输的联运。2. 干支线联运干支线联运 干支线联运是指铁水干线与地方

17、公路、水路之间的联干支线联运是指铁水干线与地方公路、水路之间的联运。运。16第一节第一节 合理选择运输方式合理选择运输方式（二）联运的组织形式（二）联运的组织形式1. 疏散型疏散型 在干支线枢纽地设有联办（或联指），但支线的各县在干支线枢纽地设有联办（或联指），但支线的各县在尚没有联运企业的情况下，由联办与干线运输企业在尚没有联运企业的情况下，由联办与干线运输企业签订疏运合同，与支线各县的货主签订送达合同，负签订疏运合同，与支线各县的货主签订送达合同，负责代办铁、江、海等干线的到达港、站物资，并为货责代办铁、江、海等干线的到达港、站物资，并为货主代办向公路、水路等支线的运输企业托运货到家。主代

18、办向公路、水路等支线的运输企业托运货到家。2. 集散型集散型 在干支线枢纽地设有联运企业或联办，但在支线经济在干支线枢纽地设有联运企业或联办，但在支线经济吸引范围内各地尚未建立联运企业的情况下，由支线吸引范围内各地尚未建立联运企业的情况下，由支线枢纽城市的联运企业或联办负责为货主代办公、水等枢纽城市的联运企业或联办负责为货主代办公、水等支线运来的货物，并向铁、江、河等干线托运；也代支线运来的货物，并向铁、江、河等干线托运；也代办铁、江、海等干线到达港、站得货物向公、水等支办铁、江、海等干线到达港、站得货物向公、水等支线托运，送货上门。线托运，送货上门。17第一节第一节 合理选择运输方式合理选择

19、运输方式3. 线条型线条型 在干支线枢纽城市设有联运企业或联办，同时在经济在干支线枢纽城市设有联运企业或联办，同时在经济吸引腹地内直线上的一部分县（市）也有联运企业或吸引腹地内直线上的一部分县（市）也有联运企业或联办的情况下，各联运企业相互沟通联运业务，形成联办的情况下，各联运企业相互沟通联运业务，形成一条联运线。一条联运线。4. 网络型网络型 在干支线枢纽城市有联运企业，并在其经济吸引范围在干支线枢纽城市有联运企业，并在其经济吸引范围支线上的县（市）普遍设联运企业，联运企业之间相支线上的县（市）普遍设联运企业，联运企业之间相互沟通联运渠道，组成联运服务网络。互沟通联运渠道，组成联运服务网络。

20、18第一节第一节 合理选择运输方式合理选择运输方式（三）综合运输体系（三）综合运输体系1.各种运输方式总体服务水平各种运输方式总体服务水平（1）铁路运输铁路运输：全国铁路能力利用率普遍较高，但从一个侧面：全国铁路能力利用率普遍较高，但从一个侧面说明铁路能力供给不足，整体服务水平不能满足基本需求。说明铁路能力供给不足，整体服务水平不能满足基本需求。 （2）公路运输公路运输：主要城市间高速公路客运旅行速度、舒适性、：主要城市间高速公路客运旅行速度、舒适性、安全性有了较大提高，旅客运输服务质量有了较明显改善。但安全性有了较大提高，旅客运输服务质量有了较明显改善。但是，城乡旅客运输和农村旅客运输服务质

21、量和层次较低，与需是，城乡旅客运输和农村旅客运输服务质量和层次较低，与需求存在着较大差距；货运方面，总体服务层次很低。求存在着较大差距；货运方面，总体服务层次很低。 （3）水运运输水运运输：水路客运技术设备水平和服务水平总体不高；：水路客运技术设备水平和服务水平总体不高；水路货物运输装备水平相对不高。水路货物运输装备水平相对不高。 （4）民航运输民航运输：民航运力储备相对比较充足，服务质量和服务：民航运力储备相对比较充足，服务质量和服务意识虽在不断改进，但仍有较大的改进空间。意识虽在不断改进，但仍有较大的改进空间。 （5）管道运输管道运输：已成为正在迅速发展的一种运输方式。：已成为正在迅速发展

22、的一种运输方式。19第一节第一节 合理选择运输方式合理选择运输方式2.我国综合运输体系结构的变化我国综合运输体系结构的变化 高速公路使公路运输的中长途客货运输功能得高速公路使公路运输的中长途客货运输功能得到提升到提升 铁路大提速巩固了铁路旅客运输份额铁路大提速巩固了铁路旅客运输份额 城市经济圈的发展产生了巨大旅客运输需求城市经济圈的发展产生了巨大旅客运输需求 支线航空运输将快速发展，将进一步改善旅客支线航空运输将快速发展，将进一步改善旅客出行服务质量出行服务质量 汽车保有量的快速增加必然大幅度提高油品供汽车保有量的快速增加必然大幅度提高油品供应需求应需求20第二节第二节 运输问题与线型规划运输

23、问题与线型规划 运输问题是线型规划应用的一个典型案例，运输问题是线型规划应用的一个典型案例，本节先介绍线型规划的基本模型和求解方法本节先介绍线型规划的基本模型和求解方法，然后介绍运输问题的求解。，然后介绍运输问题的求解。21第二节第二节 运输问题与线型规划运输问题与线型规划 一、线型规划模型及求解方法一、线型规划模型及求解方法（一）线型规划问题的数学表达式（一）线型规划问题的数学表达式 一般形式一般形式目标函数：目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件：约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =,

24、）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 22第二节第二节 运输问题与线型规划运输问题与线型规划 求解之前，要把线型规划的一般形式转求解之前，要把线型规划的一般形式转化成标准型。化成标准型。 标准形式标准形式目标函数：目标函数： Max z = c1 x1 + c2 x2 + + cn xn 约束条件：约束条件： s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1

25、 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0，bi 023可以看出，线性规可以看出，线性规划的标准形式有如划的标准形式有如下四个特点：下四个特点：目标最大化目标最大化约束为等式约束为等式决策变量均非负决策变量均非负右端项非负右端项非负24第二节第二节 运输问题与线型规划运输问题与线型规划 对于各种对于各种类 型 线类 型 线性 规 划性 规 划问 题 如问 题 如何 化 为何 化 为标 准 形标 准 形式 及 如式 及 如何 选 取何 选 取初 始 变初 始 变量 如 右量 如 右表：表：线性规划模型线性规划模型化为标准形式化为标准形式变变量量约约束束

26、条条件件右端项形式目目标标函函数数极大或极小变量前的系数njijijnjijijnjijijbxabxabxa111njiaisijijnjiaijijnjisijijbxxxabxxabxxa111njjjnjjjxczxcz11minmaxnjjjxczzz1max，化为求令不变ainjjjnjsijjMxxczxxcz11max0max时加入人工变量时加入松弛变量asxx取值无约束jjjxxx00000jjjjjjjjxxxxxxxx ，其中令，则令不变00iibb”约束条件两端乘“不变1第二节第二节 运输问题与线型规划运输问题与线型规划例：将以下线性规划问题转化为标准形式例：将以下线性

27、规划问题转化为标准形式 Max f = -2x1+3x2-4x3 s.t. 3 x1 + 4x2 - 5 x3 6 2 x1 + x3 8 -x1 - x2 - x3 = -9 x1 0,x2 0 ,x3无符号限制无符号限制得到标准形式的线性规划问题：得到标准形式的线性规划问题： Min z = -2 x1 - 3x2 + 4 （x3 - x3 ） s.t. -3 x1 + 4x2 - 5 （x3 - x3 ） + x4 = 6 -2 x1 + （x3 - x3 ） - x5 = 8 -x1 + x2 + （x3 - x3 ） = 9 x1 ， x2 ， x3 ， x3 ， x4 ， x5 0

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

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

30、140深圳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供应量6152015680188705650275603560016488028第二节第二节 运输问

31、题与线型规划运输问题与线型规划表表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 0 3180 3180 0 0 60806080韶关韶

32、关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茂名茂名0 0 0 0 0 0 335 335 0 0 0 0

33、 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运输路线规划运输路线规划 运输路线选择主要是指路线的优化计算问题，运输路线选择主要是指路线的优化计算问题，物流运输界通常将其作以下归类：物流运输界通常将其作以下归类：

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

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

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

37、置都选了便停止，否则回到第二步如果所有位置都选了便停止，否则回到第二步运输路线规划运输路线规划 【例例6.2】一奶厂从站点一奶厂从站点A送奶，服务送奶，服务3个顾客个顾客B，C，D，从站点从站点A到到3个顾客的距离如表个顾客的距离如表6.1所示，确定最优的送奶所示，确定最优的送奶路线。路线。 解：解：B距距A最近。最近。 C距距B最近。最近。 只剩只剩D没选，没选，D即为继即为继C之后的顾客，然后返回之后的顾客，然后返回A。 求出的配送顺序为求出的配送顺序为ABCDA。节点节点ABCDA223145B221827C311838D452738运输路线规划运输路线规划 （3）起终点相同）起终点相同

38、遍历线问题遍历线问题 邮递员问题邮递员问题 若把它抽象为图的语言，就是给定一个连通图。在每边若把它抽象为图的语言，就是给定一个连通图。在每边ei上上赋予一个非负的权赋予一个非负的权w（ei），要求一个圈（未必是简单的），），要求一个圈（未必是简单的），并使圈的总权数最小。这个问题是我国的管梅谷同志在并使圈的总权数最小。这个问题是我国的管梅谷同志在1962年提出的，因此在国际上统称为年提出的，因此在国际上统称为中国邮递员问题中国邮递员问题。 求解这个问题的方法被称为求解这个问题的方法被称为奇偶点图上作业法奇偶点图上作业法。 奇偶点图上作业法算法口诀：奇偶点图上作业法算法口诀：先分奇偶点，奇点对对

39、联；先分奇偶点，奇点对对联；联线不重迭，重迭要改变；联线不重迭，重迭要改变；圈上联线长，不得过半圈圈上联线长，不得过半圈。运输路线规划运输路线规划 中国邮递员问题也可以表示为：中国邮递员问题也可以表示为：在一个有奇点的连通图在一个有奇点的连通图中。要求增加一些重复边，使得新的连通图不含有奇点，中。要求增加一些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。并且增加的重复边总权最小。 我们把增加重复边后我们把增加重复边后不含奇点不含奇点的新的连通图叫做的新的连通图叫做邮递路邮递路线线，而总权最小的邮递路线叫做，而总权最小的邮递路线叫做最优邮递路线。最优邮递路线。 下面我们来介绍初始邮

40、递路线的确定，改进，以及一个下面我们来介绍初始邮递路线的确定，改进，以及一个邮递路线是否是最优路线的判定标准的方法邮递路线是否是最优路线的判定标准的方法-图上图上作业法。作业法。运输路线规划运输路线规划（一）初始邮递路线的确定方法（一）初始邮递路线的确定方法 由于任何一个图中，奇点的个数为偶数，所以如果一个连由于任何一个图中，奇点的个数为偶数，所以如果一个连通图有奇点，就可以把它们两两配成对，而通图有奇点，就可以把它们两两配成对，而每对奇点之间每对奇点之间必有一条链（图是连通的），我们把这条链的所有边作为必有一条链（图是连通的），我们把这条链的所有边作为重复边追加到图中去，这样得到的新连通图必

41、无奇点，这重复边追加到图中去，这样得到的新连通图必无奇点，这就给出了初始投递路线。就给出了初始投递路线。 例如，在图例如，在图1中，中，v1是邮局所在地，并有四个奇点是邮局所在地，并有四个奇点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。 同 样 ， 任 取

42、 连 接同 样 ， 任 取 连 接 v6和和 v8的 一 条 链的 一 条 链(v8,v1,v2,v3,v4,v5,v6),在加入重复边在加入重复边v8,v1,v1,v2,v2,v3,v3,v4,v4,v5,v5,v6.于是，得到图于是，得到图2。运输路线规划运输路线规划图 2在连通图2中，没有奇点，故它是欧拉图。对于这条邮递路线，重复边的总长为:2W12+W23+W34+2W45+2W56+W67+W78+2W18=51。运输路线规划运输路线规划（二）改进邮递路线，使重复边的总长不断减少（二）改进邮递路线，使重复边的总长不断减少 从图从图2中可以看出，在边中可以看出，在边v1,v2旁边有两条

43、重复边，旁边有两条重复边，但是如果把他们都从图中去掉，所得到的连通图但是如果把他们都从图中去掉，所得到的连通图仍然无奇点，还是一个邮递路线，而总长度却有仍然无奇点，还是一个邮递路线，而总长度却有所减少。同理，在边所减少。同理，在边v1,v8,v4,v5,v5,v6旁边的重复旁边的重复边也是一样的。边也是一样的。 一般地，在邮递路线上，一般地，在邮递路线上，如果在边如果在边vi,vj旁边有两旁边有两条以上的重复边，从中去掉偶数条条以上的重复边，从中去掉偶数条，那么可以得，那么可以得到一个总长度较少的邮递路线。到一个总长度较少的邮递路线。运输路线规划运输路线规划 判定标准判定标准1 1：在最优邮递

44、路线上，图中的每一条边：在最优邮递路线上，图中的每一条边至多有一条重复边。至多有一条重复边。 按此判定标准，将图按此判定标准，将图2 2改为图改为图3 3，这时重复边的总权，这时重复边的总权减少为减少为2121。图 3运输路线规划运输路线规划 判定标准判定标准2 2。在最优邮递路。在最优邮递路线上，图中每一个圈的重复线上，图中每一个圈的重复边的总权小于或者等于该圈边的总权小于或者等于该圈总权的一半。总权的一半。在图在图3中，圈（中，圈（v2,v3,v4,v9,v2）的）的总权为总权为24，但圈上重复边的总，但圈上重复边的总权为权为14，大于该圈总权的一半。，大于该圈总权的一半。因此作一次改进，

45、在该圈上去因此作一次改进，在该圈上去掉重复边掉重复边v2,v3,v3,v4,加上重加上重复边复边v2,v9,v9,v4，如图，如图4所示。所示。这时重复边的总权减少为这时重复边的总权减少为10。图 4运输路线规划运输路线规划 在图在图4中，圈中，圈(v1,v2,v9,v6,v7,v8,v1)中重中重复边总权为复边总权为13，而该圈，而该圈的总权为的总权为24，不满足判，不满足判定标准定标准2。再次经过改。再次经过改进后，得到图进后，得到图5。此时，。此时，该圈中重复边的总权为该圈中重复边的总权为11，小于该圈的总权，小于该圈的总权24。 检查图检查图5中的每一个圈，中的每一个圈，判定标准判定标

46、准1和和2均已满足。均已满足。于是，图中的欧拉圈就于是，图中的欧拉圈就是最优邮递路线。是最优邮递路线。图 5运输路线规划运输路线规划（4）多起点、多终点，没有中间点）多起点、多终点，没有中间点运输问题运输问题 主要是将多个供应点的供应分配到多个顾客需求点，即运主要是将多个供应点的供应分配到多个顾客需求点，即运筹学中的运输问题。一般通过表上作业法求解。筹学中的运输问题。一般通过表上作业法求解。如果是产销不平如果是产销不平衡问题，转化成衡问题，转化成产销平衡问题。产销平衡问题。运输路线规划运输路线规划 一般产销平衡问题的模型为：一般产销平衡问题的模型为：A1、 A2、 Am 表示某物资货物的表示某

47、物资货物的m个产地；个产地；B1、B2、Bn 表示某货物的表示某货物的n个销地；个销地；ai 表示产地表示产地Ai的产量；的产量； bj 表示销地表示销地Bj 的销量；的销量； cij 表示把货物从产地表示把货物从产地Ai运往销地运往销地Bj的单位运价；的单位运价； 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量。的运输量。02121. .min1111ijnjiijmijijijminjijXmiaXnjbXtsXCZ，运输路线规划运输路线规划 【例例】某部门有某部门有3个生产同类产品的工厂（产地），生个生产同类产品的工厂（产地），生产的产品由产的产品由4个销售点（销地）出售，各工厂的