VRP基本知识

多回路运输——车辆路径问题模型及求解物流配送车辆优化调度，是物流糸统优化中关键的一环。对配送车辆进行优化调度，可以提高物流经济效益、实现物流科学化。对物流配送车辆优化调度理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。车辆路径问题专题主要内容一、车辆路径问题概述二、车辆路径问题数学模型车辆路径问题专题一、车辆路径问题概述•TheVehicleRoutingProblem(VRP)isagenericnamegiventoawholeclassofproblemsinwhichasetofroutesforafleetofvehiclesbasedatoneorseveraldepotsmustbedeterminedforanumberofgeographicallydispersedcitiesorcustomers.TheobjectiveoftheVRPistodeliverasetofcustomerswithknowndemandsonminimum-costvehicleroutesoriginatingandterminatingatadepot.组合爆炸•一台汽车每天要给20-30个不同的自动售货机(AVM：automaticvendingmachine)补充饮料，这个时候，巡回路线要访问20台机器的时候，就有20！＝2432902008176640000条巡回路线可供选择，若是访问30台，就有30！＝265252859812191058636308480000000条巡回路线可供选择，利用计算机，若是一秒钟可以计算100亿条路线的距离的话，20台AVM的计算需要花费7年的时间，30台AVM则需要花费8411兆年的时间，这种现象称为“组合爆炸”。Features•Depots(number,location)•Vehicles(capacity,costs,timetoleave,driverrestperiod,typeandnumberofvehicles,maxtime)•Customers(demands,hardorsofttimewindows,pickupanddelivery,accessibilityrestriction,splitdemand,priority)•RouteInformation(maximumroutetimeordistance,costonthelinks)•ObjectiveFunctions(alsomultipleobjectives)MinimisethetotaltraveldistanceMinimisethetotaltraveltimeMinimisethenumberofvehiclesFigure1TypicalinputforaVehicleRoutingProblemFigure2AnoutputfortheinstanceaboveFigure3AnoutputfortheinstanceaboveVehicle1Vehicle2Vehicle3车辆路径问题的分类一、车辆路径问题概述分类标准类型物流中心的数目单车场问题、多车场问题车辆载货状况满载问题、非满载问题、满载和非满载混合问题配送任务特征纯送货问题或纯取货问题、取送混合问题货物取(送)时间的要求无时间窗问题、有时间窗问题车辆类型数单车型问题、多车型问题车辆对车场的所属关系车辆开放问题、车辆封闭问题优化目标数单目标问题、多目标问题•CapacitatedVRP(CPRV)•MultipleDepotVRP(MDVRP)•PeriodicVRP(PVRP)•SplitDeliveryVRP(SDVRP)•StochasticVRP(SVRP)•VRPwithBackhauls•VRPwithPick-UpandDelivering•VRPwithSatelliteFacilities•VRPwithTimeWindows(VRPTW)CapacitatedVRP(CPRV)•CVRPisaVRPinwhichafixedfleetofdeliveryvehiclesofuniformcapacitymustserviceknowncustomerdemandsforasinglecommodityfromacommondepotatminimumtransitcost.Thatis,CVRPislikeVRPwiththeadditionalconstraintthateveryvehiclesmusthaveuniformcapacityofasinglecommodity.WecanfindbelowaformaldescriptionfortheCVRP:•Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltime,andthetotaldemandofcommoditiesforeachroutemaynotexceedthecapacityofthevehiclewhichservesthatroute.•Feasibility:Asolutionisfeasibleifthetotalquantityassignedtoeachroutedoesnotexceedthecapacityofthevehiclewhichservicestheroute.MultipleDepotVRP(MDVRP)•Acompanymayhaveseveraldepotsfromwhichitcanserveitscustomers.Ifthecustomersareclusteredarounddepots,thenthedistributionproblemshouldbemodeledasasetofindependentVRPs.However,ifthecustomersandthedepotsareintermingledthenaMulti-DepotVehicleRoutingProblemshouldbesolved.•AMDVRPrequirestheassignmentofcustomerstodepots.Afleetofvehiclesisbasedateachdepot.Eachvehicleoriginatefromonedepot,servicethecustomersassignedtothatdepot,andreturntothesamedepot.•Theobjectiveoftheproblemistoserviceallcustomerswhileminimizingthenumberofvehiclesandtraveldistance.WecanfindbelowaformaldescriptionfortheMDVRP:•Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltime,andthetotaldemandofcommoditiesmustbeservedfromseveraldepots.•Feasibility:AsolutionisfeasibleifeachroutesatisfiesthestandardVRPconstraintsandbeginsandendsatthesamedepot.PeriodicVRP(PVRP)•InclassicalVRPs,typicallytheplanningperiodisasingleday.InthecaseofthePeriodVehicleRoutingProblem(PVRP),theclassicalVRPisgeneralizedbyextendingtheplanningperiodtoMdays.•Wedefinetheproblemasfollows:Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltimeneededtosupplyallcustomers.Feasibility:AsolutionisfeasibleifallconstraintsofVRParesatisfied.Furthermoreavehiclemaynotreturntothedepotinthesamedayitdeparts.OvertheM-dayperiod,eachcustomermustbevisitedatleastonce.SplitDeliveryVRP(SDVRP)•SDVRPisarelaxationoftheVRPwhereinitisallowedthatthesamecustomercanbeservedbydifferentvehiclesifitreducesoverallcosts.Thisrelaxationisveryimportantifthesizesofthecustomerordersareasbigasthecapacityofavehicle.•ItisconcludedthatitismoredifficulttoobtaintheoptimalsolutionintheSDVRPthatintheVRP.•Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltimeneededtosupplyallcustomers.•Feasibility:AsolutionisfeasibleifallconstraintsofVRParesatisfiedexceptthatacustomermaybesuppliedbymorethanonevehicle.•Formulation:Minimizethesumofthecostofallroutes.AneasywaytotransformaVRPintoaSDVRPconsistsonallowingsplitdeliveriesbysplittingeachcustomerorderintoanumberofsmallerindivisibleorders.StochasticVRP(SVRP)•StochasticVRP(SVRP)areVRPswhereoneorseveralcomponentsoftheproblemarerandom.ThreedifferentkindsofSVRParethenextexamples:Stochasticcustomers:Eachcustomerviispresentwithprobabilitypiandabsentwithprobability1-pi.Stochasticdemands:Thedemanddiofeachcustomerisarandomvariable.Stochastictimes:Servicetimessiandtraveltimestijarerandomvariables.•InSVRP,twostagesaremadeforgettingasolution.Afirstsolutionisdeterminedbeforeknowingtherealizationsoftherandomvariables.Inasecondstage,arecourseorcorrectiveactioncanbetakenwhenthevaluesoftherandomvariablesareknown.•Objective:Theobjectiveistominimizethevehiclefleetand