您好,欢迎访问三七文档
1、ARoute-directedHybridGeneticApproachfortheVehicleRoutingProblemwithTimeWindowsJEANBERGER,MOHAMEDBARKAOUIDefenceResearchDevelopmentCanada-Valcartier,DecisionSupportTechnologySection2459Pie-XIBlvd.North,Val-Bélair,PQ,Canada,G3J1X5email:jean.berger@drdc-rddc.gc.ca,barkaoui@videotron.caOLLIBRÄYSYSINTEFAppliedMathematicsDepartmentofOptimisation,P.O.Box124Blindern,N-0314Oslo,Norway,email:olli.braysy@sintef.noAroute-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。
本文标题:A route-directed hybrid genetic approach for the v
链接地址:https://www.777doc.com/doc-3346163 .html