基于运输系统优化的安吉汽车物流设计方案.doc

基于运输系统优化的安吉汽车物流设计方案基于运输系统优化的安吉汽车物流设计方案 第五届“楚天杯”物流设计大赛决赛作品 团队名称：风火轮 团队成员：王文锦 陈於鑫 张欢 刘巧云 杨敏目录1.整体背景31.1我国汽车物流行业的发展现状31.2汽车物流运行模式31.3汽车物流的配送模式42.安吉物流现状分析52.1安吉物流现状描述52.2安吉公司的运输方式选择及分析62.3安吉物流的运输要求73.选题依据83.1运输系统优化在汽车物流行业中的重要性83.2所选方案83.3选择依据83.4方案框架104.安吉物流现状下多式联运的探究114.1安吉物流运输方式存在的问题114.2基本运输方式及其优缺点114.3整数规划模型的建模过程134.4整数规划模型制定出安吉多式联运方案184.5小结225.配送线路的优化235.1安吉配送线路存在的问题235.2配送线路优化的意义235.3配送线路设计思路235.4用节约里程法求出最优配送线路235.5小结366.信息技术下运输调度系统的优化366.1运输调度系统的优化与运输系统的关系366.2共享资源数据库平台的创建386.21 创建共享资源数据库平台的原因和意义386.3 基于GPS的车辆运输调度406.4安吉物流调度模式的改进436.5小结467.安吉物流运输工具和仓库创新与改进467.1运输工具和仓库创新与改进的背景467.2对于零部件与整车物流的协调与共享的解决办法487.3运输工具与仓库创新小结548.设计方案总结55641.整体背景1.1我国汽车物流行业的发展现状我国现行的主体汽车物流模式是供产销一体化的自营物流，即汽车产品原材料、零部件、辅助材料等的购进物流、汽车产品的制造物流与分销物流等物流活动全部由汽车制造企业完成。制造企业既是汽车生产活动的组织者、实施操作者，又是企业物流活动的组织者与实施者。调查结果表明物流成本每降低1个百分点，每年就可增加约100亿元的纯利润收入。因此，降低物流成本毫无疑问已经成为汽车生产企业第二利润增长点。 汽车消费需求的强劲增长，带动了汽车产量的快速增长，而汽车市场的迅速扩容也拉动了汽车物流行业的迅速发展，为我国汽车物流行业的迅速崛起提供了前所未有的发展机遇。但同时我们也必须看到所面临的一系列急待解决的问题。目前，这些问题随着汽车物流的不断发展暴露得更加突出。1.2汽车物流运行模式汽车物流是集现代运输、仓储、保管、搬运、包装、产品流通及物流信息于一体的综合性管理，是沟通原料供应商、生产商、批发商、零件商、物流公司及最终用户的桥梁，更是实现商品从生产到消费各个流通环节的有机结合。我国现性的主体汽车物流模式是供产销一体化的自营物流，即企业产品原材料、零部件、辅助材料等的购进物流、汽车产品的制造物流与分销物流等物流活动全部由汽车制造企业完成。制造企业即是企业生产活动的组织者、实施操作者，又是企业物流活动的组织者与实施者。 在这种模式下，制造商对供应物流、制造物流及分销物流拥有完全的控制权，能够掌握第一手客户信息，有利于改善客户服务和对整个物流进行协调与控制。但是，随着物流业务的不断扩大，供应全球化和电子商务对汽车产品物流的信息化、自动化和柔性化提出了全新的要求。要求制造商具有更加强大的物流实力，不断加大对物流的投入以适应电子商务发展的需要。这些变化对自营物流而言，不但加重了制造商的资金负担，而且也不能充分发挥分工的经济优势，会降低汽车产品的总体物流效率。同时，自营物流居于整车生产企业自身，往往只从整车生产企业的利益出发，过多地强调保障整个生产企业生产的连续性，会要求零配件生产企业提供远大于实际需要的库存。1.3汽车物流的配送模式汽车物流的核心在于配送，要解决中国汽车厂商的困惑，我们必须发展适合我国国情的汽车物流配送。在我国汽车行业物流配送发展的过程中，汽车行业物流配送的主要模式有市场配送模式、合作配送模式和自营配送模式，其中市场配送模式是我国汽车行业的主流配送模式。1.3.1配送模式1、市场配送模式，所谓市场配送模式就是专业化物流配送中心和社会化配送中心，通过为一定市场范围的企业提供物流配送服务而获取赢利和自我发展的物流配送组织模式。具体又有两种情况：(1) 公用配送，即面向所有企业。如：上海国际汽车物流(码头)有限公司由上海汽车工业(集团)总公司、日本邮船株式会社(NYK)和上海港务局合资组建了。该合资公司借助世界上最大的汽车船运企业之一日本邮船丰富的汽车运输管理和码头运作经验以及高新技术，加上上汽集团的雄厚实力以及管理着世界上第四大集装箱港口的上海港务局的倾力支持，明确提出了要打造世界一流的现代化汽车物流企业，以满足飞速发展的中国汽车业需要，为中国汽车业提供卓越的物流服务。(2) 合同配送，即通过签订合同，为一家或数家企业提供长期服务。这是中国汽车行业最广泛的一种物流配送模式。如：上汽集团与荷兰TPG集团下属的TNT(天地)物流公司合资组建的安吉天地汽车物流有限公司。这家汽车物流公司向上海大众、上海通用等国内汽车制造厂家提供物流服务，并为其在整车物流、零部件入厂以及售后物流等方面提供一体化、网络化的物流管理方案。2、合作配送模式，所谓合作配送模式是指若干企业由于共同的物流需求，在充分挖掘利用个企业现有物流资源基础上，联合创建配送组织模式。如：美国总统轮船(APL)公司的姊妹公司美集物流(APLL)公司与中国三大企业集团民生实业有限公司、西南兵工万友集团及长安汽车集团合资组建了重庆长安民生物流有限公司，在重庆经济开发区北部科技园区建造占地80亩的现代化仓储配送中心，负责提供汽车及零件的物流配送服务和该区域内其他生产企业的物流配送服务，主要客户有长安、福特以及铃木等。3、自营配送模式，所谓自营配送模式是指生产企业和连锁经营企业创建完全是为本企业的生产经营提供配送服务的组织模式。选择自营配送模式的企业自身物流具有一定的规模，可以满足配送中心建设发展的需要。如：上汽集团自有的安吉物流，也具有一定的规模。但随着电子商务的发展，这种模式将会向其他模式转化。1.3.2当前汽车物流存在的缺陷虽然中国汽车物流市场目前已具有一定的规模，各个层次的物流配送企业已得到不同程度的发展，具有区域配送和跨区域配送的能力。但中国汽车行业物流配送模式同其他行业的物流模式一样，也存在着不少缺陷，主要表现在以下两方面：1、技术支撑不够。我国目前许多物流企业的信息系统还很不完善，物流设施、设备的现代化水平较低，物流作业效率不高，整体技术水平落后，没有为配送发展构筑强大技术支撑。2、存在管理瓶颈。我国物流配送在管理人才上严重缺乏现代物流配送管理专业人才；在管理手段上，存在着手工操作、经验决策；在管理资源上存在着不合理配置；在管理体制上存在着行业分割、部门分割、市场分割。这些管理瓶颈将制约汽车物流配送中心的创新与发展。2.安吉物流现状分析2.1安吉物流现状描述安吉天地汽车物流有限公司是目前国内最大的中外合资汽车物流企业，主要从事汽车整车、零部件物流以及相关物流策划、物流技术咨询、规划、管理、培训等服务，是一家专业化运作、能为客户提供一体化、技术化、网络化，可靠的独特解决方案的第三方物流供应商，主要客户包括上海大众、上海通用、上汽通用五菱、华晨金杯、重庆红岩等，运输车辆共有1639辆驳运车、438节火车皮、5艘江轮、6艘海轮。2004年该公司的年运输能力已超过100万辆商品车，年销售收入已达17亿元，主要竞争优势体现在稳定的客户源和区域以及先进的汽车物流管理技术是建立在以ISO9001:2000/ISO14000:2004 /OHSAS18000:1999为基础的一体化管理体系平台上，整合基础技术标准、多目标客户的中央调度系统、整车及零部件信息管理系统、GPS全球定位系统、KPI运作系统以及精益六西格玛技术等，已形成整车及零部件安吉天地汽车物流有限公司是目前国内最大的中外合资汽车物流企业，主要从事汽车整车、零部件物流以及相关物流策划、物流技术咨询、规划、管理、培训等服务，是一家专业化运作、能为客户提供一体化、技术化、网络化，可靠的独特解决方案的第三方物流供应商，主要客户包括上海大众、上海通用、上汽通用五菱、华晨金杯、重庆红岩等，运输车辆共有1639辆驳运车、438节火车皮、5艘江轮、6艘海轮。2004年该公司的年运输能力已超过100万辆商品车，年销售收入已达17亿元，主要竞争优势体现在稳定的客户源和区域以及先进的汽车物流管理技术是建立在以ISO9001:2000/ISO14000:2004 /OHSAS18000:1999为基础的一体化管理体系平台上，整合基础技术标准、多目标客户的中央调度系统、整车及零部件信息管理系统、GPS全球定位系统、KPI运作系统以及精益六西格玛技术等，已形成整车及零部件物流运作管理技术联动平台。2.2安吉公司的运输方式选择及分析 作为上汽集团全资子公司，安吉物流承担着上海汽车两大基地商品车的运输业务，负责为客户提供点对点的运输服务。公司根据订单的具体要求，选择合适的运输方式和路线，从上海或南京的仓库发货。目前安吉物流配送城市覆盖全国大部分地区，主要城市下图所示：安吉物流针对不同运输线路，采取了不同的运输方式。例如对于广州、天津等沿海地区的整车运输，安吉物流倾向于考虑海运；对于武汉、重庆等沿江地区的整车运输，安吉物流倾向于考虑江运；对于其他城市，安吉物流倾向于采用公路运输。在一些特殊情况下，如加急订单等，一些原定于水路运输将调整为公路运输。而安吉的依据是对于不同运输方式的费用、运输标准、碳排放量、以及其他的一些条件作出的选择，我们可以从下表进行了解：运输方式特征参数模拟费用(元/辆*公里）运输标准说明碳排放(kg/辆*公里)其他公路2.0a （不大于50公里）1.7a （不大于200公里）1.5a （不大于500公里）1.3a （不大于1000公里）1.3a （大于1000公里）轿运车装卸商品车时间均为0.5天，日行驶500公里0.364单台轿运车的装载能力为10辆商品车临港库每天装载量为5辆轿运车，浦口为3辆轿运车海运（内河）1.0a每周二六开航一次，船速400公里/天（仓位：300辆/海船，：200辆/江轮）0.101目的地是码头可免费堆放两天；船舶满载发运；装卸能力200台/天注：超额运力价格为原价格标准上浮50%费用价格a随市场油价变动2.3安吉物流的运输要求 2.3.1上汽对安吉物流的要求 在长期的合作中上海汽车对安吉物流汽车运输提出了一些具体的要求：商品车要求“零”公里交车，即交车时商品车辆的行驶里程不得高于50公里；提高服务水平，缩短运输在途时间； 提高商品车交车时完好率，过多的交接环节会降低交验时的完好率； 形成商品车运输配送网络；2.3.2安吉物流对于自身运输的要求 安吉物流在保障客户要求的前提下，也考虑自身的情况，对整车运输业也制定了一些规定：多种运输方式并行降低单一运输模式的风险 在合理范围内起到优化成本作用 提高交车完好率，严格把关各种交接过程或者减少各种多余装卸交接。 充分利用现有资源，降本增效。 3.选题依据3.1运输系统优化在汽车物流行业中的重要性对于企业来说，产品和服务价格的高低直接影响企业盈利的大小，成本的高低，直接影响企业产品和服务在市场上的竞争力，甚至直接关乎企业的存亡。运输是物流的关键部分，它对物流的发展有重要的地位，主要体现在（1）运输是物流的主要功能要素之一，运输是物流的主要部分。（2）运输是社会物资生产的必要条件之一。马克思将运输称之为“第四个物资生产部门”是将运输看成生产过程的继续，这个继续虽然以生产过程为前提，但如果没有这个继续，生产过程则不能最后完成。（3）运输可以创造“场所效用”（4）运输是“第三利润源”的主要源泉。通过运输系统的优化来提高运输时效性，从而降低运输成本，为企业获取更大利润已成为物流企业发展刻不容缓的核心问题。 安吉作为一家正快速发展中的汽车物流公司，运输系统的优化对于其在竞争日趋激烈的市场环境下取得更大的业绩是至关重要的。3.2所选方案所以在基于运输系统优化的方向下，我们选取了案例3、案例4、案例6、案例7和案例11作为我们的选题。这五个个案例分别在多式联运、线路优化、运输调度、运输工具四个方面形成以运输系统优化为中心的整体。3.3选择依据3.3.1各个方案的选取依据和重要性案例3是针对多式联运的安吉汽车物流的整车资源编制问题，我们着重研究的是为安吉汽车物流安排合理的运输线路和运输方式，从而降低总费用。从案例3中我们知道，目前安吉汽车物流公司存在以下问题：没有一套完整、有效的运输线路规划系统。公司客户数量在不断增多，运输线路也变得越发复杂起来，这些对资源计划的编制提出了更高的要求；运输计划存在很大的不确定性。这种不确定性主要由两方面的原因引起的：一是需求方面的波动，二是运力方面的波动。为保证客户满意度，公司必须提供足够的运输能力，这样就有可能造成空车，形成资源浪费的现象。同样，公司有时的实际运输能力也不能满足一些特殊的运输要求。安吉虽然拥有充足的公路运力，可是铁路和水路运力仍然存在一些限制。案例6是安吉物流在配送上采用的是传统的仓储直达需求点的模式，这种模式下，各配送线路之间是相互独立的，车辆载着货物从配送中心运至一个客户需求点，然后空车返回，这样势必造成车辆紧张、运送里程大、装载不足、返程空载、车辆调度不统一、配送效率不高等问题，增加物流成本，降低企业的盈利。案例4中，我们了解到安吉的资源调度系统（RSP）还需要改进，首先是总公司的任务资源和运输公司的运力资源存在信息的不对称，这样会影响总公司订单任务的及时完成，不能满足顾客的需求。其次安吉的RSP和GSP需要进一步的融合，从而提高调度的准确性和灵活性。案例7中的总调度模式和现场调度模式各有其优缺点。总调度模式下客户的发运及时率受到威胁，总部对运输公司也难以分清责任，进行有效监督。现场调度模式则使总部统筹协调处理的效率大打折扣，且在遇到订单波动、或订单于运能不匹配的时候，处理效率不高。案例11中讲的是零部件和整车物流的共享与协调。每个物流公司都是通过业务规模和运输效率来获得利润，高效的运输工具和合理的仓储条件则可以大大缩减企业的成本投入。目前的安吉来说，正处在快速上升的阶段，对于效率和成本的控制至关重要，新的运输工具与仓储形式则正好可以大大提高效率，节约成本。3.3.2所选方案所具有的整体性我们选取的5个方案之间也是相互间有所联系，分别从多式联运、线路优化、运输调度、运输工具四个方面共同实现对安吉物流运输系统优化的运营，四个方向从多个角度对运输系统进行优化改良，其最终目的都是要提高效率、降低成本。3.4方案框架 配送线路的优化选题背景行业背景分析安吉发展及问题分析选择方向及原因物流运输系统优化新型多用途车的研究运输工具与仓库的创新整合仓库的研究基于GPS的运输调度系统资源数据库平台下的调度建立数学模型验证线 路节约里程法下的线路优化整数规划模型下的多式联 运多种运输方式的比较分析信息技术下的运输调度系统优化多式联运的探究4.安吉物流现状下多式联运的探究4.1安吉物流运输方式存在的问题随着全球经济的快速发展和市场竞争的加剧、现代社会中用户对运输质量期望的逐步提高和我国交通运输体系的不断完善,多种运输方式之间的联合运输已经成为我国现代交通运输发展的一种必然趋势,并且必将会成为我国未来综合运输体系的核心,在我国交通运输系统中发挥重要作用。多式联运成为了物流企业发展的一个热点。在多式联运过程中，合理的选择运输路线和组织多种运输方式，才能充分发挥多式联运的优势，从而提高企业运输业的服务水平、竞争能力和各种运输方式的综合效能，取得更好的经济效益。我们了解到案例3中安吉汽车物流公司所面临的两个问题：一是没有一套完整、有效的运输线路规划系统。公司客户数量在不断增多，运输线路也变得越发复杂起来，这些对资源计划的编制提出了更高的要求。二是运输计划存在很大的不确定性。这种不确定性主要由两方面的原因引起的：1.需求方面的波动，2.运力方面的波动。为保证客户满意度，公司必须提供足够的运输能力，这样就有可能造成空车，形成资源浪费的现象。同样，公司有时的实际运输能力也不能满足一些特殊的运输要求。安吉虽然拥有充足的公路运力，可是铁路和水路运力仍然存在一些限制。本方案着重研究在运输路线不确定的条件下，将安排运输路线和运输方式优选综合起来加以考虑，建立了带时间约束和能力约束的，以总成本为最少为目标的组合优化模型，并给出相应的求解方法。4.2基本运输方式及其优缺点4.2.1 公路运输公路运输在所有的运输方式中是影响面最为广泛的一种，其优势在于：1全运程速度快。公路可以实现“门到门”的运输，可以减少转换交通运输工具所需要的等待时间，对于限时运送货物，或为适应市场临时急需货物运输，公路运输服务优于其他运输工具。特别是对于短途、高价值产品运输，其整个运输过程，较其他运输工具更为迅速、方便。2运用灵活。公路运输富于灵活性，可随时调拨，不受时间限制，可随处停靠，富于弹性和适应性。3受地形气候限制小。汽车在路上行驶，可以逢山过山，不受地形限制。遇恶劣气候，较飞机、船舶影响小。但是，公路运输也存在很多不足，其表现主要有：1载运量小。从货运考虑，普通可载运3到5吨。即使使用全拖车，也不过数10吨，无法与铁路或轮船的庞大容量相比。2安全性差。公路运输，由于车种复杂、路况不良，以及驾驶人员的疏忽等因素，交通事故较多，安全性较差。因此，公路适合于短距离、小批量的运输。4.2.2 铁路运输铁路运输具有一些其他输运工具不能取代的优点。主要有：1运量大、运价低廉且运距长。铁路运输采用大功率机车牵引列车运行，可承担长距离、大运输量的运输任务，而且由于列车运行阻力小，能源消耗量低，所以系统价格低廉。2受气候限制小。铁路运输具有高度的导向性，只要列车设施无损坏，在任何气候条件下，列车均可安全行驶，受气候限制因素很小，所以铁路是营运最可靠的运输方式。3污染性较低。铁路的污染性较公路低。如在噪音方面，铁路所带来的噪音污染，不仅比公路低，而且是间断性的。但是铁路运输也有其缺点，主要表现如下：1货损较高。铁路运输可能因为列车行驶时的震动或货物装卸不当，造成所承载货物的损坏，而且运输过程需要经多次中转，也容易导致货物损坏、遗失。2营运缺乏弹性。铁路容易造成空车回送现象，从而造成营运成本的增加。4.2.3 水路运输在各种运输方式中，水路运输是便宜的运输方式，但运输速度最慢，其优势主要有运输量大、能源消耗低、单位运输成本低。水运的运输成本约为铁路运输的1/251/20，公路运输的1/100。但是水路运输受气候限制，可行性较低。4.3整数规划模型的建模过程4.3.1 问题描述假设一个物流中心要将一批货物从物流中心运送到货物目的地（A），中途经由若干随机分布的城市构成的运输网络，网络中任意相邻的城市之间都有若干种（g种）运输方式可供选择，且各种运输方式的运输时间、费用、运输能力不同，在每个城市可以进行运输方式的转换，当从一种运输方式转换另一种运输方式时，需要一定的中转时间和中转费用。而且在整个运输过程中，总的运输时间不能超过运输期限（T），如何在不超过运输时间和各种运输方式运输能力的前提下安排运输路线和选择最佳运输组合方式，使得总运费最低是要解决的问题。4.3.2 模型说明1.模型假设（1）运量在某一对城市之间不能分割，即在某一对特定的城市之间，若存在路径，则在这对城市之间只能选择一种运输方式；（2）运输成本与市场油价存在线性关系；（3）运输网络中，同一阶段和非相邻阶段城市之间可存在路径2.符号说明4.3.3 模型的建立 目标函数以整个运输过程中的运输成本最少为目标，而总费用由三部分组成，即运输费用、中转费用、惩罚费用。公式（2）表示在相邻阶段的某一城市对之间，如果存在路径，只能选择一种运输方式，即运量不能分割；式（3）表示在i阶段的j城市，最多有一次运输方式的改变；式（4）确保运输的连续性；式（5）表示货物必须在规定的期限内运到；式（6）表明货物的运量不能超过某种运输工具的能力；式（7）表示决策变量取整数0或1。4.3.4 模型的求解通过虚拟一个运输网络，将原问题转化为一个带时间约束和能力约束的最短路径问题，然后采用数学规划软件Lingo求解带有时间约束和能力约束的最短路径。例如从配送中心将一批货物中途经过若干城市运往目的地城市，如图1所示，所在路径的城市之间有三种运输方式：铁路、公路、水路可供选择。A5A4A9A8A7A6A0A3A2A1图1 运输网络图详细解法阐述如下：1划分运输区域为了方便模型的求解，首先将运输网络划分为若干阶段，A0位于第一阶段，A1、A2、A3位于第二阶段，A4、A5位于第三阶段，A6、A7、A8位于第四阶段，目的地A9位于第五阶段。如图2所示： 一阶段 二阶段 三阶段 四阶段 五阶段A5A4A9A8A7A6A0A3A2A1图2 划分阶段的运输网络图2向相邻运输网络中增加虚拟节点 对于不相邻阶段的城市之间存在路径的，应在路径上中间阶段增加虚拟节点，如图2所示，二阶段城市1与四阶段城市6之间存在一条路径，在三阶段增加虚拟节点M；二阶段城市3与四阶段城市8之间存在一条路径在三阶段增加虚拟节点N。如图3所示： A5A4A9A8A7A6A0A3A2A1 M N图3 增加虚拟节点的运输网络图3构建扩展的虚拟运输网络图方法如下：（1）为简化模型的计算，在有路径相连的城市之间默认三种运输方式均可到达。（2）除始发点A0以外，将其他每个城市分别扩展成g个城市（每个运输方式分别代表一种运输方式），扩展后的g个城市仍处于原来的网络阶段，最后虚拟一个目的地。如图4所示，其中0代表始发点A0，1、2、3为A1扩展的三个虚拟城市，1代表铁路运输，2代表公路运输，3代表水路运输，以此类推，31、32、33为目的地A9扩展的三个虚拟城市，分别代表铁路、公路、水路运输，34为虚拟的目的地。（3）同一个城市扩展来的节点与节点之间不存在连接弧，原来有连接弧的两个城市，各自扩展来的g个城市之间两两有弧连接，原来没有弧连接的两个城市，各自扩展来的g个城市间都没有弧连接。（4）各条弧上的权重分为三类：费用权重、时间权重、能力权重。费用权重=两城市间的运输费用+中转费用；时间权重=两城市间的运输时间+中转时间；能力权重=两城市间某种运输工具的运输能力。（5）对于两个网络阶段之间建立的虚拟城市，假设j阶段的第m个城市到j阶段的第n个城市之间的各阶段内都有一个虚拟城市，设i阶段的第m个城市到i+1阶段的任一虚拟城市之间的运费、运输时间、运输能力都为i阶段的第m个城市到j阶段的第n个城市的运费、运输时间、运输能力，相邻阶段的虚拟城市与虚拟城市的运费、运输时间均为零，运输能力设为一个充分大的数，依此类推，j-1阶段的虚拟城市到j阶段的第n个城市的运费、运输时间均为零，运输能力设为一个充分大的数。 将没有弧连接的城市之间的运输费用、运输时间设为一个充分大的整数，运输能力设为零。虚拟一个最终点34，因此31 34, 32 34,33 34的运输时间和运输费用均为零，而运输能力为无穷大。则原问题的求解转化为：在不超过运输期限和运输能力约束的前提下，求从节点0 34的最短路径。如图4所示：102211123122243131425311543402632516273361718287291983020921图4 扩展的虚拟运输网络图4用Lingo求解最短路径。4.4整数规划模型制定出安吉多式联运方案 根据案例3安吉汽车物流公司所面临的带时间和运输能力约束的多城市间多种运输方式的最优组合问题，我们采取上述模型来具体求解。不过我们会简化上述模型，在本案例中我们可以不考虑中转费用和惩罚费用以及中转时间，所以模型就会简单很多。我们选择从上海到天津的这一路径，在运输一次的运量不确定的前提下，根据帮助安吉汽车物流公司合理安排线路和运输方式来使带有时间约束和能力约束条件下总费用最低。安吉将汽车从上海中途经过如干城市运往目的地天津，如图5所示，所在路径的城市之间有三种运输方式：铁路、公路、水路可供选择。 南京 淄博上海 天津 南通 济南 图5 从上海到天津的运输网络图4.4.1划分运输网络 一阶段 二阶段 三阶段 四阶段 五阶段 南京 淄博上海 天津 南通 济南 图6 划分阶段的从上海到天津的运输网路图4.4.2 向运输网络中增加虚拟节点对于不相邻阶段的城市之间存在路径的，应在路径上中间阶段增加虚拟节点，如图6所示，二阶段南京与四阶段淄博之间存在一条路径，在三阶段增加虚拟节点M。三阶段的济南与五阶段的天津之间存在一条路径，在四阶段增加虚拟节点N，如图7所示： 南京 M 淄博上海 天津 南通 济南 N图7 增加虚拟节点的从上海到天津的运输网络图4.4.3 构建扩展的虚拟运输网路图方法和说明见上述模型 虚拟一个最终点22，因此19 22,20 22,21 22的运输时间和运输费用均为零，而运输能力为无穷大。则原问题的求解转化为：在不超过运输期限和运输能力约束的前提下，求从节点0 34的最短路径。如图8所示： 137114821915932220016104211711518126图8 扩展的虚拟从上海到天津的运输网路图4.4.4 已知条件以从上海到天津的运输网络图为例，各城市之间的运费、运输时间、运输能力如表1所示：表1 各城市之间运输费用、运输时间、运输能力表 铁路 公路 水路 运输 运输 运输 运输 运输 运输 运输 运输 运输 费用 时间 能力 费用 时间 能力 费用 时间 能力上海 南京 331.1aq 2 290 451.5aq 39 300 301aq 18 200上海 南通 638aq 8 290 754aq 52 300 580aq 35 200南京 淄博 854.7aq 10 290 1010.1aq 62 300 777aq 47 200南通 济南 913aq 12 290 1079aq 64 300 830aq 50 200济南 淄博 121aq 1 290 187aq 30 300 110aq 7 200淄博 天津 513.7aq 6290 700.5aq 47 300 467aq 28 200济南 天津 392.7aq 4 290 535.5aq 42 300 357aq 21 200注：运输费用的单位是元，运输时间的单位是h，运输能力的单位是辆。根据扩展虚拟的运输网络图的方法并结合表1我们可以得出图8每条路径的运输费运输时间和运输能力，如表2所示：表2 每条线路的运输费用、运输时间、运输能力 运输 运输 运输 运输 运输 运输 费用 时间 能力 费用 时间 能力0 1 331.1aq 2 290 10 17 535.5aq 42 无穷大0 2 451.5aq 39 无穷大 10 18 357aq 21 2000 3 301aq 18 200 11 1 3 121aq 1 2900 4 638aq 8 290 11 14 187aq 30 无穷大0 5 754aq 52 无穷大 11 15 110aq 7 2000 6 580aq 35 200 11 16 392.7aq 4 2901 7 854.7aq 10 290 11 17 535.7aq 42 无穷大1 8 1010.1aq 62 无穷大 11 18 357aq 21 2001 9 777aq 47 200 12 13 121aq 1 2902 7 854.7aq 10 290 12 14 187aq 30 无穷大2 8 1010.1aq 62 无穷大 12 15 110aq 7 2002 9 777aq 47 200 12 16 392.7aq 4 2903 7 854.7aq 10 290 12 17 535.7aq 42 无穷大3 8 1010.1aq 62 无穷大 12 18 357aq 21 2003 9 777aq 47 200 13 19 513.7aq 6 2904 10 913aq 12 290 13 20 700.5aq 47 无穷大4 11 1079aq 64 无穷大 13 21 467aq 28 2004 12 830aq 50 200 14 19 513.7aq 6 2905 10 913aq 12 290 14 20 700.5aq 47 无穷大5 11 1079aq 64 无穷大 14 21 467aq 28 2005 12 830aq 50 200 15 19 513.7aq 6 2906 10 913aq 12 无穷大 15 20 700.5aq 47 无穷大6 11 1079aq 64 无穷大 15 21 467aq 28 2006 12 830aq 50 无穷大