搜索
文献出处：FerrucciF,BockS.Real-timecontrolofexpresspickupanddeliveryprocessesinadynamicenvironment[J].TransportationResearchPartB:Methodological,2014,63:1-14.原文Real-timecontrolofexpresspickupanddeliveryprocessesinadynamicenvironmentFrancescoFerrucci；StefanBock1.IntroductionDailytransportationservicesofexpresscourierservicecompaniesarecharacterizedbyahighlydynamicenvironmentinwhichthesystemsituationfrequentlychangesbytheoccurrenceofvariousdynamicevents.Akeycharacteristicisthatdynamicallyarrivingrequestshavetobetransportedfrompickuplocationstodeliverylocationsonthesameday.Sinceitishighlydesiredthatrequestsarefulfilledwithingiventimewindows,transportationactivitiesareoftencarriedoutunderhightimepressure.Moreover,roadnetworksarefrequentlycongestedandunreliable.Consequently,besidesthearrivalofnewrequests,trafficcongestionandvehicledisturbances,i.e.,slowdownsandbreakdowns,havetobemanagedinreal-time.Thankstoadvancesininformationandcommunicationtechnologies,informationaboutdynamiceventswhichisonlyavailableduringtheexecutionofthetransportationservicecannowbeutilized(Larsen,2000andGiaglisetal.,2004).1.1.ContributionsInthispaper,weproposeanewreal-timecontrolapproachforefficientlycoordinatingdynamictransportationservicesofexpresscourierservicecompanies.Inordertoprovidepracticaldecisionsupport,thisapproachisbasedonanextendedDynamicPickupandDeliveryProblem(DPDP)thatintegratesvarioussourcesofdynamiceventsaswellasseveralreal-worldaspects.WedenotethisnewvariantastheDynamicPickupandDeliveryProblemwithReal-TimeControl(DPDPRC).Itisspecificallydesignedinordertoefficientlycontrolurgentreal-worldtransportationserviceswhichareexecutedbyexpresscourierservicecompanies.Themaincontributionsofthispaperare:•Considerationofvariousreal-worldaspects.TheDPDPRCextendstheDPDPbyconsideringrealisticaspectsthataretypicaloftheconsideredtransportationservices.Vehiclesareheterogeneousintermsofcapacity,personnelcosts,travelspeed,androute-dependenttravelcosts.Softrequesttimewindowswithvariablelatenesscostsareintegratedaswellaslegaldrivingtimerestrictions.Theprimaryobjectiveistominimizelatenessatrequestlocationsandthesecondaryobjectiveistominimizevehicleoperatingcosts.Moreover,vehiclestravelonadetailedrealroadnetwork.•Dynamicenvironmentcomprisingvarioustypesofdynamicevents.Besidesnewlyincomingrequests,furtherdynamiceventssuchastrafficcongestion,vehicleslowdownsaswellasvehiclebreakdownsareintegrated.Theintegrationofthesesourcesofdynamicevents,whicharecommoninreal-worldtransportationservices,ensuresthepracticalapplicabilityoftheDPDPRC.•Real-timecontrolandappropriatesolutionmethod.IntheDPDPRC,transportationservicesarecoordinatedbyareal-timecontrolapproachthathandlestheconcurrencyoftourplanexecutionandtourplanadaptation.Inordertoefficientlyadapttheexistingtransportationplanaccordingtotheconsequencesofoccurringdynamicevents,aspecificallydesignedTabuSearchapproachisapplied.Duetotheresultingextendedadaptability,manychallengingscenarioswithtighttimewindowsandalargenumberofdifferenttypesofdynamiceventscanbeefficientlyhandled.•Generationofappropriatetestinstances.Inordertoevaluatetheefficiencyandpracticabilityoftheproposedapproachesunderdifferentpossiblesituations,varioustestscenarioswithdifferenttypesofdynamiceventsaregenerated.Forthispurpose,weproposenewmethodsforgeneratingprobleminstancesofdesiredcomplexity.Furthermore,anewapproachforsimulatingtrafficcongestioninroadnetworksisintroduced.Thepracticabilityoftheproposedreal-timecontrolapproachisevaluatedbymeansofacomprehensivecomputationalstudy.1.2.LiteraturereviewTheconsideredtransportationservicescanbemodeledasavariantofthePickupandDeliveryProblem(PDP)whichisageneralizationofthewell-studiedVehicleRoutingProblem(VRP,seeTothandVigo,2002andGoldenetal.,2008)andaspecialcaseoftheGeneralPickupandDeliveryProblem(GPDP,seeSavelsberghandSol,1995).VariantsofPDPshavebecomeavitalresearchareabecauseoftheirpracticalrelevance.AcloselyrelatedproblemthatfocusesonpassengertransportationistheDial-a-RideProblem(DARP,seeCordeauandLaporte,2007,Cordeauetal.,2007,Paquetteetal.,2013andKirchlerandWolflerCalvo,2013).IntheDARP,additionaldrivingconstraintsandconvenienceobjectivesareconsidered.Intheliterature,approachesforstaticPDPsaredistinguishedfromdynamicconcepts.InapproachesforstaticPDPsitisassumedthattheproblemdataisknowninadvancewithcertainty(see,e.g.,NanryandWesleyBarnes,2000,LuandDessouky,2004andBardandJarrah,2009).Hence,onaccountoftheabsenceofdynamicevents,noplanadaptationisnecessaryduringtheexecutionofthetransportationservice.Incontrast,real-timeconceptscanhandleunexpectedchangesofthesystemsituationcausedbydynamicevents(seeGhianietal.,2003,Mitrovic-Minicetal.,2004,Mitrovic-MinicandLaporte,2004andFabriandRecht,2006).Withregardtothefocusofthispaper,onlyreal-timeapproachesaredescribedinwhatfollows.AnoverviewaboutdynamicPDPscanbefoundinBerbegliaetal.(2010).Whilemostapproachesconsiderthearrivalofnewrequests,othersourcesofdynamiceventsarealsoconsideredinselectedresearchwork.ModelingoftrafficcongestionisconsideredintheworkofFleischmannetal.,