A hybridevolutionstrategyfortheopenvehicleroutingproblem

This paperpresentsahybridevolutionstrategy(ES)forsolvingtheopenvehicleroutingproblem(OVRP), which isawell-knowncombinatorialoptimizationproblemthataddressestheserviceofasetofcustomers using ahomogeneousfleetofnon-depotreturningcapacitatedvehicles.Theobjectiveistominimizethe fleet sizeandthedistancetraveled.Theproposedsolutionmethodmanipulatesapopulationof individuals usinga( + )-ES; ateachgeneration,anewintermediatepopulationof offspring isproducedvia mutation, usingarcsextractedfromparentindividuals.Theselectionandcombinationofarcsisdictated by avectorofstrategyparameters.Amulti-parentrecombinationoperatorenablestheself-adaptationof the mutationratesbasedonthefrequencyofappearanceofeacharcandthediversityofthepopulation. Finally, eachnewoffspringisfurtherimprovedviaamemory-basedtrajectorylocalsearchalgorithm,while an elitistschemeguidestheselectionofsurvivors.Experimentalresultsonwell-knownbenchmarkdata sets demonstratethecompetitivenessoftheproposedpopulation-basedhybridmetaheuristicalgorithm.