Multiobjective Capacitated Arc Routing Problem

MultiobjectiveCapacitatedArcRoutingProblemP.Lacomme1,C.Prins2,andM.Sevaux31Universit¶eBlaisePascalCNRS,UMR6158-LIMOS/Laboratoired'InformatiqueCampusUniversitairedesC¶ezeaux-BP10125-F-63177AubiµereCedex,[e-mail]2Universit¶edeTechnologiedeTroyesLaboratoired'OptimisationdesSystµemes[e-mail]3Universit¶edeValenciennesCNRS,UMR8530-LAMIH/Systµem[e-mail]Problem(CARP)isaveryhardvehicleroutingproblemraisedforinstancebyurbanwastecollec-tion.Inadditiontothetotalroutelength(theonlycriterionminimizedintheacademicproblem),wastemanagementcompaniesseektominimizealsothelengthofthelongesttrip.Inthispaper,abi-objectivegeneticalgorithmispresentedforthismorerealisticCARP,neverstudiedbeforeinliterature.BasedontheNSGA-IItemplate,itincludestwo-keyfea-tures:useofgoodconstructiveheuristicstoseedtheinitialpopulationandhybridizationwithapowerfullocalsearchprocedure.Thisgeneticalgorithmisappraisedon23classicalCARPinstances,withexcellentresults.Forinstance,foramajorityofinstances,itse±cientsolutionsincludeanoptimalsolutiontotheacademicCARP(minimizationofthetotalroutelength).1Introduction:theCARPanditsApplicationsTheCapacitatedArcRoutingProblem(CARP)isde¯nedintheliteratureonanundirectedgraphG=(V;A)withasetVofnnodesandasetAofmedges.A°eetofidenticalvehiclesofcapacityWisbasedatadepotnodes.AsubsetRofedgesrequireservicebyavehicle.Alledgescanbetraversedanynumberoftimes.Eachedge(i;j)hasatraversalcostcijandademandqij.Thegoalistodetermineasetofvehicletrips(routes)ofminimumtotalcost,suchthateachtripstartsandendsatthedepot,eachrequirededgeisservicedbyonesingletrip,andthetotaldemandhandledbyanyvehicledoesnotexceedW.SincetheCARPisNP-hard,largescaleinstancesmustbesolvedinprac-ticewithheuristics.Amongfastconstructivemethods,onecanciteforinstancePath-Scanning[10],Augment-Merge[11]andUlusoy'ssplittingtechnique[19].Metaheuristicsavailableincludetabusearchmethods[2,12]andthememeticalgorithmofLacomme,PrinsandRamdane-Ch¶erif[14],whichiscurrentlythemoste±cientsolutionmethod.Alltheseheuristicalgorithmscanbeevaluatedthankstoverygoodlowerbounds[1,3].CARPproblemsareraisedbyoperationsonstreetnetworks,e.g.urbanwastecollection,snowplowing,sweeping,gritting,etc.Economicallyspeaking,themostimportantapplicationcertainlyismunicipalrefusecollection.Inthatcase,nodesinGcorrespondtocrossroads,whileedgesinAmodelstreetsegmentslinkingcrossroads.Thedemandsareamountsofwastetobecollected.Thecostoneachedgeisgenerallyatime.TheacademicCARPdealswithonlyoneobjective,minimizingthetotaldurationofthetrips.Infact,wastemanagementcompaniesarealsointerestedinbalancingthetrips.Forinstance,inTroyes(France),alltrucksleavethedepotat6a.m.andwastecollectionmustbe¯nishedassoonaspossibletoassignthecrewstoothertasks,e.g.sortingthewasteatarecyclingfacility.So,thecompanywishestosolveinfactabi-objectiveversionoftheCARP,inwhichboththetotaldurationofthetripsandthedurationofthelongesttrip(makespan)aretobeminimized.Inthelastdecade,therehasbeenagrowinginterestinmulti-objectivevehicleroutingproblems,butallpublishedpapersdealwithnoderoutingproblems,i.e.,inwhichthetaskstobeperformedarelocatedonthenodesofanetwork[16,5,13,18].Thispaperisthe¯rststudydevotedtoanarcroutingproblemwithmultipleobjectives.Theremainderofthepaperisorganizedasfollows.Section2recallssomede¯nitionsonmulti-objectiveoptimisation.Section3introducestheNSGA-IItemplateandourspeci¯ccomponents,whilenumericalexperimentsarecon-ductedinSection4.ConclusionisdrawninSection5.2Multi-objectiveOptimisationThegrowinginterestinmulti-objectiveoptimisationresultsfromthenumerousindustrialapplicationswheresolvingasingleobjectiveoptimisationproblemisanabusivesimpli¯cation.Insuchcases,computinganoptimalsolutionforoneobjectiveresultsinpoorvaluesforothercriteria.Hence,developingsomealgo-rithmsgivingacompromisebetweenseveralcriteriaisbettersuitedtoindustrialreality.Multi-objectiveproblemsincombinatorialoptimizationareoftenveryhardtosolve:eventheirsingle-objectiveversionsaregenerallyNP-hard.Thisiswhylotsofpapershavebeenrecentlypublishedonevolutionarytechniquesthatareabletohandleseveralobjectivesatatimeandgivee±cientsolutionsbythemeanofanevolvingpopulation.Foranextensiveinformationonmulti-objectiveoptimisationsee[4].Arecentsurveyandannotatedbibliography[9]canhelpfor¯ndingthebestsuitablemethodtotackleamulti-objectiveoptimisationproblem(seealso[6,7]).Amulti-objectiveoptimisationproblem(MOOP)canbeformulatedasfol-lows:minimizeff1(x);f2(x);:::;fnc(x)gsubjecttox2S(1)wherencisthenumberofcriteria,x=(x1;x2;:::;xnv)TavectorofnvdecisionvariablesandSasetoffeasiblesolutions.De¯nition1.Asolutionxdominatesasolutiony,xÂyifxisatleastasgoodasyforeachobjective:8k2[1;:::;nc];fk(x)·fk(y)andxisbetterthanyforatleastoneciterion:9k2[1;:::;nc];fk(x)fk(y).Accordingtothisde¯nition,xisnon-dominatedifthereisnosolutionythatdominatesx.ThesetPofallnon-dominatedsolutioniscallednon-dominatedsetore±cientset(E)orpareto-opti