A route-directed hybrid genetic approach for the v

1、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]-directedhybridgeneticapproachtoaddresstheVehicleRoutingProblemwithTimeWindowsispresent。

2、ed.Theproposedschemereliesontheconceptofsimultaneousevolutionoftwopopulationspursuingdifferentobjectivessubjecttopartialconstraintrelaxation.Thefirstpopulationevolvesindividualstominimizetotaltraveleddistancewhilethesecondfocusesonminimizingtemporalconstraintviolationtogenerateafeasiblesolution,bothsubjecttoafixednumberoftours.Geneticoperatorshavebeendesignedtoincorporatekeyconceptsemergingfromrecentpromisingtechniquessuchasinsertionheuristicsandlargeneighborhoodsearchtofurtherexplorethesolution。

3、space.Resultsfromacomputationalexperimentovercommonbenchmarkproblemsshowthattheproposedtechniquematchesoroutperformssomeofthebestheuristicroutingprocedures,providingsixnewbest-knownsolutions.Incomparison,themethodprovedtobefast,cost-effectiveandhighlycompetitive.1.INTRODUCTIONVehicleroutingproblemsareimportantandwell-knowncombinatorialoptimizationproblemsoccurringinmanydistributionsystemswithconsiderableeconomicsignificance.Itisestimatedthatdistributioncostsaccountforalmosthalfofthetotallogistic。

4、scosts,andinsomeindustries,suchasinthefoodanddrinkbusiness,distributioncostscanaccountforupto70%ofthevalueaddedcostsofgoods(DeBackeretal.,1997;GoldenandWasil1987).Togetanimpressionofthemagnitudeofthe2freighttransportation,letusmentionthattheannualcostofexcesstravelintheUnitedStateshasbeenestimatedatsomeUSD45billion(KingandMast,1997).InEUtheannualturnoveroffreighttransportationisabout150billioneuros,andthereareabout500000companiesand13milliontrucks.Halse(1992)reportsthat76,5%ofallthetransportatio。

5、nofgoodsisdonebyvehiclesthatalsounderlinestheimportanceofvehicleroutingproblems.Ontheotherhand,ithasbeenestimatedthatthecapacityutilizationwithloadisonly60%,andthevehiclesdrive36%ofthetimeempty(Hasle,2002)indicatingasignificantpotentialforimprovement.TheVehicleRoutingProblemwithTimeWindows(VRPTW)hasreceivedalotofattentionintheliteraturerecently.Thisismostlyduetothewideapplicabilityoftimewindowconstraintsinreal-worldcases.InVRPTW,customerswithknowndemandsareservicedbyahomogeneousfleetofvehicleswi。

6、thlimitedcapacity.Routesareassumedtostartandendatthecentraldepot.Eachcustomerprovidesatimeintervalduringwhichaparticulartaskmustbecompletedsuchasloading/unloadingthevehicle.Itisworthnoticingthatthetimewindowrequirementdoesnotpreventanyvehiclefromarrivingbeforetheallowedstartofserviceatacustomerlocation.Theobjectiveistominimizethenumberoftoursorroutes,andthenforthesamenumberoftours,tominimizethetotaltraveleddistance,suchthateachcustomerisservicedwithinitstimewindowandthetotalloadonanyvehicleassoc。

7、iatedwithagivenroutedoesnotexceedvehiclecapacity.AvarietyofalgorithmsincludingexactmethodsandefficientheuristicshavealreadybeenproposedforVRPTW.Forsurveysonexact,heuristicandmetaheuristicmethods,seeDesrosiersandal.(1995),Cordeauandal.(2001)andBräysyandGendreau(2001aand2001b)respectively.Inparticular,evolutionaryandgeneticalgorithmshavebeenamongthemostsuitableapproachestotackletheVRPTW,andareofparticularinteresttous.Geneticalgorithms(Holland,1975;DeJong,1975andGoldberg,1989)areadaptiveheuristicse。

8、archmethodsthatmimicevolutionthroughnaturalselection.Theyworkbycombiningselection,recombinationandmutationoperations.Theselectionpressuredrivesthepopulationtowardbetter3solutionswhilerecombinationusesgenesofselectedparentstoproduceoffspringthatwillformthenextgeneration.Mutationisusedtoescapefromlocalminima.BlantonandWainwright(1993)werethefirsttoapplyageneticalgorithmtoVRPTW.Theyhybridizedageneticalgorithmwithagreedyheuristic.Underthisscheme,thegeneticalgorithmsearchesforagoodorderingofcustomers。

9、,whiletheconstructionofthefeasiblesolutionishandledbythegreedyheuristic.Thangiah(1995aand1995b)usesageneticalgorithmtofindgoodclustersofcustomerswithina“clusterfirst,routesecond”problem-solvingstrategy.Thangiahandal.(1995)testthesameapproachtosolvevehicleroutingproblemswithtimedeadlines.InthealgorithmproposedbyPotvinandBengio(1996),newoffspringarecreatedbyconnectingtworoutesegmentsfromtwoparentsolutionsorbyreplacingtherouteofthesecondparent-solutionbytherouteofthefirstparent-solution.Mutationist。

10、henusedtoreducethenumberofroutesandtolocallyoptimizethesolution.Bergerandal.(1998)presentahybridgeneticalgorithmbasedonremovingcertaincustomersfromtheirroutesandthenreschedulingthemwithwell-knownroute-constructionheuristics.Themutationoperatorsareaimedatreducingthenumberofroutesbyreschedulingsomecustomersandatlocallyreorderingcustomers.Bräysy(1999a,1999b)continuesthestudyofBergerandal.(1998)byperformingacomprehensivesensitivityanalysis,andbycreatingnewcrossoverandmutationoperators.AlsoBergerandal。