城市物流風(fēng)險(xiǎn)ppt課件

1、Incorporating risks in city logisticsProfessor Eiichi TaniguchiKyoto University1.Outline1 Concepts of city logistics2 Class of risks related to city logistics3 Vehicle routing and scheduling problems with time windows (VRPTW)4 VRPTW with uncertainty of travel times5 Multi-agent simulation with ambig

2、uity6 Conclusion. Source: Annual Statistical Report on Automobile Transport: Information and Research Department, Policy Bureau, Ministry of Land, Infrastructure and Transport Truck loading efficiency3.City logistics is the process for totally optimising the logistics and transport activities by pri

3、vate companies with the support of advanced information systems in urban areas considering the traffic environment, its congestion, safety and energy savings within the framework of a market economy (Taniguchi et al. 2001)1 Concepts of city logistics4.5Structure of visions for city logisticsResilien

4、ce.2 Class of risks related to city logisticsCongestionCrashHazardous material transportFloodEarthquakeBush fireSnowfallFrequencycomplexityUncertaintyAmbiguityDay-to dayRareVRPTWVRPTW-D VRPTW-PMulti-agent model.3 Vehicle routing and scheduling problems with time windows (VRPTW)2Depotk = 1, 2, K67108

5、3954Vehicle Routing and scheduling Problems with Time Windows (VRPTW) is defined as to find the minimum cost routes for k vehicles to service all the clients.Constraints: A vehicle can not serve more clients than its capacity. Delivery at each client must be within some pre-defined time windows. 2 3

6、 pm 4 7 pm 7 8 pm 10 12 am 1 5 pm 10 11 am 10 11 am6 7 pm 3 4 pm7.VRPTW VariantsHard Time WindowsDelivery is not possible outside the specified Time Windows (VRPHTW). Soft Time WindowsDelivery is possible outside the specified Time Windows with penalties (VRPSTW). TimePenalty cost ai biHard Time Win

7、dows (HTW)In exact solution techniques, waiting is allowed at no costTime ai bi biPenalty costSimilarly allowing waiting without cost in Soft Time Windows results in:Semi Soft Time Windows (SSTW).ObjectivesCost of DeliveryWaiting TimeEnvironment ImpactsNOxCO2SPMDevelop an exact solution approach for

8、 VRPSSTW Using exact solution techniques for both VRPHTW and VRPSSTW, to compare their relative characteristics with respect to Using some practical logistics problems based on real road network so that above mentioned parameters can be calculated on the basis of actual traffic characteristics : Tra

9、vel time, Travel SpeedA detailed link based environmental comparison identifying emission intensities on each link produced by the VRPHTW and VRPSSTW solutions .VRPTW Formulation(1)(2)(3)(4)(5)(6)(7)(8)(9)Kohl et al., 1999. .Exact Solution Technique: Column GenerationColumn generation or Dantzig-Wol

10、fe decomposition, decomposes the VRPTW problem (1 9) into:* Elementary shortest path problem with resource constraints (ESPPRC) (3 9). (Sub-Problem) * Set partitioning problem (Master Problem). Past Research: VRPHTWNew Algorithm: VRPSSTWNew subproblem : Elementary shortest path problem with resource

11、 constraints and late arrival penalties (ESPPRCLAP). New Labeling Algorithm is developed. Time ai bi biPenalty costcij =cij , if sj bjcij + cl (sj - bj) if sj bjLate Arrival Penalty11.Exact Solution Technique: Column GenerationSub Problem ESPPRCLAP Feasible routes of negative reduced costReduce Cost

12、cij - iMaster ProblemOptimize, Prices (i)YesInteger SolutionNoYesEndNoBranch & BoundMaster ProblemSet Partitioning LP12.Upper and Lower BoundVRPSSTW Solution Col. Gen. stops but solution is not integerBranching on Number of VehiclesCol. Gen. stops but solution is not integer: Branching on xijCol. Ge

13、n. stops with integer Optimum Solution.Practical Test InstanceTest instance on Tokyo Road Network TD1_39_djkContains a single depot and 38 customers locations of a chain of convenience storeDepot.RoutesVRPHTW CaseVRPSSTW Case.TimePenalty cost ai biComparisons between VRPHTW and VRPSSTW Time ai bi bi

14、Penalty cost16.3 %Total CostParameterVRPHTWVRPSSTWNetwork Size707782No. of Subproblems81113Cols. added to LP (Paths)2782348Labels per subproblem 701447227Computation Time106.52520.8816.Comparisons of Delivery Time and Waiting Time 83.4 %Delivery Time050100150200250Time (sec.)VRPSSTWVRPHTW10.7 %17.Co

15、mparisons of Total Emissions 24 %19.3 %18.3 %Comparisons of Average Emissions per Used Link 22.4 %17.6 %16.7 %18.Distributions of Used Links (NOx)VRPSSTWVRPHTW 1.61.2 1.6 0.8 1.20.4 0.80.2 0.4 0 0.2Nox Scale (gm)19.Distributions of Used Links (CO2)VRPSSTWVRPHTW 400300 400 200 300100 20050 100 0 50CO

16、2 Scale (gm)20.Distributions of Used Links (SPM)VRPSSTWVRPHTW 0.160.12 0.16 0.08 0.120.04 0.080.02 0.04 0 0.02SPM Scale (gm)21.4 VRPTW with uncertainty of travel times.IntroductionUrban traffic congestion in Japanese citiesFreight transport has large influence on traffic conditions and the environme

17、ntICT & ITS allow us to obtain traffic informationConcept of “City Logistics becomes more importantBetter routing for pickup/delivery trucks can contribute to the improvement of traffic flow.VICS (Vehicle Information Communication System)VICS is a part of ITSNow 78,000+ links on service in Japan Inf

18、ormation are updated every 5 minutes and historical data is accumulated Historical data of travel times is available.Historical data of travel times by VICSTravel times on real network.ObjectivesForm VRPTW-P with ants routing model to incorporate the variable travel timesConfirm the effect of using

19、route learning for VRPTW-P by the experiment in terms of costs and environmental impacts.VRPTW-PVRPTW-P (probabilistic vehicle routing and scheduling with time window-probabilistic) uses travel times distribution of each link as variable travel timesObjective FunctionMinimise fixed cost operation co

20、st early arrival and delay penalty 27.Early arrival and delay penalty.Parameters of Genetic AlgorithmsVRPTW are solved with GA (Genetic Algorithm)Number of individuals = 300Number of generations = 1,000Number of elite individuals = 30Crossover rate = 0.8Mutation rate = 0.02.VRPTW-P with route learni

21、ngVisiting orders of customers are determined with travel time distributionsRoute choices were determined by shortest path method with mean value of link travel timesEffect of Ants routing (route learning) for VRPTW-P was examined.Framework of Reinforcement LearningLearn the policy to maximise rewor

22、d acquisitionAgentEnvironmentStateStActionAtRewordRtAgent learns the suitable policy through trial and error.Ants routing algorithmsAnts routing is proposed by Subramanian et al. (1997) Routing rules are treated as random variablesOnly backward exploration is used for updating routing table.Update p

23、robability table by ants routingk :learing ratef(t) :travel time33.34.Field experiments17-24 November 2006, Central Osaka JapanTravel time information: VICSNumber of customers: 24Number of trucks: 2 at each caseComparison VRPTW-P with route learning by ants routing (VRPTW-PA),VRPTW-P and VRPTW-F wit

24、h shortest path by mean value of travel times.DepotNetwork (All VICS links)225nodes, 789links# of Customers: 24 With Time Windows# of Trucks: 2Route choice:Shortest Path (Mean value of LTT)Route Learning (Ants RoutingVICS Data01 October 2004 16 November(30days)VRPVRPTW-P(SPRL),VRPTW-F(SP)Experiment

25、Date:17-24 November 2006(5days)Field Experiments36.VRPTW-FDiagram of 21 NovemberDelay even in the former half, large delay in the latter halfTime WindowDepotDelayDelay37.VRPTW-PDiagram of 21 NovemberLarge delay in the latter halfDelayDelayTime WindowDepot38.VRPTW-P + Ants RoutingDiagram of 21 Novemb

26、er Small delaysDelayDelayDelayTime WindowDepot23/2839.Results (Running time)24/2840.Results (Costs)November1718212224Mean(%)VRPTW-FEarly Arrival000000Delay38,93050,63745,93851,04652,24647,759ExpectedOperation8,8879,4699,4099,5679,4079,34862,523Total68,65280,94076,18281,44882,48877,942100VRPTW-PEarly

27、 Arrival781775013561Delay29,33536,14130,09236,18823,82131,115ExpectedOperation9,7499,9249,63410,0099,2019,70343,094Total59,99666,91860,63667,03253,99261,71579.2VRPTW-PAEarly Arrival97003516259Delay6,12010,16111,0359,2959,7259,267ExpectedOperation8,6259,1158,9929,1028,9398,95538,373Total35,67740,1114

28、0,86239,26739,66139,11650.2(Unit : Japanese Yen)41.Comparison with conventional plannerPlan was made by a planner of freight companyCompared on expected costsUse 3 trucks, no delay, large early arrivalOperation cost and total cost are larger than that of VRPTW-PAFixed costOperation costDelay Penalty

29、Early arrival penaltyTotal cost(%)VRPTW-F20,83511,00430,40827662,523129.9VRPTW-P20,83510,76011,30519443,09489.5VRPTW-PA20,83511,5935,72521938,37379.7Planner31,25314,51802,36148,132100.0(Unit:Yen).Total distance and mean vehicle speed of each caseTotal Distance (km)Mean Speed (km/h)VRPTW-F193.7017.43

30、VRPTW-P187.9016.29VRPTW-PA199.3018.72Negative impacts on the environmentCO2(g)NOx(g)SPM(g)VRPTW-F70.06 73.52 15.05 VRPTW-P69.46 72.49 14.77 VRPTW-PA69.65 73.33 15.15 Results (negative impacts on the environment)27/28.Hazardous material transportMulti-objective optimisation.5 Multi-agent simulation w

31、ith ambiguity.Interaction among stakeholders (agents)Freight carrierShipperAdministratorCity logistic measures (road pricing, co-operative freight transport systems)NOx emissionsSubsidies if choosing environmentally friendly freight carriersPropose price for maximising profitSelect freight carrier f

32、or minimising cost47.Case study (A) - Effects of VRPTW-DFixed cost5 (unit/min.)Operation cost0.05 (unit/min.)Delay penalty0.2 (unit/min.)Average 40 min.Variance 20 min260min.40 min2Link travel timeFreight carrierAFreightCarrier BShipper 2Shipper 1Cost of freight carrierShipper 10.3 (unit/min.)Shippe

33、r 23 (unit/min.)Cost of shipper due to delay arrival (time window: 60 min.)48.Comparison with game theoryPolicy of proposed price of freight carrier APolicy of proposed price of freight carrier B.Results of simulation using multi-agent model (fixed travel times)DaysDaysProposed price (6 units)Propos

34、ed price (6 units)Learning rate 0.5Learning rate 0.6Carrier ACarrier BCarrier ACarrier B.Comparison of two modelsVRPTW-FForecasted vehicle routing and scheduling with time windows with only historical data on travel times VRPTW-DDynamic vehicle routing and scheduling with time windows with real time

35、 data as well as historical data on travel times.Change of visiting order and/or route of VRPTW-D with real time information.Profit of freight carriersCase A-1Case A-2CaseA-3Freight carrier AVRPTW-FVRPTW-FVRPTW-DFreight carrier BVRPTW-FVRPTW-DVRPTW-D.Cost of shippers.Case study (B) - Evaluating city logistics measures4km40km/h30km/hFreight carrier 1-3 node 1Freight carrier 4-6 node 13Freight carrier 7-8 node 7Freight carrier 9-