MACS-VRPTW A Multiple Ant Colony System for Vehicl

1MACS-VRPTW:AMULTIPLEANTCOLONYSYSTEMFORVEHICLEROUTINGPROBLEMSWITHTIMEWINDOWSLucaMariaGambardella,ÉricTaillardandGiovanniAgazziIDSIA,CorsoElvezia36,6900Lugano,SwitzerlandTel+41919119838Fax[phone]email:{luca,eric,agazzi}@idsia.ch.:thefirstcolonyminimizesthenumberofvehicleswhilethesecondcolonyminimizesthetraveleddistances.Cooperationbetweencoloniesisperformedbyexchanginginformationthroughpheromoneupdating.WeshowthatMACS-VRPTWiscompetitivewiththebestknownexistingmethodsbothintermsofsolutionqualityandcomputationtime.Moreover,MACS-VRPTWimprovessomeofthebestsolutionsknownforanumberofprobleminstancesintheliterature.2Chapter5MACS-VRPTW:AMULTIPLEANTCOLONYSYSTEMFORVEHICLEROUTINGPROBLEMSWITHTIMEWINDOWS5.1.IntroductionThischapterpresentsMACS-VRPTW,aMultipleAntColonySystemforVehicleRoutingProblemswithTimeWindows.MACS-VRPTWisbasedonAntColonySystem(ACS)(GambardellaandDorigo,1996,DorigoandGambardella,1997a,1997b),and,moregenerally,onAntColonyOptimization(ACO),anewmetaheuristicapproachinspiredbytheforagingbehaviorofrealcoloniesofants.ThebasicACOidea(seeChapter2inthisbookand(Dorigo,DiCaroandGambardella,1998)foradetaileddescriptionoftheACOmetaheuristic)isthatalargenumberofsimpleartificialagentsareabletobuildgoodsolutionstohardcombinatorialoptimizationproblemsvialow-levelbasedcommunications.Realantscooperateintheirsearchforfoodbydepositingchemicaltraces(pheromones)onthefloor.Anartificialantcolonysimulatesthisbehavior(Dorigo,ManiezzoandColorni,1991,1996).Artificialantscooperatebyusingacommonmemorythatcorrespondstothepheromonedepositedbyrealants.Thisartificialpheromoneisoneofthemostimportantcomponentsofantcolonyoptimizationandisusedforconstructingnewsolutions.IntheACOmetaheuristic,artificialpheromoneisaccumulatedatrun-timeduringthecomputation.Artificialantsareimplementedasparallelprocesseswhoseroleistobuildproblemsolutionsusingaconstructiveproceduredrivenbyacombinationofartificialpheromone,problemdataandaheuristicfunctionusedtoevaluatesuccessiveconstructivesteps.Recently,manyACOalgorithmshavebeenproposedtosolvedifferenttypesofcombinatorialoptimizationproblems.Inparticular,ACOalgorithmshavebeenshowntobeveryefficientwhencombinedwithspecializedlocalsearchprocedurestosolvethesymmetricandasymmetrictravelingsalesmanproblems(TSP/ATSP,DorigoandGambardella,1997a,1997b,Stützle,1998,StützleandDorigo,1999),thesequentialorderingproblem(SOP,GambardellaandDorigo,1997),thequadraticassignmentproblem(QAP,Gambardella,TaillardandDorigo,1999,TaillardandGambardella,1997),thebi-quadraticassignmentproblemandthep-medianproblem(Taillard,1998).OneofthemostefficientACObasedimplementationshasbeenAntColonySystem(ACS),(GambardellaandDorigo,1996,DorigoandGambardella,1997a,1997b)thatintroducedaparticularpheromonetrailupdatingprocedureusefultointensifythesearchintheneighborhoodofthebestcomputedsolution.ThischapterpresentsanACSextensionabletosolvethevehicleroutingproblemwithtimewindows(VRPTW).VRPTWisdefinedastheproblemofminimizingtimeandcostsincaseafleetofvehicleshastodistributegoodsfromadepottoasetofcustomers.TheVRPTWconsideredinthischapterminimizesamultiple,hierarchicalobjectivefunction:thefirstobjectiveistominimizethenumberoftours(orvehicles)andthesecondistominimizethetotaltraveltime.Asolutionwithalowernumberoftoursisalwayspreferredtoasolutionwith3ahighernumberoftoursevenifthetraveltimeishigher.ThishierarchicalobjectivesVRPTWisverycommonintheliteratureandincaseproblemconstraintsareverytight(forexamplewhenthetotalcapacityoftheminimumnumberofvehiclesisveryclosetothetotalvolumetodeliverorwhencustomerstimewindowsarenarrow),bothobjectivescanbeantagonistic:theminimumtraveltimesolutioncanincludeanumberofvehicleshigherthanthesolutionwithminimumnumberofvehicles(seee.g.Kohletal.,1997).ToadaptACSforthesemultipleobjectivestheideaistodefinetwoACScolonies,eachdedicatedtotheoptimizationofadifferentobjectivefunction.InMACS-VRPTWthecoloniescooperatebyexchanginginformationthroughpheromoneupdating.MACS-VRPTWisshowntobecompetitivewiththebestexistingmethodsbothintermsofsolutionqualityandcomputationtime.Moreover,MACS-VRPTWimprovesthebestsolutionsknownforsomeprobleminstancesoftheliterature.Thischapterisorganizedasfollows:First,vehicleroutingproblemsareintroducedbypresentingaformaldefinitionofthecapacitatedvehicleroutingproblem(CVRP)andthevehicleroutingproblemwithtimewindows(VRPTW).Second,ACSmaincharacteristicsareanalyzedbyexplaininghowACShasbeenappliedtothetravelingsalesmanproblem(TSP).Then,ACSisextendedtodealwithVRPTWandtheresultingMACS-VRPTWisinvestigatedbypresentingitsmaincomponents.Last,numericalresultsarereportedandsomeconclusionsaredrawn.5.2VehicleRoutingProblemsThemostelementaryversionofthevehicleroutingproblemisthecapacitatedvehicler