资源描述：
《物流英文文献》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Computers&OperationsResearch34(2007)2403–2435www.elsevier.com/locate/corAgeneralheuristicforvehicleroutingproblemsDavidPisinger∗,StefanRopkeDIKU,DepartmentofComputerScience,UniversityofCopenhagen,Universitetsparken1,DK-2100CopenhagenO,DenmarkAvailableonline24October2005A
2、bstractWepresentaunifiedheuristicwhichisabletosolvefivedifferentvariantsofthevehicleroutingproblem:thevehicleroutingproblemwithtimewindows(VRPTW),thecapacitatedvehicleroutingproblem(CVRP),themulti-depotvehicleroutingproblem(MDVRP),thesite-dependentvehicleroutingproblem(SDVR
3、P)andtheopenvehicleroutingproblem(OVRP).Allproblemvariantsaretransformedintoarichpickupanddeliverymodelandsolvedusingtheadaptivelargeneighborhoodsearch(ALNS)frameworkpresentedinRopkeandPisinger[Anadaptivelargeneighborhoodsearchheuristicforthepickupanddeliveryproblemwithti
4、mewindows.TransportationScience,toappear].TheALNSframeworkisanextensionofthelargeneighborhoodsearchframeworkbyShaw[Usingconstraintprogrammingandlocalsearchmethodstosolvevehicleroutingproblems.In:CP-98,Fourthinternationalconferenceonprinciplesandpracticeofconstraintprogram
5、ming,Lecturenotesincomputerscience,vol.1520,1998.p.417–31]withanadaptivelayer.Thislayeradaptivelychoosesamonganumberofinsertionandremovalheuristicstointensifyanddiversifythesearch.Thepresentedapproachhasanumberofadvantages:itprovidessolutionsofveryhighquality,thealgorithm
6、isrobust,andtosomeextentself-calibrating.Moreover,theunifiedmodelallowsthedispatchertomixvariousvariantsofVRPproblemsforindividualcustomersorvehicles.AswebelievethattheALNSframeworkcanbeappliedtoalargenumberoftightlyconstrainedoptimizationproblems,ageneraldescriptionofthef
7、rameworkisgiven,anditisdiscussedhowthevariouscomponentscanbedesignedinaparticularsetting.Thepaperisconcludedwithacomputationalstudy,inwhichthefivedifferentvariantsofthevehicleroutingproblemareconsideredonstandardbenchmarktestsfromtheliterature.Theoutcomeofthetestsispromisi
8、ngasthealgorithmisabletoimprove183bestknownsolutionsoutof486benchmarktests.Theheuristichasalsosh
