VRP基本知识PPT课件

.,1,多回路运输车辆路径问题模型及求解,.,2,物流配送车辆优化调度，是物流糸统优化中关键的一环。对配送车辆进行优化调度，可以提高物流经济效益、实现物流科学化。对物流配送车辆优化调度理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。,车辆路径问题专题,.,3,主要内容,一、车辆路径问题概述二、车辆路径问题数学模型,车辆路径问题专题,.,4,一、车辆路径问题概述,TheVehicleRoutingProblem(VRP)isagenericnamegiventoawholeclassofproblemsinwhichasetofroutesforafleetofvehiclesbasedatoneorseveraldepotsmustbedeterminedforanumberofgeographicallydispersedcitiesorcustomers.TheobjectiveoftheVRPistodeliverasetofcustomerswithknowndemandsonminimum-costvehicleroutesoriginatingandterminatingatadepot.,.,5,组合爆炸,一台汽车每天要给20-30个不同的自动售货机(AVM：automaticvendingmachine)补充饮料，这个时候，巡回路线要访问20台机器的时候，就有20！2432902008176640000条巡回路线可供选择，若是访问30台，就有30！265252859812191058636308480000000条巡回路线可供选择，利用计算机，若是一秒钟可以计算100亿条路线的距离的话，20台AVM的计算需要花费7年的时间，30台AVM则需要花费8411兆年的时间，这种现象称为“组合爆炸”。,.,6,Features,Depots(number,location)Vehicles(capacity,costs,timetoleave,driverrestperiod,typeandnumberofvehicles,maxtime)Customers(demands,hardorsofttimewindows,pickupanddelivery,accessibilityrestriction,splitdemand,priority)RouteInformation(maximumroutetimeordistance,costonthelinks),.,7,ObjectiveFunctions(alsomultipleobjectives)MinimisethetotaltraveldistanceMinimisethetotaltraveltimeMinimisethenumberofvehicles,.,8,Figure1TypicalinputforaVehicleRoutingProblem,.,9,Figure2Anoutputfortheinstanceabove,.,10,Figure3Anoutputfortheinstanceabove,Vehicle1,Vehicle2,Vehicle3,.,11,车辆路径问题的分类,一、车辆路径问题概述,.,12,CapacitatedVRP(CPRV)MultipleDepotVRP(MDVRP)PeriodicVRP(PVRP)SplitDeliveryVRP(SDVRP)StochasticVRP(SVRP)VRPwithBackhaulsVRPwithPick-UpandDeliveringVRPwithSatelliteFacilitiesVRPwithTimeWindows(VRPTW),.,13,CapacitatedVRP(CPRV),CVRPisaVRPinwhichafixedfleetofdeliveryvehiclesofuniformcapacitymustserviceknowncustomerdemandsforasinglecommodityfromacommondepotatminimumtransitcost.Thatis,CVRPislikeVRPwiththeadditionalconstraintthateveryvehiclesmusthaveuniformcapacityofasinglecommodity.WecanfindbelowaformaldescriptionfortheCVRP:Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltime,andthetotaldemandofcommoditiesforeachroutemaynotexceedthecapacityofthevehiclewhichservesthatroute.Feasibility:Asolutionisfeasibleifthetotalquantityassignedtoeachroutedoesnotexceedthecapacityofthevehiclewhichservicestheroute.,.,14,MultipleDepotVRP(MDVRP),Acompanymayhaveseveraldepotsfromwhichitcanserveitscustomers.Ifthecustomersareclusteredarounddepots,thenthedistributionproblemshouldbemodeledasasetofindependentVRPs.However,ifthecustomersandthedepotsareintermingledthenaMulti-DepotVehicleRoutingProblemshouldbesolved.AMDVRPrequirestheassignmentofcustomerstodepots.Afleetofvehiclesisbasedateachdepot.Eachvehicleoriginatefromonedepot,servicethecustomersassignedtothatdepot,andreturntothesamedepot.Theobjectiveoftheproblemistoserviceallcustomerswhileminimizingthenumberofvehiclesandtraveldistance.WecanfindbelowaformaldescriptionfortheMDVRP:Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltime,andthetotaldemandofcommoditiesmustbeservedfromseveraldepots.Feasibility:AsolutionisfeasibleifeachroutesatisfiesthestandardVRPconstraintsandbeginsandendsatthesamedepot.,.,15,PeriodicVRP(PVRP),InclassicalVRPs,typicallytheplanningperiodisasingleday.InthecaseofthePeriodVehicleRoutingProblem(PVRP),theclassicalVRPisgeneralizedbyextendingtheplanningperiodtoMdays.Wedefinetheproblemasfollows:Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltimeneededtosupplyallcustomers.Feasibility:AsolutionisfeasibleifallconstraintsofVRParesatisfied.Furthermoreavehiclemaynotreturntothedepotinthesamedayitdeparts.OvertheM-dayperiod,eachcustomermustbevisitedatleastonce.,.,16,SplitDeliveryVRP(SDVRP),SDVRPisarelaxationoftheVRPwhereinitisallowedthatthesamecustomercanbeservedbydifferentvehiclesifitreducesoverallcosts.Thisrelaxationisveryimportantifthesizesofthecustomerordersareasbigasthecapacityofavehicle.ItisconcludedthatitismoredifficulttoobtaintheoptimalsolutionintheSDVRPthatintheVRP.Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltimeneededtosupplyallcustomers.Feasibility:AsolutionisfeasibleifallconstraintsofVRParesatisfiedexceptthatacustomermaybesuppliedbymorethanonevehicle.Formulation:Minimizethesumofthecostofallroutes.AneasywaytotransformaVRPintoaSDVRPconsistsonallowingsplitdeliveriesbysplittingeachcustomerorderintoanumberofsmallerindivisibleorders.,.,17,StochasticVRP(SVRP),StochasticVRP(SVRP)areVRPswhereoneorseveralcomponentsoftheproblemarerandom.ThreedifferentkindsofSVRParethenextexamples:Stochasticcustomers:Eachcustomerviispresentwithprobabilitypiandabsentwithprobability1-pi.Stochasticdemands:Thedemanddiofeachcustomerisarandomvariable.Stochastictimes:Servicetimessiandtraveltimestijarerandomvariables.InSVRP,twostagesaremadeforgettingasolution.Afirstsolutionisdeterminedbeforeknowingtherealizationsoftherandomvariables.Inasecondstage,arecourseorcorrectiveactioncanbetakenwhenthevaluesoftherandomvariablesareknown.,.,18,Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltimeneededtosupplyallcustomerswithrandomvaluesoneachexecutionforthecustomerstobeserved,theirdemandsand/ortheserviceandtraveltimes.Feasibility:Whensomedataarerandom,itisnolongerpossibletorequirethatallconstraintsbesatisfiedforallrealizationsoftherandomvariables.Sothedecisionmakermayeitherrequirethesatisfactionofsomeconstraintswithagivenprobability,ortheincorporationintothemodelofcorrectiveactionstobetakenwhenaconstraintisviolated.,.,19,VRPwithPickupandDeliveries,TheVehicleRoutingProblemwithPickupandDeliveries(VRPPD)isaVRPinwhichthepossibilitythatcustomersreturnsomecommoditiesiscontemplated.SoinVRPPDitsneededtotakeintoaccountthatthegoodsthatcustomersreturntothedelivervehiclemustfitintoit.Thisrestrictionmaketheplanningproblemmoredifficultandcanleadtobadutilizationofthevehiclescapacities,increasedtraveldistancesoraneedformorevehicles.Hence,itisusuallytoconsiderrestrictedsituationswherealldeliverydemandsstartfromthedepotandallpick-updemandsshallbebroughtbacktothedepot,sotherearenointerchangesofgoodsbetweenthecustomers.Anotheralternativeisrelaxingtherestrictionthatallcustomershavetobevisitedexactlyonce.Anotherusualsimplificationistoconsiderthateveryvehiclemustdeliverallthecommoditiesbeforepickingupanygoods(VRPB).,.,20,Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltime,withtherestrictionthatthevehiclemusthaveenoughcapacityfortransportingthecommoditiestobedeliveredandthoseonespicked-upatcustomersforreturningthemtothedepot.Feasibility:Asolutionisfeasibleifthethetotalquantityassignedtoeachroutedoesnotexceedthecapacityofthevehiclewhichservicestherouteandthevehiclehasenoughcapacityforpicking-upthecommoditiesatcustomers.,.,21,VRPwithBackhauls,TheVehicleRoutingProblemwithBackhauls(VRPB)isaVRPinwhichcustomerscandemandorreturnsomecommodities.SoinVRPPDitsneededtotakeintoaccountthatthegoodsthatcustomersreturntothedelivervehiclemustfitintoit.Thecriticalassumptioninthatalldeliveriesmustbemadeoneachroutebeforeanypickupscanbemade.Thisarisesfromthefactthatthevehiclesarerear-loaded,andrearrangementoftheloadsonthetracksatthedeliverypointsisnotdeemedeconomicalorfeasible.Thequantitiestobedeliveredandpicked-uparefixedandknowninadvance.VRPBissimilartoVRPPDwiththerestrictionthatinthecaseofVRPBalldeliveriesforeachroutemustbecompletedbeforeanypickupsaremade.,.,22,Objective:Theobjectiveistofindsuchasetofroutesthatminimizesthetotaldistancetraveled.Feasibility:Afeasiblesolutionoftheproblemconsistsofasetofrouteswherealldeliveriesforeachroutearecompletedbeforeanypickupsaremadeandthevehiclecapacityisnotviolatedbyeitherthelinehaulorbackhaulpointsassignedtotheroute.,.,23,VRPwithTimeWindows(VRPTW),TheVRPTWisthesameproblemthatVRPwiththeadditionalrestrictionthatinVRPTWatimewindowisassociatedwitheachcustomerv,defininganintervalav,bvwhereinthecustomerhastobesupplied.Theintervalav,bvatthedepotiscalledtheschedulinghorizon.Hereisaformaldescriptionoftheproblem:Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltimeandwaitingtimeneededtosupplyallcustomersintheirrequiredhours.Feasibility:TheVRPTWis,regardingtoVRP,characterizedbythefollowingadditionalrestrictions:Asolutionbecomesinfeasibleifacustomerissuppliedaftertheupperboundofitstimewindow.Avehiclearrivingbeforethelowerlimitofthetimewindowcausesadditionalwaitingtimeontheroute.Eachroutemuststartandendwithinthetimewindowassociatedwiththedepot.Inthecaseofsofttimewidows,alaterservicedoesnotaffectthefeasibilityofthesolution,butispenalizedbyaddingavaluetotheobjectivefunction.,.,24,一、车辆路径问题概述,.,25,相关网站,1.西班牙UniversityofMlaga：http:/neo.lcc.uma.es/radiaeb/WebVRP/index.html2.挪威SINTEF：http:/www.top.sintef.no/3.瑞士IDSIA：http:/www.idsia.ch/4.美国UniviversityofLehigh：/5.德国UniversityofHeidelberg：http:/www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/index.html,.,26,旅行商问题(TravellingSalemanProblem）,TSP,某货郎由一城市出发，拟去已确定的n个城市推销产品，最后回到出发城市。设任意两城市间的距离都是已知的，要求找出一条每个城市都只到一次的旅行线路，使其总旅程最短。,二、车辆路径问题数学模型,.,27,建模:,TSP又称为货郎担问题。给这些城市编号。出发城市为0，拟访问城市分别为1,2,n问题就转化为：,求一个的排序使得最小。,其中，为城市到的距离。,.,28,TSP的数学规划形式：,表示进入且仅进入城市j一次;,表示离开且仅离开城市i一次;,(保证线路连通性),其中，表示若该旅行商在访问城i后接着访问城j，则令，否则令。,.,29,Problem:WhatsdifferencebetweenTSPandVRP?,.,30,CapacitatedVRP(CVRP)(非满载/有向图）,G=(V,A)，连通有向图，V=v0,v1vn，A=(vi,vj)；v0代表配送中心或者车场，Vc=v1vn，客户点vi的需求为qi(0)；cij0代表客户点vi，vj之间的费用；M辆同车型的车辆，车载容量Q(qi),.,31,.,32,.,33,Example：,0,1,2,3,SupposeM=1,.,34,Example：,0,1,2,3,SupposeM=2,.,35,Example：,0,1,2,3,SupposeM=2,4,5,6,第1辆车服务？第2辆车服务？,.,36,VRPwithTimeWindows(VRPTW),TheVRPTWisthesameproblemthatVRPwiththeadditionalrestrictionthatinVRPTWatimewindowisassociatedwitheachcustomervi,defininganintervalai,biwhereinthecustomerhastobesupplied.TheintervalE,Latthedepotiscalledtheschedulinghorizon.,.,37,ModelDescription,VRPTWisdefinedonthen