《供应链的运输》ppt课件

1、第四部分第四部分 设计和规划运输网络设计和规划运输网络第十三章第十三章 供应链的运输供应链的运输第十三章 供应链中的运输Chapter 13 Transportation in a supplyOutline13.1 运输在供应链中的作用运输在供应链中的作用13.2 各种运输方式及其绩效特征各种运输方式及其绩效特征13.3 运输规划中的权衡运输规划中的权衡13.4 运输网络设计方案运输网络设计方案13.5 运输中的线路规划和日程安排运输中的线路规划和日程安排13.1 运输在供应链中的作用 运输运输transportation是为了使物品从生产者手中转移是为了使物品从生产者手中转移到消费者手中而

2、发生的物品空间移动。到消费者手中而发生的物品空间移动。 因为产品很少能在同一地点生产和消费，所以运输因为产品很少能在同一地点生产和消费，所以运输在每一条供应链中都能发挥着极为重要的作用。运在每一条供应链中都能发挥着极为重要的作用。运输费用供应链成本的重要组成部分。输费用供应链成本的重要组成部分。 运输是市场竞争需要，有可靠的运输保障，很多商运输是市场竞争需要，有可靠的运输保障，很多商业活动无法正常进行。业活动无法正常进行。 任何供应链的成功与运输方式的合理选择都有很大任何供应链的成功与运输方式的合理选择都有很大关系。关系。 网上交易常常吸引远方的顾客，是否拥有高效的运网上交易常常吸引远方的顾客

3、，是否拥有高效的运输系统是电子商务公司成功的关键。输系统是电子商务公司成功的关键。13.2 各种运输方式及其绩效特征 航空Air 包裹承运商Package Carriers 卡车Trucks TL LTL 铁路Rail 水路Water 管道Pipeline 联运Intermodal航空Air 航空运输在基础设施、设备投入方面的固定成本很高。劳动力和燃料费用主要取决于航程，而与乘客或货物无关。航空公司的目标是最大化每架飞机每天的飞行时间和单程收入 航空货运业务主要有三种类型。第一种类型是定期服务，主要航线利用客机上剩余空间运送包裹；第二种类型是货物服务，即运营商 要点: 确定航空港的数量和位置

4、指定飞机航线 飞机维修保养 安排机组人员 收入管理（Yield management）包裹承运商Package Carriers Companies like FedEx, UPS, that carry small packages ranging from letters to shipments of about 150 pounds Expensive、Rapid and reliable delivery、Small and time-sensitive shipments Preferred mode for e-businesses 包裹承运商使用卡车完成本地货物装载，然后将货物

5、送往大型分检中心，经过分拣再通过整车、铁路或空运送往距离交货地最近的分拣中心。最后包裹由交货地分拣中心通过小型卡车以巡回配送方式交给顾客。卡车Trucks 整车运输TL显示了它的规模经济效应，适用于从工厂到仓库之间，供应商到生产商之间的运送。 零担运输LTL Carriers适合小批量送货，是那些体积较大（不能通过包裹运输），而又不能超过卡车最大运载一半的货物。降低零担运输成本的关键在于承运商货物的集并水平。 TL Major Issues Utilization、Consistent service、Backhauls LTL Carriers Major issues: Location

6、of consolidation facilities、Utilization、Vehicle routing、Customer service铁路Rail 是距离远、体积大、高密度、高吨位货物的理想运输方式 Key issues: Scheduling to minimize delays / improve service Yard operations Variability of delivery times水路Water Limited to certain geographic areas Ocean, inland waterway system, coastal waters

7、Very large loads at very low cost Slowest Dominant in global trade (autos, grain, apparel, etc.) Key issues: 到港延迟、运输安全性、集装箱管理、港口拥堵管道Pipeline High fixed cost Primarily for crude petroleum, refined petroleum products, natural gas Best for large and predictable demand Would be used for getting crude oi

8、l to a port or refinery, but not for getting refined gasoline to a gasoline station (why?)联运Intermodal Use of more than one mode of transportation to move a shipment to its destination Most common example: rail/truck Also water/rail/truck or water/truck Grown considerably with increased use of conta

9、iners Increased global trade has also increased use of intermodal transportation More convenient for shippers (one entity provides the complete service) Key issue involves the exchange of information to facilitate transfer between different transport modes13.3 运输规划中的权衡 1、运输成本和库存成本之间的权衡运输成本和库存成本之间的权衡

10、 Choice of transportation mode Inventory aggregation 2 2、运输成本和顾客响应性的权衡、运输成本和顾客响应性的权衡1 1、运输成本和库存成本之间的权衡、运输成本和库存成本之间的权衡 (1)(1)运输方式的选择运输方式的选择 (2)(2)聚积库存聚积库存批 量安全库存中转库存运输成本运输时间铁路整车零担包裹空运水运555254443333344111612225266616各种运输方式对供应链运营的影响1表示最低，表示最低，6表示最高表示最高(1)(1)运输方式的选择运输方式的选择Table 11.4 transportation propo

11、sal for EECarrier Range of quantity shipped (cwt) Shipping cost($/cwt) Trans time (days) Lead Lead time time (days) (days) AM railroad200+6.5056Northeast trucking100+7.5034Golden freightways50-1508.0034Golden freightways150-2506.00边际单边际单位数量折扣位数量折扣34Golden freightways (old)250-4004.0034Golden freight

12、ways (new)400 +3.0034Use AM Railroad and for a lot size of Q=2000(20000 Pounds=200cwt),then Cycle inventory=Q/2=2,000/2=1,000 Safety inventory=L/2 days of demand=(6/2)(120,000/365)=986 In-transit inventory=120,000(5/365)=1,644 Total average inventory=1,000+968+1,644=3,630Annual holding cost using AM

13、 rail =3,630*30= $108,900Annual transportation cost =120,0000*0.65= $78,000The total annual cost for inventory and transportation = $186,900Carrier Lot size(motors)Trans-cost ($)Cycle inventorySafetyinventoryIn-trainsitinventoryinventoryCost ($)Total Cost ($)AM rail2,00078,0001,0009861,644108,900186

14、,900North-east 1,00090,000 500658986 64,320154,320Golden 50096,000 250658986 56,820152,820Golden1,50096,000 750658986 71,820167,820Golden2,50086,4001,250658986 86,820173,220Golden3,00080,0001,50065898694,320174,320Golden(old)4,00072,0002,000658986109,320181,320Golden(new)4,00067,5002,000658986109,32

15、0176,820Table 13-5 analysis of transportation options for EE运输方式的选择运输方式的选择 在供应链中，选择一种合适的运输方式，既是计划性决在供应链中，选择一种合适的运输方式，既是计划性决策又是操作性决策。策又是操作性决策。 与某个承运商签订合同的决策属于计划性决策与某个承运商签订合同的决策属于计划性决策 具体运载中的运输方式的选择则是操作性决策具体运载中的运输方式的选择则是操作性决策 无论哪种决策，托运人都必须权衡运输成本和库存成本。无论哪种决策，托运人都必须权衡运输成本和库存成本。 运费最低的运输方式，并不一定使供应链总成本最低运费

16、最低的运输方式，并不一定使供应链总成本最低 较廉价的运输方式通常拥有较长的供货期和较大的最小运输量，较廉价的运输方式通常拥有较长的供货期和较大的最小运输量，从而导致供应链库存水平提高。从而导致供应链库存水平提高。 如果能大大减少库存，高价的运输方式也是合理的。如果能大大减少库存，高价的运输方式也是合理的。（2） 聚积库存 通过将库存聚积于某一地点，企业可以大大减少必备安全库通过将库存聚积于某一地点，企业可以大大减少必备安全库存量。存量。 库存聚积时的运输成本通常会增加。如果库存高度分散，一库存聚积时的运输成本通常会增加。如果库存高度分散，一定程度的聚集可能降低运输成本，然而一旦超过临界点，库定

17、程度的聚集可能降低运输成本，然而一旦超过临界点，库存聚集将导致总运输成本的增加。存聚集将导致总运输成本的增加。 在进行这项决策时，企业必须在运输、库存和设施成本之间在进行这项决策时，企业必须在运输、库存和设施成本之间进行权衡。进行权衡。当库存和设施费用占供应链总成本的很大一部分当库存和设施费用占供应链总成本的很大一部分时，聚积库存就很有必要。时，聚积库存就很有必要。 对价值对价值/ /重量比很高、需求不确定性高且顾客订货批量大的重量比很高、需求不确定性高且顾客订货批量大的产品来说，聚积库存能够降低供应链成本。产品来说，聚积库存能够降低供应链成本。如个人电脑如个人电脑 对价值对价值/ /重量比很

18、低、需求不确定性低且顾客订货批量小的重量比很低、需求不确定性低且顾客订货批量小的产品来说，聚积库存能够增加供应链成本。产品来说，聚积库存能够增加供应链成本。如图书如图书2 2、运输成本和反应能力之间的权衡、运输成本和反应能力之间的权衡Week 119,97017,47011,31626,19220,2638,38125,377Week 239,1712,15820,63323,37024,10019,60318,442Table 14.7 Daily demand at Alloy Steel over Two-week period (Using LTL)- Trans cost :$100

19、+0.01X (X : the number of pounds of steel shipped)-Two days in transitDaydemandTwo-day responseQuantity costShipped ($)Three-day responseQuantity costShipped ($)Four-day response Quantity costShipped ($)119,97019,970 299.7 0 -0 -217,47017,470 274.70 37,440 474.400 -311,31611,316 213.16 0 -48,756 587

20、.56426,19226,192 361.9237,508 475.080 -520,26320,263 302.63 0 -0 -68,3818,381 183.8128,644 386.4454,836 648.36725,37725,377 353.77 0 -0 -839,17139,171 491.7164,548 745.480 -92,1582,158 121.58 0 -66,706 767.061020,63320,633 306.3322,791 327.910 -1123,37023,370 333.70 0 -0 -1224,10024,100 341.0047,470

21、 574.7068,103 781.031319,60319,603 296.03 0 -0 -1418,44218,442 284.4238,045 480.4538,045 480.45 4,164.46 - 3,464.46 - 3,264.46 700200运输成本和响应能力之间的权衡运输成本和响应能力之间的权衡 供应链引发的运输成本与供应链的响应能力是密切供应链引发的运输成本与供应链的响应能力是密切相关的。相关的。 如果企业反应迅速并在收到订单的当天就发货，那么运送如果企业反应迅速并在收到订单的当天就发货，那么运送规模必然较小，从而导致较高的运费。规模必然较小，从而导致较高的运费。

22、如果企业降低其响应能力，并将较长时间内的订货集并发如果企业降低其响应能力，并将较长时间内的订货集并发出，那么它就可以通过聚集运输获得规模经济，降低运输出，那么它就可以通过聚集运输获得规模经济，降低运输成本。成本。 集并发货是指将一定时期内的订货集中发出。集并发集并发货是指将一定时期内的订货集中发出。集并发货在延迟装运货物、降低响应能力的同时，也减少了货在延迟装运货物、降低响应能力的同时，也减少了运费。运费。 聚集运输带来的边际收益聚集货物时间跨度的增加而聚集运输带来的边际收益聚集货物时间跨度的增加而下降。下降。13.4 运输网络设计方案供应商供应商需要地需要地(1)直接发运网络 直接发运网络

23、所有货物直接从供应商处运达需要地，每一次运输所有货物直接从供应商处运达需要地，每一次运输的线路都是指定的，供应链管理者只需决定运输的的线路都是指定的，供应链管理者只需决定运输的数量并选择运输方式。数量并选择运输方式。 供应链管理者必须在运输费用和库存费用之间进行供应链管理者必须在运输费用和库存费用之间进行权衡。权衡。 直接发运网络的主要优势：直接发运网络的主要优势： 无需中介仓库，而且在操作和协调上简单易行；无需中介仓库，而且在操作和协调上简单易行； 送货决策完全本地化，一次运输决策不影响别的货物运输；送货决策完全本地化，一次运输决策不影响别的货物运输； 从供应商到需要地的运输时间较短。从供应

24、商到需要地的运输时间较短。 若需要地的若需要地的需求规模足够大需求规模足够大，每次的最佳补给，每次的最佳补给规模都与卡车的最大装载量相接近，那么直接规模都与卡车的最大装载量相接近，那么直接发运网络就是行之有效的。发运网络就是行之有效的。 对小的需求来说，直接发运网络的成本过高对小的需求来说，直接发运网络的成本过高 若采用整车运输商，必然会导致供应链中库若采用整车运输商，必然会导致供应链中库存水平提高。存水平提高。 若采用零担运输商，尽管库存量较少，但却若采用零担运输商，尽管库存量较少，但却要花费较高的运输费用和较长的运输时间。要花费较高的运输费用和较长的运输时间。 若使用包裹运输，运输成本会非

25、常高。若使用包裹运输，运输成本会非常高。 供应商零售商供应商零售商一个供应商至多家零售店或多个供应商至一家零售店的巡回运送(2) 利用巡回运送直接发运利用巡回运送直接发运利用巡回运送直接发运 供应链管理者必须对每条巡回线路进行规划。供应链管理者必须对每条巡回线路进行规划。 巡回线路通过多家零售店在一辆卡车上的联合运输巡回线路通过多家零售店在一辆卡车上的联合运输降低了运输成本。降低了运输成本。 eg. Toyota uses milk runs from suppliers to support its JIT manufacturing system. In Japan, Toyota has

26、 many assembly plants located close together and thus uses milk runs from a single supplier to many plants. In America, Toyota uses milk runs from many suppliers to its assembly plant in Kentucky. 供应商零售商配送中心(3) 所有货物通过配送中心发运所有货物通过配送中心发运所有货物通过配送中心发运 供应商并不直接将货物运送到零售店，而是先运到配供应商并不直接将货物运送到零售店，而是先运到配送中心，再运

27、到零售店。送中心，再运到零售店。 当供应商和零售店之间距离较远、运费较高时，配送当供应商和零售店之间距离较远、运费较高时，配送中心有助于降低供应链的成本，配送中心的作用：中心有助于降低供应链的成本，配送中心的作用： 进行货物保管进行货物保管 转运点的作用转运点的作用 因为每个供应商对配送中心都采取大批量送货，以满因为每个供应商对配送中心都采取大批量送货，以满足该配送中心所服务地区对产品的需求，因此配送中足该配送中心所服务地区对产品的需求，因此配送中心的建立不但使进货点更靠近最终目的地，而且使供心的建立不但使进货点更靠近最终目的地，而且使供应链获取规模经济效益。应链获取规模经济效益。 配送中心的

28、送货费配送中心的送货费(outbound transportation)(outbound transportation)不会不会太高，因为它只服务其周边区域。太高，因为它只服务其周边区域。货物对接（越库） 如果如果商店的库存更新规模大到足以获取进货规模经商店的库存更新规模大到足以获取进货规模经济效益，济效益，配送中心就没有必要为其保有库存。在这配送中心就没有必要为其保有库存。在这种情形下，可采取货物对接的方式。种情形下，可采取货物对接的方式。 货物对接：每一辆进货卡车上装有来自同一个供应货物对接：每一辆进货卡车上装有来自同一个供应商并将运送到多个零售店的产品，而每一辆送货卡商并将运送到多个零

29、售店的产品，而每一辆送货卡车则装有来自不同供应商并将被送至同一家商店的车则装有来自不同供应商并将被送至同一家商店的产品。产品。 货物对接的主要优势：无需库存；加快了供应链中货物对接的主要优势：无需库存；加快了供应链中产品的流通速度；减少了处理成本。产品的流通速度；减少了处理成本。 成功的货物对接常常需要高度的协调性和进出货物成功的货物对接常常需要高度的协调性和进出货物的步调高度一致。的步调高度一致。供应商零售商配送中心（4）通过配送中心的巡回运送通过配送中心的巡回运送 如果每家商店的进货规模较小，配送中心就可以使如果每家商店的进货规模较小，配送中心就可以使用巡回线路向零售商送货用巡回线路向零售

30、商送货 例：例： 日本日本7-117-11公司将来自新鲜食品供应商的货流在配送中心公司将来自新鲜食品供应商的货流在配送中心进行对接，并通过巡回线路向商店送货。进行对接，并通过巡回线路向商店送货。 许多网上商店在向客户送货时，也从配送中心使用巡回许多网上商店在向客户送货时，也从配送中心使用巡回线路，以便减少小规模的送货上门的运输成本。线路，以便减少小规模的送货上门的运输成本。 使用货物对接和送奶线路要求高度的协调以及对巡使用货物对接和送奶线路要求高度的协调以及对巡回线路的合理规划和安排。回线路的合理规划和安排。（5）剪裁式(定制化)的运输网络 剪裁式的运输网络是根据不同的客户和产品特征，运用不同

31、的运输方式和运输网络进行运输。 是上述运输体系的综合利用，它在运输过程中综合利用货物对接、巡回线路、整车和零担承运，甚至在某些情况下使用包裹递送。 其目的是视具体情况，采用合适的运输方案，以较低的成本满足客户需要。 1、基于顾客密度和距离的剪裁式运输 2、居于顾客规模的剪裁式运输 3、基于产品需求和价值的剪裁式运输基于顾客密度和距离的剪裁式运输短短 距距 离离中中 距距 离离长长 距距 离离高密度高密度 采用巡回线路的自营运输队采用巡回线路的自营运输队采用巡回线路的第三方运输采用巡回线路的第三方运输采用巡回线路的第三方运采用巡回线路的第三方运输或零担承运商输或零担承运商采用巡回线路的对接配送采

32、用巡回线路的对接配送零担承运商零担承运商零担或包裹承运商零担或包裹承运商采用巡回线路的对接配送采用巡回线路的对接配送零担或包裹承运商零担或包裹承运商包裹承运商包裹承运商中密度中密度低密度低密度基于顾客规模的剪裁式运输 大客户可以用整车运输进行供货，而小客户的供给则要用到零担运输或者巡回线路运输。 以相同的频率和相同的价格向大小客户供货并非明智之举。 企业的一种可行的方案是，向小客户的要价较高，而向大客户要价低。 另种可行的方案是，设计一种特殊的巡回线路，为大客户送货的频率较高，为小客户送货的频率较低。 (L,M1,S1), (L,M2,S2), (L,M1,S3), (L,M2,S1), (L

33、,M1,S2), (L,M2,S3)基于产品需求和价值的剪裁式运输 对价值高、需求量大的产品对价值高、需求量大的产品，应将其周期库存分散存放在各，应将其周期库存分散存放在各零售店，因为这样做能确保用便宜的运输方式补货；而这类零售店，因为这样做能确保用便宜的运输方式补货；而这类产品的安全库存则应聚集，以减少库存。如果需要以安全库产品的安全库存则应聚集，以减少库存。如果需要以安全库存满足客户需要，可采取快速运输方式。存满足客户需要，可采取快速运输方式。 对价值低、需求量大的产品对价值低、需求量大的产品，所有库存都必须分散进行，以，所有库存都必须分散进行，以接近客户并减少运输费用。接近客户并减少运输

34、费用。 对需求量小、价值高的产品对需求量小、价值高的产品，应聚集所有库存以节约库存成，应聚集所有库存以节约库存成本。在需要的时候，采取快速运输方式满足顾客订货要求。本。在需要的时候，采取快速运输方式满足顾客订货要求。 对低价值、小需求量的产品对低价值、小需求量的产品，应将周期库存布局在接近客户，应将周期库存布局在接近客户的地方，把安全库存集中起来，以便在获取一定程度的聚集的地方，把安全库存集中起来，以便在获取一定程度的聚集优势的同时，减少运输费用。周期库存的补充应采用廉价的优势的同时，减少运输费用。周期库存的补充应采用廉价的运输方式，以便节约运费。运输方式，以便节约运费。不同运输网络的优点和缺

35、点 网络结构网络结构优点优点缺点缺点直接运输直接运输无需中间仓库无需中间仓库易协调易协调库存水平高（由于货物批量库存水平高（由于货物批量大）大）巨大的接收费用巨大的接收费用利用巡回运送的直利用巡回运送的直接运送接运送小批量送货的运输成本较低小批量送货的运输成本较低库存成本较低库存成本较低协调难度加大协调难度加大所有货物通过配送所有货物通过配送中心的运送中心的运送通过聚集降低了进货运输成通过聚集降低了进货运输成本本增加了库存成本增加了库存成本增加了配送中心的处理费用增加了配送中心的处理费用所有货物通过配送所有货物通过配送中心对接运送中心对接运送必备库存水平很低必备库存水平很低通过联合降低了运输成

36、本通过联合降低了运输成本协调难度加大协调难度加大通过配送中心利用通过配送中心利用送奶线路的运送送奶线路的运送小批量货物有较低的送货成小批量货物有较低的送货成本本协调难度进一步加大协调难度进一步加大剪裁式运输网络剪裁式运输网络运输选择与单个产品和商店运输选择与单个产品和商店的需求十分匹配的需求十分匹配协调难度最大协调难度最大13.5 运输中的线路规划和日程安排 1、节约矩阵分析法、节约矩阵分析法Savings matrix method 2、一般划归法、一般划归法Generalized assignment method问题问题: 每辆卡车为哪些客户送货每辆卡车为哪些客户送货? ? 每辆卡车的行

37、驶路线每辆卡车的行驶路线? ?1、节约矩阵分析法 主要步骤主要步骤: 第一步第一步: 确认距离方阵确认距离方阵Identify the distance matrix 第二步第二步: 确认节约方阵确认节约方阵Identify the savings matrix 第三步第三步: 将客户划归不同运输线路的运输工具将客户划归不同运输线路的运输工具Assign customers to vehicles or routes 第四步第四步: 为运输排定为客户送货的顺序为运输排定为客户送货的顺序Sequence customers within routesExample for Webvan (the

38、 manager has four trucks, each capable of carrying up to 200 units.)Customer location and demand for Webvan (Table 13.11)X CoordinateY CoordinateOrder size Warehouse00-Customer 101248Customer 26536Customer 371543Customer 491292Customer 515357Customer 620016Customer 717-256Customer 87-430Customer 91-

39、657Customer 1015-647Customer 1120-791Customer 127-955Customer 132-1538第一步第一步 确认距离方阵确认距离方阵DCCust 1Cust 2Cust 3Cust 4Cust 5Cust 6Cust 7Cust 8Cus9Cus 10Cus11Cus12Cus13Cust 1120Cust 2890Cust 3178100Cust 4159840Cust 51517914110Cust 6202315201660Cust 71722132016540Cust 8817919161114100Cust 961812222017201

40、660Cust1016231422199848140Cust1121281826221176131950Cust121122142421141612579130Cust13152720302822232012916208022( , )()()ABABDist A Bxxyy第二步第二步 确认节约方阵确认节约方阵C1(48)C2(36)C3(43)C4(92)C5(57)C6(16)C7(56)C8(30)C9(57)C10(47)C11(91)C12(55)C13(35)Cust 10Cust 2110Cust 321150Cust 41815280Cust 5101418190Cust 6

41、9131719290Cust 7712141627330Cust 837671214150Cust 9021146780Cust1051011122228291680Cust1151112142532168320Cust121545121516141018190Cust1303228121211121516180( , )(, )(, )( , )S x yDist DC xDist DC yDist x y第三步第三步 将客户划归不同运输线路的运输工具将客户划归不同运输线路的运输工具RouteC1(48)C2(36)C3(43)C4(92)C5(57)C6(16)C7(56)C8(30)C9

42、(57)C10(47)C11(91)C12(55)C13(35)Cust 110Cust 22110Cust 3321150Cust 441815280Cust 55101418190Cust 669131719290Cust 777121416270Cust 8837671214150Cust 99021146780Cust101051011122228291680Cust1165111214253432168320Cust12121545121516141018190Cust131303228121211121516180 RouteC1(48)C2(36)C3(43)C4(92)C5(5

43、7)C6(16)C7(56)C8(30)C9(57)C10(47)C11(91)C12(55)C13(35)Cust 110Cust 22110Cust 3321150Cust 441815280Cust 55101418190Cust 669131719290Cust 767121416270Cust 8837671214150Cust 99021146780Cust101051011122228291680Cust1165111214253432168320Cust12121545121516141018190Cust131303228121211121516180Total weight

44、 200 (the capacity constraint) RouteC1(48)C2(36)C3(43)C4(92)C5(57)C6(16)C7(56)C8(30)C9(57)C10(47)C11(91)C12(55)C13(35)Cust 110Cust 22110Cust 3321150Cust 431815280Cust 55101418190Cust 669131719290Cust 767121416270Cust 8837671214150Cust 99021146780Cust101051011122228291680Cust1165111214253432168320Cus

45、t12121545121516141018190Cust131303228121211121516180将节约最大的两条线路合并，并持续该过程直到将节约最大的两条线路合并，并持续该过程直到不能合并时为止。不能合并时为止。结果：结果：1,3,4, 2,9, 6,7,8,11, 5,10,12,13第四步 为运输排定为客户送货的顺序 首先得到一个最初的行程安排，然后运用线路改进程首先得到一个最初的行程安排，然后运用线路改进程序进行改进序进行改进线路安排程序：线路安排程序： (1)最远插入法最远插入法 Farthest insert (2)最近插入法最近插入法Nearest insert (3)最近

46、邻居法最近邻居法 Nearest neighbor (4)旋转法旋转法 Sweep 线路改进程序：线路改进程序： (1)二交换法二交换法 2-OPT (2)三交换法三交换法3-OPT159981515916811510121356510131259DCDCDCDC 5,10,12,13The route sequencing procedures are illustrated for Farthest insert (Given a vehicle trip (only the DC), for each remaining customer, evaluate the minimum in

47、crease in length if this customer is inserted at a suitable point in the trip and insert the customer with the largest minimum increase to obtain a new trip)15151111151591615911161616151.05302.122213305403.12310321013476DCDCDCDCDCDDCDCDCDCCDDCDCDCC 159116162215169221516168111191615615169815101369101

48、3614.101351101101355101534836551121212DCDCDCDCDCDCDCDCDCDCDCDC 15916155101355DCDC 15916181215149161599815159915111491618155510135651051013705.5101368512121101361213562125DDCDCDCDCDCDCDCCCCDD Nearest insert (Given a vehicle trip (only the DC), for each remaining customer, evaluate the minimum increas

49、e in length if this customer is inserted at a suitable point in the trip and insert the customer with the largest minimum increase to obtain a new trip)15151616151591591111118151653010321.13305362.11222121334040DCDCDCDCDCDCDCDCDCDDCDCC 1191615118161611141698151522151148151822151011213511213513.12136

50、2121010555356121348121352DCDCDCDCDCDCDCDDCDCCCDCD 16981510121348DCDC 111491615169142215151698992281515915981510121356510121356555121013654.10121376101210537DCDCDCDCDCDCDCDDCCDC Nearest neighbor (Starting at DC, this procedure adds the closest customer to extend the trip, At each step, the trip is bu

51、ilt by adding the customer closest to the point last visited by the vehicle.)111181181611816915151615149225101.135121213121310.1213105592.1053.4DCDCDCDCDCDCDCDC Sweep (the trip is constructed by sequencing customers in the order the are encountered during the sweep.)DC5101213Table 13.17 Initial trip

52、s using different route sequencing proceduresRoute sequencing procedureResulting tripTrip lengthFarthest insertDC,5,10,12,13,DC56Nearest insertDC,5,10,12,13,DC56Nearest neighborDC,12,13,10,5,DC59SweepDC,5,10,12,13,DC56线路改进程序：线路改进程序：二交换法二交换法 2-OPT 1. dividing a trip into two paths. 2.reconnecting two

53、 paths. 3.The smaller of the length used to define a new trip. (,12,10,5,13,): (,12,10,5),(13,)(,13,12,10,5,)A trip DCDCTwo pathsDCDCAnew trip DCDCLength: 66 Length: 56DC1213510 二交换法二交换法 3-OPT 1. dividing a trip into three paths. 2.reconnecting three paths. 3.The smaller of the length used to define

54、 a new trip. (, 5 ,1 0 ,1 2 ,1 3 ,): () , ( 5 ,1 0 ) , (1 2 ,1 3 )(,1 2 ,1 3 , 5 ,1 0 ,) (6 5 )(,1 2 ,1 3 ,1 0 , 5 ,) (8 1)(,1 3 ,1 2 , 5 ,1 0 ,)6 1Atr ipD CD CT h r e ep a th sD CD CD CLD CD CLD CD CLTable 13.18 Web delivery schedule using saving matrix methodTruckTripLength of tripLoad on truck1DC

55、,2,9,DC32932DC,1,3,4,D391833DC,8,11,6,7,DC491934DC,5,10,12,13,DC56197Figure 13.6 Delivery routes using saving matrix methodDC134295101213611872、一般划归方法 步骤：步骤： 第一步 为每条线路找一个源点；为每条线路找一个源点； 第二步第二步 计算每一客户纳入的成本；计算每一客户纳入的成本； 第三步第三步 将客户划归不同线路；将客户划归不同线路； 第四步第四步 线路设计安排方法的适应性线路设计安排方法的适应性 Table 10.19 Angular pos

56、itions of Webvan customersX CoordinateY CoordinateAngular position(Radians) ( )Order size Warehouse00-Customer 10121.5748Customer 2650.6936Customer 37151.1343Customer 49120.9392Customer 51530.2057Customer 62000.0016Customer 717-2-0.1256Customer 87-4-0.5230Customer 91-6-1.4157Customer 1015-6-0.3847Customer 1120-7-0.3491Customer 127-9-