The Vehicle Routing Problem with Discrete

《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