a hybrid mulitiobjective evolutionary algorithm fo

AHybridMultiobjectiveEvolutionaryAlgorithmforSolvingVehicleRoutingProblemwithTimeWindowsAbstract.Vehicleroutingproblemwithtimewindows(VRPTW)involvestheroutingofasetofvehicleswithlimitedcapacityfromacentraldepottoasetofcustomerswithknowndemandsandpredefinedtimewindows.Routesforthevehiclesmustmeetallgivenconstraintsaswellasminimizetheobjectivesoftraveldistanceandvehiclesnumbers.Weproposedhybridmultiobjectiveevolutionaryalgorithm(HMOEA)incorporatessimpleheuristicsforlocalexploitationandtheconceptofPareto'soptimalityforsolvingmultiobjectiveoptimizationinVRPTW.Itisfeaturedwithspecializedevolutionaryoperatorsandvariable-lengthchromosomerepresentationtoaccommodatethesequenceorientedoptimizationinVRPTW.TheHMOEAimprovestheroutingsolutionsinmanyaspects,suchaslowerroutingcost,betterpopulationdistribution,widerscatteringareaandgoodconvergencetrace.1IntroductionVehicleroutingproblemswithtimewindow(VRPTW)isanexampleofthepopularextensionfromVRP.InVRPTW,asetofvehicleswithlimitedcapacityistoberoutedfromacentraldepottoasetofgeographicallydispersedcustomerswithknowndemandsandpredefinedtimewindows.Avehiclearrivingearlierthantheearliestservicetimeofanodewillincurwaitingtime.Thispenalizesthetransportmanagementeitherinthedirectwaitingcostortheincreasednumberofvehicleduetothefactthatavehiclewillservicefewernodeswhenwaitingtimeislonger.Duetoitsinherentcomplexitiesandusefulnessinreallife,theVRPTWcontinuestodrawattentionsfromresearchersandhasbecomeawell-knownprobleminnetworkoptimization.SurveysaboutVRPTWcanbefoundin[1][2][3],etc.ManyheuristicapproachesandexactmethodshavebeenappliedtotheproblemofVRPTW[1][4][5][6][7].Usingexactmethods,thecomputationtimerequiredtoobtainsuchsolutionsisprohibitiveiftheproblemsizegrowslarge.Someheuristicapproachesarelackingofrobustnessorsensitivetodatasetsgiven.Evolutionaryalgorithm(EA)thatemulatestheDarwinian-Wallaceprincipleof“survival-of-the-fittest”innaturalselectionandgeneticshavebeenappliedtoproducenear-optimalsolutionsforVRPTW[8][9][10].Prinettoetal.[11]proposedahybridgeneticalgorithmfortravelingsalesmanproblem,inwhich2-optandOr-optwereincorporatedwiththegeneticalgorithm.BlantonandWainwright[12]presentedtwonewcrossoveroperators,MergeCross#1andMergeCross#2,andshowedthatthenewoperatorsaresuperiortotraditionalcrossoveroperators.HombergerandGehring[9]proposedtheapproachofsub-dividingtheoptimizationproblemintophasesbasedontheoptimizationobjectivesinVRPTW.Intheirapproach,theoptimizationwasperformedintwoindependentevolutionphasesfordifferentobjectives.VRPTWinvolvestheroutingoptimizationformultiplevehiclessoastomeetallgivenconstraints.Itminimizesmultipleobjectivessuchasthetraveldistanceandnumberofvehiclesconcurrently,whichhasmadeitbestsolvedbymultiobjectiveoptimizationapproaches.Mostoftheexistingroutingtechniques,however,aresingleobjectiveoptimizationbasedapproacheswhichapplythemethodofpenaltyfunctionorcombinethedifferentcriteriaviaaweightingfunction.Suchmethodsoftenrequireasetofprecisesettingsofweights,whichareusuallynotmanageablenorunderstood.Thispaperthusproposesahybridmultiobjectiveevolutionaryalgorithm(HMOEA)thatincorporatessimpleheuristicsforlocalexploitationandtheconceptofPareto'soptimalityforsolvingmultiobjectiveoptimizationinVRPTW.Itisfeaturedwithmodifiedevolutionaryoperatorsandvariablelengthchromosomerepresentation.ThedesignofthealgorithmhasitsfocusontheneedofVRPTWthatintegratesvehicleroutingsequencewiththeconsiderationsoftimings,costs,andvehiclenumbers.Withoutaggregatingmultiplecriteriaintoacompromisefunction,theHMOEAoptimizesallroutingconstraintsandobjectivesconcurrently,whichgreatlyimprovestheroutingsolutionsinmanyaspects,suchaslowerroutingcost,betterpopulationdistribution,widerscatteringarea,andgoodconvergencetrace.Thispaperisorganizedasfollows:Section2givesthebriefproblemmodelandthetestproblemsforVRPTW.TheprogramflowchartofHMOEAisdescribedindetailedinSection3.Section4presentstheextensivesimulationsandcomparisonresultsofHMOEAbasedupontheSolomon’s56datasets.ConclusionsaredrawninSection5.2ProblemFormulationVehicleroutingproblemwithtimewindows(VRPTW)involvestheroutingofasetofvehicleswithlimitedcapacityfromacentraldepottoasetofgeographicallydispersedcustomerswithknowndemandsandpredefinedtimewindows.Arouteforvehicleisdescribedbythesequenceofcustomersthatthevehiclearegoingtovisit.Timewindow(theearliestservicetimeandlatestservicetime)aregivenforeverycustomersite.Vehiclemustarrivebeforeorwithinthetimewindowofeachcustomer.Vehiclethatarrivesearliermustwaituntilearliestservicetimestarts.Fig.1showsagraphicalmodelofVRPTWanditssolution.Thissimpleexamplehastworoutes,R1andR2,andeverycustomerisgivenanumberasitsidentity.Thearrowsconnectingthecustomersshowthesequencesofvehiclevisit,whereeveryroutemuststartandendatthedepot.Travelcostbetweencustomersiandjisdenotedbycij.Thecostiscalculatedwiththefollowingequation:()()22yyxxijjijic-+-=(1)whereixisthecoordinatexforcustomeri;andiyisthecoordinateyforcustomeri..Fig.1.ExamplesolutionforroutingplanThemathematicalmodelforVRPTWcanbefoundinSolomon[3]wheresixbenchmarkproblems