A route-directed hybrid genetic approach for the v

ARoute-directedHybridGeneticApproachfortheVehicleRoutingProblemwithTimeWindowsJEANBERGER,MOHAMEDBARKAOUIDefenceResearchDevelopmentCanada-Valcartier,DecisionSupportTechnologySection2459Pie-XIBlvd.North,Val-Bélair,PQ,Canada,G3J1X5email:[e-mail],[e-mail]ÄYSYSINTEFAppliedMathematicsDepartmentofOptimisation,P.O.Box124Blindern,N-0314Oslo,Norway,email:[e-mail]-directedhybridgeneticapproachtoaddresstheVehicleRoutingProblemwithTimeWindowsispresented.Theproposedschemereliesontheconceptofsimultaneousevolutionoftwopopulationspursuingdifferentobjectivessubjecttopartialconstraintrelaxation.Thefirstpopulationevolvesindividualstominimizetotaltraveleddistancewhilethesecondfocusesonminimizingtemporalconstraintviolationtogenerateafeasiblesolution,bothsubjecttoafixednumberoftours.Geneticoperatorshavebeendesignedtoincorporatekeyconceptsemergingfromrecentpromisingtechniquessuchasinsertionheuristicsandlargeneighborhoodsearchtofurtherexplorethesolutionspace.Resultsfromacomputationalexperimentovercommonbenchmarkproblemsshowthattheproposedtechniquematchesoroutperformssomeofthebestheuristicroutingprocedures,providingsixnewbest-knownsolutions.Incomparison,themethodprovedtobefast,cost-effectiveandhighlycompetitive.1.INTRODUCTIONVehicleroutingproblemsareimportantandwell-knowncombinatorialoptimizationproblemsoccurringinmanydistributionsystemswithconsiderableeconomicsignificance.Itisestimatedthatdistributioncostsaccountforalmosthalfofthetotallogisticscosts,andinsomeindustries,suchasinthefoodanddrinkbusiness,distributioncostscanaccountforupto70%ofthevalueaddedcostsofgoods(DeBackeretal.,1997;GoldenandWasil1987).Togetanimpressionofthemagnitudeofthe2freighttransportation,letusmentionthattheannualcostofexcesstravelintheUnitedStateshasbeenestimatedatsomeUSD45billion(KingandMast,1997).InEUtheannualturnoveroffreighttransportationisabout150billioneuros,andthereareabout500000companiesand13milliontrucks.Halse(1992)reportsthat76,5%ofallthetransportationofgoodsisdonebyvehiclesthatalsounderlinestheimportanceofvehicleroutingproblems.Ontheotherhand,ithasbeenestimatedthatthecapacityutilizationwithloadisonly60%,andthevehiclesdrive36%ofthetimeempty(Hasle,2002)indicatingasignificantpotentialforimprovement.TheVehicleRoutingProblemwithTimeWindows(VRPTW)hasreceivedalotofattentionintheliteraturerecently.Thisismostlyduetothewideapplicabilityoftimewindowconstraintsinreal-worldcases.InVRPTW,customerswithknowndemandsareservicedbyahomogeneousfleetofvehicleswithlimitedcapacity.Routesareassumedtostartandendatthecentraldepot.Eachcustomerprovidesatimeintervalduringwhichaparticulartaskmustbecompletedsuchasloading/unloadingthevehicle.Itisworthnoticingthatthetimewindowrequirementdoesnotpreventanyvehiclefromarrivingbeforetheallowedstartofserviceatacustomerlocation.Theobjectiveistominimizethenumberoftoursorroutes,andthenforthesamenumberoftours,tominimizethetotaltraveleddistance,suchthateachcustomerisservicedwithinitstimewindowandthetotalloadonanyvehicleassociatedwithagivenroutedoesnotexceedvehiclecapacity.AvarietyofalgorithmsincludingexactmethodsandefficientheuristicshavealreadybeenproposedforVRPTW.Forsurveysonexact,heuristicandmetaheuristicmethods,seeDesrosiersandal.(1995),Cordeauandal.(2001)andBräysyandGendreau(2001aand2001b)respectively.Inparticular,evolutionaryandgeneticalgorithmshavebeenamongthemostsuitableapproachestotackletheVRPTW,andareofparticularinteresttous.Geneticalgorithms(Holland,1975;DeJong,1975andGoldberg,1989)areadaptiveheuristicsearchmethodsthatmimicevolutionthroughnaturalselection.Theyworkbycombiningselection,recombinationandmutationoperations.Theselectionpressuredrivesthepopulationtowardbetter3solutionswhilerecombinationusesgenesofselectedparentstoproduceoffspringthatwillformthenextgeneration.Mutationisusedtoescapefromlocalminima.BlantonandWainwright(1993)werethefirsttoapplyageneticalgorithmtoVRPTW.Theyhybridizedageneticalgorithmwithagreedyheuristic.Underthisscheme,thegeneticalgorithmsearchesforagoodorderingofcustomers,whiletheconstructionofthefeasiblesolutionishandledbythegreedyheuristic.Thangiah(1995aand1995b)usesageneticalgorithmtofindgoodclustersofcustomerswithina“clusterfirst,routesecond”problem-solvingstrategy.Thangiahandal.(1995)testthesameapproachtosolvevehicleroutingproblemswithtimedeadlines.InthealgorithmproposedbyPotvinandBengio(1996),newoffspringarecreatedbyconnectingtworoutesegmentsfromtwoparentsolutionsorbyreplacingtherouteofthesecondparent-solutionbytherouteofthefirstparent-solution.Mutationisthenusedtoreducethenumberofroutesandtolocallyoptimizethesolution.Bergerandal.(1998)presentahybridgeneticalgorithmbasedonremovingcertaincustomersfromtheirroutesandthenreschedulingthemwithwell-knownroute-constructionheuristics.Themutationoperatorsareaimedatreducingthenumberofroutesbyreschedulingsomecustomersandatlocallyreorderingcustomers.Bräysy(1999a,1999b)continuesthestudyofBergerandal.(1998)byperformingacomprehensivesensitivityanalysis,andbycreatingnewcrossoverandmutationoperators.AlsoBergerandal