城市物流風(fēng)險-文庫吧資料
2025-01-10 10:13本頁面
【正文】 RPSSTW solutions Kyoto University Global COE “Human Security Engineering”VRPTW Formulation(1)(2)(3)(4)(5)(6)(7)(8)(9)Kohl et al., 1999. Kyoto University Global COE “Human Security Engineering”Exact Solution Technique: Column GenerationColumn generation or DantzigWolfe deposition, deposes the VRPTW problem (1 – 9) into:* Elementary shortest path problem with resource constraints (ESPPRC) (3 – 9). (SubProblem) * Set partitioning problem (Master Problem). Past Research: VRPHTWNew Algorithm: VRPSSTWNew subproblem : Elementary shortest path problem with resource constraints and late arrival penalties (ESPPRCLAP). New Labeling Algorithm is developed. Time[ ] ]ai bi bi’∞Penalty costc’ij = cij , if sj ≤ bjcij + cl (sj bj) if sj bjLate Arrival Penalty 11Kyoto University Global COE “Human Security Engineering”Exact Solution Technique: Column Generation Sub Problem ESPPRCLAP Feasible routes of negative reduced costReduce Costcij πiMaster ProblemOptimize, Prices (πi)YesInteger SolutionNoYesEndNoBranch BoundMaster ProblemSet Partitioning LP12Kyoto University Global COE “Human Security Engineering”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. Gen. stops with integer Optimum SolutionKyoto University Global COE “Human Security Engineering”Practical Test InstanceTest instance on Tokyo Road Network TD1_39_djkContains a single depot and 38 customers’ locations of a chain of convenience storeDepotKyoto University Global COE “Human Security Engineering”RoutesVRPHTW CaseVRPSSTW CaseKyoto University Global COE “Human Security Engineering”TimePenalty cost[ ]ai bi∞Comparisons between VRPHTW and VRPSSTW Time[ ] ]ai bi bi’∞Penalty cost %Total CostParameter VRPHTW VRPSSTWNetwork Size 707 782No. of Subproblems81 113Cols. added to LP (Paths)278 2348Labels per subproblem 7014 47227Computation Time 16Comparisons of Delivery Time and Waiting Time %Delivery Time050100150200250Time (sec.)VRPSSTW VRPHTW %17Comparisons of Total Emissions 24 % % %Comparisons of Average Emissions per Used Link % % %18Distributions of Used Links (NOx)VRPSSTW VRPHTW – – – – 0 – Nox Scale (gm)19Distributions of Used Links (CO2)VRPSSTW VRPHTW 400300 – 400 200 – 300100 – 20050 – 100 0 – 50CO2 Scale (gm)20Distributions of Used Links (SPM)VRPSSTW VRPHTW – – – – 0 – SPM Scale (gm)21Kyoto University Global COE “Human Security Engineering”4 VRPTW with uncertainty of travel timesKyoto University Global COE “Human Security Engineering”Introduction? Urban traffic congestion in Japanese cities? Freight transport has large influence on traffic conditions and the environment? ICT ITS allow us to obtain traffic information? Concept of “City Logistics” bees more important? Better routing for pickup/delivery trucks can contribute to the improvement
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1