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:Theobjectiveistominimizethevehiclefleetandthesumoftraveltimeneededtosupplyallcustomerswithrandomvaluesoneachexecutionforthecustomerstobeserved,theirdemandsand/ortheserviceandtraveltimes. Feasibility:Whensomedataarerandom,itisnolongerpossibletorequirethatallconstraintsbesatisfiedforallrealizationsoftherandomvariables.Sothedecisionmakermayeitherrequirethesatisfactionofsomeconstraintswithagivenprobability,ortheincorporationintothemodelofcorrectiveactionstobetakenwhenaconstraintisviolated.VRPwithPickupandDeliveries TheVehicleRoutingProblemwithPickupandDeliveries(VRPPD)isaVRPinwhichthepossibilitythatcustomersreturnsomecommoditiesiscontemplated.SoinVRPPDit'sneededtotakeintoaccountthatthegoodsthatcustomersreturntothedelivervehiclemustfitintoit.Thisrestrictionmaketheplanningproblemmoredifficultandcanleadtobadutilizationofthevehiclescapacities,increasedtraveldistancesoraneedformorevehicles. Hence,itisusuallytoconsiderrestrictedsituationswherealldeliverydemandsstartfromthedepotandallpick-updemandsshallbebroughtbacktothedepot,sotherearenointerchangesofgoodsbetweenthecustomers. Anotheralternativeisrelaxingtherestrictionthatallcustomershavetobevisitedexactlyonce. Anotherusualsimplificationistoconsiderthateveryvehiclemustdeliverallthecommoditiesbeforepickingupanygoods(VRPB). Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltime,withtherestrictionthatthevehiclemusthaveenoughcapacityfortransportingthecommoditiestobedeliveredandthoseonespicked-upatcustomersforreturningthemtothedepot. Feasibility:Asolutionisfeasibleifthethetotalquantityassignedtoeachroutedoesnotexceedthecapacityofthevehiclewhichservicestherouteandthevehiclehasenoughcapacityforpicking-upthecommoditiesatcustomers.VRPwithBackhauls TheVehicleRoutingProblemwithBackhauls(VRPB)isaVRPinwhichcustomerscandemandorreturnsomecommodities. SoinVRPPDit’sneededtotakeintoaccountthatthegoodsthatcustomersreturntothedelivervehiclemustfitintoit.Thecriticalassumptioninthatalldeliveriesmustbemadeoneachroutebeforeanypickupscanbemade.Thisarisesfromthefactthatthevehiclesarerear-loaded,andrearrangementoftheloadsonthetracksatthedeliverypointsisnotdeemedeconomicalorfeasible.Thequantitiestobedeliveredandpicked-uparefixedandknowninadvance.VRPBissimilartoVRPPDwiththerestrictionthatinthecaseofVRPBalldeliveriesforeachroutemustbecompletedbeforeanypickupsaremade. Objective:Theobjectiveistofindsuchasetofroutesthatminimizesthetotaldistancetraveled. Feasibility:Afeasiblesolutionoftheproblemconsistsofasetofrouteswherealldeliveriesforeachroutearecompletedbeforeanypickupsaremadeandthevehiclecapacityisnotviolatedbyeitherthelinehaulorbackhaulpointsassignedtotheroute.VRPwithTimeWindows(VRPTW) TheVRPTWisthesameproblemthatVRPwiththeadditionalrestrictionthatinVRPTWatimewindowisassociatedwitheachcustomerv,defininganinterval[av,bv]whereinthecustomerhastobesupplied.Theinterval[av,bv]atthedepotiscalledtheschedulinghorizon.Hereisaformaldescriptionoftheproblem: Objective:Theobjectiveistominimizethevehiclefleetandthesumoftraveltimeandwaitingtimeneededtosupplyallcustomersintheirrequiredhours. Feasibility:TheVRPTWis,regardingtoVRP,characterizedbythefollowingadditionalrestrictions: Asolutionbecomesinfeasibleifacustomerissuppliedaftertheupperboundofitstimewindow. Avehiclearrivingbeforethelowerlimitofthetimewindowcausesadditionalwaitingtimeontheroute. Eachroutemuststartandendwithinthetimewindowassociatedwiththedepot. Inthecaseofsofttimewidows,alaterservicedoesnotaffectthefeasibilityofthesolution,butispenalizedbyaddingavaluetotheobjectivefunction.一、车辆路径问题概述 系统名称 开发者 核心算法 VRPX IBM(美国) 最短路算法启发式算法 VSS 富士通(日本) 节约法 HPCAD 美孚(美国) 扫描法相关网站 1.西班牙UniversityofMálaga：http://neo.lcc.uma.es/radiaeb/WebVRP/index.html 2.挪威SINTEF：http://www.top.sintef.no/ 3.瑞士IDSIA：http://www.idsia.ch/ 4.美国UniviversityofLehigh：http://branchandcut.org/ 5.德国UniversityofHeidelberg：http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/index.html旅行商问题(TravellingSalemanProblem）TSP某货郎由一城市出发，拟去已确定的n个城市推销产品，最后回到出发城市。设任意两城市间的距离都是已知的，要求找出一条每个城市都只到一次的旅行线路，使其总旅程最短。二、车辆路径问题数学模型建模:TSP又称为货郎担问题。给这些城市编号。出发城市为0，拟访问城市分别为1,2,…,n问题就转化为：求一个的排序使得最小。其中，为城市到的距离。TSP的数学规划形式：表示进入且仅进入城市j一次;表示离开且仅离开城市i一次;(保证线路连通性)其中，表示若该旅行商在访问城i后接着访问城j，则令，否则令。 Problem: What’sdifferencebetweenTSPandVRP?CapacitatedVRP(CVRP)(非满载/有向图） G=(V,A)，连通有向图，V={v0,v1…vn}，A={(vi,vj)}； v0代表配送中心或者车场，Vc={v1…vn}，客户点vi的需求为qi(>0)； cij>0代表客户点vi，vj之间的费用； M辆同车型的车辆，车载容量Q(>qi)Example：0123SupposeM=1Example：0123SupposeM=2Example：0123SupposeM=2456第1辆车服务？第2辆车服务？VRPwithTimeWindows(VRPTW) TheVRPTWisthesameproblemthatVRPwiththeadditionalrestrictionthatinVRPTWatimewindowisassociatedwitheachcustomervi,defininganinterval[ai,bi]whereinthecustomerhastobesupplied.Theinterval[E,L]atthedepotiscalledtheschedulinghorizon.ModelDescription VRPTWisdefinedonthenetworkG=(V,A),wherenoden+1isaddedinV. AllfeasiblevehicleroutescorrespondtopathsinGthatstartfromnodev0andendalsoatnodev0. Atimewindowisalsoassociatedwithnodes0andn+1,i.e.,[a0,b0]=[an+1,bn+1]=[E,L],whereEandLrepresenttheearliestpossibledeparturefromthedepotandthelatestpossiblearrivalatthedepot,respectively. Zerodemandsandservicetimesaredefinedforv0.Thatis,q0=s0=0. tij表示车辆由vi驶到vj的时间 客户点vi的需求为qi(>0) 客户点vi的开始服务时间需在一定的时间范围[ai,bi] si表示车辆对客户点vi的时间硬时间窗问题 每个客户点vi的开始服务时间必须落在时间窗[ai,bi]中；MDVRP(MultipleDepotVRP) 从多个车场(配送中心)用多辆车向多个客户送货，组织适当的行车路线，使车辆有序地通过它们；每个配送中心的位置一定，每个客户的位置和需求量一定，每台车辆的载重量一定，其一次配送的最大行驶距离一定，配送中心供应的货物，能够满足所有客户的需求，要求合理安排车辆配送路线，使目标函数得到优化(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)，从而加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。并满足以下条件：①每条配送路径上客户的需求量之和不超过车载容量；②每条配送路径的长度不超过车辆一次配送的最大行驶距离；③每个客户的需求必须满足，且只能由一辆车送货。ProblemStatementTheMultipleDepotVehicleRoutingProblem(MDVRP):DCustomersDD*MDVRP(MultipleDepotVRP)(非满载/有向图） G=(V,A)，连通有向图，,Vc={v1…vN}，Vd={vN+1,…vN+M}，A={(vi,vj)}，Vd代表配送中心集合，Vc代表客户点集合； 客户点vi的需求为qi(>0)； cij>0代表客户点vi,vj之间的费用； 配送中心vi有Km辆车 同车型的车辆，车载容量Q(>qi)*