A Local Search Based Multi-objective Optimization

1ALocalSearchBasedMulti-objectiveOptimizationAlgorithmforMulti-objectiveVehicleRoutingProblemWithTimeWindowsYingZhouandJiahaiWang,Member,IEEEAbstract—Vehicleroutingproblemwithtimewindows(VRPTW)isanimportantlogisticsproblemwhichappearstobemulti-objectiveinreal-world.Recently,ageneralmulti-objectiveVRPTW(MOVRPTW)problemwithfiveobjectivesisdefinedandasetofMOVRPTWprobleminstancesbasedondatafromreal-worldareproposed.Theseinstancesindicatemoretrulymulti-objectivenatureandrepresentmorerealisticandchallengingMOVRPTWcases.Inthispaper,alocalsearchbasedmulti-objectiveoptimizationalgorithmisproposedforthereal-worldMOVRPTWinstances.ConsideringtheproblemstructureofMOVRPTW,wedesigndifferentlocalsearchmethodsfordifferentobjectives.Thesesimplebuteffectivelocalsearchmeth-odscooperatetooptimizedifferentobjectivessimultaneously.Moreproblem-specificknowledgecanbeextractedbyusingobjective-wiselocalsearchcomponentsandthushigh-qualitysolutionsareexpectedtobegenerated.Theproposedalgorithmistestedon45realisticandchallengingMOVRPTWbenchmarkinstancesfromreal-world.Experimentalresultsshowthattheproposedalgorithmcanobtainbettersolutionsthanthepreviousevolutionaryalgorithmbasedmulti-objectivealgorithmonnewMOVRPTWcases.Additionalresultson56Solomoninstancesshowthestabilityoftheproposedalgorithmacrossdatasets.IndexTerms—multi-objectiveoptimization,vehicleroutingproblemwithtimewindows,multi-objectivelocalsearch.I.INTRODUCTIONVEHICLEroutingproblem(VRP)isoneofthemostwidelystudiedcombinatorialoptimizationproblemsbe-causeextremelybroadrangeofproblemsinmanyapplicationfieldscanbeformulatedasVRP.Theseapplicationfieldsincludetransportation,supplychainmanagement,productionplanning,telecommunicationsandsoon[1],[2].VRPhasalotofvariantswithdifferentconstraints,suchas[3],[4].Detailscanbefoundintherecentreview[5].VRPwithtimewindows(VRPTW)isoneofthevariantsofVRPbyimposingtimewindowconstraintsoncustomers.ItisanimportantNP-hardproblemandparticularlyrelevanttopracticalapplication[6]–[8].VRPTWconsistsofasetofcustomerstobeservedandafleetofvehiclesdepartedfromacentraldepot.Eachcustomeristobeservedexactlyoncebyonlyonevehicle,eachvehiclehasalimitedcapacity,andeachcustomerisassociatedwithaspecificdeliverytimewindow.ThegoalofVRPTWistoManuscriptreceivedMar2,2013;revisedOct.7,2013;acceptedJanuary2,2014.DateofpublicationApril24,2014;dateofcurrentversionAugust21,2014.ThisworkissupportedbytheNationalNaturalScienceFoundationofChina(60805026,61070076,61033010),andtheZhujiangNewStarofScienceandTechnologyinGuangzhouCity(2011J2200093).Correspondingauthor:J.Wang.Y.Zhou,J.WangarewithDepartmentofComputerScience,SunYat-senUniversity,P.R.China(e-mail:[e-mail])createleastcostroutessatisfyingallconstrains.Costusuallymeansthenumberofroutes,totaltraveldistance,traveltime,etc.Costscanalsoincludetheservicepenaltiesincurredwhenacustomerreceivesalateorincompletedelivery[2].Inmostcases,severalcostsshouldbeoptimizedsimultaneously.VRPTWhasbeenthesubjectofintensiveresearcheffortsforexact,heuristicandmetaheuristicoptimizationapproaches[9].SinceVRPTWisNP-hard[10],exactmethods(seethemostrecentreview[11])areonlyapplicabletosmall-scaleprobleminstances.Metaheuristicalgorithmshaveshowntobeverysuccessfulinsolvinghardcombinatorialoptimizationproblemsinreasonablecomputationtime.Thus,alotofmetaheuristicapproacheshavebeensuccessfullyappliedtoVRPTW[12]–[23].Severalpreviousresearchesstudysingle-objectiveVRPTW.Forexample,simulatedannealing[12]andgeneticalgorithm[13]areproposedtoreducethetotaltraveldistanceasasoleobjective.ConsideringVRPTWwithmultipleobjec-tives(oftentwoobjectivesincludingthenumberofvehiclesandtotaldistance),mostpreviousstudiestransformittoasingle-objectiveoptimizationproblem,andthusadoptsingle-objectiveapproachestosolveitandreturnasinglesolutionfinally.Oneofthemostpopulartechniquesistousescalartechniques[14].In[14],asetbasedparticleswamoptimiza-tionisproposedtooptimizeaweightedlinearaggregationfunctionwiththeroutenumberandtotaldistance.However,thiskindoftechniquemustsettheweightsaccordingtotheimportanceoftheobjectives,whichisadifficulttask[2].Usingtwo-phasehybridtechniquesisanotherwaytodealwithVRPTW.Ahierarchicalorderingofobjectivesisconsidered,i.e.,thenumberofvehicleroutes,astheprimaryobjective,isfirstminimizedandthen,fixingthenumberofvehicles,thesecondaryobjective(traveldistance)isminimized.Thiskindofalgorithmsinclude[15]–[18].However,inthiskindofmethods,determiningtheimportanceofdifferentobjectivesisproblemdependent,andtheorderingoftheobjectivesmayaffecttheperformancesignificantly.DuetotheconstraintsandproblemstructureofVRPTW,theoptimizationofoneobjectivemayleadtothedeteriorationofotherobjectives,thusVRPTWisessentiallyamulti-objectiveoptimizationproblem(MOP).Sincedecisionmaker’sprefer-enceisnotknownapriori,multi-objectivefashionisnecessaryforVRPTWtoprovideasetofsolutionsthatrepresentthetradeoffsbetweenobjectives,ratherthanasinglesolution[19].However,onlyfewworksutilizethemulti-objectivemethodsforVRPTW.Thefeatureofmulti-objectivefashion2istoconsiderallobjectiveswiththesameimportanceandaset