A SWEEP BASED HEURISTIC FOR THE FLEET SIZE AND MIX

ASWEEPBASEDALGORITHMFORTHEFLEETSIZEANDMIXVEHICLEROUTINGPROBLEMJacquesRenaudandFayezF.BoctorCentrederecherchesurlestechnologiesdel’organisationréseau(CENTOR)&Facultédessciencesdel’administration,UniversitéLaval,Sainte-Foy,Canada,G1K7P4Email:jrenaud@[e-mail]@fsa.ulaval.caMay2001ASWEEPBASEDHEURISTICFORTHEFLEETSIZEANDMIXVEHICLEROUTINGPROBLEMAbstractThispaperpresentsanewsweepbasedheuristicforthefleetsizeandmixvehicleroutingproblem.Thisprobleminvolvestwokindsofdecisions:theselectionofamixofvehiclesamongtheavailablevehicletypesandtheroutingoftheselectedfleet.Theproposedalgorithmfirstgeneratesalargenumberofroutesthatareservicedbyoneortwovehicles.Theselectionofroutesandvehiclestobeusedisthenmadebysolvingtooptimality,inpolynomialtime,aset-partitioningproblemhavingaspecialstructure.Resultsonasetofbenchmarktestproblemsshowthattheproposedheuristicproducesexcellentsolutionsinshortcomputingtimes.Havingafastbutgoodsolutionmethodisneededfortransportationcompaniesthatrentasignificantpartoftheirfleetandconsequentlycantakeadvantageoffrequentchangesinfleetcomposition.Finally,theproposedheuristicproducednewbest-knownsolutionsforthreeofthetestproblems;thesesolutionsarereported.Keywords:Vehicleroutingproblem,fleetselection,sweepbasedheuristic11.IntroductionThefleetsizeandmixvehicleroutingproblem(FSMVRP),alsocalledvehiclefleetmixproblemorfleetsizeandcompositionvehicleroutingproblem(Taillard1999),involvestwobasicdecisions:thecompositionofaheterogeneousvehiclefleetandtheroutingofthisfleet.Thevehiclefleetcanbecomposedofvehicleshavingdifferentcapacitiesaswellasdifferentfixedandvariablecosts.Theobjectiveistominimizethetotalcost,whichiscomposedofvehiclefixedutilizationcostsandofvariabletravelingcosts.Thisobjectivecanbeachievedbyfindingtheoptimalmixofvehiclesandbydeterminingtheassociatedrouteswhilesatisfyingtheproblemconstraints.Mathematically,theproblemmaybedefinedasfollows.LetG=(V,A)beagraphwhereV={v0,...,vn}isthevertexsetandA={(vi,vj):vi,vj∈V,i≠j}isthearcset.Vertexv0representsadepotwhereMdifferentvehicletypesarebased.Eachvertexvi∈V\{v0}correspondstoacustomerandisassociatedwithanon-negativedemandqiandaservicetimesi.Intheversionoftheproblemunderconsideration,allarcsareundirected,i.e.theyareedges.Eachedge(vi,vj)isassociatedwithanon-negativecost,cij,representingitstravelcostandanon-negativetime,tij,representingitstraveltime.Inaddition,Fk,QkandTkrepresentrespectivelythevehiclefixedcost,thevehiclecapacityandthemaximumtraveltimeforvehicletypek=1,...,M.Weassumethat1kF2kFimplies1kQ2kQ,thatvehicletypesarenumberedinascendingorderofFkandthatwecanuseanynumberofvehiclesoftypek.TheFSMVRPistodetermineamixofvehiclesaswellastheirroutessuchthat:(1)routesstartandendatthedepot;(2)eachcustomerisvisitedexactlyonce;(3)thetotaldemandofaroutedoesnotexceedthecapacityofthevehicletypeused;(4)thetotaldurationofeachroute(includingtravelandservicetimes)doesnotexceedthemaximaltravelingtimeTkofthevehicletypeused;and(5)thesumoffixedandvariablecostsareminimized.2Inthispaperweproposeanewsweepbasedheuristicthathasproducedhighlycompetitiveresultsonasetofbenchmarkproblems.ThiscompositeheuristiccansolvebothEuclideanplanarproblemsandnonEuclideanproblemsaswell,whichisnotthecaseofsomeoftherecentlypublishedheuristics.Inaddition,theproposedheuristicproducesbetterresultsthancomparablecompositeheuristicsandresultsveryclosetothoseobtainedbythebest-published,Tabu-basedheuristicalgorithms.Theremainderofthispaperisorganizedasfollows.InSection2,wereviewthemainalgorithmsfortheFSMVRP.OurheuristicisdescribedinSection3,followedbyourcomputationalresultsinSection4andconclusionsinSection5.2.LiteraturereviewTheFSMVRPisclearlyNP-hardasitreducestothevehicleroutingproblem(VRP)whenM=1.Thislatterproblemhasgeneratedaconsiderableamountofresearchoverthelastthreedecades(seethereviewbyLaporte(1992b)andthebibliographybyLaporteandOsman(1995)).ThebestexistingoptimalalgorithmsfortheVRPappeartobethoseofCornuéjolsandHarche(1993),andofHadjiconstantinou,ChristofidesandMingozzi(1995),andcanrarelysolveprobleminstancesinvolvingmorethan50customers.ThebestheuristicsfortheVRPappeartobethetabusearchbasedalgorithmsofTaillard(1993),Osman(1993)andGendreau,HertzandLaporte(1994),andtheimprovedpetalheuristicofRenaud,BoctorandLaporte(1996a).Inspiteofitspracticalimportance,theFSMVRPhasattractedlessresearcheffort.Gould(1969)developedalinearprogramforaproblemversionwhereonlyroundtripsbetweenthedepotandeachcustomerareconsidered.WoodsandHarris(1979)alsoaddressedthisproblembyusingasimulationapproach.EtezadiandBeasley(1983)presentedaformulationwherevehiclesmayvisit3manycustomers.Golden,Assad,LevyandGheysens(1984)presentedamathematicalformulationoftheFSMVRP.Becauseofitscomplexity,theresearcheffortdealingwiththeFSMVRPhasfocusedonheuristics.OneofthemostimportantcontributionstothisfieldisthatofGolden,Assad,LevyandGheysens(1984)whosuggestedfiveadaptationsofClarkeandWright’s(1964)savingsalgorithm.Thefirstone,denotedCW,isastraightforwardadaptationoftheoriginalalgorithmtotheFSMVRP.Thesecond,calledcombinedsavings,orCS,