运输管理与配送.ppt

《运输管理与配送.ppt》由会员分享，可在线阅读，更多相关《运输管理与配送.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运输管理与配送2021/9/242021/9/241 1大纲n n物流运输业发展趋势及存在问题n n各种运输方式的技术经济特点n n运输合理化n n运输决策问题n n运输管理的计算方法2021/9/242021/9/242 2物流运输业发展趋势及存在问题2021/9/242021/9/243 3物流业的重要性n n据最新估算，2004年我国社会物流总额达38.4万亿元，同比增长近30%；由此引起的货运、仓储和管理等活动的社会物流总成本高达2.9万亿元，占当年GDP的比重为21%。这一比重多年来居高不下，高于发达国家810个百分点。2021/9/242021/9/244 4物流业重要性n n据国

2、内有经验物流供应商提供的信息显示，运用信息技术，优化整合工业的采购、库存、储运、销售流程，我国可降低现有物流成本的50%60%。另据匡算，在现阶段我国物流成本占GDP的比重降低1%，则可以在货物运输、仓储方面节能降耗1000亿元以上。在此基础上，倘若我国能逐步逼近工业化国家物流的平均成本（物流成本占GDP的12%），则可节约当年物流成本8000亿元。2021/9/242021/9/245 5运输是物流的支柱。说到物流，人们就会认为运输是物流的支柱。说到物流，人们就会认为“那是运输产业那是运输产业”运输成本通常占了物流成本中的最大部分。运输成本通常占了物流成本中的最大部分。2021/9/2420

3、21/9/246 6美国企业物流成本(2002.9-2003.9)成本内容成本内容占物流总成本的百分占物流总成本的百分比（比（%）占销售额的百分比占销售额的百分比(%)(%)运输成本运输成本35352.632.63存货持有成本存货持有成本35352.602.60仓储成本仓储成本21211.601.60订单处理订单处理/客户服务成本客户服务成本5 50.40.4管理成本管理成本4 40.280.28物流总成本物流总成本1001007.527.522021/9/242021/9/247 7 2003年度日本企业物流成本物流成本物流成本构成百分比（构成百分比（%）支付形支付形态态企业内物流费企业内物

4、流费22.522.5支付给子公司物流费支付给子公司物流费21.121.1支付给专业物流公司物流费支付给专业物流公司物流费56.456.4物流成本物流成本100100物流范物流范围围销售物流费销售物流费73.973.9企业内物流费企业内物流费16.516.5供应物流费供应物流费9.69.6物流成本物流成本100100物流功物流功能能运输费运输费57.057.0保管费保管费17.217.2其他其他25.825.8物流成本物流成本1001002021/9/242021/9/248 8华东地区储运业占GDP比重图变化图2021/9/242021/9/249 92021/9/242021/9/24101

5、0华东三省一市运价变化图2021/9/242021/9/241111国内经济形势导致运输行业整体利润降低：国内经济形势导致运输行业整体利润降低：物流企业高 端 客 户个体司机/运输公司价格/成本传统运输企业在激烈的竞争中分化：传统运输企业在激烈的竞争中分化：服务/方案2021/9/242021/9/241212华东主要省市物流成本占GDP的比重图2021/9/242021/9/241313n n我国物流过程中物资消耗严重：全国全年运输中物资损失达全国全年运输中物资损失达30003000亿元以上，亿元以上，其中仅蔬菜运输损失就达其中仅蔬菜运输损失就达13541354亿元亿元n n我国运输车辆空载

6、率达37%生产企业为生产企业为34.7%34.7%商业企业为商业企业为38.5%38.5%物流企业为物流企业为39.8%39.8%2021/9/242021/9/241414各种运输方式的技术经济特点2021/9/242021/9/241515 各种运输方式的技术经济特点铁路、公路、水路、航空和管道五种运输方式在技术经济特征各有其特点。每一种运输方式有其优势但同时又存在其不足。因此，如何扬长避短，充分发挥各种运输方式的优点，并按照各种运输方式技术经济特点组成分工协作、有机结合、连接贯通、布局合理的交通运输体系是我们重点要考虑的问题。2021/9/242021/9/241616一、铁路运输n n

7、1.铁路运输的特点n n1)很少受天气影响；n n2)安全、节能；n n3)中长距离运货运费低廉；n n4)运输批量大；n n5）可以高速运输。2021/9/242021/9/2417172.铁路运输的优点n n1）单车装载量大；运输能力大；n n2）车速较高;n n3)可以方便地实现集装箱运输及多方式联运。2021/9/242021/9/241818铁路运输的缺点n n1.原始投资较大，建设周期长；n n2.货物的在途时间较长；n n3.铁路运输中的货损率比较高；n n4.不能实现“门到门”运输，通常要依靠其它运输方式配合，才能完成运输的任务2021/9/242021/9/241919二、公

8、路运输n n特点特点:n n公路运输最显著的特点是公路运输的灵活性、从技术经济特性方面来看，其灵活性在所有运输方式中最强。2021/9/242021/9/242020公路运输的优缺点n n1.适应性强2.机动灵活n n3.快速运达4.方便性好n n5.经济性好6.联运范围广2021/9/242021/9/242121三、水路运输n n涵义：水路运输是指利用船舶、排筏和其他浮运工具，在江、河、湖泊、人工水道及海洋上运送旅客和货物的一种运输方式。n n分类：水路运输按其航行的区域，大体上可划分为运洋运输、沿海运输和内河运输三种类型。2021/9/242021/9/242222 水路运输的特点n n

9、（一）运量大n n（二）占地少n n（三）基建投资少n n（四）节省能源n n（五）运费低2021/9/242021/9/242323四、航空运输的特点 n n1速度快2机动性大3舒适、安全4基本建设周期短、投资少航空货运市场三种方式：直接销售、代理销售和联运。2021/9/242021/9/242424五、管道运输的特点和缺点 n n管道运输具有以下其他运输方式不具有的优点：1不受地面气候影响并可连续作业。2运输的货物不需包装，节省包装费用。3货物在管道内移动，货损货差率低。2021/9/242021/9/242525运营特征运营特征运营特征运营特征铁路铁路铁路铁路公路公路公路公路水路水路水

10、路水路管道管道管道管道航空航空航空航空速度速度速度速度3 3 3 34 4 4 42 2 2 21 1 1 15 5 5 5可得性可得性可得性可得性4 4 4 45 5 5 52 2 2 21 1 1 13 3 3 3可靠性可靠性可靠性可靠性3 3 3 34 4 4 42 2 2 25 5 5 51 1 1 1能力能力能力能力4 4 4 43 3 3 35 5 5 51 1 1 12 2 2 2频率频率频率频率2 2 2 24 4 4 41 1 1 15 5 5 53 3 3 3合计得分合计得分合计得分合计得分161616162020202012121212131313131414141420

11、21/9/242021/9/242626 运输合理化 2021/9/242021/9/242727一、运输的合理与不合理 n n（一）成本、速度和一致性，是影响运输合理化的重要因素n n运输成本是指为两个地理位置间的运输所支付的款项以及与管理和维持运输中的存货相关费用。物流系统的设计应该利用能把系统总成本降到最低程度的运输，这意味着最低的运输总成本并不意味着合理化的运输。2021/9/242021/9/242828（二）运输方式的选择n n五五种种基基本本的的运运输输方方式式（铁铁路路、公公路路、水水路路、航航空空、管道）管道）n n水路运输具有运量大，成本低的优点；水路运输具有运量大，成本低

12、的优点；n n公公路路运运输输则则具具有有机机动动灵灵活活，便便于于实实现现货货物物门门到到门门的运输的特点；的运输的特点；n n铁铁路路运运输输的的主主要要优优点点是是不不受受气气候候影影响响，可可深深入入内内陆和横贯内陆实现货物长距离的准时运输；陆和横贯内陆实现货物长距离的准时运输；n n航空运输的主要优点是可实现货物的快速运输航空运输的主要优点是可实现货物的快速运输。2021/9/242021/9/242929（三）不合理运输表现形式n n1 1返程或起程空驶返程或起程空驶返程或起程空驶返程或起程空驶n n2.2.对流运输对流运输对流运输对流运输n n3 3迂回运输迂回运输迂回运输迂回运

13、输n n4 4过远运输过远运输过远运输过远运输n n5 5倒流运输倒流运输倒流运输倒流运输n n6 6无效运输无效运输无效运输无效运输n n7 7运力选择不当运力选择不当运力选择不当运力选择不当2021/9/242021/9/243030 2.对流运输n n指的是同种货物以不同的发送点同时或先后作面指的是同种货物以不同的发送点同时或先后作面指的是同种货物以不同的发送点同时或先后作面指的是同种货物以不同的发送点同时或先后作面对面的运输，并且彼此重复对方旅程的全部或一对面的运输，并且彼此重复对方旅程的全部或一对面的运输，并且彼此重复对方旅程的全部或一对面的运输，并且彼此重复对方旅程的全部或一部。对

14、流运输是明显的不合理运输，是对运力的部。对流运输是明显的不合理运输，是对运力的部。对流运输是明显的不合理运输，是对运力的部。对流运输是明显的不合理运输，是对运力的纯浪费。纯浪费。纯浪费。纯浪费。n n在在在在同同同同一一一一交交交交通通通通线线线线上上上上发发发发生生生生的的的的相相相相向向向向运运运运输输输输成成成成为为为为明明明明显显显显的的的的相相相相向向向向运运运运输输输输，它它它它易易易易于于于于被被被被识识识识别别别别出出出出来来来来，如如如如果果果果相相相相向向向向运运运运输输输输发发发发生生生生在在在在走走走走向向向向大大大大致致致致平平平平行行行行，距距距距离离离离不不不不远

15、远远远的的的的线线线线路路路路上上上上，或或或或者者者者线线线线路路路路相相相相同同同同，但但但但时时时时间间间间不不不不同同同同，则则则则称称称称之之之之为为为为隐隐隐隐蔽蔽蔽蔽的的的的相相相相向向向向运运运运输输输输，在在在在作作作作城城城城市市市市和和和和区区区区域域域域布布布布局局局局规规规规划划划划的的的的货货货货流流流流分分分分析析析析时时时时，必必必必须须须须予予予予以以以以注意。注意。注意。注意。2021/9/242021/9/2431313.迂回运输n n 在在在在货货货货物物物物发发发发点点点点与与与与收收收收点点点点之之之之间间间间由由由由两两两两条条条条以以以以上上上上

16、的的的的同同同同类类类类交交交交通通通通线线线线可可可可以以以以采用时，未能利用最短路径的运输，称之为迂回运输。采用时，未能利用最短路径的运输，称之为迂回运输。采用时，未能利用最短路径的运输，称之为迂回运输。采用时，未能利用最短路径的运输，称之为迂回运输。n n 在在在在交交交交通通通通网网网网发发发发达达达达，特特特特别别别别时时时时拥拥拥拥有有有有环环环环状状状状交交交交通通通通线线线线时时时时，迂迂迂迂回回回回运运运运输输输输是是是是最最最最容容容容易易易易出出出出现现现现的的的的。在在在在环环环环状状状状线线线线路路路路条条条条件件件件下下下下，货货货货物物物物调调调调运运运运的的的的

17、重重重重要要要要原原原原则则则则是是是是：收收收收点点点点和和和和发发发发点点点点间间间间的的的的货货货货物物物物行行行行走走走走公公公公路路路路数数数数，不不不不应应应应该该该该超超超超过过过过整整整整个个个个环环环环状状状状线线线线路路路路总总总总长长长长度度度度的的的的一一一一半半半半，即即即即必必必必须须须须小小小小于于于于或或或或等等等等于于于于环环环环形形形形园园园园长长长长的的的的二二二二分分分分之之之之一一一一。根根根根据据据据上上上上述述述述原原原原则则则则，在在在在规规规规划划划划货货货货流流流流时时时时，可可可可以以以以编编编编出出出出现现现现状状状状交通线的最短路径图。

18、交通线的最短路径图。交通线的最短路径图。交通线的最短路径图。2021/9/242021/9/2432324.过远运输n n这是一种舍近求远物资运输。这是一种舍近求远物资运输。n n从产生的根源来看，过远运输不外两类，从产生的根源来看，过远运输不外两类，一类是由于产销计划和运输计划不当，人一类是由于产销计划和运输计划不当，人为造成的物资调拨不合理，从而引起的货为造成的物资调拨不合理，从而引起的货物运行距离的加大。另一类是由生产力布物运行距离的加大。另一类是由生产力布局所造成的，局所造成的，2021/9/242021/9/2433335.重复运输n n重复运输是指同一批货物由产地运抵目的重复运输是

19、指同一批货物由产地运抵目的地地,没经过任何加工和必要的作业没经过任何加工和必要的作业,也不是为也不是为联运及中转需要联运及中转需要,又重新装运到别处的现象。又重新装运到别处的现象。n n重复运输引起运量的重复计算，造成多余重复运输引起运量的重复计算，造成多余的中转、倒装，虚幻耗了装卸费用，增大的中转、倒装，虚幻耗了装卸费用，增大了货损，增加了作业量了货损，增加了作业量。2021/9/242021/9/243434重复运输举例n n10T10Tn n10T10Tn n10T10Tn nn n10T10Tn n10T10T10T10T2021/9/242021/9/2435356.倒流运输n n是

20、指货物从销地或中转地向产地或起运地指货物从销地或中转地向产地或起运地回流的一种运输现象。其不合理程度要甚回流的一种运输现象。其不合理程度要甚于对流运输，其原因在于，往返两程的运于对流运输，其原因在于，往返两程的运输都是不必要的，形成了双程的浪费。倒输都是不必要的，形成了双程的浪费。倒流运输也可以看成是隐蔽对流的一种特殊流运输也可以看成是隐蔽对流的一种特殊形式。形式。2021/9/242021/9/2436367.运力选择不当n n未考虑各种运输工具的优缺点而进行不适未考虑各种运输工具的优缺点而进行不适当的选择造成不合理的运输。当的选择造成不合理的运输。n n不不同同的的运运输输工工具具各各有有

21、其其有有缺缺点点，故故在在运运输输过过程程中中，应应根根据据使使各各种种交交通通工工具具取取长长补补短短、相相互互协协作作、综综合合利利用用的的原原则则进进行行选选择择，否否则就会形成不必要的浪费。则就会形成不必要的浪费。2021/9/242021/9/243737二、影响运输合理化的外部因素 n n影影响响运运输输合合理理化化的的外外部部因因素素主主要要有有以以下下五五个方面：个方面：n n（一）政府（一）政府n n（二）资源分布状况（二）资源分布状况n n（三）国民经济结构的变化（三）国民经济结构的变化n n（四）运输网布局的变化（四）运输网布局的变化n n（五）运输决策的参与者（五）运输

22、决策的参与者 2021/9/242021/9/243838三、影响运输合理化的内部因素n n（一）运输距离n n（二）运输环节n n（三）运输工具n n（四）运输时间n n（五）运输费用2021/9/242021/9/243939四、运输合理化的有效措施n n（一）提高运输工具实载率n n（二）减少动力投入，增加运输能力n n1“满载超轴”。n n2水运拖排和拖带法。n n3顶推法。n n4汽车挂车法。n n（三）发展社会化运输体系2021/9/242021/9/244040四、运输合理化的有效措施n n（四）开展中短距离铁路公路分流，“以公代铁”的运输n n（五）尽量发展直达运输n n（六）

23、配载运输n n（七）“四就”直拨运输n n（八）预先对货物进行加工2021/9/242021/9/244141运输决策问题2021/9/242021/9/244242运输决策问题n n委托运输还是自营运输委托运输还是自营运输n n运输服务的选择运输服务的选择n n承运人的选择承运人的选择n n路线调度计划路线调度计划2021/9/242021/9/244343n n委托运输还是自营运输委托运输还是自营运输自营运输的优势自营运输的优势n n服务的可靠性；服务的可靠性；n n缩短订货周期；缩短订货周期；n n应对紧急事件的能力；应对紧急事件的能力；n n改善与客户的关系；改善与客户的关系；委托运输

24、可以使企业专心于开发自己的核心竞委托运输可以使企业专心于开发自己的核心竞争力，但是增加了交易成本，也增加了对运输争力，但是增加了交易成本，也增加了对运输控制的难度。控制的难度。2021/9/242021/9/244444n n运输服务的选择运输服务的选择据研究，在选择运输服务时，决策者认为最据研究，在选择运输服务时，决策者认为最重要的因素是：重要的因素是：运输成本、速度和一致性运输成本、速度和一致性。成本的权衡成本的权衡设有四种运输方式设有四种运输方式n n铁路：费率为铁路：费率为铁路：费率为铁路：费率为0.100.10，运输时间，运输时间，运输时间，运输时间2424天，每年可运输天，每年可运

25、输天，每年可运输天，每年可运输1010次；次；次；次；n n铁铁铁铁+卡卡卡卡:费率为费率为费率为费率为0.150.15，运输时间，运输时间，运输时间，运输时间1414天，每年可运输天，每年可运输天，每年可运输天，每年可运输2020次；次；次；次；n n卡车：费率为卡车：费率为卡车：费率为卡车：费率为0.200.20，运输时间，运输时间，运输时间，运输时间5 5天，每年可运输天，每年可运输天，每年可运输天，每年可运输2020次；次；次；次；n n航空：费率为航空：费率为航空：费率为航空：费率为1.401.40，运输时间，运输时间，运输时间，运输时间2 2天，每年可运输天，每年可运输天，每年可运

26、输天，每年可运输4040次；次；次；次；2021/9/242021/9/244545设库存成本设库存成本I=30%/年，单位产品出厂年，单位产品出厂时的价值为时的价值为C=30美圆，运输时间美圆，运输时间为为T，年需求量为年需求量为D，工厂和仓库的工厂和仓库的平均库存均为平均库存均为K，运输费率为运输费率为R，则则每种运输方式的总成本为每种运输方式的总成本为RD+ICDT/365+ICK+I(C+R)K2021/9/242021/9/244646如果年需求量为如果年需求量为如果年需求量为如果年需求量为700,000700,000件，工厂和仓库的平均库存一样，件，工厂和仓库的平均库存一样，件，工

27、厂和仓库的平均库存一样，件，工厂和仓库的平均库存一样，在铁路运输时需要在铁路运输时需要在铁路运输时需要在铁路运输时需要100,000100,000件；卡车和铁路卡车混合时为件；卡车和铁路卡车混合时为件；卡车和铁路卡车混合时为件；卡车和铁路卡车混合时为50,00050,000件；航空运输时为件；航空运输时为件；航空运输时为件；航空运输时为2,50002,5000件；则综合结果如下：件；则综合结果如下：件；则综合结果如下：件；则综合结果如下：2021/9/242021/9/244747考虑竞争等因素考虑竞争等因素更好的运输服务可以吸引更多的业务，更多的业更好的运输服务可以吸引更多的业务，更多的业务

28、可以得到更多的收益。务可以得到更多的收益。在选择运输方式时，要考虑竞争对手的行为和买在选择运输方式时，要考虑竞争对手的行为和买方的需求。方的需求。2021/9/242021/9/244848n n承运人的选择承运人的选择承运人的选择要考虑企业的具体业务需求，重点承运人的选择要考虑企业的具体业务需求，重点要放在收货人而不是发货人所认为重要的内容要放在收货人而不是发货人所认为重要的内容上。对承运人的正确评价可以通过利用承运人上。对承运人的正确评价可以通过利用承运人的运输记录、客户的意见等给出每个指标的评的运输记录、客户的意见等给出每个指标的评价。价。2021/9/242021/9/244949评估

29、因素评估因素评估因素评估因素相对重相对重相对重相对重要性要性要性要性承运人表现承运人表现承运人表现承运人表现承运人承运人承运人承运人得分得分得分得分成本成本成本成本3 3 3 3*3 3 3 3=9 9 9 9运输时间运输时间运输时间运输时间1 1 1 1*2 2 2 2=2 2 2 2时间可靠性时间可靠性时间可靠性时间可靠性3 3 3 3*2 2 2 2=6 6 6 6能力能力能力能力2 2 2 2*2 2 2 2=4 4 4 4方便得到方便得到方便得到方便得到2 2 2 2*2 2 2 2=4 4 4 4安全安全安全安全2 2 2 2*1 1 1 1=2 2 2 2272727272021

30、/9/242021/9/245050路线调度计划n n最短路径问题最短路径问题最短路径问题最短路径问题n n运输调配问题运输调配问题运输调配问题运输调配问题n n车辆调度问题车辆调度问题车辆调度问题车辆调度问题2021/9/242021/9/245151运输问题的计算方法2021/9/242021/9/245252几种典型的运输问题n n最短路径问题最短路径问题最短路径问题最短路径问题单个起点单个终点的最短路径问题单个起点单个终点的最短路径问题单个起点单个终点的最短路径问题单个起点单个终点的最短路径问题n n运输调配问题运输调配问题运输调配问题运输调配问题n n旅行商旅行商旅行商旅行商问题问题

31、问题问题（Traveling Salesman Traveling Salesman Problem,TSP)Problem,TSP)起讫点相同起讫点相同起讫点相同起讫点相同n n车辆调度问题车辆调度问题车辆调度问题车辆调度问题(Vehicle Routing Problem(Vehicle Routing Problem VRPVRP考虑到路线优化，车辆装载、时间要求，货物需求考虑到路线优化，车辆装载、时间要求，货物需求考虑到路线优化，车辆装载、时间要求，货物需求考虑到路线优化，车辆装载、时间要求，货物需求2021/9/242021/9/2453531、最短路径问题2021/9/242021

32、/9/245454n nDijkstr法n n原理：如果v0,v1,vn是最短路径，则v0,v1,vn-1也是最短路径。1、找出(n-1)个节点距离起点的最近路径的路线，并计算其距离。2、在此基础上，再找出n个节点的最短路径2021/9/242021/9/245555v0v1v2v3v4v53517168961.l(v1)=3,l(v2)=5;l(v1)=3 已解：(v1(0 1),3)2.l(v2)=4,l(v3)=10,l(v2)=4 (v2(0 1 2),4)3.l(v3)=10,l(v4)=12,l(v3)=10 (v3(0 1 3),10)4.l(v4)=11 ;l(v5)=19,l

33、(v4)=11 (v4(0 1 3 4),11)5.l(v5)=17.(v5(0 1 3 4 5),17)712021/9/242021/9/2456562 运输调配问题2021/9/242021/9/245757多起点多终点的问题多起点多终点的问题例：一家肥皂和清洗剂生产商在例：一家肥皂和清洗剂生产商在X,Y,ZX,Y,Z有三家生有三家生产厂，主要的仓库位于产厂，主要的仓库位于A,BC,D,E.A,BC,D,E.预计下年各预计下年各仓库的需求为，仓库的需求为，仓库仓库年销量（千箱）年销量（千箱）A A5050B B1010C C6060DD3030E E2020总计总计1701702021/

34、9/242021/9/245858n n各生产厂家到各仓库每千箱的运费：A AB BC CDDE EX X240240300300160160500500360360Y Y420420440440300300200200220220Z Z300300340340300300480480400400从到2021/9/242021/9/245959n n工厂的能力限制：X100,000箱Y60,000箱Z50,000箱。公司希望建立一个调拨计划使得运输成本最小。2021/9/242021/9/246060数学模型：数学模型：设设X X1111是从第一个工厂（是从第一个工厂（X X）运到第一个仓库运

35、到第一个仓库(A)A)的千箱数的千箱数;同理设同理设X Xij ij是从第是从第i i个工厂到第个工厂到第j j个仓库的千箱数，个仓库的千箱数，i=1,2,3;j=1,2,3,4,5;i=1,2,3;j=1,2,3,4,5;则问题就是要最小化：则问题就是要最小化：C=240XC=240X1111+300X+300X1212+160X+160X1313+500X+500X1414+360X360X1515+420X+420X2121+440X+440X2222+300X+300X2323+200X200X2424+220X+220X2525+300X+300X3131+340X+340X3232

36、+300X300X3333+480X+480X3434+400X+400X35352021/9/242021/9/246161变量变量X Xij ij要满足仓库需求的约束：要满足仓库需求的约束：X X1111+X+X2121+X+X3131=50=50XX1212+X+X2222+X+X3232=10=10X X1313+X+X2323+X+X3333=60=60X X1414+X+X2424+X+X3434=30=30X X1515+X+X2525+X+X3535=20=20和生产能力的约束：和生产能力的约束：X X1111+X+X1212+X+X1313+X+X1414+X+X1515 1

37、00100 X X2121+X+X2222+X+X2323+X+X2424+X+X2525 6060 X X3131+X+X3232+X+X3333+X+X3434+X+X3535 5050 另外还有：另外还有：X Xij ij 0 02021/9/242021/9/246262利用一般的线性规划解法，就可以解得：X11=40；X13=60；X24=30；X25=20；X31=10；X32=10；其余为零。406010103020CincinnatiDenverAtlantaNew YorkBostonChicagoLos AngelesDallas2021/9/242021/9/246363

38、3 旅行商问题TSP1 1、旅行商问题、旅行商问题（Traveling Salesman Problem,TSP)一个旅行者从某地出发，经过所有要到达的城市后，返回出发地，要求总行程最短。n n对应的配送问题：一辆车从配送中心出发，为全部客户送货，使总行驶里程最短。2021/9/242021/9/246464起讫点重合的问题起讫点重合的问题起讫点重合的路径问题一般被称为旅行商问题。起讫点重合的路径问题一般被称为旅行商问题。直觉方法、解析法和启发式方法是求解这类问题的有效方直觉方法、解析法和启发式方法是求解这类问题的有效方法。法。1 1、直觉法、直觉法例如，好的路线规划中应没有线路交叉，呈凸形或

39、水滴形。例如，好的路线规划中应没有线路交叉，呈凸形或水滴形。2021/9/242021/9/246565n n行车路线和时刻表的制订行车路线和时刻表的制订原则原则n n划分站点群以分派车辆时，将距离靠近的站点划划分站点群以分派车辆时，将距离靠近的站点划在一起；在一起；n n在安排每天各车的运输线路时，同样要使它们的在安排每天各车的运输线路时，同样要使它们的站点群不重叠；站点群不重叠；n n从距离仓库最远的站点开始划分站点群，分派车从距离仓库最远的站点开始划分站点群，分派车辆；辆；n n各卡车的行车路线应呈水滴状，避免交叉；各卡车的行车路线应呈水滴状，避免交叉；n n对于孤立于站点群之外的站点，

40、可采用其它配送对于孤立于站点群之外的站点，可采用其它配送方式，如第三方服务；方式，如第三方服务；n n各站点规定的取货各站点规定的取货/送货时间要与行车路线之间送货时间要与行车路线之间协调；协调；2021/9/242021/9/2466662021/9/242021/9/246767 2 2 解析法：建立线性规划模型：解析法：建立线性规划模型：X Xijkijk=1 =1 车辆车辆 k k 从从 i i 点行驶到点行驶到 j j点点;X Xijkijk=0 =0 否则。否则。EXCEL EXCEL 软件求解：软件求解：X Xijkijk，如果，如果X Xijkijk=1=1，即表示从，即表示从

41、i i地到地到j j地用地用k k车配送。否则，车配送。否则，X Xijkijk=0=02021/9/242021/9/24686833启发式方法启发式方法启发式方法中很多启发式方法中很多，例如，例如最近邻点法，最近插入法等。最近邻点法，最近插入法等。n n最近邻点法就是从某点开始，总是找离目前位置最近最近邻点法就是从某点开始，总是找离目前位置最近的、还未到过的节点作为下一点，直到所有节点走完，的、还未到过的节点作为下一点，直到所有节点走完，再回到起点。得到的结果常常是不理想的。再回到起点。得到的结果常常是不理想的。n n最近插入法要更进一步，在选择下一点时，不仅仅只最近插入法要更进一步，在选

42、择下一点时，不仅仅只考虑当前的一点，而是考虑所有已走过的点。另外，考虑当前的一点，而是考虑所有已走过的点。另外，它每一步是整个回路的扩张，即从一开始它就考虑回它每一步是整个回路的扩张，即从一开始它就考虑回到起点的成本。方法描述如下：到起点的成本。方法描述如下：（1 1）找出离起点最近的节点，构成子回路找出离起点最近的节点，构成子回路T T。（2 2）重复（重复（3 3）直到）直到T T包含所有节点：包含所有节点：（3 3）从子回路）从子回路T T以外的节点中找出离回路以外的节点中找出离回路T T中节点最近的节中节点最近的节点点v v，在在T T中找到一条边中找到一条边(a,ba,b)，使使av

43、+vb-abav+vb-ab最小，将最小，将v v插在插在a,ba,b之间，用之间，用av+vbav+vb代替代替(a,ba,b)，构成新的回路构成新的回路TT2021/9/242021/9/246969例如一家面包房每天要向五家零售店送货，各例如一家面包房每天要向五家零售店送货，各点之间的行车时间如下：点之间的行车时间如下：自 到面包房0零 售店1零 售店2零 售店3零 售店4零 售店5面 包房002450385520零 售店122032234518零 售店247350152160零 售店339271701425零 售店457421816042零 售店5211657214102021/9/2

44、42021/9/247070n n扫描法扫描法扫描法扫描法方法简单，在较快时间内得到一个合理解。方法简单，在较快时间内得到一个合理解。方法简单，在较快时间内得到一个合理解。方法简单，在较快时间内得到一个合理解。1.1.在地图或方格图上确定所有站点的位置；在地图或方格图上确定所有站点的位置；在地图或方格图上确定所有站点的位置；在地图或方格图上确定所有站点的位置；2.2.划分站点群：自仓库向任意方向划一直线，沿划分站点群：自仓库向任意方向划一直线，沿划分站点群：自仓库向任意方向划一直线，沿划分站点群：自仓库向任意方向划一直线，沿一个方向（顺时针或逆时针）旋转，依次根据一个方向（顺时针或逆时针）旋转

45、，依次根据一个方向（顺时针或逆时针）旋转，依次根据一个方向（顺时针或逆时针）旋转，依次根据一辆车能装载的站点划分出所有的站点群；一辆车能装载的站点划分出所有的站点群；一辆车能装载的站点划分出所有的站点群；一辆车能装载的站点划分出所有的站点群；3.3.用用用用“水滴法水滴法水滴法水滴法”或其它方法确定每个站点群的路或其它方法确定每个站点群的路或其它方法确定每个站点群的路或其它方法确定每个站点群的路线计划。线计划。线计划。线计划。缺点：缺点：缺点：缺点：在划分站点群时，没有考虑在途总运行时间、各站在划分站点群时，没有考虑在途总运行时间、各站在划分站点群时，没有考虑在途总运行时间、各站在划分站点群时

46、，没有考虑在途总运行时间、各站点的取货点的取货点的取货点的取货/送货时间等，有些地图的线路分布送货时间等，有些地图的线路分布送货时间等，有些地图的线路分布送货时间等，有些地图的线路分布不均匀。不均匀。不均匀。不均匀。可以对结果调整可以对结果调整可以对结果调整可以对结果调整2021/9/242021/9/247171节约法节约法节约法的目标是使所有车辆的行驶总里程最短，并且服务节约法的目标是使所有车辆的行驶总里程最短，并且服务的车辆数最小。的车辆数最小。1.1.首先假设每个站点都有一辆虚拟的卡车提供服务，随首先假设每个站点都有一辆虚拟的卡车提供服务，随后返回仓库；后返回仓库；2.2.将两个站点合

47、并到同一线路上，缩短了路线里程，减将两个站点合并到同一线路上，缩短了路线里程，减少了一辆车；少了一辆车；OAB节约的里程为dOA+dAO+dOB+dBO(dOA+dAB+dBO)=dAO+dOB dAB 2021/9/242021/9/247272考虑节约路程最多的两个站点，如果合并后能够满考虑节约路程最多的两个站点，如果合并后能够满足各种约束条件，如：载货能力、时间限制、足各种约束条件，如：载货能力、时间限制、路程条件等，则合并；否则考虑节约路程次多路程条件等，则合并；否则考虑节约路程次多的站点；的站点；重复重复2 2，直到完成路线设计。，直到完成路线设计。优点：在划分站点群和制订路线规划时

48、可以考虑各优点：在划分站点群和制订路线规划时可以考虑各种约束因素。种约束因素。LogwareLogware中的中的ROUTER;ROUTER;2021/9/242021/9/2473734、车辆调度问题2021/9/242021/9/247474启发式算法：（节约法)Sij=2d0i+2d0j d0i-d0j dij =d0i+d0j dij配送中心 P0PiPjd0id0jdij2021/9/242021/9/247575n n步骤：1 1、各客户与物流中心相连，得总费用；、各客户与物流中心相连，得总费用；2 2、计算每两个用户间的节约里程；、计算每两个用户间的节约里程；3 3、将各对用户间

49、的节约里程排序；、将各对用户间的节约里程排序；4 4、从最大节约里程的用户对开始连接，逐渐、从最大节约里程的用户对开始连接，逐渐形成回路，直到达到车辆载重标准。形成回路，直到达到车辆载重标准。5 5、将已连接的客户从剩余的节约里程排序重、将已连接的客户从剩余的节约里程排序重去掉；去掉；6 6、再从剩下的节约里程集合中继续以上过程，、再从剩下的节约里程集合中继续以上过程，直到全部用户都连接起来。直到全部用户都连接起来。2021/9/242021/9/247676554676368552467910471181043249（0.4）（0.8）（1.5）（0.7）（1.4）（1.5）（0.6）（0.

50、8）（0.5）（0.6）2吨车、吨车、4吨车吨车2021/9/242021/9/247777节约里程表节约里程表 最短距离表最短距离表P1P14 49 91414181818181313141411114 41515P2P25 51010141417171212131315158 88 81111P3P35 59 9151510101111171713134 47 71010P4P46 6131311111212181815150 03 36 61010P5P57 710101212181815150 00 00 03 39 9P6P66 68 8171715150 00 00 00 01 1