Chapter6
VehicleRouting
Jean-FrançoisCordeau
CanadaResearchChairinLogisticsandTransportation,HECMontréal,3000chemindelaCôte-Sainte-Catherine,Montréal,H3T2A7,CanadaE-mail:Jean-Francois.Cordeau@hec.ca
GilbertLaporte
CanadaResearchChairinDistributionManagement,HECMontréal,3000chemindelaCôte-Sainte-Catherine,Montréal,H3T2A7,CanadaE-mail:gilbert@crt.umontreal.ca
MartinW.P.Savelsbergh
SchoolofIndustrialandSystemsEngineering,GeorgiaInstituteofTechnology,Atlanta,GA30332-0205,USAE-mail:mwps@isye.gatech.edu
DanieleVigo
DipartimentodiElettronica,InformaticaeSistemistica,UniversityofBologna,VialeRisorgimento2,40136Bologna,ItalyE-mail:dvigo@deis.umibo.it
1Introduction
Thevehicleroutingproblemliesattheheartofdistributionmanagement.Itisfacedeachdaybythousandsofcompaniesandorganizationsengagedinthedeliveryandcollectionofgoodsorpeople.Becauseconditionsvaryfromonesettingtothenext,theobjectivesandconstraintsencounteredinpracticearehighlyvariable.Mostalgorithmicresearchandsoftwaredevelopmentinthisareafocusonalimitednumberofprototypeproblems.Bybuildingenoughflexibilityinoptimizationsystemsonecanadaptthesetovariouspracticalcon-texts.
Muchprogresshasbeenmadesincethepublicationofthefirstarticleonthe“truckdispatching”problembyDantzigandRamser(1959).Severalvari-antsofthebasicproblemhavebeenputforward.Strongformulationshavebeenproposed,togetherwithpolyhedralstudiesandexactdecompositional-gorithms.Numerousheuristicshavealsobeendevelopedforvehicleroutingproblems.Inparticularthestudyofthisclassofproblemshasstimulatedtheemergenceandthegrowthofseveralmetaheuristicswhoseperformanceisconstantlyimproving.
Thischapterfocusesonsomeofthemostimportantvehicleroutingprob-lemtypes.Anumberofothervariantshavebeentreatedinrecentarticlesand
367
368J.-F.Cordeauetal.
bookchapters(see,e.g.,TothandVigo,2002a).Thepickupanddeliveryvehi-cleroutingproblem,whichhasalsobeenextensivelystudied,iscoveredinthe“TransportationonDemand”chapter.
Theremainderofthischapterisorganizedasfollows.Section2isdevotedtotheclassicalvehicleroutingproblem(simplyreferredtoasVRP),definedwithasingledepotandonlycapacityandroutelengthconstraints.ProblemswithtimewindowsaresurveyedinSection3.Section4isdevotedtoinventoryrout-ingproblemswhichcombineroutingandcustomerreplenishmentdecisions.Finally,Section5coversthefieldofstochasticvehicleroutinginwhichsomeoftheproblemdataarerandomvariables.2Theclassicalvehicleroutingproblem
TheClassicalVehicleRoutingProblem(VRP)isoneofthemostpopularproblemsincombinatorialoptimization,anditsstudyhasgivenrisetoseveralexactandheuristicsolutiontechniquesofgeneralapplicability.ItgeneralizestheTravelingSalesmanProblem(TSP)andisthereforeNP-hard.Arecentsur-veyoftheVRPcanbefoundinthefirstsixchaptersofthebookeditedbyTothandVigo(2002a).TheaimofthissectionistoprovideacomprehensiveoverviewoftheavailableexactandheuristicalgorithmsfortheVRP,mostofwhichhavealsobeenadaptedtosolveothervariants,aswillbeshownintheremainingsections.
TheVRPisoftendefinedundercapacityandroutelengthrestrictions.WhenonlycapacityconstraintsarepresenttheproblemisdenotedasCVRP.Mostexactalgorithmshavebeendevelopedwithcapacityconstraintsinmindbutseveralapplymutatismutandistodistanceconstrainedproblems.Incon-trast,mostheuristicsexplicitlyconsiderbothtypesofconstraint.2.1Formulations
ThesymmetricVRPisdefinedonacompleteundirectedgraphG=(VE).ThesetV={0n}isavertexset.Eachvertexi∈V\\{0}representsacus-tomerhavinganonnegativedemandqi,whilevertex0correspondstoadepot.Toeachedgee∈E={(ij):ij∈Vi ij∈Vi=j}isanarcset.Inthiscaseacircuit(directedcycle)isassociatedwithavehicleroute.MostresultsofSections2.1and2.2applytothesymmetricCVRP. AnintegerlinearprogrammingformulationoftheCVRPfollows,whereforeachedgee∈Etheintegervariablexeindicatesthenumberoftimesedgeeistraversedinthesolution.Letr(S)denotetheminimumnumberofvehiclesneededtoservethecustomersofasubsetSofcustomers.Thevalueofr(S)maybedeterminedbysolvinganassociatedBinPackingProblem(BPP)withitemsetSandbinsofcapacityQ.Finally,forS⊂V,letδ(S)={(ij):i∈Sj∈/Sori∈/Sj∈S}.IfS={i},thenwesimplywriteδ(i)insteadofδ({i}).TheCVRPformulationproposedbyLaporteetal.(1985)isthen: (CVRP1) minimize e∈E cexe(1) subjectto xe=2 e∈δ(i) i∈V\\{0} (2)(3) xe=2mxe2r(S) S⊆V\\{0}S=∅ e∈δ(0) (4)(5)(6) e∈δ(S) xe∈{01}xe∈{012} e∈/δ(0)e∈δ(0) Thedegreeconstraints(2)statethateachcustomerisvisitedexactlyonce, whereasthedepotdegreeconstraint(3)meansthatmroutesarecreated.Capacityconstraints(4)imposeboththeconnectivityofthesolutionandthevehiclecapacityrequirementsbyforcingasufficientnumberofedgestoentereachsubsetofvertices.WenotethatsincetheBPPisNP-hardinthestrongsense,r(S)maybeapproximatedfrombelowbyanyBPPlowerbound,suchasi∈Sqi/Q.Finally,constraints(5)and(6)imposethateachedgebetweentwocustomersistraversedatmostonceandeachedgeincidenttothedepotistraversedatmosttwice.Inthislattercase,thevehicleperformsaroutevisitingasinglecustomer. Awidelyusedalternativeformulationisbasedonthesetpartitioningorsetcoveringmodels.TheformulationwasoriginallyproposedbyBalinskiandQuandt(1964)andcontainsapotentiallyexponentialnumberofbinaryvari-ables.LetR={R1Rs}denotethecollectionofallfeasibleroutes,withs=|R|.EachrouteRjhasanassociatedcostγj,andaijisabinarycoefficientequalto1ifandonlyifvertexiisvisited(i.e.,covered)byrouteRj.Thebinaryvariablexj,j=1s,isequalto1ifandonlyifrouteRjisselectedinthe 370J.-F.Cordeauetal. solution.Themodelis: (CVRP2)minimizesubjectto s aijxj=1 j=1sj=1 sj=1 γjxj (7) i∈V\\{0} (8) xj=m j=1s (9)(10) xj∈{01} Constraints(8)imposethateachcustomeriiscoveredbyexactlyoneroute, and(9)requiresthatmroutesbeselected.Becauseroutefeasibilityisimplic-itlyconsideredinthedefinitionofR,thisisaverygeneralmodelwhichmayeasilytakeadditionalconstraintsintoaccount.Moreover,whenthecostmatrixsatisfiesthetriangleinequality(i.e.,cijcik+ckjforallijk∈V),thesetpartitioningmodelCVRP2maybetransformedintoanequivalentsetcover-ingmodelCVRP2byreplacingtheequalitysignwith“”in(8).AnyfeasiblesolutiontoCVRP2isclearlyfeasibleforCVRP2,andanyfeasiblesolutiontoCVRP2maybetransformedintoafeasibleCVRP2solutionofsmallerorequalcost.Indeed,iftheCVRP2solutionisinfeasibleforCVRP2,thenoneormorecustomersarevisitedmorethanonce.Thesecustomersmaythere-foreberemovedfromtheirroutebyapplyingshortcutswhichwillnotincreasethesolutioncostbecauseofthetriangleinequality.Themainadvantageofus-ingCVRP2isthatonlyinclusion-maximalfeasibleroutes,amongthosewiththesamecost,needbeconsideredinthedefinitionofR.Thissignificantlyreducesthenumberofvariables.Inaddition,whenusingCVRP2thedualso-lutionspaceisconsiderablyreducedsincedualvariablesarerestrictedtobenonnegative.OneofthemaindrawbacksofmodelsCVRP2andCVRP2liesintheirverylargenumberofvariables,whichinlooselyconstrainedmediumsizeinstancesmayeasilyrunintothebillions.Thus,onehastoresorttoacolumngenerationalgorithmtosolvetheseproblems.Thelinearprogram-mingrelaxationofthesemodelstendstobeverytight,asshownbyBramelandSimchi-Levi(1997).Furtherdetailsontheseformulationsandtheirextensions,aswellasadditionalformulationsforthesymmetricandasymmetriccases,canbefoundinLaporteandNobert(1987)andinTothandVigo(2002b,2002d).2.2ExactalgorithmsfortheCVRP WenowreviewthemainexactapproachespresentedinthelasttwodecadesforthesolutionoftheCVRP.Forathoroughreviewofpreviousexactmeth-ods,seeLaporteandNobert(1987).Wefirstdescribethealgorithmsbasedon Ch.6.VehicleRouting371 branch-and-bound,includingthosethatmakeuseofthesetpartitioningfor-mulationandcolumngenerationschemes,andwethenexaminethealgorithmsbasedonbranch-and-cut.Inpractice,theCVRPturnsouttobesignificantlyhardertosolvethantheTSP.ThebestCVRPalgorithmscanrarelytacklein-stancesinvolvingmorethan100vertices,whileTSPinstanceswithhundredsandeventhousandsofverticesarenowroutinelysolvedtooptimality.2.2.1Branch-and-boundandsetpartitioningbasedalgorithms Severalbranch-and-boundalgorithmsareavailableforthesolutionoftheCVRP.Untilthelate1980s,themosteffectiveexactmethodsweremainlybranch-and-boundalgorithmsbasedonelementarycombinatorialrelaxations.Recently,moresophisticatedboundshavebeenproposed,namelythosebasedonLagrangianrelaxationsorontheadditiveboundingprocedure,whichhavesubstantiallyincreasedthesizeoftheproblemsthatcanbesolvedtooptimal-ity.Wenowdescribesomebranch-and-boundalgorithmswithanemphasisonlowerboundcomputationswhichconstitutethemostcriticalcomponentofmethodsofthistype.Moredetailsonthestructureofbranch-and-boundal-gorithmstrategiesanddominancerulesmaybefoundinTothandVigo(1998,2002c,2002d).Wealsoreviewinthissectionexactsetpartitioningbasedalgo-rithmsfortheCVRP. Manydifferentelementarycombinatorialrelaxationswereusedinearlybranch-and-boundalgorithms,includingthosebasedontheAssignmentProb-lem(AP),onthedegree-constrainedshortestspanningtree,andonstate-spacerelaxation.Hereweoutlinethetwofamiliesofrelaxationsusedasabasisforthemorerecentbranch-and-boundalgorithmsforthesymmetricandasym-metricCVRP.Afirstrelaxationisobtainedfromtheintegerprogrammingformulationsoftheseproblemsbydroppingtheconnectivityandcapacitycon-straints.Inthesymmetriccasetheresultingproblemisab-MatchingProblem(b-MP),i.e.,theproblemofdeterminingaminimumcostsetofcyclescover-ingallverticesandsuchthatthedegreeofeachvertexiisequaltobi,wherebi=2forallthecustomervertices,andb0=2mforthedepotvertex.Itiseasytoseethatbyaddingm−1copiesofthedepottoGtherelaxationbe-comesa2-MP.Intheasymmetriccasetherelaxedproblemisthewell-knowntransportationproblemwhichmaybetransformedintoanAPbyintroducingcopiesofthedepot.Alsointhiscase,theAPmaybeseenastheproblemofdeterminingasetofcircuitscoveringallverticesandsuchthateachvertexhasoneenteringandoneleavingarc.ThesolutionoftheserelaxedproblemsmaybeinfeasiblefortheCVRPsincethedemandassociatedwithacycleorcircuitmayexceedthevehiclecapacity,andsomeofthesemaybedisconnectedfromthedepot.Therelaxedproblemsmaythenbesolvedinpolynomialtime(see,e.g.,MillerandPekny,1995,fortheb-MPandDell’AmicoandToth,2000fortheAP).However,thequalityofthelowerboundsobtainedwiththeserelax-ationsisgenerallyverypoorandnotsufficienttosolveinstanceswithmorethan15or20customers.TothandVigo(2002c)reportaveragegapsinexcessof20%withrespecttotheoptimalsolutionvalueonbenchmarkCVRPin- 372J.-F.Cordeauetal. stances.ThesituationisslightlybetterfortheAPrelaxationoftheasymmetricCVRPthatyieldsaveragegapsofabout10%orless.Laporteetal.(1986)haveproposedabranch-and-boundalgorithmforasymmetricCVRP,basedontheAPrelaxationandcapableofsolvingrandomlygeneratedproblemsinvolvingtensofcustomersandbetweentwoandfourvehicles. Thesecondfamilyofelementaryrelaxationsusedinrecentbranch-and-boundalgorithmsisbasedondegree-constrainedspanningtrees.Thesere-laxationsextendthewell-known1-treerelaxationproposedbyHeldandKarp(1971)fortheTSP.Theearliestbranch-and-boundalgorithmbasedonthisrelaxation,proposedbyChristofidesetal.(1981a),couldonlysolverelativelysmallinstances.Morerecently,Fisher(1994)haspresentedanothertreebasedrelaxationrequiringthedeterminationofaso-calledm-tree,definedasamini-mumcostsetofn+medgesspanningthegraph.TheapproachusedbyFisherisbasedonCVRP1withtheadditionalassumptionthatsingle-customerroutesarenotallowed.FishermodeledtheCVRPastheproblemofdetermininganm-treewithdegreeequalto2matthedepotvertex,withadditionalconstraintsonvehiclecapacityandadegreeof2foreachcustomervertex.Thedetermi-nationofanm-treewithdegree2matthedepotrequiresO(n3)time.Thedegree-constrainedm-treerelaxationiseasilyobtainedfromCVRP1byre-movingthedegreeconstraints(2)forcustomerverticesandweakeningthecapacityconstraints(4)intoconnectivityconstraints,i.e.,byreplacingtheirright-handsidewith1.Them-treesolutionisnotalwaysfeasiblefortheCVRPsincesomeverticesmayhaveadegreedifferentfrom2andthedemandasso-ciatedwiththesubtreesincidenttothedepotmayexceedthevehiclecapacity.FortheasymmetricCVRP,similarrelaxationsmaybederivedfromdirectedtrees,alsocalledarborescences,spanningthegraphandhavinganoutdegreeequaltomatthedepotvertex.Toobtainthefinalboundaminimumcostsetofmvertex-disjointarcsenteringthedepotareaddedtotheconstrainedarbores-cence.Inthiscase,therelaxedsubproblemmaybesolvedinpolynomialtime,butagainthequalityoftheresultinglowerboundisverypoor.TothandVigo(2002c)reportthatonbenchmarkasymmetricinstances,theaveragegapoftheserelaxationswithrespecttotheoptimalsolutionvalueislargerthan25%.DifferentimprovedboundingtechniqueswerelaterdevelopedtonarrowthegapbetweenthelowerboundandtheoptimalsolutionvalueoftheCVRP.TheseincludetwoboundingproceduresbasedonLagrangianrelax-ationproposedbyFisher(1994)andMiller(1995).ThesearestrengtheningsofthebasicCVRPrelaxationsobtainedbydualizingsomeoftherelaxedconstraintsinaLagrangianfashion.Inparticular,theybothincludeintheobjectivefunctionasuitablesubsetofthecapacityconstraints(4),whereastheFisherrelaxationalsoincorporatesdegreeconstraints(2)whichwerere-laxedinthem-treerelaxation.Asinrelatedproblems,goodvaluesfortheLagrangianmultipliersassociatedwiththerelaxedconstraintsaredeterminedbyusingasubgradientoptimizationprocedure(see,e.g.,HeldandKarp,1971;Heldetal.,1974).Themaindifficultyassociatedwiththeserelaxationsliesintheexponentialcardinalityofthesetofrelaxedconstraintswhichdoesnot Ch.6.VehicleRouting373 allowfortheircompleteinclusionintheobjectivefunction.TheseauthorsincludealimitedfamilyFofcapacityconstraintsanditerativelygeneratetheconstraintsviolatedbythecurrentsolutionoftheLagrangianproblem.Theprocessterminateswhennoviolatedconstraintisdetected(hencetheLagrangiansolutionisfeasible)orapresetnumberofsubgradientitera-tionshavebeenexecuted.RedundantconstraintsareperiodicallyremovedfromF.Therelax-and-cutalgorithmofMartinhonetal.(2000)generalizestheseLagrangian-basedapproachesbyalsoconsideringcombandmultistarinequalities,andmoderatelyimprovesthequalityoftheLagrangianbound.SomeexactalgorithmsfortheCVRParebasedonthesetpartitioningformulationCVRP2.ThefirstoftheseisduetoAgarwaletal.(1989)whocon-sideredarelaxationofmodelCVRP2notincludingconstraints(9)andsolvedtheresultingmodelthroughcolumngeneration.Agarwal,Mathur,andSalkinusedtheiralgorithmtosolvesevenEuclideanCVRPinstanceswithupto25customers.Hadjiconstantinouetal.(1995)proposedabranch-and-boundal-gorithminwhichthelowerboundwasobtainedbyconsideringthedualofthelinearrelaxationofmodelCVRP2,followingtheapproachintroducedbyMingozzietal.(1994).Bylinearprogrammingduality,anyfeasiblesolu-tiontothisdualproblemyieldsavalidlowerbound.Hadjiconstantinouetal.(1995)determinedtheheuristicdualsolutionsbycombiningtworelaxationsoftheoriginalproblem:theq-pathrelaxationofChristofidesetal.(1981a)andthem-shortestpathrelaxationofChristofidesandMingozzi(1989).Theal-gorithmwasabletosolverandomlygeneratedEuclideaninstanceswithupto30verticesandbenchmarkinstanceswithupto50vertices.Furtherdetailsonsetpartitioning-basedalgorithmsfortheCVRPareprovidedinBramelandSimchi-Levi(2002). Fischettietal.(1994)haveimprovedtheAPrelaxationoftheasymmet-ricCVRPbycombiningintoanadditiveboundingproceduretwonewlowerboundsbasedondisjunctionsoninfeasiblearcsubsetsandonminimumcostflows.TheadditiveapproachwasproposedbyFischettiandToth(1989)andal-lowsforthecombinationofdifferentlowerboundingprocedures,eachexploit-ingadifferentsubstructureoftheproblemunderconsideration.Theresultingbranch-and-boundapproachwasabletosolverandomlygeneratedinstancescontainingupto300verticesandfourvehicles.Otherboundsfortheasym-metricCVRPmaybederivedbygeneralizingthemethodsproposedforthesymmetriccase.Forexample,Fisher(1994)proposedawayofextendingtotheasymmetricCVRPtheLagrangianboundbasedonm-trees.InthisextensiontheLagrangianproblemcallsforthedeterminationofanundirectedm-treeontheundirectedgraphobtainedbyreplacingeachpairofarcs(ij)and(ji) =min{cc}.Nocomputationaltestingforwithasingleedge(ij)ofcostcijijji thisboundwaspresentedbyFisher(1994).Potentiallybetterboundsmaybeobtainedbyexplicitlyconsideringtheasymmetryoftheproblem,i.e.,byusingm-arborescencesratherthanm-treesandbystrengtheningtheboundinaLa-grangianfashionasproposedbyTothandVigo(1995,1997)forthecapacitatedshortestspanningarborescenceproblemandfortheVRPwithbackhauls. 374J.-F.Cordeauetal. 2.2.2Branch-and-cutalgorithms Branch-and-cutalgorithmscurrentlyconstitutethebestavailableexactap-proachforthesolutionoftheCVRP.Researchinthisareahasbeenstronglymotivatedbytheemergenceandthesuccessofpolyhedralcombinatoricsasaframeworkforthesolutionofhardcombinatorialproblems,particularlytheTSP.However,inarecentsurveyonbranch-and-cutapproachesfortheCVRP,NaddefandRinaldi(2002)state:“...theamountofresearcheffortspenttosolveCVRPbythismethodisnotcomparablewithwhathasbeendedicatedtotheTSP[...theresearchinthisfield]isstillquitelimitedandmostofitisnotpublishedyet”.Inthefollowingwesummarizethemainavailablebranch-and-cutapproachesfortheCVRP.ThereaderisreferredtoNaddefandRinaldi(2002)foramoredetailedpresentation. Theuseofbranch-and-cutfortheCVRPisrootedintheexactalgorithmofLaporteetal.(1985).ThisalgorithmusestheLinearProgramming(LP)re-laxationofmodelCVRP1withoutcapacityconstraints(4)asabasisfortheso-lutionoftheVRPwithcapacityandmaximumdistancerestrictions.Thisinitialrelaxationisiterativelystrengthenedbyaddingviolatedcapacityconstraintswhichareheuristicallyseparatedbyconsideringtheconnectedcomponentsin-ducedbythesetofnonzerovariablesinthecurrentLPsolution.Gomorycutsarealsointroducedattherootnodeofthebranch-and-cuttree.ThealgorithmwascapableofsolvingrandomlygeneratedlooselyconstrainedEuclideanandnon-Euclideaninstanceswithtwoorthreevehiclesandupto60customers.ThefirstpolyhedralstudyoftheCVRPwaspresentedbyCornuéjolsandHarche(1993).Thepresenceofequalities(2)and(3)makestheCVRPnonfully-dimensional.Therefore,asintheTSP,CornuéjolsandHarchefirstconsideredthefull-dimensionalpolyhedron,containingtheCVRPpolyhedronasaface,associatedwiththeso-calledGraphicalVRP(GVRP)wherecus-tomersmaybevisitedmorethanonce.ThebasicpropertiesoftheGVRPpolyhedronwerealsoinvestigated.Conditionsunderwhichthenonnegativity,degreeandcapacityconstraintsdefinefacetsoftheGVRPandCVRPpoly-hedrawerealsodetermined.CornuéjolsandHarchehaveextendedtotheGVRPandtheCVRPseveralotherfamiliesofvalidinequalitiesproposedfortheTSPandthegraphicalTSP.Inparticular,comb,path,wheelbarrow,andbicycleinequalitieswereextendedtothecapacitatedcaseandagain,suffi-cientconditionsunderwhichtheseinequalitiesdefinefacetsoftheGVRPandCVRPpolyhedrawerederived.TheseinequalitieswereusedbyCornuéjolsandHarcheascuttingplanestosolvetwoinstancesofCVRPwith18and50customers,withinabranch-and-cutalgorithm.Thedetectionofviolatedin-equalitieswasperformedmanually,startingfromthecurrentoptimalLPsolu-tion. Augeratetal.(1995)havedevelopedthefirstcompletebranch-and-cutap-proachfortheCVRP.TheydescribedseveralheuristicseparationproceduresfortheclassesofvalidinequalitiesproposedbyCornuéjolsandHarche,aswellasfournewclassesofvalidinequalities.Separationprocedureswerefurtherin-vestigatedbyAugeratetal.(1999).Theresultingapproachwasabletosolve Ch.6.VehicleRouting375 severalCVRPinstancescontainingupto134customers.Ralphsetal.(2003)havepresentedabranch-and-cutalgorithmfortheCVRPinwhichanexactseparationofvalidm-TSPinequalitiesisusedinadditiontoheuristicsepara-tionofcapacityinequalities.TheresultingalgorithmwasimplementedwithintheSYMPHONYparallelbranch-and-cut-and-priceframeworkandwasabletosolveseveralinstancesinvolvingfewerthan100vertices.Lysgaardetal.(2004)havedevelopednewseparationproceduresformostofthefamiliesofvalidinequalitiesproposedsofar(seealsoLetchfordetal.,2002).Theirover-allbranch-and-cutapproach,whichisfurtherenhancedbytheuseofGomorycuts,wasabletosolvewithinmoderatecomputingtimespreviouslysolvedin-stancesandthreenewmediumsizeones. Baldaccietal.(2004)haveputforwardabranch-and-cutalgorithmbasedonatwo-commoditynetworkflowformulationoftheCVRPandrequiringapolynomialnumberofintegervariables.Itseemstoprovideaninterestingalternativetootherclassicalformulations(seealsoGouveia,1995,forasingle-commodityformulation).TheoverallalgorithmstrengthenstheLPrelaxationbyaddingviolatedcapacityinequalitiesandimplementsvariousvariablere-ductionandbranchingrules.Theresultsobtainedwiththisapproacharecom-parablewiththoseoftheotherbranch-and-cutalgorithmsjustdescribed. Finally,Fukasawaetal.(2006)haveproposedasuccessfulbranch-and-cut-and-pricealgorithmcombiningbranch-and-cutwiththeq-routesrelaxationofChristofidesetal.(1981a),usedhereinacolumngenerationfashion.Thismethodproducestighterboundsthanotherbranch-and-cutalgorithmsandiscapableofsolvingseveralpreviouslyunsolvedinstanceswithupto75customers.Baldaccietal.(2006)haveusedtheirsetpartitioningalgorithm,previouslydevelopedforarollon–rolloffVRP,tosolvedifficultCVRPin-stances.TheirapproachyieldsboundswhosequalityiscomparabletothoseofFukasawaetal.(2006),butseemsmuchquicker. Otherbranch-and-cutalgorithmsaredescribedinAchuthanetal.(1996,2003)andBlasumandHochstättler(2000).Wealsomentionthatthepoly-hedralstructureofthespecialcaseofCVRPwhereallthecustomershaveaunitdemandwasstudiedbyCamposetal.(1991)andbyAraqueetal.(1990).Branch-and-cutalgorithmsforthisproblemarepresentedbyAraqueetal.(1994)andbyGhianietal.(2006).2.3HeuristicsfortheVRP AnimpressivenumberofheuristicshavebeenproposedfortheVRP.Ini-tiallytheseweremainlystandardrouteconstructionalgorithms,whereasmorerecentlypowerfulmetaheuristicapproacheshavebeendeveloped.Inthefol-lowingweseparatelyreviewthesetwofamiliesofalgorithms.Almostallofthesemethodsweredeveloped,describedandtestedforthesymmetricVRP.Inaddition,sincefindingafeasiblesolutionwithexactlymvehiclesisitselfanNP-completeproblem,almostallmethodsassumeanunlimitednumber 376J.-F.Cordeauetal. ofavailablevehicles.However,itshouldbeobservedthatmanyofthepro-posedmethodsmaybequiteeasilyadaptedtotakeintoaccountadditionalpracticalconstraints,althoughthesemayaffecttheiroverallperformance(see,e.g.,Vigo,1996,foranextensionofsomeclassicalheuristicstotheasymmetriccase). 2.3.1Classicalheuristics UsingtheclassificationproposedbyLaporteandSemet(2002),wedescribeclassicalVRPheuristicsundertheseheadings:routeconstructionmethods,two-phasemethods,androuteimprovementmethods. Routeconstructionheuristics.RouteconstructionmethodswereamongthefirstheuristicsfortheCVRPandstillformthecoreofmanysoftwareimple-mentationsforvariousroutingapplications.Thesealgorithmstypicallystartfromanemptysolutionanditerativelybuildroutesbyinsertingoneormorecustomersateachiteration,untilallcustomersarerouted.Constructionalgo-rithmsarefurthersubdividedintosequentialandparallel,dependingonthenumberofeligibleroutesfortheinsertionofacustomer.Sequentialmethodsexpandonlyonerouteatatime,whereasparallelmethodsconsidermorethanoneroutesimultaneously.Routeconstructionalgorithmsarefullyspecifiedbytheirthreemainingredients,namelyaninitializationcriterion,aselectioncriterionspecifyingwhichcustomersarechosenforinsertionatthecurrentiteration,andaninsertioncriteriontodecidewheretolocatethechosencus-tomersintothecurrentroutes. ThefirstandmostfamousheuristicofthisgroupwasproposedbyClarkeandWright(1964)andisbasedontheconceptofsaving,anestimateofthecostreductionobtainedbyservingtwocustomerssequentiallyinthesameroute,ratherthanintwoseparateones.Ifiisthelastcustomerofarouteandjisthefirstcustomerofanotherroute,theassociatedsavingisdefinedassij=ci0+c0j−cij.Ifsijispositive,thenservingiandjconsecutivelyinarouteisprofitable.TheClarkeandWrightalgorithmconsidersallcustomerpairsandsortsthesavingsinnonincreasingorder.Startingwithasolutioninwhicheachcustomerappearsseparatelyinaroute,thecustomerpairlistisex-aminedandtworoutesaremergedwheneverthisisfeasible.Generally,aroutemergeisacceptedonlyiftheassociatedsavingisnonnegativebut,ifthenum-berofvehiclesistobeminimized,thennegativesavingmergesmayalsobeconsidered.TheClarkeandWrightalgorithmisinherentlyparallelsincemorethanonerouteisactiveatanytime.However,itmayeasilybeimplementedinasequentialfashion.Theresultingalgorithmisquitefastbutmayhaveapoorperformance(see,e.g.,LaporteandSemet,2002).Goldenetal.(1977),Paessens(1988),andNelsonetal.(1985)haveproposedvariousenhancementstrategiesofthesavingsapproachaimedatimprovingeitheritseffectivenessoritscomputationalefficiencybymeansofbetterdatastructures.OtherattemptstoimprovetheeffectivenessofthesavingsmethodweremadebyDesrochersandVerhoog(1989),AltinkemerandGavish(1991),andbyWarkandHolt Ch.6.VehicleRouting377 (1994)whoproposedtoimplementroutemergesbyusingamatchingalgo-rithm,togetherwithamoresophisticatedestimateofactualmergesavings.Theresultsobtainedwiththesealgorithmsareingeneralbetterthanthoseofprevioussavingsmethods,butmatching-basedalgorithmsrequiremuchlargercomputingtimes. Anotherclassicalrouteconstructionheuristicisthesequentialinsertional-gorithmofMoleandJameson(1976).Thealgorithmusesasselectionandinsertioncriteriontheevaluationoftheextradistanceresultingfromthein-sertionofanunroutedcustomerkbetweentwoconsecutivecustomersiandjofthecurrentroute,namelyα(ikj)=cik+ckj−λcij,whereλisauser-controlledparameter.Variationsofthiscriteriontakingintoaccountotherfactors,suchasthedistanceofthecustomerfromthedepot,werealsocon-sidered.Aftereachinsertion,thecurrentrouteispossiblyimprovedbyusinga3-optprocedure.Amoregeneralandeffectivetwo-stepinsertionheuristicwasproposedbyChristofidesetal.(1979).Inthefirststep,asequentialinser-tionalgorithmisusedtodetermineasetoffeasibleroutes.Thesecondstepisaparallelinsertionapproach.Foreachroutedeterminedinthefirststep,arepresentativecustomerisselectedandasetofsingle-customerroutesisinitializedwiththesecustomers.Theremainingunroutedcustomersaretheninsertedbyusingaregretcriterion,wherethedifferencebetweenthebestandthesecond-bestinsertioncostistakenintoaccount,andpartialroutesareim-provedbymeansofa3-optprocedure.TheresultingalgorithmissuperiortothatofMoleandJamesonandrepresentsagoodcompromisebetweeneffec-tivenessandefficiency. Two-phaseheuristics.Two-phasemethodsarebasedonthedecompositionoftheVRPsolutionprocessintothetwoseparatesubproblems: (1)clustering:determineapartitionofthecustomersintosubsets,eachcor-respondingtoaroute,and (2)routing:determinethesequenceofcustomersoneachroute. Inacluster-first-route-secondmethod,customersarefirstgroupedintoclus-tersandtheroutesarethendeterminedbysuitablysequencingthecustomerswithineachcluster.Differenttechniqueshavebeenproposedfortheclusteringphase,whiletheroutingphaseamountstosolvingaTSP. Thesweepalgorithm,duetoWren(1971),WrenandHolliday(1972),andGillettandMiller(1974),isoftenreferredtoasthefirstexampleofcluster-first-route-secondapproach.ThealgorithmappliestoplanarVRPinstances.Thealgorithmstartswithanarbitrarycustomerandthensequentiallyassignstheremainingcustomerstothecurrentvehiclebyconsideringtheminorderofincreasingpolaranglewithrespecttothedepotandtheinitialcustomer.Assoonasthecurrentcustomercannotbefeasiblyassignedtothecurrentvehicle,anewrouteisinitializedwithit.Onceallcustomersareassignedtovehicles,eachrouteisseparatelydefinedbysolvingaTSP.Anotherearlytwo-phasemethodisthetruncatedbranch-and-boundmethodofChristofidesetal. 378J.-F.Cordeauetal. (1979)inwhichthesetofroutesisdeterminedthroughanadaptationofanex-actbranch-and-boundalgorithmthatusesabranching-on-routesstrategy.Thedecisiontreecontainsasmanylevelsasthenumberofavailablevehicles,andateachlevelofthedecisiontreeagivennodecorrespondstoapartialsolu-tionmadeupofsomecompleteroutes.Thedescendantnodescorrespondtoallpossibleroutesincludingasubsetoftheunroutedcustomers.Therunningtimeofthealgorithmiscontrolledbylimitingtoonethenumberofroutesgeneratedateachlevel. TheFisherandJaikumar(1981)algorithmsolvestheclusteringstepbymeansofanappropriatelydefinedGeneralizedAssignmentProblem(GAP)whichcallsforthedeterminationofaminimumcostassignmentofitemstoagivensetofbinsofcapacityQ,andwheretheitemsarecharacterizedbyaweightandanassignmentcostforeachbin.Eachvehicleisassignedarepre-sentativecustomer,calledaseed,andtheassignmentcostofacustomertoavehicleisequaltoitsdistancetotheseed.TheGAPisthensolved,eitheropti-mallyorheuristically,andthefinalroutesaredeterminedbysolvingaTSPoneachcluster. Anothertwo-phasemethodworkingwithafixednumbermofvehicleswasdescribedbyBramelandSimchi-Levi(1995).Thisalgorithmdeterminesrouteseedsbysolvingacapacitatedlocationproblem,wheremcustomersarese-lectedbyminimizingthetotaldistancebetweeneachcustomeranditsclosestseed,andbyimposingthatthetotaldemandassociatedwitheachseedbeatmostQ.Onceseedshavebeendeterminedandthesingle-customerroutesareinitialized,theremainingcustomersareinsertedinthecurrentroutesbyminimizinginsertioncosts.Variouswaysofapproximatingtheinsertioncostareproposedandanalyzed.Itisworthnotingthatallthreecluster-first-route-secondapproachesjustdescribedallowforadirectcontrolofthenumberofroutesinthefinalsolution,whereasthesweepalgorithmdoesnot.Theperfor-manceofthesealgorithmsisgenerallycomparabletothatofrouteconstructionalgorithmsintermsofeffectiveness.ThelocationbasedapproachofBramelandSimchi-Leviproducesbettersolutionsbutrequiresmuchlargercomputingtimes. Adifferentfamilyoftwo-phasemethodsistheclassofso-calledpetalalgo-rithms.Thesegeneratealargesetoffeasibleroutes,calledpetals,andselectthefinalsubsetbysolvingasetpartitioningmodel.FosterandRyan(1976)andRyanetal.(1993)haveproposedheuristicrulesfordeterminingthesetofroutestobeselected,whileRenaudetal.(1996b)havedescribedanextensionthatconsidersmoreinvolvedconfigurations,called2-petals,consistingoftwoembeddedorintersectingroutes.Theoverallperformanceofthesealgorithmsisgenerallysuperiortothatofthesweepalgorithm. Finally,inroute-first-cluster-secondmethods,agiantTSPtouroverallcus-tomersisconstructedinafirstphaseandlatersubdividedintofeasibleroutes.ExamplesofsuchalgorithmsaregivenbyBeasley(1983),HaimovichandRinnooyKan(1985),andBertsimasandSimchi-Levi(1996),buttheperfor-manceofthisapproachisgenerallypoor. Ch.6.VehicleRouting379 Routeimprovementheuristics.Localsearchalgorithmsareoftenusedtoim-proveinitialsolutionsgeneratedbyotherheuristics.Startingfromagivensolu-tion,alocalsearchmethodappliessimplemodifications,suchasarcexchangesorcustomermovements,toobtainneighborsolutionsofpossiblybettercost.Ifanimprovingsolutionisfound,itthenbecomesthecurrentsolutionandtheprocessiterates;otherwisealocalminimumhasbeenidentified. Alargevarietyofneighborhoodsareavailable.Thesemaybesubdividedintointra-routeneighborhoods,iftheyoperateonasinglerouteatatime,orinter-routeneighborhoodsiftheyconsidermorethanoneroutesimultaneously.Themostcommonneighborhoodtypeistheλ-optheuristicofLin(1965)fortheTSP,whereλedgesareremovedfromthecurrentsolutionandreplacedbyλothers.Thecomputingtimerequiredtoexamineallneighborsofasolutionisproportionaltonλ.Thus,onlyλ=2or3areusedinpractice.Asanalterna-tive,onecanuserestrictedneighborhoodscharacterizedbysubsetsofmovesassociatedwithlargerλvalues,suchasOr-exchanges(Or,1976)orthe4-opt*neighborhoodofRenaudetal.(1996a)whichconsidersonlyasubsetofallpotential4-optexchanges.LaporteandSemet(2002)haveconductedacom-putationalcomparisonofsomebasicrouteimprovementprocedures.Morecomplexinter-routeneighborhoodsareanalyzedbyThompsonandPsaraftis(1993),VanBreedam(1994),andKindervaterandSavelsbergh(1997).2.3.2Metaheuristics SeveralmetaheuristicshavebeenappliedtotheVRP.Withrespecttoclas-sicalheuristics,theyperformamorethoroughsearchofthesolutionspaceandarelesslikelytoendwithalocaloptimum.Thesecanbebroadlydividedintothreeclasses: (1)localsearch,includingsimulatedannealing,deterministicannealing, andtabusearch; (2)populationsearch,includinggeneticsearchandadaptivememorypro-cedures; (3)learningmechanisms,includingneuralnetworksandantcolonyopti-mization.Thebestheuristicsoftencombineideasborrowedfromdifferentmeta-heuristicprinciples.RecentsurveysofVRPmetaheuristicscanbefoundinGendreauetal.(2002),CordeauandLaporte(2004),andCordeauetal.(2005). Localsearchalgorithmsexplorethesolutionspacebyiterativelymovingfromasolutionxtatiterationttoasolutionxt+1intheneighborhoodN(xt)ofxtuntilastoppingcriterionissatisfied.Iff(x)denotesthecostofsolutionx,thenf(xt+1)isnotnecessarilysmallerthanf(xt).Asaresult,mechanismsmustbeimplementedtoavoidcycling.Insimulatedannealing,asolutionxisdrawnrandomlyfromN(xt).Iff(x)f(xt),thenxt+1:=x.Otherwise, xwithprobabilitypt xt+1:= xtwithprobability1−pt 380J.-F.Cordeauetal. whereptisadecreasingfunctionoftandoff(x)−f(xt).Thisprobabilityisoftenequalto f(x)−f(xt) pt=exp− θtwhereθtisthetemperatureatiterationt,usuallydefinedasanonincreasingfunctionoft.Deterministicannealing(Dueck,1990,1993)issimilar.Therearetwomainversionsofthisalgorithm:inathreshold-acceptingalgorithm,xt+1:=xiff(x) Neuralnetworksaremodelscomposedofrichlyinterconnectedunitsthroughweightedlinks,likeneuronsinthebrain.Theygraduallyconstructasolutionthroughafeedbackmechanismthatmodifiesthelinkweightstobettermatchanobservedoutputtoadescribedoutput.Inthefieldofvehicleroutingneuralnetworkmodelscalledtheelasticnetandtheself-organizingmaparedeformabletemplatesthatadjustthemselvestothecontouroftheverticestogenerateafeasibleVRPsolution.AnexampleisprovidedbyGhaziri(1993).Antcolonyalgorithms(seeDorigoetal.,1999)alsousealearningmechanism.Theyarederivedfromananalogywithantswhichlaysomepheromoneontheirtrailwhenforagingforfood.Withtimemorepheromoneisdepositedonthemorefrequentedtrails.WhenconstructingaVRPsolutionamovecan Ch.6.VehicleRouting381 beassignedahigherprobabilityofbeingselectedifithaspreviouslyledtoabettersolutioninpreviousiterations. InwhatfollowswesummarizethemosteffectivemetaheuristicsfortheCVRP.Initiallythebestmethodswerealmostexclusivelybasedontabusearchbutinrecentyearsseveralexcellentmethodsinspiredfromdifferentparadigmshavebeenproposed. Localsearchheuristics.AlimitednumberofsimulatedannealingheuristicsfortheCVRPwereproposedintheearly1990s.Osman’simplementation(Osman,1993)isthemostinvolvedandalsothemostsuccessful.Itdefinesneighborhoodsbymeansofa2-interchangeschemeandappliesadifferentruleoftemperaturechanges.Insteadofusinganonincreasingfunction,asdomostauthorsinthefield,Osmandecreasesθtcontinuouslyaslongastheso-lutionimproves,butwheneverxt+1=xt,θtiseitherhalvedorreplacedbythetemperatureatwhichtheincumbentwasidentified.Thisalgorithmsucceededinproducinggoodsolutionsbutwasnotcompetitivewiththebesttabusearchimplementationsavailableatthesameperiod. Alargenumberoftabusearchalgorithmshavebeenproducedoverthepastfifteenyears(asurveyisavailableinCordeauandLaporte,2004).Inthefirstknownimplementation,duetoWillard(1989),aCVRPsolutionisrepresentedasagianttourcontainingseveralcopiesofthedepotandinter-depotchainscorrespondingtofeasiblevehicleroutes,andneighborhoodsaredefinedbymeansof3-optexchanges.Themethodwassoontobesupersededbymorepowerfulalgorithms,includingthoseofOsman(1993),Taillard(1993),andGendreauetal.(1994). Taillard’salgorithmremainstothisdayoneofthemostsuccessfultabusearchimplementationsfortheCVRP.Itisbasedontheuseofan1-inter-changemechanismtodefineneighborsolutions,combinedwithperiodicroutereoptimizationsbymeansofanexactTSPalgorithm(VolgenantandJonker,1983).Thealgorithmalsousesrandomtabudurations.Acontinuousdiversifi-cationmechanismthatpenalizesfrequentlyperformedmovesisimplementedinordertoprovideamorethoroughexplorationofthesearchspace.Finally,Taillard’salgorithmemploysadecompositionschemethatallowsfortheuseofparallelcomputing.Inplanarproblemsthecustomersetispartitionedintosectorsandthenconcentricrings,whileinrandominstancestheregionsaredefinedbymeansofshortestspanningarborescencesrootedatthedepot.Theregionboundariesareperiodicallyupdatedtoproduceadiversificationeffect. TheTaburoutealgorithmofGendreauetal.(1994)movesateachitera-tionavertexfromitscurrentroutetoanotherroutecontainingoneofitsclosestneighbors.Insertionsareperformedsimultaneouslywithalocalre-optimizationoftheroute,basedontheGENIprocedure(Gendreauetal.,1992).Onlyasubsetofverticesareconsideredforreinsertionatanygiveniteration.Novertexcanreturntoitsformerrouteduringthenextθitera-tions,whereθisrandomlyselectedinaclosedinterval.Taburoutealsouses 382J.-F.Cordeauetal. acontinuousdiversificationmechanism.Duringthecourseofthesearchin-feasiblesolutionsarepenalized.Thismechanismisimplementedbyreplacingthesolutionvaluef(x)associatedatsolutionxwithapenalizedobjectivef(x)=f(x)+αQ(x)+βL(x),whereQ(x)isthetotalcapacityviolationofsolutionxandL(x)isthetotalroutelengthviolation.Thetwoparametersαandβself-adjustduringthesearchtoproduceamixoffeasibleandinfeasiblesolutions:everyμiterations,α(resp.β)isdividedby2ifthepastμsolutionswerefeasiblewithrespecttocapacity(resp.routelength),ormultipliedby2iftheywereallinfeasiblewithrespecttocapacity(resp.routelength).OtherfeaturesofTaburouteincludetheuseofrandomtabudurations,periodicroutereoptimizationsbymeansoftheUSprocedureofGendreauetal.(1992),falsestartstoinitializethesearch,andafinalintensificationphasearoundthebestknownsolution. TheRegoandRoucairol(1996)Tabuchainalgorithmisbasedontheuseofejectionchainsinvolvingroutestodefineneighborhoods.Thisprocessbumpsavertexfromonerouteofthechaintoanotherroute.Thelastbumpedver-texmayberelocatedinthepositionofthefirstbumpedvertexorelsewhere.Theprocessensuresthatnoarcoredgeisconsideredmorethanonceinthesolution.AsinTaburoute,intermediateinfeasiblesolutionsareallowed.Theauthorshavealsoimplementedasequentialandaparallelversionoftheirmethod.Anotherejectionscheme,calledFlower,waslaterdevelopedbyRego(1998).Itisbasedontheideaofexploitingtherepresentationofroutesasblossomsandofpathsasstems,andofperformingejectionmovesbymeansofedgedeletionsandcreations.ThismethodwasnotassuccessfulasTabuchain.AnothermethodemployingejectionchainswasdevelopedbyXuandKelly(1996).Itoscillatesbetweenejectionchainsandvertexswapsbetweentworoutes.Theejectionchainsareobtainedbysolvinganauxiliarynetworkflowproblem.Onthewholethismethodsucceededinobtainingsev-eralgoodCVRPsolutionsonbenchmarkinstancesbutitisratherinvolvedandtimeconsuming. Morerecently,Ergunetal.(2003)havedevelopedaVeryLargeNeigh-borhoodSearch(VLNS)algorithmfortheVRP.Thisalgorithmoperatesonseveralroutessimultaneously,notunlikewhatisdoneincyclictransfers(ThompsonandPsaraftis,1993)orinejectionchains.Neighborhoodsarede-finedbyacombinationof2-optmoves,vertexswapsbetweenroutes,andvertexinsertionsindifferentroutes.Thebestchoiceofmovesandofroutesinvolvedinthemovesisdeterminedthroughthesolutionofanetworkflowproblemonanauxiliarygraph.OneadvantageofVLNSisthatitallowsabroadsearchbyactingonseveralroutesatonce.Itsmaindisadvantageliesintheeffortrequiredateachiterationtoperformmoves. AveryusefulconceptputforwardbyTothandVigo(2003)isthatofGran-ularTabuSearch(GTS).Thisalgorithmaprioriremovesfromthegraphlongedgesthatareunlikelytobelongtoanoptimalsolution.Todeterminetheseedges,theproblemisfirstsolvedbymeansofafastheuristic,e.g.,theClarke ¯inthissolutionandWright(1964)algorithm,andtheaverageedgecostc Ch.6.VehicleRouting383 isdetermined.Thenonlytwofamiliesofedgesareretained:thoseincident ¯,whereβisauser-tothedepot,andthosewhosecostdoesnotexceedβc definedsparsificationparameter.Theauthorsshowthatonbenchmarkin-stances,choosingβin[1020]yieldstheeliminationofbetween80–90%ofalledges.GranulartabusearchwasimplementedinconjunctionwithsomeofthefeaturesofTaillard’salgorithm(Taillard,1993)andTaburoute(Gendreauetal.,1994),andneighborsolutionswereobtainedbyperformingintra-routeandinter-routeexchanges. DeterministicannealingwasfirstappliedtotheVRPbyGoldenetal.(1998)andmorerecentlybyLietal.(2005).Thelatteralgorithmcombinestherecord-to-recordprincipleofDueck(1993)withGTS.Itworksonasparsifiedgraphcontainingonlyaproportionαofthe40shortestedgesincidenttoeachver-tex,whereαvariesthroughoutthealgorithm.ThealgorithmisappliedseveraltimesfromthreeinitialsolutionsgeneratedbytheClarkeandWright(1964)algorithm,withsavingssijdefinedasci0+c0j−λcij,andλ=0614and16.Neighborsaredefinedbymeansofintra-andinter-route2-optmoves,andnonimprovingsolutionsareacceptedaslongastheircostdoesnotexceedthatoftheincumbentbymorethan1%.Wheneverthesolutionhasnotimprovedforanumberofiterations,aperturbationisappliedtothebestknownsolutiontorestartthesearch.Thisisachievedbytemporarilymovingsomeverticestodifferentpositions. Populationsearchheuristics.TheAdaptiveMemoryProcedure(AMP)putforwardbyRochatandTaillard(1995)constitutesamajorcontributiontothefieldofmetaheuristics.InitiallydevelopedinthecontextoftheVRP,itisofgeneralapplicabilityandhasbeenused,forexample,tosolvepoliticaldistrict-ingproblems(Bozkayaetal.,2003).Anadaptivememoryisapoolofgoodsolutionswhichisupdatedbyreplacingitsworstelementswithbetterones.Inordertogenerateanewsolution,severalsolutionsareselectedfromthepoolandrecombined.InthecontextoftheVRP,vehicleroutesareextractedfromthesesolutionsandusedasthebasisofanewsolution.Theextractionprocessisappliedaslongasitispossibletoidentifyroutesthatdonotoverlapwithpre-viouslyselectedroutes.Whenthisisnolongerpossible,asearchprocess(e.g.,tabusearch)isinitiatedfromapartiallyconstructedsolutionmadeupoftheselectedroutesandsomeunroutedcustomers.Anysolutionconstructedinthisfashionreplacestheworstsolutionofthepoolifithasabettercost.TarantilisandKiranoudis(2002)haveproposedavarianttothisscheme.InafirstphaseasolutionisobtainedbymeansofthePaessens(1988)constructiveprocedure,whichisanapplicationoftheClarkeandWrightsavingsheuristicfollowedby2-optmoves,vertexswapsbetweenroutes,andvertexreinsertions.Inordertogeneratenewsolutionsfromtheadaptivememory,TarantilisandKiranoudisextractroutesegments,calledbones,asopposedtofullvehicleroutesasdidRochatandTaillard. Prins(2004)hasdevelopedanalgorithmcombiningtwomainfeaturesofevolutionarysearch,namelycrossoversandmutations.Crossoversconsistof 384J.-F.Cordeauetal. creatingoffspringsolutionsfromparents,whilemutationsareobtainedherebyapplyingalocalsearchalgorithmtoanoffspring.Thiscombinationofso-lutionrecombinationandlocalsearchissometimesreferredtoasamemeticalgorithm(MoscatoandCotta,2003).Inthisalgorithm,solutionsarerepre-sentedasagianttourwithouttripdelimiters.Tocreateanoffspringfromtwoparents,achain(ij)isfirstselectedfromthefirstparentandtheverticesofthesecondparentarescannedfrompositionj+1byskippingthoseofthechain(ij).Asecondoffspringisgeneratedinasimilarwaybyreversingtherolesofthetwoparents.Offspringareimprovedbyapplyingacombinationofvertexandedgereinsertions,vertexswaps,combinedvertexandedgeswaps.TwoothermemeticalgorithmshaverecentlybeenproposedbyBergerandBarkaoui(2004)andbyMesterandBräysy(2005).Thefirstworksontwopop-ulationswhosesizesarekeptconstantthroughthereplacementofparentsbynewlycreatedoffspring,andmigrationstakeplacebetweenthetwopopula-tions.Offspringareobtainedbycombiningroutesfromtwoparentsaslongasthiscanbedonewithoutoverlapping,andbyinsertingtheunroutedcustomersaccordingtoaproximitycriterion.AVLNSheuristic(Shaw,1998)combin-ingthreeinsertionmechanismsisthenappliedtotheoffspring,followedbyanimprovementschemeconsistingofremovingverticesfromthesolutionandreinsertingthembymeansoftheI1procedureofSolomon(1987). TheActiveGuidedEvolutionStrategies(AGES)ofMesterandBräysywasinitiallydevelopedtosolvetheVRPwithtimewindowsandwaslaterappliedtotheclassicalVRP.Itcombineslocalsearch(Voudouris,1997)withanevolutionstrategy(Rechenberg,1973)toproduceaniterativetwo-stageprocedure.Theevolutionarystrategyusesadeterministicruletoselectaparentsolutionandcreateasingleoffspringfromasingleparent.Theoffspringreplacestheparentifitimprovesuponit.Offspringareimprovedbymeansofanelaboratesearchprocedurecombininggranulartabusearch,continuousdiversification,vertexswapsandmoves,2-opt*moves(PotvinandRousseau,1995),VLNS(Shaw,1998),andrestarts. Learningmechanisms.AlimitednumberofheuristicsbasedonlearningmechanismshavebeenproposedfortheVRP.Noneoftheknownneuralnetworksbasedmethodsissatisfactory,andtheearlyantcolonybasedheuris-ticscouldnotcompetewiththebestavailableapproaches.Recently,how-ever,Reimannetal.(2004)haveproposedawell-performingheuristicscalledD-ants.Themethodrepeatedlyappliestwophasesuntilastoppingcriterionisreached.Inthefirstphase,afirstgenerationofgoodsolutionsisgener-atedthroughtheapplicationsofasavingsbasedheuristic(ClarkeandWright,1964)anda2-optimprovementprocedureisappliedtoeachsolution.Newgenerationsofsolutionsarethencreatedbybenefitingfromtheknowledgegainedinproducingpastgenerations.Thus,insteadofusingthestandardsav-αsβisnowemployed,ingssij=ci0+c0j−cij,anattractivenessvalueχij=τijij αwhereτijcontainsinformationonhowgoodlinkingiandjturnedouttobe inpreviousgenerations,andαandβareuser-controlledparameters.Vertices Ch.6.VehicleRouting385 iandjarelinkedwithprobabilitypij=χij/((h)∈Ωkχh),whereΩkisthesetofthefeasible(ij)pairsyieldingthekbestsavings.Inthesecondphasethebestsolutionidentifiedinthefirstphaseisdecomposedintosubproblemswhicharethenreoptimizedusingtheprocedureusedinthefirstphase.Computationalcomparisonofmetaheuristics.Cordeauetal.(2005)provideacomputationalcomparisonofrecentVRPheuristicsonthe14Christofidesetal.(1979)instances(50n199)andonthe20largerLietal.(2005)instances(200n480).Mostmetaheuristicsusedinthecomparisoncon-sistentlyyieldsolutionswhosevaluelieswithin1%ofthebestknownvalue.OntheChristofidesetal.(1979)instances,thebestsolutionsareobtainedbyTaillard(1993),RochatandTaillard(1995),andMesterandBräysy(2005).Ifthetwoinstancesetsaretakentogether,thebestperformers,intermsofac-curacyandcomputingtimeareprobablyMesterandBräysy(2005),TarantilisandKiranoudis(2002),andPrins(2004).Itshouldbenotedthatthesethreemethodsallcombinepopulationsearchandlocalsearch,thusallowingforabroadanddeepexplorationofthesolutionspace. AsnotedbyCordeauetal.(2002b)heuristicsshouldnotbejudgedsolelyonspeedandaccuracy.Simplicityandflexibilityarealsoimportant.Inthisre-specttheLietal.(2005)record-to-recordalgorithmisratherinteresting:thisalgorithmpossessesasimplestructureandiscapableofgeneratingveryhighqualitysolutions.Asfarasflexibilityisconcerned,thegranularityprinciple(TothandVigo,2003)andtheadaptivememoryconcept(RochatandTaillard,1995)aregeneralandusefulideaswhichcaneasilybeappliedtootherprob-lems. 3Thevehicleroutingproblemwithtimewindows TheVehicleRoutingProblemwithTimeWindows(VRPTW)isanimpor-tantgeneralizationoftheclassicalVRPinwhichserviceateverycustomerimuststartwithinagiventimewindow[aibi].Avehicleisallowedtoarrivebe-foreaiandwaituntilthecustomerbecomesavailable,butarrivalsafterbiareprohibited.TheVRPTWhasnumerousapplicationsindistributionmanage-ment.Commonexamplesarebeverageandfooddelivery,newspaperdelivery,andcommercialandindustrialwastecollection(see,e.g.,Goldenetal.,2002).TheVRPTWisNP-hardsinceitgeneralizestheCVRPwhichisobtainedwhenai=0andbi=∞foreverycustomeri.Inthecaseofafixedfleetsize,evenfindingafeasiblesolutiontotheVRPTWisitselfanNP-completeproblem(Savelsbergh,1985).Asaresult,researchontheVRPTWhasconcen-tratedonheuristics.Nevertheless,whentheproblemissufficientlyconstrained(i.e.,whentimewindowsaresufficientlynarrow),realisticsizeinstancescanbesolvedoptimallythroughmathematicalprogrammingtechniques.ThissectionpresentsamathematicalformulationoftheVRPTWfollowedbyadescriptionofsomeofthemostimportantavailableexactandheuristicalgorithms.Itis 386J.-F.Cordeauetal. worthpointingoutthatwhileexactmethodsusuallyminimizedistance,mostheuristicsconsiderahierarchicalobjectivewhichfirstminimizesthenumberofvehiclesusedandthendistance.3.1FormulationoftheVRPTW TheVRPTWcanbedefinedonadirectedgraphG=(VA),where|V|=n+2,andthedepotisrepresentedbythetwovertices0andn+1.Feasiblevehicleroutesthencorrespondtopathsstartingatvertex0andend-ingatvertexn+1.ThesetofvehiclesisdenotedbyK,with|K|=m.Letsidenotetheservicetimeati(withs0=sn+1=0)andlettijbethetraveltimefromitoj.Inadditiontothetimewindow[aibi]associatedwitheachvertexi∈N=V\\{0n+1},timewindows[a0b0]and[an+1bn+1]canalsobeasso-ciatedwiththedepotvertex.Ifnoparticularrestrictionsareimposedonvehicleavailability,onemaysimplyseta0=mini∈N{ai−t0i},b0=maxi∈N{bi−t0i},an+1=mini∈N{ai+si+tin+1},andbn+1=maxi∈N{bi+si+tin+1}.AsintheCVRP,letqidenotethedemandofcustomeri,andletQbethevehiclecapacity. WhileseveralmodelsareavailablefortheVRPTW,thisproblemisoftenformulatedasamulticommoditynetworkflowmodelwithtimewindowandca-pacityconstraints.Thismodelinvolvestwotypesofvariables:binaryvariablesxkij,(ij)∈A,k∈K,equalto1ifandonlyifarc(ij)isusedbyvehiclek,and k,i∈N,k∈K,indicatingthetimeatwhichvehiclekcontinuousvariableswi startsservicingvertexi.Letδ+(i)={j:(ij)∈A}andδ−(j)={i:(ij)∈A}.Theproblemcanthenbestatedasfollows(see,e.g.,Desrochersetal.,1988): minimize(11)cijxkij k∈K(ij)∈A subjectto k∈Kj∈δ+(i) xkij=1 i∈N (12)(13) k∈Kj∈N (14)(15) k∈K(ij)∈A (16)(17)(18) xk0j=1xkij − k∈Kxkji=0 j∈δ+(0) i∈δ−(j) i∈δ+(j) xkin+1=1 k∈K kk w+s+t−wxkiijijij0 i∈δ−(n+1) kaiwibik∈Ki∈V qixkk∈KijQi∈N j∈δ+(i) Ch.6.VehicleRouting387 xkij∈{01} k∈K(ij)∈A (19) Theobjectivefunction(11)minimizesthetotalroutingcost.Constraints (12)statethateachcustomerisvisitedexactlyonce,whileconstraints(13)–(15)ensurethateachvehicleisusedexactlyonceandthatflowconservationis ksatisfiedateachcustomervertex.Theconsistencyofthetimevariableswi isensuredthroughconstraints(16)whiletimewindowsareimposedby(17).Theseconstraintsalsoeliminatesubtours.Finally,constraints(18)enforcethevehiclecapacityrestriction. Formulation(11)–(19)isnonlinearbecauseofconstraints(16).Thesecon-straintscan,however,belinearizedasfollows: kk wj(20)wi+si+tij−Mij1−xkk∈K(ij)∈AijwhereMij=max{0bi+si+tij−aj}isaconstant.AssuggestedbyDesrochers andLaporte(1991),theboundsonthetimevariablesbkicanalsobestrength-ened: k wiai+max{0aj−ai+sj+tji}xkk∈Ki∈V(21)ji j∈δ−(i) kwi bi− max{0bi−bj+si+tij}xkij k∈Ki∈V(22) j∈δ+(i) 3.2ExactalgorithmsfortheVRPTW Asformostothervehicleroutingproblems,itisdifficulttosolvethe VRPTWexactlythroughclassicalsimplex-basedbranch-and-boundmethods,evenforsmallinstances.ThisisinlargepartexplainedbythefactthattheLPrelaxationoftheproblemprovidesaweaklowerbound.Thefirstoptimiza-tionalgorithmfortheVRPTWcanbeattributedtoKolenetal.(1987)whouseddynamicprogrammingcoupledwithstatespacerelaxation(Christofidesetal.,1981b)tocomputelowerboundswithinabranch-and-boundalgorithm.Instanceswithn15weresolvedusingthisapproach.Mostsubsequentalgo-rithmsrelyeitheronthegenerationofvalidinequalitiestostrengthentheLPrelaxationoronmathematicaldecompositiontechniques.Thissectionreviewsthethreemainavailableapproaches:Lagrangianrelaxation,columngener-ation,andbranch-and-cut.AdditionalreferencesonthesubjectcanalsobefoundintheCordeauetal.(2002a)review. 3.2.1Lagrangianrelaxationbasedalgorithms LagrangianrelaxationcanbeappliedtotheVRPTWinseveralways.Itiswellknownthatwhenthesubproblemobtainedbyrelaxingsomeoftheconstraintspossessestheintegralityproperty,thebestlowerboundobtainedbyLagrangianrelaxation(i.e.,thevalueoftheLagrangiandual)isequaltothevalueofthelinearprogrammingrelaxationoftheoriginalproblem.But 388J.-F.Cordeauetal. asmentionedabove,theLPrelaxationofformulation(11)–(19)providesaweaklowerboundwhichwillusuallypreventtheproblemfrombeingsolvedbybranch-and-bound.Asaresult,successfulimplementationsofLagrangianrelaxationfortheVRPTWshouldretainatleastsomeofthecomplicatingcon-straintsinthesubproblem. Fisher(1994)andFisheretal.(1997)havedescribedLagrangianrelaxationbasedonm-trees(seeSection2.2.1).Thisapproachrelaxestheflowconserva-tionconstraintsaswellasthecapacityandtimewindowconstraints.ViolatedcapacityconstraintsarehandledbyidentifyingsubsetsofcustomersS⊆Nthatmustbevisitedbyatleastκ(S)vehiclesandimposingtheconstraint xk(23)ijκ(S) k∈Ki∈V\\Sj∈S TheseconstraintsarerelaxedinaLagrangianfashionsothattheresulting problemremainsanm-treeproblemwithmodifiedcosts.Timewindowsarehandledsimilarlybyidentifyinginfeasiblepathsandimposingtheconstraintthatatleastonearcinthepathbeleftoutofthesolution.ThisapproachhassolvedafewoftheSolomon(1987)testinstanceswithn=100.Inadditiontothem-treerelaxationmethod,Fisheretal.(1997)havealsoexperimentedwithavariablesplittingapproachinwhichadditionalvariablesyik,equalto1ifandonlyifcustomeriisvisitedbyvehiclek,areintroducedintheformu-klation,andtheconstraintsj∈Vxkij=yi(i∈N,k∈K)aredualized.The Lagrangiansubproblemdecomposesintoasemi-assignmentproblemintheyikvariableswhichissolvablebyinspection,andasetofmelementaryshortestpathproblemswithtimewindowsandcapacityconstraints. AnotherpossibleLagrangianrelaxationconsistsofdualizingthedemandconstraints.Letλ=(λi)(i∈N)bethevectorofmultipliersassociatedwithconstraints(12)requiringthateachcustomerbevisitedexactlyonce.Forgivenvaluesofthemultipliers,theLagrangiansubproblemL(λ)obtainedbyrelax-ingtheseconstraintsintheobjectivefunctionis k (cij−λi)xij+λimin(24) k∈K(ij)∈A i∈N subjecttoconstraints(13)–(19). Thissubproblemdoesnotpossesstheintegralityproperty.Itdoes,however,decomposeintomdisjointelementaryshortest-pathproblemswithcapacityandtimewindowconstraints.Whenallvehiclesareidentical,asingleprob-lemcanbesolvedtocomputethelowerbound.TheLagrangiandual,i.e.,theproblemoffindingoptimalmultipliersthatmaximizeL(λ),isaconcavenondifferentiablemaximizationproblem.Usingsubgradientandbundlemeth-ods,KohlandMadsen(1997)wereabletosolvesomeinstanceswithupto100customers.Theyreportedoptimalsolutionstoeachofthe27clusteredandshort-horizonSolomoninstances. Ch.6.VehicleRouting389 Kallehaugeetal.(2006)havedevelopedastabilizedcutting-planealgorithmtosolvetheLagrangiandual.CuttingplanesaregeneratedbysolvingtheLa-grangiansubproblemandareintroducedinamasterproblemwhichimposesbounds(i.e.,atrustregion)onthedualvariablestoensurethestabilityoftheirvaluesfromoneiterationtothenext.Optimizingtherelaxedmasterproblem(amaximizationlinearprogram)providesalowerboundonthevalueoftheoriginalproblem.Toobtainfeasibleintegersolutions,thecutting-planealgo-rithmisembeddedwithinabranch-and-boundalgorithmandvalidinequalitiesareintroducedinthemasterproblem.Becausetherelaxedmasterproblemisstatedonthedualvariables,violatedsubtoureliminationconstraintsand2-pathinequalities(seeSection3.2.2)areaddedascolumnstothisproblem.ThisapproachhasyieldedgoodresultsontheSolomontestinstancesandwasabletosolvetwolargeinstanceswith400and1000customers,respectively.3.2.2Columngenerationalgorithms Columngenerationisintimatelyrelatedtoconstraintgenerationandcanbeseenasaspecialwayofupdatingthemultipliersassociatedwiththerelaxedconstraints.LetΩkdenotethesetoffeasiblepathsforvehiclek∈K.Foreach kbethecostofthispathandletθkbeabinaryvariablepathω∈Ωk,letcωω equalto1ifandonlyifvehiclekusespathω.Letalsoaiωbethenumberoftimescustomeri∈Nisvisitedbypathω.AsfirstsuggestedbyBalinskiandQuandt(1964),theVRPTWcanbestatedasfollows: kk minimize(25)cωθω k∈Kω∈Ωk subjectto k∈Kω∈Ωk kaiωθω=1 i∈N (26)(27)(28) kθω=1 k∈Kk∈Kω∈Ωk ω∈Ωk k ∈{01}θω BecausethesetsΩkarelikelytohaveaverylargecardinality,thisproblem canbetackledbyabranch-and-boundalgorithminwhichthelinearrelaxationsaresolvedbycolumngeneration.Ateachnodeoftheenumerationtree,are-strictedcolumngenerationmasterproblemissolvedoverthecurrentsetofcolumns.Newcolumnsofnegativereducedcostaregeneratedbysolvingare-sourceconstrainedshortestpathproblem(13)–(19)withmodifiedarccostsreflectingthecurrentvaluesofthedualvariablesassociatedwiththecon-straintsofthecolumngenerationmasterproblem.Thisprocessstopswhennonegativereducedcostcolumncanbegenerated.Becausethecolumngenera-tionsubproblemisequivalenttotheLagrangiansubproblemL(λ),thelowerboundprovidedbycolumngenerationisequaltothevalueoftheLagrangian 390J.-F.Cordeauetal. dual.ThedualoftheLPrelaxationofformulation(25)–(28)is,infact,equiv-alenttotheLagrangiandualdefinedintheprevioussection.ThisformulationcanalsobeobtainedbyapplyingtheDantzig–Wolfedecompositionprinciple(DantzigandWolfe,1960)totheoriginalformulation(11)–(19). Branchingmustbeperformedateachnodeofthebranch-and-boundtree,wheretheoptimalsolutiontothelinearrelaxationincludesfractionalpathvariables.Whileitisinprinciplepossibletobranchdirectlyonfractionalθωvariables,thisapproachisdifficulttoimplementinpractice.Indeed,itiseasytosetsuchvariablesequalto1butitismuchmoredifficulttoimposetheop-positedecision.Inthelattercase,caremustbetakentoensurethatthesamepathwillnotbegeneratedmorethanoncebythesubproblem.Tothispurpose,onecoulduseamodifieddynamicprogrammingalgorithmtoimplicitlyhandleforbiddenpaths,orap-shortestpathalgorithmwherepisequaltothenum-berofforbiddenpathsplusone.Thiswouldensurethegenerationofatleastonevalidpathofnegativereducedcostwheneveroneexists.Amoreconve-nientbranchingschemeconsistsofmakingdecisionsontheoriginalarcflowvariablesxkijoronsumsofthesevariables.Forexample,binarydecisionscanbemadeonthefollowingsumofvariables: xkij j∈Nk∈K wherei∈N,N⊆δ+(i),andK⊆K.Forcingthissumtobeequalto1 requiresthatsomevertexinsubsetNbevisitedimmediatelyafteribysomevehicle.If|N|=1,thenthecorrespondingvertexmustbevisitedafteribysomevehicle.If|K|=1,thenvertexiisimplicitlyassignedtovehiclek.Thespecialcase|N|=1and|K|=1isequivalenttoforcingxkij=1forsomegivenjandk.Itisworthpointingoutthatallsuchdecisionscanbehandleddirectlyatthesubproblemlevelthroughthesimpleeliminationofarcsinthenetworks. ColumngenerationwassuccessfullyappliedtotheVRPTWbyDesrochersetal.(1992)andbyKohletal.(1999).Thelatterauthorsalsousedvalidinequalitiestostrengthentheboundsobtainedbycolumngeneration.Morespecifically,let x(S)=xkij k∈Ki∈V\\Sj∈S denotetheflowintosetS⊆Nanddenotebyκ(S)theminimumnumberof vehiclesneededtoserveallcustomersinS.Thentheconstraint x(S)κ(S) (29) isavalidinequalityfortheVRPTWandiscalledaκ-pathinequality.Com-putingκ(S)isadifficultproblemwhichisequivalenttosolvingtheVRPTWonasubsetofverticeswiththeobjectiveofminimizingthenumberofvehi-clesused.Kohletal.(1999)have,infact,restrictedtheirattentiontothecase Ch.6.VehicleRouting391 κ=2.Determiningwhetherκ(S)=1foraparticularsubsetScanbeachievedbycheckingthatthecapacityofasinglevehicleissufficientandthecorre-spondingTSPTWisfeasible.ThelatterproblemisNP-hardbutcanbesolvedrelativelyquicklybydynamicprogrammingforsmallinstances.ThealgorithmofKohletal.wascapableofsolving70ofthe87Solomonshort-horizonin-stancestooptimality.CookandRich(1999)haveextendedthisapproachtothecaseκ6byusingparallelcomputingandreplacingtheTSPTWfeasibilityproblemwithaVRPTW.Theywerethusabletosolve80oftheshort-horizoninstances.Theyalsosolved30ofthe81long-horizoninstances. WhiletheconstrainedelementaryshortestpathproblemisNP-hard,therelaxationobtainedbyallowingcyclescanbesolvedbyapseudopolynomiallabelingalgorithm(see,e.g.,DesrochersandSoumis,1988).Becauseoftimewindowsandcapacityconstraints,thesecycleswillneverthelessbeoffinitelength.Thisrelaxationwillofcourseweakenthevalueofthelowerbound,butcycleeliminationprocedurescanbeusedtocircumventthisdifficulty.Aproce-dureforeliminating2-cycles(i.e.,cyclesoftheform(iji))wasfirstproposedbyHoucketal.(1980).Morerecently,IrnichandVilleneuve(2003)developedanefficientapproachtoforbidcyclesoflengthgreaterthan2.Experimentsperformedbytheauthorsshowthatk-cycleeliminationwithk3cansub-stantiallyimprovethelowerbounds.Embeddingthistechniquewithincolumngenerationenabledtheexactsolutionof15previouslyunsolvedinstancesoftheSolomonbenchmarkset. Recently,Chabrier(2006)proposedamodifiedlabelingalgorithmtohandletheconstrainedelementaryshortestpathproblemandthusobtainimprovedlowerbounds.Inthisalgorithm,bothexactandheuristicdominancerulesareconsidered.Whenevertheheuristicapproachcannotfindapathofnegativereducedcost,theexactbutslowerimplementationisused.Thisapproachhasallowedtheauthortofindtheoptimalsolutionto17previouslyunsolvedlong-horizoninstancesfromtheSolomonbenchmarkset. PromisingresultswerealsoreportedbyDannaandLePape(2003)whode-velopedacooperationschemebetweencolumngenerationandlocalsearchappliedtotheVRPTW.Duringthebranch-and-priceprocess,localsearchisregularlyappliedfromthebestknownintegersolution.Thisoftenresultsinanimprovedupperboundthatcanthenbeusedtoprunenodesintheenumer-ationtree.Furthermore,columnsassociatedwithsolutionsidentifiedduringlocalsearchcanbefedintotherestrictedmasterproblem.Thebranch-and-pricealgorithmthusbenefitsfromlocalsearchbybeingprovidedatanearlystagewithhighqualityupperbounds,resultinginasmallersearchtree.Inturn,localsearchbenefitsfrombranch-and-pricebyworkingwithavarietyofdiffer-entinitialsolutions,resultinginaneffectiveformofdiversification. 3.2.3Abranch-and-cutalgorithm Abranch-and-cutalgorithmfortheVRPTWwasdevelopedbyBardetal.(2002).AsinmostsuchalgorithmsfortheVRP,theproblemisformulatedusingtwo-indexvariablesxijequalto1ifandonlyifavehicletravelsdirectly 392J.-F.Cordeauetal. fromvertexitovertexj.Thealgorithmincorporatesfivetypesofinequali-ties:subtoureliminationconstraints,capacityconstraints,combinequalities,incompatiblepairinequalities,andincompatiblepathinequalities.AteachnodeofthesearchtreeanupperboundiscomputedbymeansoftheGreedyRandomizedAdaptiveSearchProcedure(GRASP)describedbyKontoravdisandBard(1995). Incompatiblepairinequalitiesrelyontheexistenceofvertexpairsthatcan-notbelongtothesamevehicleroute.IfiandjdenotetwoincompatibleverticesandP=(ih1h|P|−2j)isapath,thenthefollowinginequal-ityisvalid: xi1h1+xh1i+···+xh|P|−2j+xjh|P|−2|P|−2 (30) Incompatiblepathinequalitiesaresimilartoinfeasiblepairinequalitiesbuttakearcorientationsintoaccount.IfiandjaretwoverticessuchthaticannotprecedejinafeasiblevehicleroutethenthefollowinginequalityisvalidforanypathPbetweeniandj: xih1+xh1h2+···+xh|P|−2j|P|−2 (31) Theauthorspresentfourseparationheuristicstoidentifyviolatedcapacityconstraints.ThefirstisbasedonthecomputationofminimumcutsinG.ThesecondappliesagraphshrinkingheuristicsimilartothatproposedbyAraqueetal.(1994)fortheVRP.Thethirdconsistsofidentifyingconnectedcom-ponentsinGthatdonotcontainthedepot.Finally,thefourthisaheuristicproposedbyKohletal.(1999)toidentifyviolated2-pathinequalities.Heuris-ticseparationalgorithmsarealsodescribedfortheidentificationofviolatedcombinequalities,incompatiblepathinequalities,andincompatiblepairin-equalities.Thebranch-and-cutalgorithmofBard,Kontoravdis,andYuhasobtainedgoodresultsontheSolomontestinstances:all50-customerinstancesandseveral100-customerinstancesweresolvedoptimally.3.3HeuristicsfortheVRPTW BecauseofthedifficultyoftheVRPTWanditshighpracticalrelevance,thereisagenuineneedtodevelopfastalgorithmscapableofproducinggoodqualitysolutionsinshortcomputingtimes.Heuristicscanalsobeusedtopro-videupperboundsfortheexactalgorithmsdescribedintheprevioussection.ThissectiondescribesthethreemainclassesofheuristicsfortheVRPTW:constructionheuristics,improvementheuristics,andmetaheuristics. 3.3.1Constructionheuristics Routeconstructionalgorithmsworkbyinsertingcustomersoneatatimeintopartialroutesuntilafeasiblesolutionisobtained(seeSection2.3.1).Routescaneitherbeconstructedsequentiallyorinparallel.Constructional-gorithmsaremainlydistinguishedbytheorderinwhichcustomersareselectedandbythemethodusedtodeterminewhereacustomershouldbeinserted. Ch.6.VehicleRouting393 SeveralsequentialinsertionheuristicsfortheVRPTWwereproposedbySolomon(1987).Amongtheseheuristics,themostefficient,calledI1,con-sistsoffirstselectingthefarthestcustomerfromthedepotasaseedcustomer.Theremainingcustomersaretheninsertedoneatatimeintothecurrentroutebyselectingateachiterationthecustomerthatmaximizesasavingmeasure,takingintoaccountthedistancefromthedepotandthecostofinsertioninthecurrentroute.Thecustomeristheninsertedinthepositionminimizingaweightedcombinationofextradistanceandextratimerequiredtovisitthecustomer.Theprocessisrepeateduntilallcustomershavebeeninsertedoritisnolongerpossibletoinsertadditionalcustomerswithoutviolatingeitherthecapacityortimewindowconstraints.Atthispointanewrouteisinitializedbyselectinganewseedcustomerandtheprocessrepeatsitselfuntilnocustomersremain. AparallelversionofthisheuristicwaslaterdevelopedbyPotvinandRousseau(1993)whoproposedageneralizedregretmeasuretoselectthenextcustomerforinsertion.Thismeasurereflectsthecostincreaselikelytoresultifacustomerisnotassignedtotherouteminimizingtheinsertioncost.Fur-therimprovementstothesequentialheuristicofSolomon(1987)werealsodescribedbyIoannouetal.(2001)whoproposedmodifyingthecriteriaforcustomerselectionandinsertiontotakeintoaccounttheimpactoftheinser-tiononallroutedandunroutedcustomers. 3.3.2Improvementheuristics Improvementheuristicsiterativelyimproveaninitialfeasiblesolutionbyperformingexchangeswhilemaintainingfeasibility.Theprocessnormallystopswhennofurtherexchangecanbemadewithoutdeterioratingthesolu-tion.Improvementheuristicsaremainlycharacterizedbythetypeofexchangesconsideredateachiteration.Thesedefinetheneighborhoodofasolution,i.e.,thesetofsolutionsreachablefromthecurrentsolutionbyperformingasingleexchange. ThefirstimprovementheuristicsfortheVRPTW(see,e.g.,Russell,1977;BakerandSchaffer,1986)wereadaptationsofthe2-opt(Croes,1958),3-opt(Lin,1965),andOr-opt(Or,1976)edgeexchangemechanismsoriginallyin-troducedfortheTSP.Becauseoftimewindows,checkingwhetheragivenexchangemaintainsfeasibilityofthesolutioncanberathertimeconsuming.StartingwiththeworkofSavelsbergh(1985),severalattemptshavebeenmadetodevelopefficientimplementationsofneighborhoodevaluationproceduresforλ-exchanges(seealsoSolomonetal.,1988;Savelsbergh,1990,1992).Acomparisonof2-opt,3-opt,andOr-optexchangeheuristicsfortheVRPTWwasperformedbyPotvinandRousseau(1995)whoalsointroducedanewex-change,called2-opt*,aspecialcaseof2-optthatmaintainstheorientationofthesubroutesinvolvedintheexchange.Thisisaccomplishedbyremovingthelastn1customersfromaroutek1,insertingthemafterthefirstn2customersofaroutek2,andreconnectingtheinitialpartofroutek1withtheterminalpartofroutek2.AnotherexchangemechanismwasdescribedbyThompsonand 394J.-F.Cordeauetal. Psaraftis(1993)whoproposedtransferringsetsofcustomersinacyclicfashionbetweenroutes. Severalattemptshavealsobeenmadetointegrateconstructionandim-provementheuristics.Russell(1995)developedaprocedurethatembedsrouteimprovementwithinthesolutionconstructionprocess.Moreprecisely,cus-tomerscanbeswitchedbetweenroutes,androutescanbeeliminatedduringtheconstructionofthesolutionwhichisperformedbyaproceduresimilartothatofPotvinandRousseau(1993).Morerecently,CordoneandWolflerCalvo(2001)haveproposedacompositeheuristicinwhichasetofinitialsolutionsisfirstconstructedbymeansofSolomon’sI1insertionheuristicandanimprove-mentprocedureisthenappliedtoeachofthem.Thisprocedureapplies2-optand3-optexchangesandattemptstoreducethenumberofroutesbyrelocat-ingcustomers.Toescapefromlocaloptima,theheuristicalternatesbetweenanobjectiveminimizingtotaldistanceandanobjectiveminimizingtotalrouteduration(theprimaryobjectivebeinginbothcasestominimizethenumberofroutes).SeveraldeterministiclocalsearchheuristicswerealsoproposedbyBräysy(2002),basedonanewthree-phaseapproach.Inafirstphase,anini-tialsolutioniscreatedwithoneoftwoproposedrouteconstructionheuristics(acheapestinsertion-basedheuristicwithperiodicrouteimprovementsandaparallelsavingsheuristic).Thesecondphaseattemptstoreducethenumberofroutesbyapplyingalocalsearchoperatorbasedonejectionchains(see,e.g.,Glover,1992).Finally,thethirdphaseappliesOr-optexchangestoreducethetotallengthoftheroutes. 3.3.3Metaheuristics MostoftherecentresearchonapproximatealgorithmsfortheVRPTWhasconcentratedonthedevelopmentofmetaheuristics.Unlikeclassicalimprove-mentmethods,metaheuristicsusuallyincorporatemechanismstocontinuetheexplorationofthesearchspaceafteralocalminimumisencountered.Tabusearchheuristics.SomeofthefirstapplicationsoftabusearchtotheVRPTWcanbeattributedtoSemetandTaillard(1993)andtoPotvinetal.(1996)whocombinedSolomon’sinsertionheuristicswithimprovementschemesbasedonvertexandchainexchangeprocedures. AmoresophisticatedalgorithmwaslaterdevelopedbyTaillardetal.(1997)fortheVRPwithsofttimewindowsinwhichvehiclesareallowedtoarrivelateatcustomerlocationsbuttimewindowviolationsarepenalizedintheobjectivefunction.ThisheuristicreliesontheconceptofadaptivememoryintroducedbyRochatandTaillard(1995)andonthedecompositionandreconstructionproceduredevelopedbyTaillard(1993)fortheclassicalVRP.Anadaptivememoryisapoolofroutesextractedfromthebestsolutionsfoundduringthesearch.Thismemoryisfirstinitializedwithroutesproducedbyarandomizedinsertionheuristic.Ateachiterationofthemetaheuristic,asolutioniscon-structedfromtheroutesbelongingtotheadaptivememoryandisimprovedthroughtabusearch.Theroutesoftheresultingsolutionarethenstoredin Ch.6.VehicleRouting395 theadaptivememoryifthissolutionimprovesupontheworstsolutionalreadystored.Thetabusearchheuristicusesanexchangeoperator,calledCROSSex-change,whichswapssequencesofconsecutivecustomersbetweentworoutes.Individualroutesarealsooptimizedbyremovingtwoedgesfromarouteandmovingthesegmentbetweenthesetwoedgestoanotherlocationwithintheroute.AparallelcomputingimplementationofthisapproachisdescribedinBadeauetal.(1997). Ametaheuristicembeddingreactivetabusearch(see,e.g.,BattitiandTecchiolli,1994)withintheparallelconstructionheuristicofRussell(1995)wasdevelopedbyChiangandRussell(1997).Inthisimplementation,thetabulistlengthisincreasedifidenticalsolutionsoccurtoofrequentlyandisdecreasedifnofeasiblesolutioncanbefound.Usingavarietyofcustomerorderingrulesandcriteriaformeasuringthebestinsertionpoints,themetaheuristicfirstconstructssixdifferentinitialsolutionsbygraduallyinsertingcustomersandrepeatedlyapplyingtabusearchtothepartialsolutions.Thebestsolutionobtainedafterthisstepisfurtherimprovedthroughtabusearch.Exchangesareperformedbyusingsomeoftheλ-interchangesofOsman(1993):switchacustomerfromoneroutetoanotherandswaptwocustomersbelongingtodifferentroutes. Morerecently,atabusearchheuristicwasdevelopedbyCordeauetal.(2001)fortheVRPTWandtwoofitsgeneralizations:theperiodicVRPTWandthemultidepotVRPTW(seealsoCordeauetal.,1997).Inthisheuris-tic,aninitialsolutionisobtainedbymeansofamodifiedsweepheuristic.Infeasiblesolutionsareallowedduringthesearchandviolationsofcapacity,durationortimewindowconstraintsarepenalizedintheobjectivefunctionthroughdynamicallyupdatedpenaltyfactors.Ateachiterationofthetabusearch,acustomerisremovedfromitscurrentrouteandinsertedintoadif-ferentroutebyusingaleastcostinsertioncriterion.Acontinuousdiversifica-tionmechanismthatpenalizesfrequentlymadeexchangesisusedtodrivethesearchprocessawayfromlocaloptima.Finally,apost-optimizerbasedonaspecializedTSPTWheuristic(Gendreauetal.,1998)isappliedtoindividualroutes.AnimprovementtothisheuristicforthehandlingofroutedurationconstraintswasrecentlydescribedbyCordeauetal.(2004).TheheuristicwasalsoextendedbyCordeauandLaporte(2001)tohandleheterogeneousvehi-cles.OthertabusearchalgorithmsfortheVRPTWwereproposedbyBrandão(1998),SchulzeandFahle(1999),andLauetal.(2003). Geneticalgorithms.HombergerandGehring(1999)havedescribedtwoevo-lutionstrategiesfortheVRPTW.Botharebasedonthe(μλ)strategy:start-ingfromapopulationwithμindividuals,subsetsofindividualsarerandomlyselectedandrecombinedtoyieldatotalofλ>μoffspring.Eachoffspringisthensubjectedtoamutationoperator,andtheμfittestareselectedtoformthenewpopulation.Inthefirstmethod,newindividualsaregenerateddirectlythroughmutationsandnorecombinationtakesplace.Mutationsareobtainedbyperformingoneorseveralmovesfromthe2-opt,Or-opt,and 396J.-F.Cordeauetal. 1-interchangefamilies.Inthesecondmethod,offspringaregeneratedthroughatwo-steprecombinationprocedureinwhichthreeindividualsareinvolved.Inbothmethods,thefitnessofanindividualdependsfirstonthenumberofvehi-clesused,andsecondonthetotaldistancetraveled.GehringandHomberger(2002)laterproposedatwo-phasemetaheuristicinwhichthefirstphasemin-imizesthenumberofvehiclesthroughanevolutionstrategy,whilethesecondoneminimizesthetotaldistancethroughtabusearch.Aparallelizationstrat-egyisalsousedtorunseveralconcurrentsearchesofthesolutionspacewithdifferentlyconfiguredmetaheuristicscooperatingthroughtheexchangeofso-lutions. Bergeretal.(2003)havedevelopedageneticalgorithmthatconcurrentlyevolvestwodistinctpopulationspursuingdifferentobjectivesunderpartialconstraintrelaxation.Thefirstpopulationaimstominimizethetotaldistancetraveledwhilethesecondonefocusesonminimizingtheviolationsofthetimewindowconstraints.Themaximumnumberofvehiclesimposedinthefirstpopulationisequaltokminwhereasthesecondpopulationisallowedonlykmin−1vehicles,wherekminreferstothenumberofroutesinthebestknownfeasiblesolution.Wheneveranewfeasiblesolutionemergesfromthesecondpopulation,thefirstpopulationisreplacedwiththesecondandthevalueofkminisupdatedaccordingly.Tworecombinationoperatorsandfivemutationoperatorsareusedtoevolvethepopulations.Thisapproachhasprovedtoberatherefficientinminimizingthenumberofvehiclesused. Morerecently,MesterandBräysy(2005)havedevelopedaniterativemeta-heuristicthatcombinesguidedlocalsearchandevolutionstrategies.Aninitialsolutionisfirstcreatedbyaninsertionheuristic.Thissolutionisthenimprovedbytheapplicationofatwo-stageprocedure.Thefirststageconsistsofaguidedlocalsearchprocedureinwhich2-opt*andOr-optexchangesareperformedtogetherwith1-interchanges.Thislocalsearchisguidedbypenalizinglongarcsappearingofteninlocalminima.Thesecondstageiterativelyremovesaselectedsetofcustomersfromthecurrentsolutionandreinsertsthere-movedcustomersatminimumcost.Thesetwostagesarethemselvesrepeatediterativelyuntilnofurtherimprovementcanbeobtained.Verygoodresultsarereportedbytheauthorsonlarge-scaleinstances.AccordingtoBräysyandGendreau(2005b),thethreeapproachesjustdescribedseemtoproducethebestresultsamonggeneticalgorithms.OthersuchalgorithmshavealsobeenproposedbyanumberofresearchersincludingPotvinandBengio(1996),ThangiahandPetrovic(1998),andTanetal.(2001). Othermetaheuristics.KontoravdisandBard(1995)havedescribedatwo-phaseGRASPfortheVRPTW.Anumberofroutesarefirstinitializedbyselectingseedcustomers.Theremainingcustomersarethengraduallyinsertedintheroutesbyusingarandomizedleastinsertioncostprocedure.Duringthisprocess,periodicattemptsaremadetoimprovetheroutesbylocalsearch.Inthisphasecertainroutesmaybeeliminatedbymeansofadeterministicproce-durethatattemptstorelocatethecustomerstoadifferentroute.Toestimate Ch.6.VehicleRouting397 therequirednumberofroutes,theauthorshaveproposedthreelowerboundsforfleetsize.Twoarebasedonbinpackingstructuresgeneratedbythecapac-ityortimewindowconstraints.Theotherisderivedfromtheassociatedgraphcreatedbypairsofcustomershavingincompatibledemandsortimewindows.AguidedlocalsearchalgorithmfortheVRPTWwasintroducedbyKilbyetal.(1998).Inguidedlocalsearch,theobjectivefunctionisaugmentedwithapenaltytermreflectingtheproximityofthecurrentsolutionvaluetothatofpreviouslyencounteredlocalminima.Themethodisusedtodrivealocalsearchheuristicthatmodifiesthecurrentsolutionbyperformingoneoffourmoves:2-optexchangeswithinaroute,switchingacustomerfromoneroutetoanother,exchangingcustomersbelongingtotwodifferentroutes,andswap-pingtheendsoftworoutes.Allcustomersarefirstassignedtoavirtualvehicleandtheroutesfortheactualvehiclesareleftempty.Becauseapenaltyisas-sociatedwithnotvisitingacustomer,afeasiblesolutionwillbeconstructedintheprocessofminimizingcost.Thelocalsearchalgorithmstartsfromthissolutionandperformsaseriesofexchangesuntilalocalminimumisreached.Theobjectivefunctionisthenmodifiedbyaddingatermpenalizingthepres-enceofthearcsusedinthissolution.Thesearchiteratesbyfindingnewlocalminimaandaccumulatingpenaltiesuntilastoppingcriterionismet.Thisap-proachwaslatercoupledwithtabusearchandembeddedwithinaconstraintprogrammingframeworkbyDeBackeretal.(2000). Gambardellaetal.(1999)havedevelopedanantcolonyoptimizationalgo-rithmfortheVRPTWwhichassociatesanattractivenessmeasuretothearcs.Artificialantsrepresentparallelprocesseswholeroleistoconstructfeasiblesolutions.Todealwiththehierarchicalobjectiveoffirstminimizingthenum-berofvehiclesandthenminimizingdistance,twoantcoloniesareused,eachdedicatedtotheoptimizationofadifferentobjective.Thesecoloniescoop-eratebyexchanginginformationthroughpheromoneupdating.Wheneverafeasiblesolutionwithasmallernumberofvehiclesisfound,bothcoloniesarereactivatedwiththereducednumberofvehicles. BentandVanHentenryck(2004)havedescribedatwo-stagehybridalgo-rithmthatfirstminimizesthenumberofroutesbysimulatedannealingandthenminimizestotaldistancetraveledbyusingalargeneighborhoodsearch(Shaw,1998)whichmayrelocatealargenumberofcustomers.Thefirststageusesalexicographicevaluationfunctiontominimizethenumberofroutes,maximizethesumofthesquaresoftheroutesizes,andminimizetheminimaldelay(ameasureoftimewindowtightness)ofthesolution.Theneighborhoodusedinthisstageconsistsof2-opt,Or-opt,relocating,exchange,andcrossovermoves.Inthesecondstage,subsetsofcustomersareremovedfromtheircur-rentrouteandreinsertedinpossiblydifferentroutes.Customersselectedforremovalarerandomlychosenbutthealgorithmfavorscustomersthataregeographicallyclosetoeachotherandbelongtodifferentroutes.Abranch-and-boundalgorithmisthenusedtoreinsertthesecustomers. Afour-phasemetaheuristicbasedonamodificationofthevariableneigh-borhoodsearchwasdescribedbyBräysy(2003).Inthefirstphase,aninitial 398J.-F.Cordeauetal. solutioniscreatedbyusingrouteconstructionheuristics.Duringthisprocess,thepartialroutesareperiodicallyreoptimizedthroughOr-optexchanges.Inthesecondphase,anattemptismadetoreducethenumberofroutesbyapply-ingarouteeliminationoperatorbasedonejectionchains.Inthethirdphase,fourlocalsearchproceduresembeddedwithinavariableneighborhoodsearch(see,e.g.,Mladenovi´candHansen,1997)areappliedtoreducethetotaldis-tancetraveled.TheseproceduresarebasedonmodificationstotheCROSSexchangesofTaillardetal.(1997)andcheapestinsertionheuristics.Inthefourthphase,amodifiedobjectivefunctionconsideringwaitingtimeisusedbythelocalsearchoperatorsinthehopeoffurtherimprovingthesolution.Morerecently,alocalsearchalgorithmwithrestartswasalsoproposedbyLiandLim(2003).Thisalgorithmfirstconstructsaninitialsolutionbyusinganinsertionheuristic.Localsearchisthenperformedfromthissolutionus-ingthreeexchangeoperatorsthatmovesegmentsofcustomerseitherbetweenroutesorwithinthesameroute.Wheneveralocalminimumisreached,mul-tiplerestartsareperformedstartingfromthebestknownsolution,andatabulistisusedtopreventcycling. Alargenumberofothermetaheuristicsbasedonvariousparadigmshavebeendescribedinrecentyears.Foradditionalreferencesonapproximateal-gorithmsfortheVRPTWaswellasdetailedcomputationalexperiments,thereaderisreferredtorecentsurveysbyBräysyandGendreau(2005a,2005b). 4Theinventoryroutingproblem TheInventoryRoutingProblem(IRP)isanimportantextensionoftheVRPwhichintegratesroutingdecisionswithinventorycontrol.TheproblemarisesinenvironmentswhereVendorManagedInventory(VMI)resupplypoliciesareemployed.Thesepoliciesallowavendortochoosethetimingandsizeofdeliveries.Inexchangeforthisfreedom,thevendoragreestoensurethatitscustomersdonotrunoutofproduct.Inamoretraditionalrelationship,wherecustomerscallintheirorders,largeinefficienciescanoccurduetothetimingofcustomers’orders(resultinginhighinventoryanddistributioncosts).Realizingthecostsavingsopportunitiesofvendormanagedinventorypolicies,however,isnotasimpletask,particularlywithalargenumberandvarietyofcustomers.Theinventoryroutingproblemachievesthisgoalbydeterminingadistributionstrategythatminimizeslongtermdistributioncosts.Thisdescriptionofthein-ventoryroutingproblemfocusesprimarilyondistribution.Inventorycontrolisrestrictedtoensuringthatnostockoutsoccuratthecustomers.Inventorycontroltakesamoreprominentrolewheninventoryholdingcostsareconsid-ered.Intheinventorycontrolliterature,theresultingenvironmentisusuallyreferredtoasaonewarehousemultiretailersystem. InventoryroutingproblemsareverydifferentfromVRPs.Vehicleroutingproblemsoccurwhencustomersplaceordersandthevendor,onanygivenday, Ch.6.VehicleRouting399 assignstheordersforthatdaytoroutesforvehicles.InIRPs,thedeliverycom-pany,notthecustomer,decideshowmuchtodelivertowhichcustomerseachday.Therearenocustomerorders.Instead,thedeliverycompanyoperatesundertherestrictionthatitscustomersarenotallowedtorunoutofproduct.Anotherkeydifferenceistheplanninghorizon.Vehicleroutingproblemstyp-icallydealwithasingleday,theonlyrequirementbeingthatallordershavetobedeliveredbytheendoftheday.Inventoryroutingproblemsaredefinedonalongerhorizon.Eachdaythedeliverycompanymakesdecisionsaboutwhichcustomerstovisitandhowmuchtodelivertoeachofthem,whilekeepinginmindthatdecisionsmadetodayhaveanimpactonwhathastobedoneinthefuture.Theobjectiveistominimizethetotalcostovertheplanninghorizonwhileensuringthatnocustomerrunsoutofproduct.4.1DefinitionoftheIRP ThedeterministicIRPisconcernedwiththerepeateddistributionofasingleproductfromasinglefacility,toasetofncustomersoveraplanninghorizonoflengthT,possiblyinfinity.Customericonsumestheproductatarateui(sayvolumeperday)andcanmaintainalocalinventoryofproductofuptoamaximumofCi.TheinventoryatcustomeriisIi0attime0.Afleetofmho-mogeneousvehicles,withcapacityD,isavailableforthedistributionoftheproduct.Ifaquantitydiisdeliveredatcustomeri,thevendorearnsarewardequaltoridi.Ittakesavehicleatimetijtotraversearc(ij)ofthedistri-butionnetworkandacostcijisincurredwhendoingso.Theobjectiveistomaximizetheprofit(revenueminuscost)overtheplanninghorizon,withoutcausingstockoutsatanyofthecustomers.(Notethatbecauseproductusageisassumedtobedeterministicandnostockoutsareallowed,longrunrevenuesarefixedandthekeyistoreducedeliverycosts.)Adispatcherhastodecidewhentoserveacustomer,howmuchtodeliver,andwhichdeliveryroutestousetoservecustomers. InthestochasticIRPcustomerdemandsaredefinedatdiscretetimein-stantstbymeansofrandomvariables.LetUt=(U1tUnt)denotethevectorofrandomcustomerdemandsattimet.Customerdemandsondiffer-entdaysareindependentrandomvectorswithajointprobabilitydistributionFthatdoesnotchangewithtime;thatis,U0U1isanindependentandiden-ticallydistributedsequence,andFistheprobabilitydistributionofeachUt.TheprobabilitydistributionFisknowntothedecisionmaker.ThevendorcanmeasuretheinventorylevelXitofeachcustomeriatanytimet.Ateachtimeinstantt,thevendormakesadecisionthatcontrolstheroutingofvehiclesandthereplenishmentofcustomerinventories.Becausedemandisuncertain,thereisoftenapositiveprobabilitythatacustomerwillrunoutofstock,andthusshortagescannotalwaysbeprevented.Shortagesresultinapenaltypisiiftheunsatisfieddemandondaytatcustomeriissi.Unsatisfieddemandistreatedaslostdemand.Theobjectiveistoconstructadistributionpolicymax-imizingtheexpecteddiscountedprofitoveraninfinitetimehorizon. 400J.-F.Cordeauetal. 4.2Motivatingexample Toillustratethedifficultyofinventoryroutingproblems,wereproduceasmalldeterministicexampleintroducedbyFisheretal.(1982)andBelletal.(1983).TherelevantoptimaltourcostscanbederivedfromthenetworkshowninFigure1,e.g.,theoptimaltourcostsforvisitingcustomers1and2,denotedbyC12,isequalto$210.Thevehiclecapacityis5000gallonsandcustomertankcapacityandusagedata,ingallons,areasfollows: Customeri1234 di5000300020004000 ui1000300020001500 Asimpleschedulejointlyreplenishescustomers1and2aswellascustomers3and4onadailybasis.Thisscheduleisnaturalbecausecustomers1and2(3and4,respectively)areneareachother.Eachcustomerireceivesaquantityequaltoitsdailyconsumptionui.Thelong-runaveragecostofthisscheduleis420milesperday.Animprovedscheduleconsistsofacyclethatrepeatsitselfeverytwodays.Onthefirstday,onetripreplenishes3000gallonstocus-tomer2and2000gallonstocustomer3,atacostof340miles.Onthesecondday,twotripsaremade.Thefirsttripreplenishes2000gallonstocustomer1and3000gallonstocustomer2.Thesecondtripreplenishes2000gallonsto Fig.1.Afour-customerexamplewithdistancesshownonedges. Ch.6.VehicleRouting401 customer3and3000gallonstocustomer4.Eachtripcosts210miles.Theav-eragecostofthisscheduleis380milesperday,whichisnearly10%lowerthanthefirstschedule. 4.3ObservationsontheIRP Beforedescribingsolutionapproaches,wepresentsomegeneralobser-vationsconcerninginventoryroutingproblemsandsomecommonelementsfoundinmostsolutionapproaches. TheIRPisalong-termdynamiccontrolproblemwhichisextremelydifficulttosolve.Therefore,mostoftheavailablealgorithmssolveonlyashort-termplanningproblem.Inearlypublications,itwasoftenjustasingledaybutlater,short-termwasexpandedtoafewdays.Twokeyissuesneedtoberesolvedwithsuchapproaches:howtomodelthelong-termeffectofshort-termde-cisions,andwhichcustomerstoconsiderintheshort-termplanningperiod.Ashort-termapproachthatonlyminimizescostshasthetendencytodeferasmanydeliveriesaspossibletofutureplanningperiods,whichmayleadtoanundesirablesituationinthefuture.Therefore,aproperincorporationofthelong-termobjectiveintotheshort-termplanningproblemisessential.Thelong-termeffectofshort-termdecisionsneedstocapturethecostsandbenefitsofdeliveringtoacustomerearlierthannecessary.Thisusuallymeansdeliver-inglessandmayleadtohigherfuturedistributioncosts,butreducestheriskofastockoutandmaythusreducefutureshortagecosts.Decisionsregard-ingwhichcustomersneedtobeconsideredintheshort-termplanningperiodareusuallyguidedbysomemeasureoftheurgencytomakeadeliverytoacustomerandthequantitythatcanbedelivered.Usually,itisassumedthatcustomersconsideredintheshort-termplanningperiodmayactuallybevis-ited,butthedecisionwhetherornottoactuallyvisitthemstillhastobemade.Whentheshort-termplanningproblemconsistsofasingleday,theproblemcanbeviewedasanextensionoftheVRPandsolutiontechniquesfortheVRPcanbeadapted.Forexample,CampbellandSavelsbergh(2004c)havediscussedefficientimplementationsofinsertionheuristicstohandlesituationswherethedeliveryamounthastoliebetweenalowerandanupperbound,asopposedtobeingfixed.Inrelatedwork,CampbellandSavelsbergh(2004b)havestudiedtheproblemofdetermininganoptimaldeliveryscheduleforaroute,i.e.,givenasequenceofcustomervisits,determinethetimingofthevisitssoastomaximizethetotalamountoftheproductdeliveredontheroute.Becausesingledayapproachesusuallybasedecisionsonthelatestinventorymeasurementandapredictedusageforthatday,theyavoidthedifficultyofforecastinglong-termusage,whichmakestheproblemmuchsimpler.4.4Singlecustomeranalysis Itisinsightfultoanalyzethe“simple”situationinwhichthereisonlyasinglecustomer.Theresultsofthistypeofanalysiscanbeusedeffectivelytoguide 402J.-F.Cordeauetal. decisionsonwhichcustomerstoconsiderinashorttermplanninghorizon.ThematerialpresentedinthissubsectionisprimarilybasedonJailletetal.(2002),althoughmuchofitdatesbacktotheworkofDrorandBall(1987).Wefirstconsiderthedeterministiccase.Foreaseofnotation,lettheusagerateofthecustomerbeu,thestoragecapacityofthecustomerbeC,theinitialinventorylevelbeI0,thedeliverycosttothecustomerbec,andthevehiclecapacitybeQ.Itiseasytoseethatanoptimalpolicyistofillupthestoragespacepreciselyatthetimewhenitbecomesempty.ThereforethecostvTforaplanningperiodoflengthTis Tu−I0 vT=max0c min{CQ} Nowconsiderthestochasticcaseinwhichonedecidesdailywhethertomakeadeliverytothecustomerornot.ThedemandUbetweenconsecutivedecisionpoints,i.e.,thedemandperday,isarandomvariablewithknownprobabil-itydistributionandfinitemean.Assumingthatthestoragecapacityateachcustomerisatleastaslargeasthevehiclecapacityandthevendorcanonlymonitortheinventoryinthestoragespaceatthetimeofadelivery,itcanbeshownthatfortheinfinitehorizoncase,thereexistsanoptimalpolicythatfillsupthestoragespaceateachdeliveryand,followinganyscheduledorstock-outdelivery,plansthenextdeliveryddaysafter.Theoptimalreplenishmentintervaldisaconstantchosentominimizetheexpecteddailycost. Ad-daypolicymakesadeliverytothecustomereveryddaysandde-liversasmuchaspossible,unlessastockoutoccursearlier.Insuchacase,thevehicleissentrightaway,whichgeneratesacostS.Itisassumedthatdeliveriesareinstantaneous,sothatnoadditionalstockoutpenaltiesarein-curred.Furthermore,assumethatinitiallythestoragespaceisfull.Letpjbetheprobabilitythatastockoutfirstoccursondayj(1jd−1).Thenp=p1+p2+···+pd−1istheprobabilitythatthereisastockoutinperiod[1d−1].Furthermore,letvT(d)betheexpectedtotalcostofthispolicyoveraplanningperiodoflengthT.Wenowhaveford>T vT(d)=pjvT−j(d)+S 1jT andfordT vT(d)= 1jd−1 pjvT−j(d)+S+(1−p)vT−d(d)+c Asaconsequence,theexpectedtotalcostoffillingupacustomer’stankeveryddaysoveraT-dayperiod(Td)isgivenby vT(d)=α(d)+β(d)T+f(Td) Ch.6.VehicleRouting403 whereα(d)isaconstantdependingonlyond,f(Td)isafunctionthattendstozeroexponentiallyfastasTtendstoinfinity,and pS+(1−p)c β(d)= jpj1jd withpd=1−p.Thevalueβ(d)isthelong-runaveragecostperday.To determinethebestpolicyinthisclass,weneedtominimizevT(d)whichforlargeTmeansfindingavalueofdminimizingβ(d).4.5Thetwo-customerIRP Whenmorethanonecustomerisserved,theproblembecomessignificantlyharder.Notonlyisitnecessarytodecidewhichcustomerstovisitnext,butonemustalsodeterminehowtocombinethemintovehicletours,andhowmuchtodelivertoeachofthem.Evenifthereareonlytwocustomers,thesedecisionsmaynotbeeasy.ThematerialintheremainderofthissectionisprimarilybasedonCampbelletal.(1998). Ifthetwocustomersarevisitedtogether,itisintuitivelyclearthatgiventheamountdeliveredatthefirstcustomer,itisoptimaltodeliverasmuchaspossibleatthesecondone(determinedbytheremainingamountinthevehicle,andtheremainingcapacityatthesecondcustomer).Thustheproblemofdecidinghowmuchtodelivertoeachcustomerinvolvesasingledecision.However,makingthatdecisionmaynotbeeasy,asthefollowingtwo-customerstochasticIRPexampleshows. Assumetheproductisdeliveredandconsumedindiscreteunitsandthateachcustomerhasastoragecapacityof20units.Thedailydemandsofthecus-tomersareindependentandidenticallydistributed(acrosscustomersaswellasacrosstime),withP(U=0)=04andP(U=10)=06.Theshortagepenaltyiss1=1000perunitatcustomer1ands2=1005perunitatcustomer2.Thevehiclecapacityis10units.Atthebeginningofeachdaytheinventoryatthetwocustomersismeasured,andthedecisionmakerdetermineshowmuchtodelivertoeachcustomer.Therearethreepossiblevehicletours,namelytoursexclusivelytocustomers1and2,ofcost120each,andatourtobothcus-tomers1and2,ofcost180.Onlyonevehicletourcanbecompletedperday.ThissituationcanbemodeledasaninfinitehorizonMarkovdecisionprocess,withtheobjectiveofminimizingtheexpectedtotaldiscountedcost.Becauseofthesmallsizeofthestatespace,itispossibletocomputetheoptimalexpectedvalueandanoptimalpolicy. Figure2showstheexpectedvalue(totaldiscountedcost)asafunctionoftheamountdeliveredatcustomer1(andthereforealsoatcustomer2),whentheinventoryateachcustomeris7,andbothcustomersaretobevisitedinthenextvehicletour(whichistheoptimaldecisioninthegivenstate).Thefigureshowsthattheobjectivefunctionisnotunimodal,withalocalminimumat3,andaglobalminimumat7.Consequently,decidingjusthowmuchtodelivertoeachcustomermayrequiresolvinganonlinearoptimizationproblemwith 404J.-F.Cordeauetal. Fig.2.Nonunimodalobjectivefunctionfordeterminingtheoptimaldeliveryquantity. anonunimodalobjectivefunction.Thisisahardproblemforwhichavailablesearchmethodsmaynotconvergetoanoptimalsolution.4.6LiteraturereviewontheIRP RatherthanprovidingacomprehensivereviewoftheIRPliterature,wedis-cussseveralresearchstreamsrepresentingavarietyofsolutionapproachesthathavebeenproposedandinvestigated.Weencouragethereadertoexaminethereferencedpapersformoreelaborateandprecisecoverage. Afirststreamofresearchusestime-discretizedintegerprogrammingmod-elstodeterminethesetofcustomerstobevisitedinashort-termplanninghorizonaswellastheamountofproducttodelivertothem.Inordertoaccu-ratelyreflectcostsandtimerelatedaspects,theintegerlinearprogramsworkwithasetofpotentialdeliveryroutes.Fisheretal.(1982)andBelletal.(1983)pioneeredthisapproachwhentheystudiedtheIRPatAirProducts,apro-ducerofindustrialgases.Theirformulationdeterminesthedeliveryvolumestocustomers,theassignmentofcustomerstoroutes,theassignmentofvehi-cletoroutes,andthestarttimesofroutes.Thecorestructureoftheirmodelispresentedbelow,wherethevariablexirtvrepresentstheamountofproductdeliveredtocustomeri∈Nonrouter∈Rstartingattimet∈T,thevariableyrtis1ifrouterstartsattimetand0otherwise,Srthesetofcustomersvisitedonrouter,pithevalueofdeliveringaunitofproducttocustomeri,Frthefixedcostofexecutingrouter,qitalowerboundonthecumulativeamount Ch.6.VehicleRouting405 deliveredtocustomeribytimet,andqitanupperboundonthecumulativeamountthatcanbedeliveredtocustomeribytimet: maximizepixirt−Fryrt r∈Rt∈T i∈Sr subjectto xirsqitqit i∈Sr r∈Rst i∈Nt∈T xirtQyrt r∈Rt∈T xirt0yrt∈{01} Inthemodel,theperunitvalueofadeliverytoacustomerisusedtorepre-senttheeffectofdecisionsoneventsoccurringbeyondtheplanninghorizonof themodel.Intheshort-termplanningperiodconsideredbythemodel,thereisconsiderablediscretionintheamountofproducttodeliver.Inthelongrunthisamountisdeterminedbycustomerusage.Hence,eachunitscheduledfordeliverytoacustomerwithintheplanninghorizonreducestheamounttobedeliveredinthefuture.Thisisaccountedforbysettingtheunitvaluetoanestimateofthecostofdeliveringtoacustomeratapointintimeoutsidetheplanninghorizonofthemodel.Furthermore,ratherthanexplicitlyincorpo-ratingcustomerusageratesintothemodel,lowerandupperboundsonthecumulativeamounttobedeliveredtoeachcustomerineachtimeperiodintheplanninghorizonareused.Itissimple,ofcourse,toconvertcustomerusageratesintobounds,i.e.,qit=max{0tui−Ii0}andqit=tui+Ci−Ii0.Lagrangianrelaxationwasacentraltoolindevelopinganeffectiveheuristicforsolvingtheintegerprogram.Thesizeoftheintegerprogramstobesolveddependsonthechosentimediscretizationaswellasonthesizeofsetofroutes. CampbellandSavelsbergh(2004a)useanintegerlinearprogramwithasim-ilarstructuretodeterminewhichcustomerstovisitinthenextfewdays(eventhoughtheintegerprogramcoversseveralweeks)andtosuggestquantitiesanddeliverytimestothesecustomers.However,then,inasecondphase,theyusemodifiedinsertionheuristicstodeterminetheactualdeliveryroutesandquan-tities.Theadvantageofsuchatwo-phaseapproachisthatahigherdegreeofaccuracy(intermsoftimingofevents)canbeprovidedinthesecondphaseandotherpracticaldetails,suchasdriversshifts,canbeconsidered.Thedeliveryquantitiesandtimesspecifiedbythesolutiontotheintegerprogramaregoodfromalong-termperspective;theymayneedtobemodifiedsomewhattoalsobegoodfromashort-termperspective.Whenconstructingtheactualdeliveryroutes,CampbellandSavelsberghconsiderdeliveringmoretothecustomersthanthequantitysuggestedbytheintegerprogram(andslightlyalteringthedeliverytimeifneeded)sincethismayresultinhighervehicleutilizationandthushigherrevenues.AsinBardetal.(1998b)theirapproachisembeddedintoarollinghorizonframework. 406J.-F.Cordeauetal. Asecondstreamofresearchisbasedonthesinglecustomeranalysispre-sentedabove.ThisapproachwaspioneeredbyDroretal.(1985)andDrorandBall(1987).Theoptimalreplenishmentdayti∗minimizingtheexpectedtotalcostforcustomeriisusedtodeterminethesetofcustomersconsideredina ¯,thenthecustomer¯days.Ifti∗tshort-termplanningproblemforthenextt willbeincludedandwilldefinitelybevisited.Avaluectiscomputedforeachdayoftheplanningperiodtoreflecttheexpectedincreaseinfuturecostifthedeliveryismadeondaytinsteadoft∗.Ift∗T,i.e.,theoptimalreplenish-mentdayfallsoutsidetheshort-termplanningperiod,thenafuturebenefitgtcanbecomputedformakinganearlydeliverytothecustomerondaytoftheshort-termplanningperiod.Thesecomputedvaluesreflectthelongtermef-fectsofshorttermdecisions.Anintegerlinearprogramissubsequentlysolvedtoassigncustomerstoavehicleandaday,orjustaday,thatminimizesthesumofthesecostsplusthetransportationcosts.(ItwasshownbyAdelman(2004)thatthisobjectivefunctionisinfactequivalenttothatusedbyFisheretal.(1982).)Thedeliveryamounttoacustomeronaspecificdayisfixedandsettothequantityneededtofillupthestoragetankonthatday.ThisleaveseitherTSPsorVRPstobesolvedinthesecondstage.TheseideasareextendedandimprovedinTrudeauandDror(1992).ThemostrecentworkalongtheselinesisthatofBardetal.(1998a,1998b)whoworkwitharollinghorizonapproachinwhichashorttermplanningproblemisdefinedforatwo-weekperiod,butonlythedecisionsforthefirstweekareimplemented.Inaddition,satellitefa-cilitiesareconsidered,i.e.,locationsotherthanthedepotwherevehiclescanberefilled. Athirdstreamofresearchfocusesontheasymptoticanalysisofdeliverypolicies.AnilyandFedergruen(1990,1991,1993)analyzefixedpartitionpoli-ciesfortheIRPwithanunlimitednumberofvehicles.Customerswithinthesamepartitionaredividedintoregionssoastomakethedemandofeachre-gionroughlyequaltoavehicleload.Acustomermayappearinmorethanoneregion,butthenacertainpercentofhisdemandisallocatedtoeachregion.Whenonecustomerinaregionisalsovisited,allothercustomersinthatre-gionarealsovisited.Theauthorsdeterminelowerandupperboundsontheminimumlong-runaveragecostoverallfixedpartitionpolicies,andproposeaheuristic,calledmodifiedcircularregionalpartitioning,tochooseafixedparti-tion.Usingsimilarideas,GallegoandSimchi-Levi(1990)evaluatethelong-runeffectivenessofdirectdeliveries(onecustomeroneachroute).Directship-pingisshowntobeatleast94%effectiveoverallinventoryroutingstrategieswhenevertheminimaleconomiclotsizeisatleast71%ofvehiclecapacity.Thisindicatesthatdirectshippingbecomesanundesirableandcostlypolicywhenmanycustomersrequiresignificantlylessthanavehicleload,makingmorecomplicatedroutingpoliciestheappropriatechoice.AnotheradaptationoftheseideascanbefoundinBramelandSimchi-Levi(1995)whoconsideravariantoftheIRPinwhichcustomerscanholdanunlimitedamountofin-ventory.Toobtainasolution,theytransformtheproblemintoaCapacitatedConcentratorLocationProblem(CCLP),solveit,transformthesolutionback Ch.6.VehicleRouting407 intoasolutiontotheIRP,andheuristicallyimproveit.TheCCLPsolutionwillpartitionthecustomersintodisjointsets,whichintheIRPwillbecomethefixedpartitions.Chanetal.(1998)analyzezero-inventoryorderingpolicies,inwhichacustomer’sinventoryisreplenishedonlywhenithasbeendepleted,incombinationwithfixedpartitioningroutingpoliciesandderiveasymptoticworst-caseboundsontheirperformance.GaurandFisher(2004)consideranIRPwithtimevaryingdemand.Theyproposearandomizedheuristictofindafixedpartitionpolicywithperiodicdeliveries.Theirmethodwasimplementedforasupermarketchain. ThefourthstreamofresearchisbasedonformulatingthestochasticIRPasaMarkovdecisionprocessandthusexplicitlyincorporatingdemandun-certainty.ThisapproachwaspioneeredbyMinkoff(1993)whoproposedadecompositionheuristictoovercomethecomputationaldifficultiescausedbylargestatespaces.Theheuristicsolvesalinearprogramtoallocatejointtrans-portationcoststoindividualcustomersandthensolvesindividualcustomersubproblems.Thevaluefunctionsofthesubproblemsareaddedtoapproxi-matethevaluefunctionoftheoriginalproblem.Themainlimitationoftheproposedapproachisthatitassumestheavailabilityofasetofdeliveryrouteswithfixeddeliveryquantitiesforthecustomersonarouteandthedispatcheronlyhastodecidewhichofthedeliveryroutestouseateachdecisionpoint.ThislimitationisremovedintheworkofKleywegtetal.(2002,2004)onap-proximatedynamicprogrammingapproachesandinthatofAdelman(2003a,2004)onprice-directedapproaches.Letstatex=(x1x2xn)representthecurrentinventoryateachcustomer,andletA(x)denotethesetofallfeasi-bledecisionswhentheprocessisinstatex.Adecisiona∈A(x)specifieswhichcustomerinventoriestoreplenish,howmuchtodeliverateachcustomerloca-tion,andhowtocombinecustomersintovehicleroutes.LetQbetheMarkovtransitionfunctionaccordingtowhichtransitionsoccur.Letg(xa)denotetheexpectedsinglestagenetrewardiftheprocessisinstatexattimetanddecisiona∈A(x)isimplemented.Theobjectiveistomaximizetheexpectedtotaldiscountedvalueoveraninfinitehorizon.LetV∗(x)denotetheoptimalexpectedvaluegiventhattheinitialstateisx.Then,foranystatex, V∗(x)=supg(xa)+αV∗(y)Q[dy|xa](32) a∈A(x) Apolicyπ∗iscalledoptimalifVπ=V∗,whereVπrepresentsthevalue functionofpolicyπ.SolvingaMarkovdecisionprocessinvolvescomputingtheoptimalvaluefunctionV∗andanoptimalpolicyπ∗bysolvingtheoptimalityequation(32).Thisrequiresperformingthefollowingmajorcomputationaltasks: (1)ThecomputationoftheoptimalvaluefunctionV∗.Mostalgorithmsfor computingV∗involvethecomputationofsuccessiveapproximationstoV∗(x)foreverystatex.Thesealgorithmsarepracticalonlyifthestatespaceissmall. ∗ 408J.-F.Cordeauetal. (2)Theestimationoftheexpectedvalue(theintegralin(32)).Forthesto-chasticIRP,thisisahighdimensionalintegral.Conventionalnumericalintegrationmethodsarenotpracticalforthecomputationofsuchhigh-dimensionalintegrals. (3)Themaximizationproblemontheright-handsideof(32)hastobe solvedtodeterminetheoptimaldecisionforeachstate.Forthesto-chasticIRP,thismeanssolvingacomplexvariantoftheVRP.Kleywegt,Nori,andSavelsberghdevelopapproximationmethodstoeffi-cientlyperformthesecomputationaltasks.Furthermore,theirapproachhastheabilitytohandleafinitefleetofvehicles,whereasinotherMarkovdecisionprocessbasedapproachesitisassumedthatthereexistsaninfinitefleetofve-asfollows.First,hicles.TheoptimalvaluefunctionV∗isapproximatedbyV thestochasticIRPisdecomposedintosubproblemsdefinedforspecificsubsetsofcustomers.EachsubproblemisalsoaMarkovdecisionprocess.Thesubsetsofcustomersdonotnecessarilypartitionthesetofcustomers,butmustcoverit.Theideaistodefineeachsubproblemsothatitprovidesanaccuraterep-resentationoftheoverallprocessasexperiencedbythesubsetofcustomers.Todoso,theparametersofeachsubproblemaredeterminedbysimulatingtheoverallstochasticIRPprocess,andbyconstructingsimulationestimatesofsubproblemparameters.Next,eachsubproblemissolvedoptimally.Finally, (x)isdeterminedbychoosingaforanygivenstatex,theapproximatevalueV (x)equaltothesumoftheoptimalpartitionofthecustomersandbysettingV valuefunctionsofthesubproblemscorrespondingtothepartitionatstates (x).Randomizedcorrespondingtox.ThepartitionischosentomaximizeV methods,incorporatingvariancereductiontechniquestolimittherequiredsamplesize,areusedtoestimatetheexpectedvalueontheright-handsideof(32).Actiondeterminationinvolvesdecidingwhichcustomerstovisitonarouteandhowmuchtodelivertothem.Thisisachievedthroughaheuristic.Aninitialsolutionconsistingofonlydirectdeliveryroutesisconstructed.Thisisfollowedbyalocalsearchprocedurethatexaminesthebenefitofaddingacustomertoanexistingrouteandmodifyingthedeliveryquantities.UsingtheirapproachKleywegt,Nori,andSavelsberghcansolveproblemsinvolvingupto50customers. Morerecently,Adelman(2003a,2004)proposedaprice-directedoperatingpolicybasedonasimpleeconomicmechanismtodetermineroutingandde-liverydecisionsforagiveninventorystate.SupposemanagementspecifiesavalueViforreplenishingoneunitofproductatcustomeri.Adispatchercannowevaluateafeasibledeliveryrouteasfollows.IfasetS={s1sn}ofcus-tomersisvisited,quantitiesd1dnaredelivered,andacostcSisincurred.Thenthenetvalueoftherouteequalsi∈SVidi−cS.Thedispatcherhastochoosedeliveryroutessoastomaximizehistotalnetvaluewithoutstockoutsatcustomers.Thismechanismmotivatesthedispatchertoreplenishacustomeriwhosecurrentinventorylevelislow,becausethendicanbesetlarge.WhenfacedwiththeoptionofexpandingthesetSofcustomerstovisitonaroute Ch.6.VehicleRouting409 whichdoesnotyetusethefullvehiclecapacity,thedispatcherwillconsidertheincrementalcostcS∪{k}−cSanddetermineifaquantitydkcanbereplen-ishedthatislargeenoughtojustifyit,i.e.,whetherdkVk−(cS∪{k}−cS)>0ordk(cS∪{k}−CS)/Vk. Thekeytosuccessinsolvingmanagement’sproblemistosettheVi’sinsuchawaythatthedispatcherismotivatedto(ideally)minimizethelong-runtimeaveragereplenishmentcosts.Ifthedispatcher’stotalnetvalueisregularlypositive,thenhisperformanceexceedsmanagement’slongrangeexpectations.ManagementshoulddecreasetheVi’stomakethemconsistentwithactualper-formance.Ontheotherhand,ifthedispatcher’stotalnetvalueisregularlynegative,thentheVi’simposeunrealisticexpectationsonthedispatcherandmanagementshouldincreasethem.Ideally,managementshouldsettheVi’sequaltothelowestachievablemarginalcosts. Startingfromadynamiccontrolmodeloftheinventoryroutingproblem,Adelman(2003b)derivesthefollowingnonlinearprogrammingrelaxation,whichcomputesalongrun“average”solutiontotheinventoryroutingprob-lem.LetzRbeadecisionvariablerepresentingtherateatwhichasubsetRofcustomersisvisitedtogether.Furthermore,letdiRforalli∈Rbeade-cisionvariablerepresentingtheaveragequantitydeliveredtocustomerionadeliveryroutevisitingsubsetR.Thisyieldsthefollowingformulation: (NLP)minimize(33)CRzR R⊆N subjectto diRzR=ui R⊆N i∈N(34)(35)(36)(37) i∈R diRQR⊆N diRCizRdiR0 R⊆Ni∈RR⊆Ni∈R Theobjective(33)minimizesthelongrunaveragereplenishmentcost.Con-straints(34)statethatforeachcustomeritherateatwhichquantitiesarereplenishedmustequaltherateatwhichtheyareconsumed.Constraints(35)statethatonaveragevehiclecapacityissatisfied,andconstraints(36)statethatonaveragethequantitydeliveredatcustomeriislessthanthestoragecapacity.Considerthefollowinglinearprogram uiVi(D)maximize(38) i∈N subjectto diRViCR i∈R R⊆N(39) 410J.-F.Cordeauetal. withdecisionvariablesVi.Adelmanshowsthatthissemi-infinitelinearpro-gramisdualtothenonlinearprograminthatthereisnodualitygapbetweenthemandaversionofcomplementaryslacknessholds.In(NLP)diRisade-cisionvariablewhilein(D)itispartoftheinput.ThedecisionvariablesViatoptimalityarethemarginalcostsassociatedwithsatisfyingconstraints(34)of(NLP).ThismeansthatatoptimalityuiViisthetotalallocatedcostrateforreplenishingcustomeriinanoptimalsolutionto(NLP).EachVicanbeinter-pretedasthepaymentmanagementtransferstothedispatcherforreplenishingoneunitofproductofcustomeri.Hence,theobjective(38)maximizestheto-taltransferrate,subjecttotheconstraint(39)thatthepaymentscanbenolargerthanthecostofanyreplenishment.NLPcanbesolvedeffectivelybymeansofcolumngenerationtechniques. Wehaveoptedtofocusononlyafewresearchstreamswithanemphasisonmorerecentefforts.However,manyotherresearchershavecontributedtotheinventoryroutingliterature,includingFedergruenandZipkin(1984),Goldenetal.(1984),Burnsetal.(1985),Larson(1988),Chienetal.(1989),WebbandLarson(1995),Barnes-SchusterandBassok(1997),HererandRoundy(1997),ViswanathanandMathur(1997),ChristiansenandNygreen(1998a,1998b),Christiansen(1999),Reimannetal.(1999),Walleretal.(1999),ÇetinkayaandLee(2000),Lauetal.(2002),Bertazzietal.(2002),SavelsberghandSong(2005),andSongandSavelsbergh(2005).5Stochasticvehicleroutingproblems StochasticVehicleRoutingProblems(SVRPs)areextensionsofthedeter-ministicVRPinwhichsomecomponentsarerandom.Thethreemostcommoncasesare: (1)stochasticcustomers:customeriispresentwithprobabilitypiandab-sentwithprobability1−pi; (2)stochasticdemands(tobecollected,say):thedemandξiofcustomeri isarandomvariable; (3)stochastictimes:theservicetimesiofcustomeriandthetraveltimetij ofedge(ij)arerandomvariables.Becausesomeofthedataarerandomitisnolongerrequiredtosatisfytheconstraintsforallrealizationsoftherandomvariables,andnewfeasibilityandoptimalityconceptsarerequired.Withrespecttotheirdeterministiccounter-parts,SVRPsareconsiderablymoredifficulttosolve.Notonlyisthenotionofasolutiondifferent,butsomeofthepropertiesthatwerevalidinadetermin-isticcontextnolongerholdinthestochasticcase(see,e.g.,Droretal.,1989;Gendreauetal.,1996). ApplicationsofSVRPariseinanumberofsettingssuchasthedeliveryofmealsonwheels(Bartholdietal.,1983)orofhomeheatingoil(Droretal.,1985),sludgedisposal(Larson,1988),forkliftroutinginwarehouses Ch.6.VehicleRouting411 (Bertsimas,1992),moneycollectioninbankbranches(Lambertetal.,1993),andgeneralpickupanddeliveryoperations(Hvattumetal.,2006). StochasticVRPscanbeformulatedandsolvedinthecontextofstochasticprogramming:afirststageorapriorisolutioniscomputed,therealizationsoftherandomvariablesarethendisclosedand,inasecondstage,arecourseorcorrectiveactionisappliedtothefirststagesolution.Therecourseactionusuallygeneratesacostorasavingwhichmaybetakenintoaccountwhende-signingthefirststagesolution.Toillustrate,consideraplannedvehiclerouteinanSVRPwithstochasticdemands.Becausedemandsarestochastic,thevehi-clecapacitymaybeattainedorexceededatsomecustomerjbeforetherouteiscompleted.Inthiscaseseveralpossiblerecoursepoliciesarepossible.Forex-ample,thevehiclecouldreturntothedepottounloadandresumecollectionsatcustomerj(ifthevehiclecapacitywasexceededatj)oratthesuccessorofjontheroute(ifthevehiclecapacitywasattainedexactlyatj).Anotherpolicywouldbetoplanpreventivereturntripstothedepotinthehopeofavoidinghighercostsatalaterstage(see,e.g.,LaporteandLouveaux,1990;Droretal.,1993;Yangetal.,2000).Amoreradicalpolicywouldbetore-optimizetheroutesegmentfollowingjuponarrivalatthedepot(see,e.g.,BastianandRinnooyKan,1992;Secomandi,1998;Haughton,1998,2000).Thebestchoiceofarecoursepolicydependsonthetimeatwhichinformationbe-comesavailable.Forexample,informationaboutacustomerdemandmayonlybeavailableuponarrivingatthatcustomerorwhenvisitingthepreviouscus-tomer,thusallowingforawiderrangeofrecourseactions,suchasreturningtothedepotinanticipationoffailureorpostponingthevisitofahighdemandcustomer.Anextensivediscussionofrecoursepoliciesinthecontextofavail-abilityofinformationisprovidedinDroretal.(1989). Thereexisttwomainsolutionconceptsinstochasticprogramming.InChanceConstrainedProgramming(CCP)thefirststageproblemissolvedun-dertheconditionthattheconstraintsaresatisfiedwithsomeprobability.Forexample,onecouldimposeafailurethresholdα,i.e.,plannedvehicleroutesshouldfailwithprobabilityatmostequaltoα.Thecostoffailureistypicallydisregardedinthisapproach.StewartandGolden(1983)haveproposedthefirstCCPformulationfortheVRPwithstochasticdemands.Usingathree-indexmodeltheyshowedthatprobabilisticconstraintscouldbetransformedintoadeterministicequivalentform.Laporteetal.(1989)laterproposedasimilartransformationforatwo-indexmodel.Theinterestofsuchtransfor-mationsisthatthechanceconstrainedSVRPcanthenbesolvedusinganyofthealgorithmsavailableforthedeterministiccase.InStochasticProgrammingwithRecourse(SPR)twosetsofvariablesareused:first-stagevariableschar-acterizethesolutiongeneratedbeforetherealizationoftherandomvariables,whilesecond-stagevariablesdefinetherecourseaction.Thesolutioncostisde-finedasthesumofthecostofthefirst-stagesolutionandthatoftherecourseaction.TheaimofSPRistodesignafirst-stagesolutionofleastexpectedtotalcost. 412J.-F.Cordeauetal. StochasticVRPsareusuallymodeledandsolvedwiththeframeworkofapriorioptimization(Bertsimasetal.,1990)orasMarkovdecisionprocesses(Droretal.,1989).Apriorioptimizationcomputesafirst-stagesolutionofleastexpectedcostunderagivenrecoursepolicy.ThemostfavoredapriorioptimizationmethodologyistheintegerL-shapedmethod(LaporteandLou-veaux1993,1998)whichbelongstothesameclassasBendersdecomposition(Benders,1962)andtheL-shapedmethodforcontinuousstochasticprogram-ming(VanSlykeandWets,1969).Whileroutereoptimizationispreferabletoapriorioptimizationfromasolutioncostpointofview,itiscomputationallymorecumbersome.Incontrast,apriorioptimizationentailssolvingonlyoneinstanceofanNP-hardproblemandproducesamorestableandpredictablesolution(Bertsimasetal.,1990).ItisalsosuperiortosolvingadeterministicVRPinstancewithexpecteddemands(Louveaux,1998). TheintegerL-shapedmethodisessentiallyavariantofbranch-and-cut.Itoperatesonacurrentproblemobtainedbyrelaxingintegralityrequirementsandsubtoureliminationconstraints,andbyreplacingthecostofrecourseQ(x)offirst-stagesolutionxbyalowerboundθonitsvalue.Integralityandsubtoureliminationconstraintsaregraduallysatisfiedasiscommonlydoneinbranch-and-cutalgorithmsforthedeterministicVRP(see,e.g.,NaddefandRinaldi,2002)whilelowerboundingfunctionalsonθ,calledoptimalitycuts,areintro-ducedintotheproblematintegerorfractionalsolutions.ThemethodassumesthatalowerboundLonθisavailable.Inthefollowingdescriptionxijisabinaryvariableequalto1ifandonlyifedge(ij)isusedinthefirststagesolution. Step0.Settheiterationcountν:=0andintroducetheboundingconstraint ¯ofthebestknownsolutionθLintothecurrentproblem.Setthevaluez equalto∞.Atthisstage,theonlyactivenodecorrespondstotheinitialcurrentproblem. Step1.Selectapendentnodefromthelist.Ifnoneexistsstop. Step2.Setν:=ν+1andsolvethecurrentproblem.Let(xνθν)beanoptimal solution. Step3.Checkforanysubtoureliminationconstraintviolation.Ifatleastone violationcanbeidentified,introduceasuitablenumberofsubtourelimina-tionconstraintsintothecurrentproblem,andreturntoStep2.Otherwise, ¯,fathomthecurrentnodeandreturntoStep1.ifcxν+θνz Step4.Ifthesolutionisnotinteger,branchonafractionalvariable.Append thecorrespondingsubproblemstothelistofpendentnodesandreturntoStep1. ¯,setz¯:=zν.Step5.ComputeQ(xν)andsetzν:=cxν+Q(xν).Ifzν Otherwise,imposetheoptimalitycut ν xij−xνθL+Qx−L(40)ij+1 1 intothecurrentproblemandreturntoStep2. Theoptimalitycut(40)usesthefactthatafeasiblesolutionisfullychar-acterizedbythexijvariablesassociatedwithedgesnonincidenttothedepot.Theystatethateitherthecurrentsolutionmustbemaintained,inwhichcasethecutbecomesθQ(xν),oranewsolutionmustbeidentified,inwhichcasethecutbecomesθLorlessandisthusredundant. Markovdecisionmodelsaredefinedonastatespace.Thesystemisob-servedatvarioustransitiontimescorrespondingtomomentsatwhichanewcustomerisvisited,andnewdecisionsaretakenatthesemoments.Thestateofthesystematagiventransitiontimeisdescribedbythesetofcustomersalreadyvisitedbythevehicleandbyitscurrentload.Becausethestatespaceistypicallyverylarge,thisapproachcanonlybeappliedtorelativelysmallscaleinstances. HeuristicsforSVRPsareadaptationsofmethodsoriginallydesignedforthedeterministiccase,whichcanberatherintricatebecauseoftheprobabilitycomputationsinvolved.Inparticular,computingtheexpectedcostofavehiclerouteisitselfcomplicatedanditmaybeadvisabletouseapproximationsifsuchcomputationsaretobeperformedrepeatedlywithinasearchprocess(see,e.g.,Gendreauetal.,1996).InwhatfollowswestudysomeparticularclassesofSVRPs. 5.1Thevehicleroutingproblemwithstochasticcustomers Invehicleroutingproblemswithstochasticcustomerseachvertexiispresentwithprobabilitypi.Afirst-stagesolutionconsistsofasetofvehicleroutesvisitingthedepotandeachcustomerexactlyonce.Thesetofabsentcustomersisthenrevealedandthesecond-stagesolutionconsistsoffollowingthefirst-stagerouteswhileskippingtheabsentvertices.Jaillet(1985)laidthefoundationsofthislineofresearchinhisstudyoftheTravelingSalesmanProb-lemwithStochasticCustomers(TSPSC).Heproposedmathematicalmodelsandbounds,andheinvestigatedanumberofpropertiesoftheproblem.Forexample,heshowedthatthesolutionofadeterministicTSPcanbearbitrarilybadfortheTSPSC.Also,eveniftheTSPSCisdefinedinaplanewithEuclid-eandistances,anoptimalcyclemaycrossitself,contrarytowhathappensfortheTSP(Flood,1956).Jézéquel(1985)andRossiandGavioli(1987)haveproposedanumberofheuristicsfortheTSPSCbasedonadaptationsoftheClarkeandWright(1964)savingsprinciple.Bertsimas(1988)andBertsimasandHowell(1993)laterinvestigatedfurtherpropertiesoftheTSPSCandpro-posednewheuristics,namelymethodsbasedonspacefillingcurves(BartholdiandPlatzman,1982)andona2-optedgeinterchangemechanism.ThefirstexactalgorithmfortheTSPSCisanintegerL-shapedalgorithmdevelopedbyLaporteetal.(1994)andcapableofsolvinginstancesinvolvingupto50cus-tomers.AnextensionoftheTSPSC,calledthePickupandDeliveryTravelingSalesmanProblemwithStochasticCustomers(PDTSPSC),wasrecentlyin-vestigatedbyBeraldietal.(2005).Inthisproblemtherearenrequests,each 414J.-F.Cordeauetal. consistingofapickuplocationandofadeliverylocation,butrequestionlyma-terializeswithprobabilitypi.Theauthorsshowhowtoefficientlyimplementalowcomplexityinterchangeheuristicforthisproblem. TheVehicleRoutingProblemwithStochasticCustomers(VRPSC)hasbeenmostlystudiedinthecontextofunitdemandcustomers.AsintheTSPSC,vehiclesfollowthefirst-stagerouteswhileskippingtheabsentcustomersandreturntothedepottounloadwhentheircapacityisreached.ThisproblemwasfirststudiedbyJézéquel(1985),Jaillet(1987),andJailletandOdoni(1988).ThelatterreferencestatestwointerestingpropertiesoftheVRPSC: (1)eveniftravelcostsaresymmetrictheoverallsolutioncostisdependent onthedirectionoftravel; (2)largervehiclecapacitiesmayyieldlargersolutioncosts. Bertsimas’PhDthesis(Bertsimas,1988)isanexcellentsourceofinforma-tiononthisproblem.Itdescribesseveralproperties,boundsandheuristics.Waters(1989)hasstudiedthecaseofgeneralintegerdemandsandhascom-paredthreesimpleheuristicsforthisproblem. 5.2Thevehicleroutingproblemwithstochasticdemands TheVehicleRoutingProblemwithStochasticDemands(VRPSD)hasbeenthemoststudiedstochasticVRP.Inthisproblemcustomerdemandsareran-domandusually(butnotalways)independent.Tillman(1969)wasprobablythefirsttostudythisprobleminamultidepotcontext.Heproposedasavingsbasedheuristicforitssolution.Thefirst,majorstudyoftheVRPSDcanbeattributedtoGoldenandStewart(1978)whopresentedachanceconstrainedmodelandtworecoursemodels.Inthefirstoftheseapenaltyproportionaltovehicleovercapacityisimposed;inthesecond,thepenaltyisproportionaltotheexpecteddemandinexcessofthevehiclecapacity.Severalbasicheuris-ticswereimplementedandtested.DrorandTrudeau(1986)developedfurtherheuristicsandshowedthatforthisproblemexpectedtravelcostdependsonthedirectionoftraveleveninthesymmetriccase.Again,Bertsimas’thesis(1988)constitutesamajorcontributiontothestudyoftheVRPSD.Itproposesseveralbounds,asymptoticresultsandpropertiesforthecasewhereξiisequalto1withprobabilitypi,andequalto0otherwise.Intheirsurveypaper,Droretal.(1989)haveshownthatsomepropertiesestablishedbyJaillet(1985,1988)andJailletandOdoni(1988)extendtotheVRPSC,namely(1)inanoptimalsolu-tionavehicleroutemayintersectitself;(2)inaEuclideanproblemcustomersarenotnecessarilyvisitedintheorderinwhichtheyappearontheconvexhullofvertices;(3)segmentsofanoptimalroutearenotnecessarilyoptimalwhenconsideredseparately.ThelatterpropertycanhaveamajorimpactonthedesignofadynamicalgorithmfortheVRPSD. Laporteetal.(1989)proposedatwo-indexchanceconstrainedmodelfortheVRPSCaswellasanassociatedbranch-and-cutalgorithmcapableofsolv-inginstanceswithn30.Theyalsointroducedaboundedpenaltymodelin Ch.6.VehicleRouting415 whichthecostofrecourseassociatedwithagivenroutecannotexceedapre-setproportionofthefirst-stageroutecost.ThebestexactsolutionapproachfortheVRPSDisagaintheintegerL-shapedalgorithm.Séguin(1994)andGendreauetal.(1995)proposedthefirstimplementationofthismethodforthesolutionoftheVRPSDandwereabletosolveinstancesofupto70vertices.Themostdifficultcaseariseswhentheexpectedfillingratefofthevehiclesislarge.Forexample,whenf=03instanceswithn=70canbesolvedoptimally,butwhenf=10instanceswithn=10canrarelybesolved.Us-ingasimilarapproach,HjorringandHolt(1999)solvedone-vehicleinstances(m=1)with095f105andn=90.Laporteetal.(2002)imposedanadditionalrestriction,namelythattheexpecteddemandofaroutedoesnotexceedthevehiclecapacity,andtheyalsoexploitedpropertiesofthedemandunderknowndistributions(Poissonandnormal)inthegenerationoflowerboundingfunctionalsonthecostofrecourse.Thisenabledthemtosolvelargerinstances:forPoissondemandstheysolvedinstanceswithf=09,m=4,andn=25,orwithm=2andn=100;fornormaldemandstheysolvedinstanceswithf=09,m=3,andn=50. DynamicprogrammingwasappliedbySecomandi(1998)totheVRPwithstochasticdemands.Thelargestinstancesolvedtooptimalitywiththismethodcontainedonly10customers.TheauthoralsodevelopedNeuro-DynamicPro-gramming(NDP)algorithms(Secomandi,1998,2000,2003)forthesameprob-lem.Neuro-dynamicprogramming(see,e.g.,Bertsekas,1995)isaheuristicapproachusedtosolvelarge-scaledynamicprograms.Itreplacesthe“cost-to-go”computationsbyproxiesbasedonsimulationandparametricfunctionapproximations.Secomandi(2000)comparedtwoNDPimplementationsfortheVRPwithstochasticdemands:anoptimisticapproximateiterationpolicyinwhichaneuralnetworkmethodologyisusedtocomputetheapproxima-tions,andarolloutpolicyinwhichthecost-to-goisapproximatedbymeansofaheuristic.Computationalresultsshowthatthesecondofthesetwopoliciesisconsistentlyandsubstantiallysuperiortothefirst. 5.3ThevehicleroutingproblemwithstochasticcustomersanddemandsTheVRPwithstochasticcustomersanddemandscombinestwodifficultcases.ThisproblemwasfirstmentionedbyJézéquel(1985),Jaillet(1987),JailletandOdoni(1988),andwaslaterformallydefinedbyBertsimas(1992).Afirst-stagesolutionvisitingallcustomersisfirstconstructed,thesetofpresentcustomersisthenrevealedandtheirdemandbecomesknownuponthearrivalofthevehicleatthecustomer’slocation,routesarefollowedasplannedbutabsentcustomersareskippedandthevehiclereturnstothede-pottounloadwheneveritscapacitybecomesattained.BentonandRossetti(1992)proposedanalgorithmwhichperformsroutereoptimizationswheneverdemandsarerevealed.Onemajordifficultyinsolvingthisproblemliesinthecomputationoftheobjectivefunctionvalue.Recursions,bounds,asymptoticresults,andacomparisonofvariousreoptimizationpoliciesareprovidedby 416J.-F.Cordeauetal. Bertsimas(1992).Séguin(1994)andGendreauetal.(1995)developedthefirstexactalgorithmforthisproblem,basedagainontheintegerL-shapedap-proach.Theysolvedinstancesinvolvingupto46customersandconcludedthatstochasticcustomersareafarmorecomplicatingfactorthanarestochasticde-mands.Inadifferentstudy,Gendreauetal.(1996)developedatabusearchalgorithmwhichusesanapproximationoftheobjectivefunctioncostinordertoeasecomputations.Onasetof825instanceswith6n46forwhichtheoptimumwasknown,anoptimalsolutionwasidentifiedin89.45%ofthecasesandtheaverageoptimalitygapwas0.38%. 5.4Thevehicleroutingproblemwithstochastictraveltimes IntheVehicleRoutingProblemwithStochasticTravelTimes(VRPSTT)traveltimesontheedgesandservicetimesattheverticesarerandomvari-ables.Vehiclesfollowtheirplannedroutesandmayincurapenaltyiftheroutedurationexceedsagivendeadline.Itisnaturaltomakethispenaltypropor-tionaltotheelapsedroutedurationinexcessofthedeadline(Laporteetal.,1992).Anotherpossibilityistodefineapenaltyproportionaltotheuncollecteddemandwithinthetimelimit,asisthecaseinamoneycollectionapplicationstudiedbyLambertetal.(1993). ThesimplestcaseoftheVRPSTTistheTravelingSalesmanProblemwithStochasticTravelTime(TSPSTT)inwhichthereisonlyonevehicle.ItwasfirststudiedbyLeipälä(1978)whocomputedtheexpectedlengthoftourswithrandomtraveltimes.AcommonversionoftheTSPSTTisthecasewheretheobjectiveistodesignatourhavingthelargestprobabilityofbeingcompletedwithinthedeadline.Kao(1978)proposedtwoheuristicsforthisproblem:onebasedondynamicprogrammingandtheotheronimplicitenumeration.Sniedovich(1981)hasshownthatdynamicprogrammingappliedtothesameproblemcanbesuboptimalbecausethemonotonicitypropertyrequiredforthismethodisnotsatisfiedintheTSPSTT.Carrawayetal.(1989)laterdevel-opedaso-calledgeneralizeddynamicprogrammingalgorithmthatovercomesthisdifficulty.KenyonandMorton(2003)haveshownthatanoptimalTSPSTTcanbeidentifiedbysolvingadeterministicTSPinwhichthetravelandservicetimesarereplacedbytheirmeanvalues.Verweijetal.(2003)havedevelopedaheuristicforthecasewhereapenaltyproportionaltoroutedurationinexcessofthedeadlineisincurred.Themethodusesasampleaverageapproximationtechniqueinwhichasampleofinstancerealizationsisdrawnandeachissolvedoptimallybymeansofadeterministictechnique.Byrepeatingthemethodwithdifferentsamplesastatisticalestimateoftheoptimalitygapcanbecomputed.Laporteetal.(1992)wereprobablythefirsttoprovideexactalgorithmsfortheVRPSTT.Theyformulatedthechanceconstrainedversionoftheproblem,andtheymodeledarecourseversionoftheprobleminwhichapenaltypropor-tionaltoroutedurationinexcessofthedeadlineisincurred.TheproblemwassolvedoptimallybymeansofanintegerL-shapedalgorithmfor10n20 Ch.6.VehicleRouting417 andtwotofivetraveltimescenarios(eachscenariocorrespondstoadiffer-enttravelspeedfortheentirenetwork).Inamorerecentstudy,KenyonandMorton(2003)haveinvestigatedpropertiesofVRPSTTsolutionsandhavedevelopedboundsontheobjectivefunctionvalue.Theyhavedevelopedaheuristicthatcombinesbranch-and-cutandMonteCarlosimulationwhich,ifruntocompletion,terminateswithasolutionvaluewithinapresetpercentageoftheoptimum. Finally,vehicleroutingwithstochastictraveltimeisfrequentlyencounteredinpickupanddeliveryproblemssuchasthosearisingintruckloadoperations.WangandRegan(2001)haveproposedmodelsforthisclassofproblemsunderthepresenceoftimewindows. Acknowledgements ThisworkhasbeensupportedbytheCanadianNaturalSciencesandEn-gineeringResearchCouncilunderGrants227837-00andOGP0039682,bytheMinisterodell’UniversitàedellaRicerca(MIUR),andbytheConsiglioNazionaledelleRicerche(CNR),Italy.Thissupportisgratefullyacknowl-edged. References Achuthan,N.R.,Caccetta,L.,Hill,S.P.(1996).Anewsubtoureliminationconstraintforthevehicle routingproblem.EuropeanJournalofOperationalResearch91,573–586. Achuthan,N.R.,Caccetta,L.,Hill,S.P.(2003).Animprovedbranchandcutalgorithmforthecapaci-tatedvehicleroutingproblem.TransportationScience37,153–169. Adelman,D.(2003a).Price-directedreplenishmentofsubsets:Methodologyanditsapplicationtoin-ventoryrouting.Manufacturing&ServiceOperationsManagement5,348–371. Adelman,D.(2003b).Internaltransferpricingforadecentralizedoperationwithasharedsupplier. Workingpaper,GraduateSchoolofBusiness,TheUniversityofChicago. Adelman,D.(2004).Aprice-directedapproachtostochasticinventory/routing.OperationsResearch52, 499–514. Agarwal,Y.,Mathur,K.,Salkin,H.M.(1989).Aset-partitioning-basedexactalgorithmforthevehicle routingproblem.Networks19,731–749. Altinkemer,K.,Gavish,B.(1991).Parallelsavingsbasedheuristicforthedeliveryproblem.OperationsResearch39,456–469. Anily,S.,Federgruen,A.(1990).Onewarehousemultipleretailersystemswithvehicleroutingcosts.ManagementScience36,92–114. Anily,S.,Federgruen,A.(1991).Rejoinderto“Onewarehousemultipleretailersystemswithvehicle routingcosts”.ManagementScience37,1497–1499. Anily,S.,Federgruen,A.(1993).Two-echelondistributionsystemswithvehicleroutingcostsandcentral inventories.OperationsResearch41,37–47. Araque,J.R.,Hall,L.,Magnanti,T.L.(1990).Capacitatedtrees,capacitatedroutingandassociated polyhedra.DiscussionPaper90-61,CORE,UniversityofLouvain-la-Neuve,Belgium. Araque,J.R.,Kudva,G.,Morin,T.,Pekny,J.F.(1994).Abranch-and-cutalgorithmforvehiclerouting problems.AnnalsofOperationsResearch50,37–59. 418J.-F.Cordeauetal. Augerat,P.,Belenguer,J.M.,Benavent,E.,Corberán,A.,Naddef,D.,Rinaldi,G.(1995).Computa-tionalresultswithabranchandcutcodeforthecapacitatedvehicleroutingproblem.TechnicalReportRR949-M,UniversitéJosephFourier,Grenoble. Augerat,P.,Belenguer,J.M.,Benavent,E.,Corberán,A.,Naddef,D.(1999).Separatingcapacityin-equalitiesintheCVRPusingtabusearch.EuropeanJournalofOperationalResearch106,546–557.Badeau,P.,Gendreau,M.,Guertin,F.,Potvin,J.-Y.,Taillard,É.D.(1997).Aparalleltabusearchheuris-ticforthevehicleroutingproblemwithtimewindows.TransportationResearchC5,109–122. Baker,E.,Schaffer,J.(1986).Computationalexperiencewithbranchexchangeheuristicsforvehicleroutingproblemswithtimewindowconstraints.AmericanJournalofMathematicalandManagementSciences6,261–300. Baldacci,R.,Hadjiconstantinou,E.,Mingozzi,A.(2004).Anexactalgorithmforthecapacitatedvehicleroutingproblembasedonatwo-commoditynetworkflowformulation.OperationsResearch52,723–738. Baldacci,R.,Bodin,L.,Mingozzi,A.(2006).Themultipledisposalfacilitiesandmultipleinventorylocationsrollon–rolloffvehicleroutingproblem.Computers&OperationsResearch33,2667–2702.Balinski,M.,Quandt,R.(1964).Onanintegerprogramforadeliveryproblem.OperationsResearch12,300–304. Bard,J.F.,Huang,L.,Dror,M.,Jaillet,P.(1998a).AbranchandcutalgorithmfortheVRPwithsatellitefacilities.IIETransactions30,831–834. Bard,J.F.,Huang,L.,Jaillet,P.,Dror,M.(1998b).Adecompositionapproachtotheinventoryroutingproblemwithsatellitefacilities.TransportationScience32,189–203. Bard,J.F.,Kontoravdis,G.,Yu,G.(2002).Abranch-and-cutprocedureforthevehicleroutingproblemwithtimewindows.TransportationScience36,250–269. Barnes-Schuster,D.,Bassok,Y.(1997).Directshippingandthedynamicsingle-depot/multi-retailerinventorysystem.EuropeanJournalofOperationalResearch101,509–518. Bartholdi,J.J.,Platzman,L.K.(1982).AnNlogNplanartravelingsalesmanheuristicbasedonspace-fillingcurves.OperationsResearchLetters1,121–125. Bartholdi,J.J.,Platzman,L.K.,Collins,R.L.,Warden,W.H.(1983).Aminimaltechnologyroutingsys-temformealsonwheels.Interfaces13(3),1–8. Bastian,C.,RinnooyKan,A.H.G.(1992).Thestochasticvehicleroutingproblemrevisited.EuropeanJournalofOperationalResearch56,407–412. Battiti,R.,Tecchiolli,G.(1994).Thereactivetabusearch.ORSAJournalonComputing6,126–140.Bean,J.C.(1994).Geneticalgorithmsandrandomkeysforthesequencingandoptimization.ORSAJournalonComputing6,154–160. Beasley,J.E.(1983).Route-firstcluster-secondmethodsforvehiclerouting.Omega11,403–408. Bell,W.,Dalberto,L.,Fisher,M.L.,Greenfield,A.,Jaikumar,R.,Kedia,P.,Mack,R.,Prutzman,P.(1983).Improvingthedistributionofindustrialgaseswithanon-linecomputerizedroutingandschedulingoptimizer.Interfaces13(6),4–23. Benders,J.F.(1962).Partitioningproceduresforsolvingmixedvariablesprogrammingproblems.Nu-merischeMathematik4,238–252. Bent,R.,VanHentenryck,P.(2004).Atwo-stagehybridlocalsearchforthevehicleroutingproblemwithtimewindows.TransportationScience38,515–530. Benton,W.C.,Rossetti,M.D.(1992).Thevehicleschedulingproblemwithintermittentcustomerde-mands.Computers&OperationsResearch19,521–531. Beraldi,P.,Ghiani,G.,Laporte,G.,Musmanno,G.(2005).Efficientneighbourhoodsearchfortheprobabilisticpickupanddeliverytravellingsalesmanproblem.Networks46,195–198. Berger,J.,Barkaoui,M.(2004).Anewhybridgeneticalgorithmforthecapacitatedvehicleroutingproblem.JournaloftheOperationalResearchSociety54,1254–1262. Berger,J.,Barkaoui,M.,Bräysy,O.(2003).Aroute-directedhybridgeneticapproachforthevehicleroutingproblemwithtimewindows.INFOR41,179–194. Bertazzi,L.,Paletta,G.,Speranza,M.G.(2002).Deterministicorder-up-tolevelpoliciesinaninventoryroutingproblem.TransportationScience36,119–132. Bertsekas,D.P.(1995).DynamicProgrammingandOptimalControl.AthenaScientific,Belmont,MA. Ch.6.VehicleRouting419 Bertsimas,D.J.(1988).Probabilisticcombinatorialoptimizationproblems.PhDthesis,OperationsRe-searchCenter,MassachusettsInstituteofTechnology,Cambridge,MA. Bertsimas,D.J.(1992).Avehicleroutingproblemwithstochasticdemand.OperationsResearch40, 574–585. Bertsimas,D.J.,Howell,L.H.(1993).Furtherresultsontheprobabilistictravelingsalesmanproblem. EuropeanJournalofOperationalResearch65,68–95. Bertsimas,D.J.,Simchi-Levi,D.(1996).Anewgenerationofvehicleroutingresearch:Robustalgo-rithmsaddressinguncertainty.OperationsResearch44,286–304. Bertsimas,D.J.,Jaillet,P.,Odoni,A.R.(1990).Apriorioptimisation.OperationsResearch38,1019–1033. Blasum,U.,Hochstättler,W.(2000).Applicationofthebranchandcutmethodtothevehi-cleroutingproblem.TechnicalReportZPR2000-386,ZPR,UniversitätzuKöln.Availableathttp://www.zaik.uni-koeln.de/~paper. Bozkaya,B.,Erkut,E.,Laporte,G.(2003).Atabusearchalgorithmandadaptivememoryprocedure forpoliticaldistricting.EuropeanJournalofOperationalResearch144,12–26. Bramel,J.,Simchi-Levi,D.(1995).Alocationbasedheuristicforgeneralroutingproblems.OperationsResearch43,649–660. Bramel,J.,Simchi-Levi,D.(1997).Ontheeffectivenessofsetcoveringformulationsforthevehicle routingproblemwithtimewindows.OperationsResearch45,295–301. Bramel,J.,Simchi-Levi,D.(2002).Set-covering-basedalgorithmsforthecapacitatedVRP.In:Toth, P.,Vigo,D.(Eds.),TheVehicleRoutingProblem.SIAMMonographsonDiscreteMathematicsandApplications.SIAM,Philadelphia,pp.85–108. Brandão,J.(1998).Metaheuristicforthevehicleroutingproblemwithtimewindows.In:Voss,S., Martello,S.,Osman,I.H.,Roucairol,C.(Eds.),Meta-Heuristics:AdvancesandTrendsinLocalSearchParadigmsforOptimization.KluwerAcademic,Boston,pp.19–36. Bräysy,O.(2002).Fastlocalsearchesforthevehicleroutingproblemwithtimewindows.INFOR40, 319–330. Bräysy,O.(2003).Areactivevariableneighborhoodsearchforthevehicleroutingproblemwithtime windows.INFORMSJournalonComputing15,347–368. Bräysy,O.,Gendreau,M.(2005a).Vehicleroutingproblemwithtimewindows,PartI:Routeconstruc-tionandlocalsearchalgorithms.TransportationScience39,104–118. Bräysy,O.,Gendreau,M.(2005b).Vehicleroutingproblemwithtimewindows,PartII:Metaheuristics. TransportationScience39,119–139. Burns,L.D.,Hall,R.W.,Blumenfeld,D.E.,Daganzo,C.F.(1985).Distributionstrategiesthatminimize transportationandinventorycosts.OperationsResearch33,469–490. Campbell,A.M.,Savelsbergh,M.W.P.(2004a).Deliveryvolumeoptimization.TransportationScience38, 210–223. Campbell,A.M.,Savelsbergh,M.W.P.(2004b).Adecompositionapproachfortheinventory-routing problem.TransportationScience38,488–502. Campbell,A.M.,Savelsbergh,M.W.P.(2004c).Efficientinsertionheuristicsforvehicleroutingand schedulingproblems.TransportationScience38,269–378. Campbell,A.M.,Clarke,L.,Kleywegt,A.J.,Savelsbergh,M.W.P.(1998).Theinventoryroutingprob-lem.In:Crainic,T.G.,Laporte,G.(Eds.),FleetManagementandLogistics.KluwerAcademic,Boston,pp.95–112. Campos,V.,Corberán,A.,Mota,E.(1991).Polyhedralresultsforavehicleroutingproblem.EuropeanJournalofOperationalResearch52,75–85. Carraway,R.L.,Morin,T.L.,Moskowitz,H.(1989).Generalizeddynamicprogrammingforstochastic combinatorialoptimization.OperationsResearch37,819–829. Çetinkaya,S.,Lee,C.Y.(2000).Stockreplenishmentandshipmentschedulingforvendormanaged inventorysystems.ManagementScience46,217–232. Chabrier,A.(2006).Vehicleroutingproblemwithelementaryshortestpathbasedcolumngeneration. Computers&OperationsResearch33,2972–2990. Chan,L.M.,Federgruen,A.,Simchi-Levi,D.(1998).Probabilisticanalysesandpracticalalgorithmsfor inventory-routingmodels.OperationsResearch46,96–106. 420J.-F.Cordeauetal. Chiang,W.-C.,Russell,R.A.(1997).Areactivetabusearchmetaheuristicforthevehicleroutingprob-lemwithtimewindows.INFORMSJournalonComputing9,417–430. Chien,T.,Balakrishnan,A.,Wong,R.(1989).Anintegratedinventoryallocationandvehicleroutingproblem.TransportationScience23,67–76. Christiansen,M.(1999).Decompositionofacombinedinventoryandtimeconstrainedshiproutingproblem.TransportationScience33,3–16. Christiansen,M.,Nygreen,B.(1998a).Amethodforsolvingshiproutingproblemswithinventoryconstraints.AnnalsofOperationsResearch81,357–378. Christiansen,M.,Nygreen,B.(1998b).Modellingpathflowsforacombinedshiproutingandinventorymanagementproblem.AnnalsofOperationsResearch82,391–412. Christofides,N.,Mingozzi,A.(1989).Vehiclerouting:Practicalandalgorithmicaspects.In:VanRijn,C.F.H.(Ed.),Logistics:WhereEndsHavetoMeet.Pergamon,Oxford,pp.30–48. Christofides,N.,Mingozzi,A.,Toth,P.(1979).Thevehicleroutingproblem.In:Christofides,N.,Mingozzi,A.,Toth,P.,Sandi,C.(Eds.),CombinatorialOptimization.Wiley,Chichester,pp.315–338. Christofides,N.,Mingozzi,A.,Toth,P.(1981a).Exactalgorithmsforthevehicleroutingproblembasedonthespanningtreeandshortestpathrelaxations.MathematicalProgramming20,255–282. Christofides,N.,Mingozzi,A.,Toth,P.(1981b).State-spacerelaxationproceduresforthecomputationofboundstoroutingproblems.Networks11,145–164. Clarke,G.,Wright,J.W.(1964).Schedulingofvehiclesfromacentraldepottoanumberofdeliverypoints.OperationsResearch12,568–581. Cook,W.,Rich,J.L.(1999).Aparallelcutting-planealgorithmforthevehicleroutingproblemwithtimewindows.TechnicalReportTR99-04,ComputationalandAppliedMathematicsDepartment,RiceUniversity,TX. Cordeau,J.-F.,Laporte,G.(2001).Atabusearchalgorithmforthesitedependentvehicleroutingproblemwithtimewindows.INFOR39,292–298. Cordeau,J.-F.,Laporte,G.(2004).Tabusearchheuristicsforthevehicleroutingproblem.In:Rego,C.,Alidaee,B.(Eds.),MetaheuristicOptimizationviaMemoryandEvolution:TabuSearchandScatterSearch.KluwerAcademic,Boston,pp.145–163. Cordeau,J.-F.,Gendreau,M.,Laporte,G.(1997).Atabusearchheuristicforperiodicandmulti-depotvehicleroutingproblems.Networks30,105–119. Cordeau,J.-F.,Laporte,G.,Mercier,A.(2001).Aunifiedtabusearchheuristicforvehicleroutingproblemswithtimewindows.JournaloftheOperationalResearchSociety52,928–936. Cordeau,J.-F.,Desaulniers,G.,Desrosiers,J.,Solomon,M.M.,Soumis,F.(2002a).VRPwithTimeWindows.In:Toth,P.,Vigo,D.(Eds.),TheVehicleRoutingProblem.SIAMMonographsonDiscreteMathematicsandApplications.SIAM,Philadelphia,pp.157–193. Cordeau,J.-F.,Gendreau,M.,Laporte,G.,Potvin,J.-Y.,Semet,F.(2002b).Aguidetovehicleroutingheuristics.JournaloftheOperationalResearchSociety53,512–522. Cordeau,J.-F.,Laporte,G.,Mercier,A.(2004).Animprovedtabusearchalgorithmforthehandlingofroutedurationconstraintsinvehicleroutingproblemswithtimewindows.JournaloftheOperationalResearchSociety55,542–546. Cordeau,J.-F.,Gendreau,M.,Hertz,A.,Laporte,G.,Sormany,J.-S.(2005).Newheuristicsforthevehi-cleroutingproblem.In:Langevin,A.,Riopel,D.(Eds.),LogisticsSystems:DesignandOptimization.Springer-Verlag,NewYork,pp.279–297. Cordone,R.,WolflerCalvo,R.(2001).Aheuristicforthevehicleroutingproblemwithtimewindows.JournalofHeuristics7,107–129. Cornuéjols,G.,Harche,F.(1993).Polyhedralstudyofthecapacitatedvehicleroutingproblem.Mathe-maticalProgramming60,21–52. Croes,A.(1958).Amethodforsolvingtravelingsalesmanproblems.OperationsResearch6,791–812.Danna,E.,LePape,C.(2003).Acceleratingbranch-and-pricewithlocalsearch:Acasestudyonthevehicleroutingproblemwithtimewindows.TechnicalReport03-006,ILOG. Dantzig,G.B.,Ramser,J.M.(1959).Thetruckdispatchingproblem.ManagementScience6,81–91.Dantzig,G.B.,Wolfe,P.(1960).Decompositionprincipleforlinearprogramming.OperationsRe-search8,101–111. Ch.6.VehicleRouting421 DeBacker,B.,Furnon,V.,Kilby,P.,Prosser,P.,Shaw,P.(2000).Solvingvehicleroutingproblemsusingconstraintprogrammingandmetaheuristics.JournalofHeuristics6,501–523. Dell’Amico,M.,Toth,P.(2000).Algorithmsandcodesfordenseassignmentproblems:Thestateoftheart.DiscreteAppliedMathematics100,17–48. Desrochers,M.,Laporte,G.(1991).ImprovementsandextensionstotheMiller–Tucker–Zemlinsub-toureliminationconstraints.OperationsResearchLetters10,27–36. Desrochers,M.,Soumis,F.(1988).Ageneralizedpermanentlabelingalgorithmfortheshortestpathproblemwithtimewindows.INFOR26,191–212. Desrochers,M.,Verhoog,T.W.(1989).Amatchingbasedsavingsalgorithmforthevehicleroutingproblem.LesCahiersduGERADG–89–04,HECMontréal. Desrochers,M.,Lenstra,J.K.,Savelsbergh,M.W.P.,Soumis,F.(1988).Vehicleroutingwithtimewin-dows:Optimizationandapproximation.In:Golden,B.L.,Assad,A.A.(Eds.),VehicleRouting:MethodsandStudies.North-Holland,Amsterdam,pp.65–84. Desrochers,M.,Desrosiers,J.,Solomon,M.M.(1992).Anewoptimizationalgorithmforthevehicleroutingproblemwithtimewindows.OperationsResearch40,342–354. Dorigo,M.,DiCaro,G.,Gambardella,L.M.(1999).Antalgorithmsfordiscreteoptimization.ArtificialLife5,137–172. Drezner,Z.(2003).Anewgeneticalgorithmforthequadraticassignmentproblem.INFORMSJournalonComputing15,320–330. Dror,M.,Ball,M.O.(1987).Inventory/routing:Reductionfromanannualtoashortperiodproblem.NavalResearchLogisticsQuarterly34,891–905. Dror,M.,Trudeau,P.(1986).Stochasticvehicleroutingwithmodifiedsavingsalgorithm.EuropeanJournalofOperationalReserach23,228–235. Dror,M.,Ball,M.O.,Golden,B.L.(1985).Acomputationalcomparisonofalgorithmsfortheinventoryroutingproblem.AnnalsofOperationsResearch4,3–23. Dror,M.,Laporte,G.,Trudeau,P.(1989).Vehicleroutingwithstochasticdemands:Propertiesandsolutionframeworks.TransportationScience23,166–176. Dror,M.,Laporte,G.,Louveaux,F.V.(1993).Vehicleroutingwithstochasticdemandsandrestrictedfailures.ZeitschriftfürOperationsResearch37,273–283. Dueck,G.(1990).Newoptimizationheuristics,thegreatdelugealgorithmandtherecord-to-recordtravel.Technicalreport,IBMGermany,HeidelbergScientificCenter. Dueck,G.(1993).Newoptimizationheuristics:Thegreatdelugealgorithmandtherecord-to-recordtravel.JournalofComputationalPhysics104,86–92. Ergun,Ö.,Orlin,J.B.,Steele-Feldman,A.(2003).Creatingverylargescaleneighborhoodsoutofsmalleronesbycompoundingmoves:Astudyonthevehicleroutingproblem.MITSloanwork-ingPaper4393-02,MassachusettsInstituteofTechnology,Cambridge,MA. Federgruen,A.,Zipkin,P.(1984).Acombinedvehicleroutingandinventoryallocationproblem.Oper-ationsResearch32,1019–1036. Fischetti,M.,Toth,P.(1989).Anadditiveboundingprocedureforcombinatorialoptimizationprob-lems.OperationsResearch37,319–328. Fischetti,M.,Toth,P.,Vigo,D.(1994).Abranch-and-boundalgorithmforthecapacitatedvehiclerout-ingproblemondirectedgraphs.OperationsResearch42,846–859. Fisher,M.L.(1994).Optimalsolutionofvehicleroutingproblemsusingminimumk-trees.OperationsResearch42,626–642. Fisher,M.L.,Jaikumar,R.(1981).Ageneralizedassignmentheuristicforthevehicleroutingproblem.Networks11,109–124. Fisher,M.L.,Greenfield,A.,Jaikumar,R.,Kedia,P.(1982).Real-timeschedulingofabulkdeliveryfleet:PracticalapplicationofLagrangeanrelaxation.Technicalreport,TheWhartonSchool,Uni-versityofPennsylvania. Fisher,M.L.,Jörnsten,K.O.,Madsen,O.B.G.(1997).Vehicleroutingwithtimewindows–twoopti-mizationalgorithms.OperationsResearch45,488–492. Flood,M.M.(1956).Thetravellingsalesmanproblem.OperationsResearch4,61–75. Foster,B.A.,Ryan,D.M.(1976).Anintegerprogrammingapproachtothevehicleschedulingproblem.OperationsResearch27,367–384. 422J.-F.Cordeauetal. Fukasawa,R.,Longo,H.,Lysgaard,J.,PoggideAragão,M.,Reis,M.,Uchoa,E.,Werneck,R.F.(2006).Robustbranch-and-cut-and-priceforthecapacitatedvehicleroutingproblem.MathematicalPro-grammingA106,491–511. Gallego,G.,Simchi-Levi,D.(1990).Ontheeffectivenessofdirectshippingstrategyfortheone-warehousemulti-retailerr-systems.ManagementScience36,240–243. Gambardella,L.M.,Taillard,É.D.,Agazzi,G.(1999).MACS-VRPTW:Amultipleantcolonysystemforvehicleroutingproblemswithtimewindows.In:Corne,D.,Dorigo,M.,Glover,F.(Eds.),NewIdeasinOptimization.McGraw-Hill,London,pp.63–76. Gaur,V.,Fisher,M.L.(2004).Aperiodicinventoryroutingproblematasupermarketchain.OperationsResearch52,813–822. Gehring,H.,Homberger,J.(2002).Parallelizationofatwo-phasemetaheuristicforroutingproblemswithtimewindows.JournalofHeuristics8,251–276. Gendreau,M.,Hertz,A.,Laporte,G.(1992).Newinsertionandpost-optimizationproceduresforthetravelingselesmanproblem.OperationsResearch40,1083–1094. Gendreau,M.,Hertz,A.,Laporte,G.(1994).Atabusearchheuristicforthevehicleroutingproblem.ManagementScience40,1276–1290. Gendreau,M.,Laporte,G.,Séguin,R.(1995).Anexactalgorithmforthevehicleroutingproblemwithstochasticcustomersanddemands.TransportationScience29,143–155. Gendreau,M.,Laporte,G.,Séguin,R.(1996).Atabusearchalgorithmforthevehicleroutingproblemwithstochasticdemandsandcustomers.OperationsResearch44,469–477. Gendreau,M.,Hertz,A.,Laporte,G.,Stan,M.(1998).Ageneralizedinsertionheuristicforthetravel-ingsalesmanproblemwithtimewindows.OperationsResearch43,330–335. Gendreau,M.,Laporte,G.,Potvin,J.-Y.(2002).MetaheuristicsforthecapacitatedVRP.In:Toth,P.,Vigo,D.(Eds.),TheVehicleRoutingProblem.SIAMMonographsonDiscreteMathematicsandApplications.SIAM,Philadelphia,pp.129–154. Ghaziri,H.(1993).Algorithmesconnexionistespourl’optimisationcombinatoire.Thèsededoctorat,ÉcolePolytechniqueFédéraledeLausanne,Switzerland. Ghiani,G.,Laporte,G.,Semet,F.(2006).Theblackandwhitetravelingsalesmanproblem.OperationsResearch54,366–378. Gillett,B.E.,Miller,L.R.(1974).Aheuristicalgorithmforthevehicle-dispatchproblem.OperationsResearch21,340–349. Glover,F.(1992).Newejectionchainandalternatingpathmethodsfortravelingsalesmanproblems.In:Balci,O.,Sharda,R.,Zenios,S.(Eds.),ComputerScienceandOperationsResearch:NewDevel-opmentsinTheirInterfaces.Pergamon,Oxford,pp.449–509. Golden,B.L.,Stewart,W.R.(1978).Vehicleroutingwithprobabilisticdemands.In:Hogben,D.,Fife,D.(Eds.)ComputerScienceandStatistics:TenthAnnualSymposiumontheInterface.NBSSpecialPublication,vol.503,pp.252–259. Golden,B.L.,Magnanti,T.L.,Nguyen,H.Q.(1977).Implementingvehicleroutingalgorithms.Net-works7,113–148. Golden,B.L.,Assad,A.A.,Dahl,R.(1984).Analysisofalargescalevehicleroutingproblemwithaninventorycomponent.LargeScaleSystems7,181–190. Golden,B.L.,Wasil,E.A.,Kelly,J.P.,Chao,I-M.(1998).Metaheuristicsinvehiclerouting.In:Crainic,T.G.,Laporte,G.(Eds.),FleetManagementandLogistics.KluwerAcademic,Boston,pp.33–56.Golden,B.L.,Assad,A.A.,Wasil,E.A.(2002).Routingvehiclesintherealworld:Applicationsinthesolidwaste,beverage,food,dairy,andnewspaperindustries.In:Toth,P.,Vigo,D.(Eds.),TheVehicleRoutingProblem.SIAMMonographsonDiscreteMathematicsandApplications.SIAM,Philadelphia,pp.245–286. Gouveia,L.(1995).Aresultonprojectionforthevehicleroutingproblem.JournalofOperationalRe-searchSociety85,610–624. Hadjiconstantinou,E.,Christofides,N.,Mingozzi,A.(1995).Anewexactalgorithmforthevehiclerout-ingproblembasedonq-pathsandk-shortestpathsrelaxations.AnnalsofOperationsResearch61,21–43. Haimovich,M.,RinnooyKan,A.H.G.(1985).Boundsandheuristicsforcapacitatedroutingproblems.MathematicsofOperationsResearch10,527–542. Ch.6.VehicleRouting423 Haughton,M.A.(1998).Theperformanceofroutemodificationanddemandstabilizationstrategiesinstochasticvehiclerouting.TransportationResearch32,551–566. Haughton,M.A.(2000).Quantifyingthebenefitsofroutereoptimisationunderstochasticcustomerdemands.JournaloftheOperationalResearchSociety51,320–332. Held,M.,Karp,R.M.(1971).Thetravelingsalesmanproblemandminimumspanningtrees:PartII.MathematicalProgramming1,6–25. Held,M.,Wolfe,P.,Crowder,M.P.(1974).Validationofthesubgradientoptimization.MathematicalProgramming6,62–88. Herer,Y.,Roundy,R.(1997).Heuristicsforaone-warehousemultiretailerdistributionproblemwithperformancebounds.OperationsResearch45,102–115. Hjorring,C.,Holt,J.(1999).Newoptimalitycutsforasingle-vehiclestochasticroutingproblem.AnnalsofOperationsResearch86,569–585. Homberger,J.,Gehring,H.(1999).Twoevolutionarymetaheuristicsforthevehicleroutingproblemwithtimewindows.INFOR37,297–318. Houck,D.J.,Picard,J.-C.,Queyranne,M.,Vemuganti,R.R.(1980).Thetravelingsalesmanproblemasaconstrainedshortestpathproblem:Theoryandcomputationalexperience.Opsearch17,93–109.Hvattum,L.M.,Løkketangen,A.,Laporte,G.(2006).Solvingadynamicandstochasticvehicleroutingproblemwithasamplescenariohedgingheuristic.TransportationScience,inpress. Ioannou,G.,Kritikos,M.,Prastacos,G.(2001).Agreedylook-aheadheuristicforthevehicleroutingproblemwithtimewindows.JournaloftheOperationalResearchSociety52,523–537. Irnich,S.,Villeneuve,D.(2003).Theshortestpathproblemwithresourceconstraintsandk-cycleeliminationfork3.Technicalreport,Rheinisch-WestfälischeTechnischeHochschule,Aachen,Germany. Jaillet,P.(1985).Probabilistictravelingsalesmanproblem.PhDthesis,OperationsResearchCenter,MassachusettsInstituteofTechnology,Cambridge,MA. Jaillet,P.(1987).Stochasticroutingproblems.In:Andreatta,G.,Mason,F.,Serafini,P.(Eds.),Stochas-ticsinCombinatorialOptimization.WorldScientific,Singapore,pp.197–213. Jaillet,P.(1988).Apriorisolutionofatravelingsalesmanprobleminwhicharandomsubsetofthecustomersarevisited.OperationsResearch36,929–936. Jaillet,P.,Odoni,A.R.(1988).Theprobabilisticvehicleroutingproblem.In:Golden,B.L.,Assad,A.A.(Eds.),VehicleRouting:MethodsandStudies.North-Holland,Amsterdam,pp.293–318. Jaillet,P.,Bard,J.F.,Huang,L.,Dror,M.(2002).Deliverycostapproximationsforinventoryroutingproblemsinarollinghorizonframework.TransportationScience3,292–300. Jézéquel,A.(1985).Probabilisticvehicleroutingproblems.MScdissertation,DepartmentofCivilEn-gineering,MassachusettsInstituteofTechnology,Cambridge,MA. Kallehauge,B.,Larsen,J.,Madsen,O.B.G.(2006).Lagrangeandualityappliedtothevehicleroutingwithtimewindows.Computers&OperationsResearch33,1464–1487. Kao,E.P.C.(1978).Apreferenceorderdynamicprogramforastochastictravelingsalesmanproblem.OperationsResearch26,1033–1045. Kenyon,A.S.,Morton,D.P.(2003).Stochasticvehicleroutingwithrandomtraveltimes.TransportationScience37,69–82. Kilby,P.J.,Prosser,P.,Shaw,P.(1998).Guidedlocalsearchforthevehicleroutingproblemwithtimewindows.In:Voss,S.,Martello,S.,Osman,I.H.,Roucairol,C.(Eds.),MetaHeuristics:AdvancesandTrendsinLocalSearchParadigmsforOptimisation.KluwerAcademic,Boston,pp.473–486. Kindervater,G.A.P.,Savelsbergh,M.W.P.(1997).Vehiclerouting:Handlingedgeexchanges.In:Aarts,E.H.L.,Lenstra,J.K.(Eds.),LocalSearchinCombinatorialOptimization.Wiley,Chichester,pp.337–360. Kleywegt,A.J.,Nori,V.,Savelsbergh,M.W.L.(2002).Thestochasticinventoryroutingproblemwithdirectdeliveries.TransportationScience36,94–118. Kleywegt,A.J.,Nori,V.,Savelsbergh,M.W.L.(2004).Dynamicprogrammingapproximationsforasto-chasticinventoryroutingproblem.TransportationScience38,42–70. Kohl,N.,Madsen,O.B.G.(1997).AnoptimizationalgorithmforthevehicleroutingproblemwithtimewindowsbasedonLagrangeanrelaxation.OperationsResearch45,395–406. 424J.-F.Cordeauetal. Kohl,N.,Desrosiers,J.,Madsen,O.B.G.,Solomon,M.M.,Soumis,F.(1999).2-pathcutsforthevehicleroutingproblemwithtimewindows.TransportationScience33,101–116. Kolen,A.W.J.,RinnooyKan,A.H.G.,Trienekens,H.W.J.M.(1987).Vehicleroutingwithtimewindows.OperationsResearch35,256–273. Kontoravdis,G.,Bard,J.F.(1995).AGRASPforthevehicleroutingproblemwithtimewindows.ORSAJournalonComputing7,10–23. Lambert,V.,Laporte,G.,Louveaux,F.V.(1993).Designingcollectionroutesthroughbankbranches.Computers&OperationsResearch20,783–791. Laporte,G.,Louveaux,F.V.(1990).Formulationsandboundsforthestochasticcapacitatedvehi-cleroutingproblemwithuncertainsupplies.In:Gabzewicz,J.,Richard,J.-F.,Wolsey,L.(Eds.),EconomicDecisionMaking:Games,EconometricsandOptimisation.North-Holland,Amsterdam,pp.443–455. Laporte,G.,Louveaux,F.V.(1993).TheintegerL-shapedmethodforstochasticintegerprogramswithcompleterecourse.OperationsResearchLetters13,133–142. Laporte,G.,Louveaux,F.V.(1998).SolvingstochasticroutingproblemswiththeintegerL-shapedmethod.In:Crainic,T.G.,Laporte,G.(Eds.),FleetManagementandLogistics.KluwerAcademic,Boston,pp.159–167. Laporte,G.,Nobert,Y.(1987).Exactalgorithmsforthevehicleroutingproblem.AnnalsofDiscreteMathematics31,147–184. Laporte,G.,Semet,F.(2002).ClassicalheuristicsforthecapacitatedVRP.In:Toth,P.,Vigo,D.(Eds.),TheVehicleRoutingProblem.SIAMMonographsonDiscreteMathematicsandApplications.SIAM,Philadelphia,pp.109–128. Laporte,G.,Nobert,Y.,Desrochers,M.(1985).Optimalroutingundercapacityanddistancerestric-tions.OperationsResearch33,1050–1073. Laporte,G.,Mercure,H.,Nobert,Y.(1986).Anexactalgorithmfortheasymmetricalcapacitatedvehicleroutingproblem.Networks16,33–46. Laporte,G.,Louveaux,F.V.,Mercure,H.(1989).Modelsandexactsolutionsforaclassofstochasticlocation-routingproblems.EuropeanJournalofOperationalResearch39,71–78. Laporte,G.,Louveaux,F.V.,Mercure,H.(1992).Thevehicleroutingproblemwithstochastictraveltimes.TransportationScience26,161–170. Laporte,G.,Louveaux,F.V.,Mercure,H.(1994).Apriorioptimizationoftheprobabilistictravelingsalesmanproblem.OperationsResearch42,543–549. Laporte,G.,Louveaux,F.V.,Vanhamme,L.(2002).AnintegerL-shapedalgorithmforthecapacitatedvehicleroutingproblemwithstochasticdemands.OperationsResearch50,415–423. Larson,R.C.(1988).Transportationofsludgetothe106-milesite:Aninventoryroutingproblemforfleetsizingandlogisticsystemdesign.TransportationScience22,186–198. Lau,H.C.,Liu,Q.,Ono,H.(2002).Integratinglocalsearchandnetworkflowtosolvetheinventoryroutingproblem.AmericanAssociationforArtificialIntelligence2,9–14. Lau,H.C.,Sim,M.,Teo,K.M.(2003).Vehicleroutingproblemwithtimewindowsandalimitednumberofvehicles.EuropeanJournalofOperationalResearch148,559–569. Leipälä,T.(1978).Onthesolutionsofstochastictravelingsalesmanproblems.EuropeanJournalofOperationalResearch2,291–297. Letchford,A.,Eglese,R.W.,Lysgaard,J.(2002).Multistars,partialmultistarsandthecapacitatedve-hicleroutingproblem.MathematicalProgramming94,21–40. Li,F.,Golden,B.L.,Wasil,E.A.(2005).Verylarge-scalevehiclerouting:Newtestproblems,algorithmsandresults.Computers&OperationsResearch32,1165–1179. Li,H.,Lim,A.(2003).Localsearchwithannealing-likerestartstosolvetheVRPTW.EuropeanJournalofOperationalResearch150,115–127. Lin,S.(1965).Computersolutionsofthetravellingsalesmanproblem.BellSystemTechnicalJournal44,2245–2269. Louveaux,F.V.(1998).Anintroductiontostochastictransportationmodels.In:Labbé,M.,Laporte,G.,Tanczos,K.,Toint,P.(Eds.),OperationsResearchandDecisionAidMethodologiesinTrafficandTransportationManagement.NATOASISeriesF:ComputerandSystemsSciences,vol.166.Springer-Verlag,Berlin/Heidelberg,pp.244–263. Ch.6.VehicleRouting425 Lysgaard,J.,Letchford,A.,Eglese,R.W.(2004).Anewbranch-and-cutalgorithmforthecapacitatedvehicleroutingproblem.MathematicalProgramming100,423–445. Martinhon,C.,Lucena,A.,Maculan,N.(2000).Arelaxandcutalgorithmforthevehicleroutingprob-lem.TechnicalReportRT-05/00,UniversidadeFederalFluminense,Niterói,Brasil. Mester,D.,Bräysy,O.(2005).Activeguidedevolutionstrategiesforlargescalevehicleroutingproblemwithtimewindows.Computers&OperationsResearch32,1593–1614. Miller,D.L.(1995).Amatchingbasedexactalgorithmforcapacitatedvehicleroutingproblems.ORSAJournalonComputing7,1–9. Miller,D.L.,Pekny,J.F.(1995).Astagedprimal-dualalgorithmforperfectb-matchingwithedgeca-pacities.ORSAJournalonComputing7,298–320. Mingozzi,A.,Christofides,N.,Hadjiconstantinou,E.(1994).Anexactalgorithmforthevehicleroutingproblembasedonthesetpartitioningformulation.Technicalreport,DepartmentofMathematics,UniversityofBologna,Italy. Minkoff,A.(1993).AMarkovdecisionmodelanddecompositionheuristicfordynamicvehicledis-patching.OperationsResearch41,77–90.Mladenovi´c,N.,Hansen,P.(1997).Variableneighborhoodsearch.Computers&OperationsResearch24,1097–1100. Mole,R.H.,Jameson,S.R.(1976).Asequentialroute-buildingalgorithmemployingageneralizedsav-ingscriterion.OperationalResearchQuarterly27,503–511. Moscato,P.,Cotta,C.(2003).Agentleintroductiontomemeticalgorithms.In:Glover,F.,Kochen-berger,G.A.(Eds.),HandbookofMetaheuristics.KluwerAcademic,Boston,pp.105–144. Naddef,D.,Rinaldi,G.(2002).Branch-and-cutalgorithmsforthecapacitatedVRP.In:Toth,P.,Vigo,D.(Eds.),TheVehicleRoutingProblem.SIAMMonographsonDiscreteMathematicsandApplications.SIAM,Philadelphia,pp.53–84. Nelson,M.D.,Nygard,K.E.,Griffin,J.H.,Shreve,W.E.(1985).Implementationtechniquesforthevehicleroutingproblem.Computers&OperationsResearch12,273–283. Or,I.(1976).Travelingsalesman-typecombinatorialproblemsandtheirrelationtothelogisticsofbloodbanking.PhDthesis,DepartmentofIndustrialEngineeringandManagementScience,North-westernUniversity,Evanston,IL. Osman,I.H.(1993).Metastrategysimulatedannealingandtabusearchalgorithmsforthevehiclerout-ingproblem.AnnalsofOperationsResearch41,421–451. Paessens,H.(1988).Thesavingsalgorithmforthevehicleroutingproblem.EuropeanJournalofOper-ationalResearch34,336–344. Potvin,J.-Y.(1996).Geneticalgorithmsforthetravelingsalesmanproblem.AnnalsofOperationsRe-search63,339–370. Potvin,J.-Y.,Bengio,S.(1996).Thevehicleroutingproblemwithtimewindows–PartII:Geneticsearch.INFORMSJournalonComputing8,165–172. Potvin,J.-Y.,Rousseau,J.-M.(1993).Aparallelroutebuildingalgorithmforthevehicleroutingandschedulingproblemwithtimewindows.EuropeanJournalofOperationalResearch66,331–340.Potvin,J.-Y.,Rousseau,J.-M.(1995).Anexchangeheuristicforroutingproblemswithtimewindows.JournaloftheOperationalResearchSociety46,1433–1446. Potvin,J.-Y.,Kervahut,T.,Garcia,B.L.,Rousseau,J.-M.(1996).Thevehicleroutingproblemwithtimewindows–PartI:Tabusearch.INFORMSJournalonComputing8,158–164. Prins,C.(2004).Asimpleandeffectiveevolutionaryalgorithmforthevehicleroutingproblem.Com-puters&OperationsResearch31,1985–2002. Ralphs,T.K.,Kopman,L.,Pulleyblank,W.R.,Trotter,Jr.,L.E.(2003).Onthecapacitatedvehicleroutingproblem.MathematicalProgrammingB94,343–359. Rechenberg,I.(1973).Evolutionsstrategie.Fromman-Holzboog,Stuttgart,Germany. Rego,C.(1998).Asubpathejectionmethodforthevehicleroutingproblem.ManagementScience44,1447–1459. Rego,C.,Roucairol,C.(1996).Aparalleltabusearchalgorithmusingejectionchainsforthevehi-cleroutingproblem.In:Osman,I.H.,Kelly,J.P.(Eds.),Meta-Heuristics:TheoryandApplications.KluwerAcademic,Boston,pp.661–675. 426J.-F.Cordeauetal. Reimann,M.,Rubio,R.,Wein,L.M.(1999).Heavytrafficanalysisofthedynamicstochasticinventory-routingproblem.TransportationScience33,361–380. Reimann,M.,Doerner,K.,Hartl,R.F.(2004).D-ants:Savingsbasedantsdivideandconquerforthevehicleroutingproblem.Computers&OperationsResearch31,563–591. Renaud,J.,Boctor,F.F.,Laporte,G.(1996a).Afastcompositeheuristicforthesymmetrictravelingsalesmanproblem.INFORMSJournalonComputing8,134–143. Renaud,J.,Boctor,F.F.,Laporte,G.(1996b).Animprovedpetalheuristicforthevehicleroutingprob-lem.JournaloftheOperationalResearchSociety47,329–336. Rochat,Y.,Taillard,É.D.(1995).Probabilisticdiversificationandintensificationinlocalsearchforvehiclerouting.JournalofHeuristics1,147–167. Rossi,F.A.,Gavioli,I.(1987).Aspectsofheuristicmethodsinthe“Probabilistictravelingsalesmanproblem”.In:Andreatta,G.,Mason,F.,Serafini,P.(Eds.),StochasticsinCombinatorialOptimiza-tion.WorldScientific,Singapore,pp.214–227. Russell,R.A.(1977).AneffectiveheuristicfortheM-tourtravelingsalesmanproblemwithsomesideconditions.OperationsResearch25,517–524. Russell,R.A.(1995).Hybridheuristicsforthevehicleroutingproblemwithtimewindows.Transporta-tionScience29,156–166. Ryan,D.M.,Hjorring,C.,Glover,F.(1993).Extensionsofthepetalmethodforvehiclerouting.JournalofOperationalResearchSociety44,289–296. Savelsbergh,M.W.P.(1985).Localsearchinroutingproblemswithtimewindows.AnnalsofOperationsResearch4,285–305. Savelsbergh,M.W.P.(1990).Enefficientimplementationoflocalsearchalgorithmsforconstrainedroutingproblems.EuropeanJournalofOperationalResearch47,75–85. Savelsbergh,M.W.P.(1992).Thevehicleroutingproblemwithtimewindows:Minimizingroutedura-tion.ORSAJournalonComputing4,146–154. Savelsbergh,M.W.P.,Song,J.-H.(2005).Inventoryroutingwithcontinuousmoves.Computers&Oper-ationsResearch,inpress. Schulze,J.,Fahle,T.(1999).Aparallelalgorithmforthevehicleroutingproblemwithtimewindowconstraints.AnnalsofOperationsResearch86,585–607. Secomandi,N.(1998).Exactandheuristicdynamicprogrammingalgorithmsforthevehicleroutingproblemwithstochasticdemands.PhDdissertation,FacultyoftheCollegeofBusinessAdministra-tion,UniversityofHouston,TX. Secomandi,N.(2000).Comparingneuro-dynamicprogrammingalgorithmsforthevehicleroutingproblemwithstochasticdemands.Computers&OperationsResearch27,1201–1225. Secomandi,N.(2003).Analysisofarolloutapproachtosequencingproblemswithstochasticroutingapplications.JournalofHeuristics9,321–352. Séguin,R.(1994).Problèmesstochastiquesdetournéesdevéhicules.PhDthesis,Départementd’informatiqueetderechercheopérationnelle,UniversitédeMontréal,Canada. Semet,F.,Taillard,É.D.(1993).Solvingreal-lifevehicleroutingproblemsefficientlyusingtabusearch.AnnalsofOperationsResearch41,469–488. Shaw,P.(1998).Usingconstraintprogrammingandlocalsearchmethodstosolvevehicleroutingproblems.In:Maher,M.,Puget,J.-F.(Eds.),PrinciplesandPracticeofConstraintProgramming.Springer-Verlag,NewYork,pp.417–431. Sniedovich,M.(1981).Analysisofapreferenceordertravelingsalesmanproblem.OperationsRe-search29,1234–1237. Solomon,M.M.(1987).Algorithmsforthevehicleroutingandschedulingproblemswithtimewindowconstraints.OperationsResearch35,254–265. Solomon,M.M.,Baker,E.K.,Schaffer,J.R.(1988).Vehicleroutingandschedulingproblemswithtimewindowconstraints:Efficientimplementationsofsolutionimprovementprocedures.In:Golden,B.L.,Assad,A.A.(Eds.),VehicleRouting:MethodsandStudies.North-Holland,Amsterdam,pp.85–106. Song,J.-H.,Savelsbergh,M.W.P.(2005).Performancemeasurementforinventoryrouting.Transporta-tionScience,inpress. Ch.6.VehicleRouting427 Stewart,W.R.,Golden,B.L.(1983).Stochasticvehiclerouting:Acomprehensiveapproach.EuropeanJournalofOperationalResearch14,371–385. Taillard,É.D.(1993).Paralleliterativesearchmethodsforvehicleroutingproblems.Networks23,661–673. Taillard,É.D.,Badeau,P.,Gendreau,M.,Guertin,F.,Potvin,J.-Y.(1997).Atabusearchheuristicforthevehicleroutingproblemwithsofttimewindows.TransportationScience31,170–186. Tan,K.C.,Lee,L.H.,Ou,K.(2001).Hybridgeneticalgorithmsinsolvingvehicleroutingproblemswithtimewindowconstraints.Asia-PacificJournalofOperationalResearch18,170–186. Tarantilis,C.-D.,Kiranoudis,C.T.(2002).Boneroute:Adaptivememorymethodforeffectivefleetmanagement.AnnalsofOperationsResearch115,227–241. Thangiah,S.R.,Petrovic,P.(1998).Introductiontogeneticheuristicsandvehicleroutingproblemswithcomplexconstraints.In:AdvancesinComputationalandStochasticOptimization,LogicPro-gramming,andHeuristicSearch.OperationsResearch/ComputerScienceInterfaces,vol.9.KluwerAcademic,Boston,pp.253–286. Thompson,P.M.,Psaraftis,H.N.(1993).Cyclictransferalgorithmsformulti-vehicleroutingandschedulingproblems.OperationsResearch41,935–946. Tillman,F.(1969).Themultipleterminaldeliveryproblemwithprobabilisticdemands.TransportationScience3,192–204. Toth,P.,Vigo,D.(1995).Anexactalgorithmforthecapacitatedshortestspanningarborescence.AnnalsofOperationsResearch61,121–142. Toth,P.,Vigo,D.(1997).Anexactalgorithmforthevehicleroutingproblemwithbackhauls.Trans-portationScience31,372–385. Toth,P.,Vigo,D.(1998).Exactalgorithmsforvehiclerouting.In:Crainic,T.,Laporte,G.(Eds.),FleetManagementandLogistics.KluwerAcademic,Boston,pp.1–31. Toth,P.,Vigo,D.(Eds.)(2002a).TheVehicleRoutingProblem.SIAMMonographsonDiscreteMathe-maticsandApplications.SIAM,Philadelphia. Toth,P.,Vigo,D.(2002b).Anoverviewofvehicleroutingproblems.In:Toth,P.,Vigo,D.(Eds.),TheVehicleRoutingProblem.SIAMMonographsonDiscreteMathematicsandApplications.SIAM,Philadelphia,pp.1–26. Toth,P.,Vigo,D.(2002c).Branch-and-boundalgorithmsforthecapacitatedVRP.In:Toth,P.,Vigo,D.(Eds.),TheVehicleRoutingProblem.SIAMMonographsonDiscreteMathematicsandApplications.SIAM,Philadelphia,pp.29–51. Toth,P.,Vigo,D.(2002d).Models,relaxationsandexactapproachesforthecapacitatedvehicleroutingproblem.DiscreteAppliedMathematics123,487–512. Toth,P.,Vigo,D.(2003).Thegranulartabusearchanditsapplicationtothevehicleroutingproblem.INFORMSJournalonComputing15,333–346. Trudeau,P.,Dror,M.(1992).Stochasticinventoryrouting:Routedesignwithstockoutsandroutefail-ures.TransportationScience26,171–184. VanBreedam,A.(1994).Ananalysisofthebehaviorofheuristicsforthevehicleroutingproblemforaselectionofproblemswithvehicle-related,customer-related,andtime-relatedconstraints.PhDdissertation,UniversityofAntwerp,Belgium. VanSlyke,R.,Wets,R.J.-B.(1969).L-shapedprogramswithapplicationstooptimalcontrolandsto-chasticprogramming.SIAMJournalofAppliedMathematics17,638–653. Verweij,B.,Ahmed,S.,Kleywegt,A.J.,Nemhauser,G.L.,Shapiro,A.(2003).Thesampleaverageap-proximationmethodappliedtostochasticroutingproblems:Acomputationalstudy.ComputationalOptimizationandApplications24,289–333. Vigo,D.(1996).Aheuristicalgorithmfortheasymmetriccapacitatedvehicleroutingproblem.Euro-peanJournalofOperationalResearch89,108–126. Viswanathan,S.,Mathur,K.(1997).Integratingroutingandinventorydecisionsinone-warehousemul-tiretailermultiproductdistributionsystems.ManagementScience43,294–312. Volgenant,A.,Jonker,R.(1983).Thesymmetrictravelingsalesmanproblemandedgeexchangeinminimal1-trees.EuropeanJournalofOperationalResearch12,395–403. Voudouris,C.(1997).Guidedlocalsearchforcombinatorialproblems.Dissertation,UniversityofEs-sex,UnitedKingdom. 428J.-F.Cordeauetal. Waller,M.,Johnson,M.E.,Davis,T.(1999).Vendor-managedinventoryintheretailsupplychain.Jour-nalofBusinessLogistics20,183–203. Wang,X.,Regan,A.C.(2001).Assignmentmodelsforlocaltruckloadtruckingproblemswithstochasticservicetimesandtimewindowconstraints.TransportationResearchRecord1171,61–68. Wark,P.,Holt,J.(1994).Arepeatedmatchingheuristicforthevehicleroutingproblem.JournalofOperationalResearchSociety45,1156–1167. Waters,C.D.J.(1989).Vehicle-schedulingproblemswithuncertaintyandomittedcustomers.JournaloftheOperationalResearchSociety40,1099–1108. Webb,R.,Larson,R.(1995).Periodandphaseofcustomerreplenishment:Anewapproachtothestrategicinventory/routingproblem.EuropeanJournalofOperationalResearch85,132–148. Willard,J.A.G.(1989).Vehicleroutingusingr-optimaltabusearch.MScdissertation,TheManagementSchool,ImperialCollege,London. Wren,A.(1971).ComputersinTransportPlanningandOperation.IanAllan,London. Wren,A.,Holliday,A.(1972).Computerschedulingofvehiclesfromoneormoredepotstoanumberofdeliverypoints.OperationalResearchQuarterly23,333–344. Xu,J.,Kelly,J.P.(1996).Anetworkflow-basedtabusearchheuristicforthevehicleroutingproblem.TransportationScience30,379–393. Yang,W.H.,Mathur,K.,Ballou,R.H.(2000).Stochasticvehicleroutingwithrestocking.TransportationScience34,99–112. 因篇幅问题不能全部显示，请点此查看更多更全内容