欢迎来到天天文库
浏览记录
ID:38615514
大小:383.08 KB
页数:26页
时间:2019-06-16
《The Vehicle Routing Problem with Discrete》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、TheVehicleRoutingProblemwithDiscreteSplitDeliveriesandTimeWindowsIlariaVaccaTransportandMobilityLaboratory,EPFLjointworkwithMatteoSalaniSeminairedu3´emecycleromanddeRechercheOp`erationnelle´Zinal-January18,2010TheVehicleRoutingProblemwithDiscreteSplitDeliveriesandTi
2、meWindows–p.1/26Outline•Problemdescriptionandapplications•MILPformulationandColumngeneration•Branch-and-pricealgorithm•Computationalresults•ConclusionsandfurtherresearchTheVehicleRoutingProblemwithDiscreteSplitDeliveriesandTimeWindows–p.2/26TheVehicleRoutingProblem(
3、VRP)Given•setofcustomerswithdemandstobeserved(withintimewindows:VRPTW);•setofcapacitatedvehiclesavailableatasingledepot;DEPOTTheVehicleRoutingProblemwithDiscreteSplitDeliveriesandTimeWindows–p.3/26TheVehicleRoutingProblem(VRP)Objective•designtheoptimalminimum-costro
4、utesforvehicles,•suchthateverycustomerisvisitedexactlyonce.Route2Route3Route1DEPOTTheVehicleRoutingProblemwithDiscreteSplitDeliveriesandTimeWindows–p.4/26VRPwithSplitDeliveries(SDVRP)Splittabledemand•demandcanbesplitandthusservedbymorethanonevehicle;•customerscanbev
5、isitedmorethanonce.Route2Route3Route1DEPOTTheVehicleRoutingProblemwithDiscreteSplitDeliveriesandTimeWindows–p.5/26VRPwithDiscreteSplitDeliveries(DSDVRP)Demandisdiscretizedinitems•variantofVRPwith(continuous)splitdeliveries;•thedemandofeachcustomerisrepresentedbyaset
6、ofitems;•demandcanbesplitbutitemscannot.Demandisdeliveredincombinationsofitems•itemsaregroupedanddeliveredincombinations(subsetsofitems);•foreverycustomer,feasiblecombinationsofitemsarepredefinedandknown;•somecombinationsofitemsarenotallowed.Sierksma&Tijssen(1998);Na
7、kao&Nagamochi(2007);Cesellietal.(2009).TheVehicleRoutingProblemwithDiscreteSplitDeliveriesandTimeWindows–p.6/26DSDVRPwithTimeWindows(DSDVRPTW)Servicetimeisquantity-dependent•wedefineservicetimethetimeneededtoperformthedeliveryoncethevehicleisarrivedatcustomer’slocati
8、on;•inourmodel,servicetimedependsonthequantitydelivered;•inparticular,aspecificservicetimeisassociatedtoeveryfeasiblecombinationofitems;•we
此文档下载收益归作者所有