资源描述:
《10软硬时间窗》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、4OR-QJOperRes(2010)8:221238DOI10.1007/s10288-010-0144-6INVITEDSURVEYRecentprogressoflocalsearchinhandlingthetimewindowconstraintsofthevehicleroutingproblemHidekiHashimoto·MutsunoriYagiura·ShinjiImahori·ToshihideIbarakiReceived:31May2010/Revised:23August2
2、010/Publishedonline:10September2010©Springer-Verlag2010AbstractVehicleroutingandschedulingproblemshaveawiderangeofapplica-tionsandhavebeenintensivelystudiedinthepasthalfcentury.Theconditionthatenforceseachvehicletostartserviceateachcustomerintheperiodspe
3、cifiedbythecustomeriscalledthetimewindowconstraint.Thispaperreviewsrecentresultsonhowtohandlehardandsofttimewindowconstraints,puttingemphasisonitsdifferentdefinitionsandalgorithms.Withthesediversetimewindows,theproblembecomesapplicabletoawiderangeofreal-w
4、orldproblems.KeywordsVehiclerouting·Timewindows·Scheduling·SurveyMSCclassification(2000)90B35·90C27·65K05·90B06·90-02H.Hashimoto(B)DepartmentofIndustrialandSystemsEngineering,ChuoUniversity,1-13-27Kasuga,Bunkyo-ku,Tokyo112-8551,Japane-mail:hasimoto@indsys
5、.chuo-u.ac.jpM.YagiuraDepartmentofComputerScienceandMathematicalInformatics,GraduateSchoolofInformationScience,NagoyaUniversity,Furocho,Chikusa-ku,Nagoya464-8603,Japane-mail:yagiura@nagoya-u.jpS.ImahoriDepartmentofComputationalScienceandEngineering,Gradu
6、ateSchoolofEngineering,NagoyaUniversity,Furocho,Chikusa-ku,Nagoya464-8603,Japane-mail:imahori@na.cse.nagoya-u.ac.jpT.IbarakiTheKyotoCollegeofGraduateStudiesforInformatics,7Monzencho,Tanaka,Sakyo-ku,Kyoto606-8225,Japane-mail:ibaraki@ieee.org123222H.Hashim
7、otoetal.1IntroductionVehicleroutingandschedulingproblemsconcernthedistributionofgoodsbetweendepotsandfinalusers(customers)(Desrochersetal.1988;SolomonandDesrosiers1988;Desrosiersetal.1995;TothandVigo2002;Goldenetal.2008;Laporte2009).Theyhavebeenintensivel
8、ystudiedsinceapaperbyDantzigandRamser(1959).Amongmanyvariations,thevehicleroutingproblemwithtimewindows(abbre-viatedasVRPTW)maybethemostcommonandbest-studied.Ithasbeenasubjectofintenseresearch,mostofwhichfocusesonheuristic