A strategyforreducingthecomputationalcomplexityoflocalsearch-based methods forthevehicleroutingproblem

This articlefocusesonthemechanismofevaluatingsolutionneighborhoods,analgorithmicaspect which playsacrucialroleontheefficiencyoflocal-searchbasedapproaches.Inspecific,itpresentsa strategyforreducingthecomputationalcomplexityrequiredforapplyinglocalsearchtotacklevarious combinatorialoptimizationproblems.Thevalueofthiscontributionistwo-fold.Ithelpspractitioners design efficientlocalsearchimplementations,anditfacilitatestheapplicationofrobustcommercial local search-basedalgorithmstopracticalinstancesofverylargesize.Thecentralrationaleunderlying the proposedcomplexityreductionstrategyisstraightforward:whenalocalsearchoperatorisapplied to agivensolution,onlyalimitedpartofthissolutionismodified.Thus,toexhaustivelyexaminethe neighborhoodofthenewsolution,onlythetentativemovesthatrefertothemodifiedsolutionpart have tobeevaluated.Toreducethecomplexityofneighborhoodevaluation,thestaticmovedescriptor (SMD)datastructuresareintroduced,whichencodelocalsearchmovesinasystematicandsolution independentmanner.Theproposedstrategyisappliedtothevehicleroutingproblem(VRP)whichisof high importancebothfromthepracticalandtheoreticalviewpoints.TheuseoftheSMDconcept,for encodingthreecommonlyappliedquadraticlocalsearchoperators,resultsintoaVRPlocalsearch methodwhichexhibitsanalmostlinearithmiccomplexityinrespecttotheinstancesize.Furthermore, exploitingtheSMDrepresentationoftentativemoves,ametaheuristicstrategyisproposed,whichis aimedatdiversifyingtheconductedsearchviaasimplepenalizationpolicy.Theproposed metaheuristicwastestedonvariouslargeandverylargescaleVRPbenchmarkinstances.Itproduced fine results,andmanagedtoimproveseveralbestknownsolutions.Themethodwasalsoexecutedon real-worldinstancesof3000customers,thedataofwhichreflectstheactualgeographicdistributionof customerswithinfourmajorcities.