第七章运输决策

运输决策TransportDecisionsCR(2004)PrenticeHall,Inc.第七章Chapter7Ifyouareplanningforoneyear,growrice.Ifyouareplanningfor20years,growtrees.Ifyouareplanningforcenturies,growmen. AChineseproverb1产品计划三角形ProductinthePlanningTriangleCR(2004)PrenticeHall,Inc.PLANNINGORGANIZINGCONTROLLINGTransportStrategy•Transportfundamentals•TransportdecisionsCustomerservicegoals•Theproduct•Logisticsservice•Oc.&info.sys.InventoryStrategy•Forecasting•Inventorydecisions•Purchasingandsupplyschedulingdecisions•Storagefundamentals•StoragedecisionsLocationStrategy•Locationdecisions•Thenetworkplanningprocess计划组织控制TransportStrategy•Transportfundamentals•TransportdecisionsCustomerservicegoals•Theproduct•Logisticsservice•Oc.&info.sys.InventoryStrategy•Forecasting•Inventorydecisions•Purchasingandsupplyschedulingdecisions•Storagefundamentals•StoragedecisionsLocationStrategy•Locationdecisions•Thenetworkplanningprocess库存战略预测客户服务目标采购和供应时间决策存储基础知识存储决策产品物流服务订单管理和信息系统库存决策运输战略运输基础知识运输决策选址战略选址决策网络规划流程2TransportDecisionsinTransportStrategyPLANNINGORGANIZINGCONTROLLINGTransportStrategy•Transportfundamentals•TransportdecisionsCustomerservicegoals•Theproduct•Logisticsservice•Oc.&info.sys.InventoryStrategy•Forecasting•Inventorydecisions•Purchasingandsupplyschedulingdecisions•Storagefundamentals•StoragedecisionsLocationStrategy•Locationdecisions•ThenetworkplanningprocessPLANNINGORGANIZINGCONTROLLINGTransportStrategy•Transportfundamentals•TransportdecisionsCustomerservicegoals•Theproduct•Logisticsservice•Oc.&info.sys.InventoryStrategy•Forecasting•Inventorydecisions•Purchasingandsupplyschedulingdecisions•Storagefundamentals•StoragedecisionsLocationStrategy•Locationdecisions•ThenetworkplanningprocessCR(2004)PrenticeHall,Inc.3Justafewofthemanyproblemsintransportation典型的运输决策TypicalTransportDecisionsCR(2004)PrenticeHall,Inc.·

模式、服务选择Mode/Serviceselection

·

Privatefleetplanning

-

路线选择Carrierrouting

-

多起迄点问题Routingfrommultiplepoints

-

Routingfromcoincidentorigin-destinationpoints起迄点重合问题-

车辆线路和时刻表Vehicleroutingandscheduling

·

Freightconsolidation

47.1运输服务的选择7.1.1基本的成本权衡Costtypes运输Transportation在途库存Intransitinventory工厂库存Sourceinventory基层库存Destinationinventory7.1.2考虑竞争因素7.1.3对选择方法的评价5方式选择Mode/ServiceSelection(Cont’d)ExampleFinishedgoodsaretobeshippedfromaplantinventorytoawarehouseinventorysomedistanceaway.Theexpectedvolumetobeshippedinayearis1,200,000lb.Theproductisworth$25perlb.andtheplantandcarryingcostsare30%peryear.Otherdataare:CR(2004)PrenticeHall,Inc.

Transport

choice

Rate,$/lb.

Transittime,days

Shipment

size,lb.

Rail

0.11

25

100,000

Truck

0.20

13

40,000

Air

0.88

1

16,000

6IncludetransportrateTransportSelectionAnalysisCosttypeCompu-tationRailTruckAirTrans-portationRD.11(1,200,000)=$132,000.20(1,200,000)=$240,000.88(1,200,000)=$1,056,000In-transitinventoryICDT365[.30(25)´1,200,000(25)]/365=$616,438[.30(25)´1,200,000(13)]/365=$320,548[.30(25)´1,200,000(1)]/365=$24,658PlantinventoryICQ2[.30(25)´100,000]/2=$375,000[.30(25)´40,000]/2=$150,000[.30(25)´16,000]/2=$60,000WhseinventoryIC'Q2[.30(25.11)´100,000]/2=$376,650[.30(25.20)´40,000]/2=$151,200[.30(25.88)´16,000]/2=$62,112

Totals$1,500,088$861,748$1,706,770ImprovedserviceCR(2004)PrenticeHall,Inc.7-677.2路线选择基本类型一是起讫点不同的单一路径规划二是多个起讫点的路径规划三是起点和终点相同的路径规划87.2.1起讫点不同的单一路径问题已知一个由链和节点组成的网络，其中节点代表由链连接的点，链代表节点之间的成本（距离、时间或距离和时间的加权平均）。最初，所有的节点都是未知解，只有起点是已解的节点。9第n次迭代的目的。找出第n个距起点最近的节点。对ｎ＝１，２，．．．重复此过程，直到所找出的最近节点是终点。第ｎ次迭代的输入值。在前面的迭代过程中找出（n-1)距起点最近的节点，及其距起点最短的路径和距离。这些节点和起点统称为已解的节点，其余的称为未解的节点。10第n个最近节点的候选点。每个已解的节点直接和一个或多个未解的节点相连接，就可以得出一个候选点－－连接距离最短的未解点。如果有多个距离相等的最短路径连接，则有多个候选点。计算出第ｎ个最近的节点。将每个已解节点与其候选节点之间的距离累加到该已解节点与起点之间最短路径的距离上。所得出的总距离最短的候选点就是地n个最近的节点，其最短路径就是得出该距离的路径。若多个候选点都得出相等的最短距离，则都是已解的节点。11OriginAmarilloOklahomaCityDestinationFortWorthABEICDGFHJ90minutes848413834815648132150126132120661264860Note:Alllinktimesareinminutes90CarrierRouting(Cont’d)CanbeaweightedindexoftimeanddistanceCR(2004)PrenticeHall,Inc.12ShortestRouteMethodCR(2004)PrenticeHall,Inc.

Step

SolvedNodesDirectlyConnectedtoUnsolvedNodes

ItsClosest

ConnectedUnsolvedNode

TotalCostInvolved

nthNearestNode

ItsMinimumCost

ItsLastConnectiona

1

A

B

90

B

90

AB*

2

A

C

138

C

138

AC

B

C

90+66=156

3

A

D

348

B

E

90+84=174

E

174

BE*

C

F

138+90=228

4

A

D

348

C

F

138+90=228

F

228

CF

E

I

174+84=258

5

A

D

348

C

D

138+156=294

E

I

174+84=258

I

258

EI*

F

H

228+60=288

6

A

D

348

C

D

138+156=294

F

H

228+60=288

H

288

FH

I

J

258+126=384

7

A

D

348

C

D

138+156=294

D

294

CD

F

G

288+132=360

H

G

288+48=336

I

J

258+126=384

8

H

J

288+126=414

I

J

258+126=384

J

384

IJ*

13MAPQUESTSOLUTIONCR(2004)PrenticeHall,Inc.14Plant1Requirements=600Plant2Requirements=500Plant3Requirements=300SupplierASupply400SupplierCSupply500SupplierBSupply7004a76555958aThetransportationratein$pertonforanoptimalroutingbetweensupplierAandplant多起讫点问题RoutingfromMultiplePointsThisproblemissolvedbythetraditionaltransportationmethodoflinearprogrammingCR(2004)PrenticeHall,Inc.15TRANLPproblemsetupSolutionCR(2004)PrenticeHall,Inc.167.2.3起迄点重合问题配送饮料到酒吧和饭店安排时间线路将现钞送到自动提款机收集饭店的油脂网上杂货店的配送从仓库到零售点的配送邮车的配送线路校车线路171.各点空间相连CR(2004)PrenticeHall,Inc.不好的路线规划-线路交叉好的路线规划-线路不交叉18RoutingwithaCoincidentOrigin/DestinationPoint·

Typicalofmanysingletruckroutingproblemsfromasingledepot.

·

Mathematically,acomplexproblemtosolveefficiently.However,goodroutescanbefoundbyformingaroutepatternwherethepathsdonotcross¾

a"teardrop"pattern.

CR(2004)PrenticeHall,Inc.19SingleRouteDevelopedbyROUTESEQinLOGWARE012345678876543210Xcoordinates1231911121314151617184567891020DYcoordinates012345678876543210Xcoordinates1231911121314151617184567891020DYcoordinates(a)Locationofbeverageaccountsanddistributioncenter(D)withgridoverlay(b)SuggestedroutingpatternCR(2004)PrenticeHall,Inc.7-14202.空间上不相连点的问题感知方法基本不适用，必须借助于多年来人们提出的数学方法来解决这类问题217.3行车路线和时刻表的确定CR(2004)PrenticeHall,Inc.每个站点都要取送货有不同运载能力的车辆的组合司机工作时间限制时间窗口限制途中只能送货后再收货驾驶员特定时间休息和用餐227.3.1合理路径和时刻表的制定原则安排车辆负责相互距离最接近的站点的货物运输。安排车辆各日的途径站点时，应注意使站点群更加紧凑从距仓库最远的站点开始设计卡车的行车路线应呈水滴状尽可能选用最大的车辆送货，这样设计出的路线是最有效的23取货、送货应该混合安排，不应该在完成全部送货任务之后再取货对过于遥远而无法归入群落的站点可以采用其他配送方式避免时间窗口过短24划分站点群以分派车辆1.

安排车辆负责相互距离最接近的站点的货物运输(a)不合理的划分方式WeakclusteringDepot(b)较合理的划分方式BetterclusteringDDDepotStopsCR(2004)PrenticeHall,Inc.25Guidelines(Cont’d)2.

对不同日期划分站点群FFFFFFFTTTTTTTDDepotFFFFFTTTFTFTTTDDepot(a)不合理的划分-线路交叉routescross(b)BetterclusteringStop可能需要配合销售实现群的划分CR(2004)PrenticeHall,Inc.26Guidelines(Cont’d)2.

Stopsondifferentdaysshouldbearrangedto producetightclustersFFFFFFFTTTTTTTDDepotFFFFFTTTFTFTTTDDepot(a)Weakclustering--routescross(b)BetterclusteringStopMayneedtocoordinatewithsalestoachieveclustersCR(2004)PrenticeHall,Inc.27ApplicationofGuidelinestoCasketDistributionWarehouseFuneralhomeTypicalweeklydemandandpickupsCR(2004)PrenticeHall,Inc.28ApplicationofGuidelinestoCasketDistribution(Cont’d)WarehouseFuneralhomeDivisionofsalesterritoriesintodaysoftheweekTerritoriesofequalsizetominimizenumberoftrucksCR(2004)PrenticeHall,Inc.29ApplicationofGuidelinestoCasketDistribution(Cont’d)WarehouseFuneralhome地区内的路线设计RoutedesignwithinterritoriesCR(2004)PrenticeHall,Inc.307.3.2行车路线和时刻表的制定方法1.扫描法2.节约法311.扫描法（1）在地图或方格图中确定所有站点（含仓库）的位置（2）自仓库始沿任一方向向外划一条直线（3）排定各线路上每个站点的顺序使行车距离最短。321.扫描法“Sweep”MethodforVRPExampleAtruckingcompanyhas10,000-unitvansformerchandisepickuptobeconsolidatedintolargerloadsformovingoverlongdistances.Aday’spickupsareshowninthefigurebelow.Howshouldtheroutesbedesignedforminimaltotaltraveldistance?CR(2004)PrenticeHall,Inc.33GeographicalregionDepot1,0002,0003,0002,0004,0002,0003,0003,0001,0002,0002,0002,000PickuppointsStopVolumeandLocationCR(2004)PrenticeHall,Inc.34SweepdirectionisarbitraryDepot1,0002,0003,0002,0004,0002,0003,0003,0001,0002,0002,0002,000Route#110,000unitsRoute#29,000unitsRoute#38,000units

“Sweep”MethodSolutionCR(2004)PrenticeHall,Inc.352.节约法目标使所有车辆行驶的总里程最短，并进而使为所有站点提供服务的卡车数量最少。36The“Savings”MethodforVRPDepotDepot(a)Initialrouting

Routedistance=d0,A+dA,0+d0,B+dB,0(b)Combiningtwostopsonaroute

Routedistance=d0,A+dA,B+dB,0ABdA,0d0,Ad0,BdB,0ABdB,0d0,AdA,BStopStop00“Savings”isbetterthan“Sweep”method—hasloweraverageerrorCR(2004)PrenticeHall,Inc.7-2537节约法求解配送方案例题：下图为某配送中心的配送网络，途中P点为配送中心，A——J为配送客户，共10位客户，括号内为配送货物吨数，线路上的数字为道路距离，单位为km。现配送中心有额定载重量分别为2t和4t两种箱式货车可供送货，试用节约法设计最佳送货路线。38（1.4）PCBAJDEFIGH（1.5）76（0.4）（1.5）（0.7）（0.5）（0.8）（0.6）（0.6）2554119264587691047810434365（0.8）39解：第一步，计算网络结点间的最短距离（可采用最短路求解法）。计算结果如表1。

表1：最短配送线路表40第二步，根据最短路结果，计算出各客户之间的节约里程，结果如表2。计算举例：A——B的节约里程：P——A的距离10，P——B的距离9，A——B的距离4则A——B的节约里程为10+9—4=1541表2配送路线节约里程表42

第三步，对节约行程按照大小顺序进行排列，如表3所示。表3：节约里程排序表43第四步，按节约里程排列顺序表，组合成配送路线图。配送路线为：线路一：P——J——A——B——C——P，需一辆4t货车。线路二：P——D——E——F——G——P，需一辆4t货车。线路三：P——H——I——P，需一辆2t货车。44PCBAJDEFIGH（1.5）（1.4）76（0.4）（1.5）（0.7）（0.5）（0.8）（0.6）（0.6）25496760471043（0.8）配送线路二配送线路一配送线路三45节约法的注意事项（1）适用于有稳定客户群的配送中心；（2）各配送线路的负荷要尽量均匀；（3）实际选择线路时还要考虑道路状况；（4）要考虑驾驶员的作息时间及客户要求的交货时间；（5）可利用计算机软件进行运算，直接生成结果。46节约法观察在同一条路线上，能够提供最大节约量的点是那些离仓库最远的并且相互最接近的地方。构建多站线路的原则CR(2004)PrenticeHall,Inc.47SavingsMethodObservationThepointsthatofferthegreatestsavingswhencombinedonthesameroutearethosethatarefarthestfromthedepotandthatareclosesttoeachother.Thisisagoodprincipleforconstructingmultiple-stoproutesCR(2004)PrenticeHall,Inc.487.3.3运输线路排序89101112123456Route#1Route#10AMPMRoute#6Route#9Route#4Route#5Route#8Route#2Route#7Route#3Truck#1Truck#2Truck#3Truck#4Truck#5MinimizenumberoftrucksbymaximizingnumberofrouteshandledbyasingletruckCR(2004)PrenticeHall,Inc.7-49对行车路线排序以尽可能减少所需卡车数49RouteSequencinginVRP89101112123456Route#1Route#10AMPMRoute#6Route#9Route#4Route#5Route#8Route#2Route#7Route#3Truck#1Truck#2Truck#3Truck#4Truck#5MinimizenumberoftrucksbymaximizingnumberofrouteshandledbyasingletruckCR(2004)PrenticeHall,Inc.7-5050方法之一是三阶段法1.预览：分析人员预览实际问题，考察有无例外情况。2.求解：通常借助于计算机3.审核：分析人员对数学求解结果进行审核，根据实际情况对结果加以修正。7.3.4行车路线和时刻表制定方法的应用7-51517.4船舶航线和船期计划某欧洲炼油企业沿欧洲海岸线有三个炼油厂D1,D2,D3,所用原油来自中东的两个港口L1，L2，装货港和卸货港之间采用油轮运输原油。以天数计算的港口间航行时间由以下矩阵给出：52为简化问题，假定港口间的航行时间与航行方向无关，且装卸时间相等，根据以后两个月的需求情况，炼油厂要求货物在下列时间运到，从现在开始计起：53根据给出的装货时间和航行时间，要满足卸货日期的要求，必须在如下时间装货：最晚装货时间54“行”代表最终状态，“列”代表起始状态。供求值是每种状态发生的次数。本例中，所有的供求值都是1.矩阵中只有某些单元格有可行解，例如第四行第二列单元格的解就不可行。因为油轮不可能在第61天卸货后，再在第8天装货。用这种方式检验所有的单元格，对于不可行的单元格就指定一个非常高的成本，如100个成本单位，使其无法求解。对于可行的单元格就确定一个较低的成本，如1个成本单位。对于空闲的单元格则指定比较高的成本，如10个成本单位，以限制其使用。对空闲单元格进行初始分派就可以得到问题的初始可行解。这个解代表所需船只数量的最大值。55以运输方法解决船期安排问题的初始解56从第一列的初始状态开始，找到第一行最终状态解值为1的单元格，这就是位于第一行第三列的单元格。然后，我们找到另一个解值是1的单元格，即第三行第五列的单元格，这是一个空闲单元格，随后停止。再从下一列开始重复上述过程，直到找到空闲行内所有解值为1的空闲单元格。第一条线路就是L2,0-D3,12-L1,32-D2,51.L1,8-D1,29-L2,49-D3,61.由于有两条不同的运输路线，因此需要两艘油轮。57船期计划问题解的矩阵587.5FreightConsolidation合并运输库存合并车辆合并仓库合并时间合并CR(2004)PrenticeHall,Inc.597.5FreightConsolidation合并运输Combinesmallshipmentsintolarger onesAproblemofbalancingcostsavings againstcustomerservicereductionsAnimportantareaforcostreductionin manyfirmsBasedontherate-shipmentsize relationshipforfor-hirecarriersCR(2004)PrenticeHall,Inc.60FreightConsolidationAnalysisCR(2004)PrenticeHall,Inc.Supposewehavethefollowingordersforthenextthreedays.Considershippingtheseorderseachdayorconsolidatingthemintooneshipment.Supposethatwek