Vehicle Routing Problem
with Time Windows
Jesper Larsen
LYNGBY2001
Ph.D. THESIS
NO.62
c
Copyright 2001
by
Jesper Larsen
PrintedbyIMM-DTUTechnicalUniversityofDenmark
ThisPh.D.thesisentitled\ParallelizationoftheVehicleRoutingProblemwith
Time Windows" has been preparedby Jesper Larsen during the period June
1995toMay1999,partlyattheDepartmentofComputerScience(DIKU)atthe
UniversityofCopenhagen,partlyattheDepartmentofMathematicalModelling
(IMM) attheTechnicalUniversityofDenmark(DTU).
ThePh.D. projecthas been supervisedby mymain advisor professorJens
Clausenand associateprofessorOli B.G. Madsen. The subjectsof thethesis
areimprovingtheperformanceofthesequentialalgorithmfortheVRPTWand
parallelization of the vehicle routing problem with time windows. The thesis
issubmittedasapartialfulllmentoftherequirementforobtainingthePh.D.
degreeattheTechnicalUniversityofDenmark.
Theprojectwassupported by theEPOS (EÆcientParallelalgorithms for
OptimizationandSimulation)projectoftheDanishNSF(StatensNaturviden-
skabeligeForskningsrad).
Acknowledgements
A Ph.D.projectis notaone-manproject,thereforeI wouldrstand foremost
liketothankmysupervisorsJensClausenandOliB.G.Madsenfortheirsup-
port and encouragements throughout theproject. Without them this project
woulddenitely nothavebeenpossible. I would also liketo thank myformer
colleaguesfromtheAlgorithmicsandOptimizationgroupattheDepartmentof
ComputerScience, UniversityofCopenhagen, and mypresentcolleaguesfrom
the section of OperationsResearch at the Departmentof Mathematical Mod-
elling,TechnicalUniversityofDenmark. EspeciallyIwouldliketothankStefan
KarischforapositiveoÆce-partnershipduringthe6monthswesharedthesame
oÆce. I would alsolike to thankNiklas Kohl, Ph.D. from the Department of
Mathematical Modelling, for quick responses to my numerous e-mails on his
codeandtheVRPTWingeneral.
A special thanks goes\down under" to New Zealand. My5 1
2
month stay
at theDepartmentofEngineeringScienceat theUniversityof Auckland,New
Zealand, was in every respect wonderful. Professor David Ryan deliveredin-
valuablesupportandsupervising. AdditionallyI wouldliketothanktheentire
Ryanfamilyforletting mebecomeanaturalpartof10 NgapuhiRoad forthe
production runs of my parallel codewasmade onthe IBM SP2at UNIC, it
wasasignicanthelpformetobeabletobuildandtestthecodeontheparallel
computersat theUniversityofPaderborn,atacentralmomentwhereCPLEX
wasnotavailableattheIBMSP2,andIalwaysgotanansweronmynumerous
emails,when I wasstuckwith someinaneerrormessage. Thanks tothem the
parallelcodewasready forproductionsrunsassoonasthenecessarysoftware
was availableontheIBMSP2.
FinallyIwouldliketothankfriendsandfamilyfortheirsupportduringthe
almost4yearsittooktocompletethisthesis. Duringaprojectthatlastsalmost
4years therearebound tobeperiods wherethings aren'tworkingastheyare
supposed todo. Intheseperiodsencouragementandcomfortfrom friendsand
familywasnevermissing.
Lyngby,May1999.
JesperLarsen
Routingwithtime windows(VRPTW)hasbeenanareaof researchthathave
attractedmanyresearcherswithinthelast10{15years. Inthisperiodanumber
ofpapersandtechnicalreportshavebeenpublishedontheexactsolutionofthe
VRPTW.
TheVRPTWisageneralizationofthewell-knowncapacitatedroutingprob-
lem(VRPorCVRP).IntheVRPaeetofvehiclesmustvisit(service)anumber
ofcustomers. Allvehiclesstartandendatthedepot. Foreachpairofcustomers
orcustomer and depot there is acost. The costdenotes howmuch is costsa
vehicletodrivefrom onecustomertoanother. Everycustomermustbevisited
exactlyones. Additionallyeachcustomerdemands acertainquantityofgoods
delivered(knowas thecustomer demand). Forthevehicles we haveanupper
limit ontheamountofgoodsthat canbecarried(knownasthecapacity). In
themost basiccaseall vehicles areof thesametypeandhencehavethesame
capacity. Theproblemisnowforagivenscenariotoplanroutesforthevehicles
in accordancewith thementioned constraintssuch that the costaccumulated
ontheroutes, thexedcosts(howmuchdoesitcostto maintainavehicle) or
acombinationhereofisminimized.
InthemoregeneralVRPTWeachcustomerhasatimewindow,andbetween
allpairsofcustomersoracustomerandthedepotwehaveatraveltime. The
vehiclesnowhavetocomplywiththeadditionalconstraintthatservicingofthe
customers can only be started within the time windows of the customers. It
is legalto arrivebefore atimewindow\opens" butthe vehiclemustwait and
servicewillnotstartuntilthetimewindowofthecustomeractuallyopens.
For solvingthe problem exactly 4general types of solution methods have
evolvedin theliterature: dynamic programming, Dantzig-Wolfe (column gen-
eration), Lagrange decomposition and solvingthe classical model formulation
directly.
Presently the algorithms that uses Dantzig-Wolfe given the best results
(Desrochers,DesrosiersandSolomon,and Kohl),but thePh.D.thesisofKon-
toravdis shows promising results for using the classicalmodel formulationdi-
rectly.
In this Ph.D. project we have used the Dantzig-Wolfe method. In the
Dantzig-Wolfemethodtheproblemissplitintotwoproblems: a\masterprob-
lem" and a \subproblem". The master problem is arelaxed set partitioning
eacharc,andthese costsarethenusedin thesubproblemin orderto generate
routesfromthedepotandbacktothedepotagain. Thebest(improving)routes
arethen returnedto themasterproblem andenteredinto therelaxedset par-
titioningproblem. Astheset partitioning problemis relaxedby removingthe
integerconstraintsthesolutionisseldomlyintegralthereforetheDantzig-Wolfe
methodisembeddedinaseparation-basedsolution-technique.
InthisPh.D.projectwehavebeentryingtoexploitstructuralpropertiesin
orderto speedupexecutiontimes,andwehavebeenusing parallelcomputers
tobeabletosolveproblemsfasterorsolvelargerproblems.
ThethesisstartswithareviewofpreviousworkwithintheeldofVRPTW
bothwithrespect to heuristicsolutionmethods andexact(optimal) methods.
Throughaseriesofexperimentaltestsweseektodeneandexamineanumber
ofstructuralcharacteristics.
The rst series of tests examine the use of dividing time windows as the
branchingprincipleintheseparation-basedsolution-technique. Insteadofusing
themethods previouslydescribedin theliterature fordividing aproblem into
smallerproblemsweuseamethodsdevelopedforavariantoftheVRPTW.The
resultsareunfortunatelynotpositive.
Instead of dividing a problem into two smaller problems and try to solve
thesewecantrytogetanintegersolutionwithouthavingtobranch. Acutisan
inequalitythatseparatesthe(non-integral)optimalsolutionfromalltheinteger
solutions. Byndingandinsertingcutswecantrytoavoidbranching. Forthe
VRPTW Kohl hasdeveloped the2-path cuts. In theseparationalgorithm for
detecting2-path cuts anumberof testare made. Bystructuringtheorder in
whichwetrytogeneratecutsweachievedverypositiveresults.
IntheDantzig-Wolfeprocessalargenumberofcolumnsmaybegenerated,
butasignicantfractionofthecolumnsintroducedwillnotbeinterestingwith
respect to the master problem. It is apriori not possible to determine which
columnsareattractiveandwhicharenot,butifacolumndoesnotbecomepart
of thebasis ofthe relaxed set partitioning problem weconsider it to beof no
benetforthesolutionprocess. Thesecolumnsaresubsequentlyremovedfrom
themasterproblem. Experimentsdemonstrateasignicantcutoftherunning
time.
Positiveresultswerealsoachievedbystoppingtheroute-generationprocess
prematurelyinthe caseoftime-consumingshortestpath computations. Often
this leads to stopping the shortest path subroutine in cases where the infor-
mation (from the dual variables) leads to \bad" routes. The premature exit
from theshortestpathsubroutinerestrictsthegeneration of\bad" routessig-
nicantly. This producesverygood results and hasmade it possible to solve
probleminstancesnotsolvedtooptimalitybefore.
The parallel algorithm is based upon the sequential Dantzig-Wolfe based
algorithm developedearlierin theproject. Inan initial(sequential) phaseun-
to startworkoneveryprocessortheparallel solutionphaseisinitiated. Inthe
parallelphaseeachprocessorrunsthesequentialalgorithm.Togetagoodwork-
loadastrategybasedonbalancingtheloadbetweenneighbouringprocessorsis
implemented. TheresultingalgorithmiseÆcientandcapableofattaininggood
speedupvalues. Theloadbalancingstrategyshowsanevendistribution ofwork
amongtheprocessors. DuetothelargedemandforusingtheIBMSP2parallel
computerat UNIC ithasunfortunately notbepossibleto run asmanytests
aswewould haveliked. Wehavealthough managed tosolveoneproblemnot
solvedbeforeusingourparallelalgorithm.
Ruteplanlgningmedtidsvinduer(VRPTW)harindenfordesidste10{15ar
optaget mange forskere. Der er i denne periode publiceret mange artikler og
rapporterindenforemneteksaktlsningafVRPTW.
VRPTWerengeneraliseringafdetvelkendteruteplanlgningsproblemmed
kapacitetsbegrnsninger(VRPellerCVRP).IVRPskalenadeafbilerbesge
en rkkekunder. Bilerne starterogslutter deres ruteri et depot, og forhver
direkte forbindelse mellem to kunder ellerenkunde og depotet erderfastlagt
en omkostning. Hver kunde skal besges af prcis en bil. Desuden nsker
hver kunde en bestemt mngde varer leveret. Den samlede mngde varer,
der kan transporteres af en bil er begrnset af bilens kapacitet. For et givet
scenarionskesatminimeredenomkostningiformafkrtafstandsombilerne
akkumulereunderdereskrsel,defasteomkostninger(hvormegetkosterdetat
holdeenbilkrende)ellerenkombinationheraf.
I VRPTW tildeles hver kunde et tidsvindue samt rejsetider mellem hver
af kunderne og mellem kunderne og depotet. En bil skal nu betjene kunden
indenfor det givne tidsvindue. Kommer bilen fr tidsvinduets start ma den
venteindtilkundenstidsvindue\abner".
Indenforeksakte metodertil lsningafVRPTW erderilitteraturenblevet
beskrevet 4 mulige metoder: dynamisk programmering, Dantzig-Wolfe (sjle-
generering), Lagrange dekomposition og direkte lsning af den klassiskemod-
elformulering.
Tildatoharalgoritmer,derbyggerpaDantzig-Wolfegivetdebedsteresul-
tater (Desrochers, Desrosiers og Solomon, og Kohl), men Kontoravdis' ph.d.-
afhandling, hvorider arbejdes direkte medden klassiskemodelformulering ser
lovendeud.
I Dantzig-Wolfemetoden, sombenyttes i dette ph.d.-projekt, opdelespro-
blemet i 2 delproblemer: et \master problem" og et \subproblem". Master
problemeteretrelaxeretklassedelingsproblemsomsikrer,athverkundebesges
prcisengang,menssubproblemeteterkorteste-vej-problem,somtagerhensyn
til kapacitetsbegrnsningerog overholdelseaf tidsvinduer. Vha. master prob-
lemet beregnes dereducerede omkostningerfor deenkelte direkte forbindelser
mellem kunderne(ogkunderogdepotet). Dissebrugessaisubproblemettilat
beregneden/dekortestevejefra depot og tilbagetil depotet. De bedsteruter
returnerestil masterproblemet, dertilfjerruternesomsjleri detrelaxerede
til at givehurtigere lsningstider,dels brug afparallelcomputerefor at kunne
lsestrreproblemerellerlseproblemerhurtigere.
Afhandlingen indledes med en gennemgang af eksakte og heuristiske me-
toder for VRPTW, samt en teoretisk gennemgang af problemet. Igennem en
langrkkeeksperimentelleafprvningersgesenrkkestrukturelleegenskaber
deneretogundersgt.
Undersgelserne starter med en rkke tests af brug af tidsvinduerne som
forgreningskriterieienseparations-baseretlsningsmetode. Istedetforatbruge
deklassiskemetodertildelingafetikkelstdelproblemitomindredelproblemer
udfresenmetodebeskrevetforenvariantafVRPTW.Resultaterneerdesvrre
ikkepositive.
I stedet for at opdele et delproblem i to mindre delproblemer kan man
gennem tilfjelse af gyldige uligheder, dvs. uligheder der afskrer den bedst
fundneikke-heltalligelsningfraalleheltalslsningerne,sgeatopnaenheltals-
lsningudenbrugafforgreningsteknikken. TilVRPTWerdesakaldte\2-path
uligheder"udvikletafKohl. Iforbindelsemedbrugaf2-pathulighederudfres
en rkke tests med henblik pa eektivisering af separationsalgoritmen. Her
opnas meget positive resultater i forbindelse med en ordnet gennemgang af
muligegyldigeuligheder.
I Dantzig-Wolfeprocessendannesen mngderuter,og enstor delaf disse
vilikkevreinteressantei forholdtil masterproblemet. Deterapriorisvrt
atsehvilkesjlerderikkeerinteressante,menhvisensjleikkeopnaratindga
ienbasistillsningenafetLP-relaxeretklassedelingsproblem,madensknnes
at vre uden nytte. Disse kan fjernes fra master problemet. Eksperimenter
viser,atdetteresultererienvsentlignedgangialgoritmenskretid.
Positive resultaterer ogsaopnaet ved at stoppe rutegenereringsprocessen
tidligere i tilflde af lange kretider for korteste-vej-algoritmen. Ofte bliver
processenstoppetitilflde,hvormanglendeinformationergiver\darlige"ruter.
Dermedundgasdannelsenaf mangedarligeruter. Denneidegivermegetgode
resultaterogharmuliggjortlsningenafproblemer,derikketidligereharvret
lsttiloptimalitet.
Den parallellealgoritmetager situdgangspunkti densekventielle Dantzig-
Wolfe baserede algoritmeudviklede tidligere i projektet. Efter en initiel fase,
hvorder dannes et antal endnu ulste delproblemer fordelesulste delproble-
mer pa alleprocessorer. Herefter sker problemlsning parallelt. For at sikre
en ligelig lastfordeling,er derimplementeret en strategi tillastfordeling. Den
resulterendeparallellealgoritmeereektivogistandtilatopnagodespeedups.
Lastfordelings-strategien fremviser en meget jvn fordeling af delproblemer
imellem processorene. Grundet det store pres pa UNIC's SP2 parallelcom-
puter har detikkevret muligt at udfre ret mange eksperimenter paendnu
ulste problemer. Deterdog lykkedesvha.den parallelle algoritmeat lse et
Abbreviations Meaning First
occurrence
CVRP CapacitatedVehicleRoutingProblem 3
ESPP ElementaryShortestPathProblem 10
ESPPCC ElementaryShortestPathProblemwith
CapacityConstraints
10
ESPPTW ElementaryShortestPathProblemwith 10
TimeWindows
ESPPTWCC ElementaryShortestPathProblemwith 10
TimeWindowsandCapacity
Constraints
GAP GeneralizedAssignmentProblem 17
GLS GuidedLocalSearch 31
GRASP Greedy Randomized Adaptive Search
Procedure
30
MCVRPTW MultiCompartmentVehicleRouting 72
ProblemwithTimeWindows
MDVRPTW Multi Depot Vehicle Routing Problem
withTimeWindows
72
MIMD MultipleInstruction-streamMultiple 79
Data-stream
MISD MultipleInstruction-streamSingle 80
Data-stream
Continuedonthe nextpage
MPI MessagePassingInterface 6
MPP MassivelyParallelProcessing 80
PRAM ParallelRandomAccessMachine 77
PVM ParallelVirtualMachine 6
RAM RandomAccessMachine 77
SAP Semi AssignmentProblem 18
SIMD SingleInstruction-streamMultiple 78
Data-stream
SISD SingleInstruction-streamSingle 78
Data-stream
SPP ShortestPathProblem 59
SPPTW ShortestPathProblem with 63
TimeWindows
SPPTWMCC ShortestPathProblem withTime 72
Windows and Multiple Capacity Con-
straints
TSP TravellingSalesmansProblem 2
TSPTW TravellingSalesmansProblemwith 9
TimeWindows
VRP VehicleRoutingProblem 3
VRPBTW Vehicle Routing Problem with Back-
haulingandTimeWindows
74
VRPLC VehicleRoutingProblemwith 4
LengthConstraint
VRPTW VehicleRoutingProblemwith 3
TimeWindows
Preface iii
Summary v
Resume(in Danish) ix
List ofAbbreviations xi
1 Introduction 1
1.1 Motivation . . . 1
1.2 CombinatorialOptimization . . . 4
1.3 Whygoparallel? . . . 5
1.4 Outlineofthethesis . . . 6
1.5 Overviewofcontributionofthisthesis . . . 6
2 Routingwith Time Windows 7 2.1 Amathematicalmodel oftheVRPTW . . . 7
2.2 Complexityissues. . . 9
2.3 Reviewofoptimalalgorithms . . . 11
2.3.1 DynamicProgramming . . . 12
2.3.2 LagrangeRelaxation-basedmethods . . . 14
2.3.3 Othermethods . . . 18
2.4 Reviewofapproximationalgorithmsandheuristics . . . 19
2.4.1 Route-buildingheuristics . . . 19
2.4.2 Route-improvingheuristics . . . 21
2.5 Overviewofexactmethodsandheuristics . . . 31
3 SequentialRoutingwith TimeWindows 37 3.1 Aset partitioningmodeloftheVRPTW. . . 37
3.2 Preprocessing . . . 39
3.3 Branch-and-Price . . . 40
3.3.1 ColumnGeneration . . . 40
3.3.2 Branch-and-Bound . . . 42
3.4 Achievingtighterlowerbounds . . . 48
3.4.1 TheSubtoureliminationconstraints . . . 49
4 Shortest Path with Constraints 57
4.1 Themathematicalmodel. . . 57
4.2 ADynamicProgrammingAlgorithm . . . 59
4.2.1 Thealgorithm . . . 59
4.2.2 Dominancecriterion . . . 63
4.2.3 Eliminationoftwo-cycles . . . 64
4.3 Implementationissues . . . 66
4.3.1 Implementationofdominance . . . 66
4.3.2 Generalizedbuckets . . . 66
4.3.3 Miscellaneousremarks . . . 69
5 Generalizations of the VRPTW model 71 5.1 Non-identicalvehicles . . . 71
5.2 Multipledepots . . . 71
5.3 MultipleCompartments . . . 72
5.4 MultipleTimeWindows . . . 74
5.5 SoftTimeWindows . . . 74
5.6 Pick-upanddelivery . . . 74
5.7 Additionalconstraints . . . 75
6 ParallelImplementation 77 6.1 ParallelProgramming . . . 77
6.2 TheIBMSP2computeratUNIC. . . 80
6.3 AparallelVRPTW algorithm . . . 83
6.3.1 Solvingthesubproblem(SPPTWCC) . . . 83
6.3.2 Solvingthemasterproblem . . . 84
6.3.3 Branchingandbounding. . . 85
6.4 Implementationaldetails . . . 88
6.4.1 Theinitial phase . . . 89
6.4.2 Theparallelphase . . . 89
6.4.3 Themessagepassing/loadbalancingframework . . . 90
6.5 Summary . . . 91
7 Sequential computationalexperiments 93 7.1 TheSolomontest-sets . . . 93
7.2 UsingtheRyan-Fosterbranchingrulein VRPTW . . . 94
7.3 Experimentswithbranchingonresources . . . 99
7.4 Speedinguptheseparationalgorithmfor2-pathcuts . . . 109
7.4.1 AnewwayofgeneratingtheS sets. . . 109
7.4.2 Heuristicforthe\feasibilityTSPTW"problem . . . 115
7.5 Usingthe\trivial"lowerbound . . . 120
7.7 Reducingthenumberofcolumns . . . 122
7.8 Speedingupthecolumngeneration. . . 131
7.8.1 Randomselection. . . 132
7.8.2 Forcedearlystop. . . 135
8 Parallel computationalexperiments 145 8.1 Thebasicparallelprogram . . . 145
8.2 Strategyforselectionofsubspaces . . . 149
8.3 Exchangeof\good"routes . . . 151
9 Conclusions 155 9.1 TheRoadAhead . . . 155
9.1.1 Forcedearlyofstopthethe2-path separationalgorithm . 155 9.1.2 Describingandimplementingnewcuts. . . 156
9.1.3 Redesignofthe2-pathcuts . . . 156
9.1.4 Heuristicsbasedonthecolumn generationtechnique . . . 156
9.1.5 Advanced branchingmethods . . . 157
9.1.6 Stabilizedcolumngeneration . . . 159
9.1.7 Limitedsubsequence . . . 161
9.1.8 Speedinguptheparallelalgorithm . . . 162
9.2 Mainconclusions . . . 162
Bibliography 165
A The R1, C1and RC1 problems 177
B The R2, C2and RC2 problems 199
C Ph. D. thesesfrom IMM 217
Introduction
Allobstaclesinlife aremereopportunities.
- (writtenon abenchatMt.Hobsonpark, Auckland)
In modelling of routingproblems terminology is to agreat extent derived
fromgraphtheory. Notionslikevertex,node,arc,pathetc.willnotbeexplained.
Ingeneralit isassumed that thereaderis familiarwith theconceptsofgraph
theoryandlinearprogramming.
Thenotation presented and used throughout this thesisis identical to the
notationusedin [Koh95].
1.1 Motivation
Intherealworldmanycompaniesarefacedwithproblemsregardingthetrans-
portation of people, goods orinformation { commonly denoted routingprob-
lems. Thisisnotrestrictedtothetransportsectoritselfbutalsoother compa-
niese.g.factoriesmayhavetransportofpartstoandfromdierentsitesofthe
factory,andbigcompaniesmayhaveinternalmaildeliveries. These companies
haveto optimize transportation. As theworld economyturns moreand more
global,transportationwillbecomeevenmoreimportantinthefuture.
Backin1983Bodinetal.in[BGAB83]reportedthatin1980approximately
$400billionwereusedindistributioncostintheUnitedStatesandintheUnited
Kingdom the corresponding gure was $15 billion. Halse reports in [Hal92]
from an article from the Danish newspaper Berlingske Tidende that in 1989
76:5%ofallthetransportationofgoodswasdonebyvehicles,whichunderlines
Denmarktheguresare13%for1981and15%for1994accordingto[The98].
Therefore solving dierent kindsof routing and scheduling problems is an
importantareaofOperationsResearch (OR).Cuttingevenasmall fractionof
thecostsmayresultinlargesavingsandreduce thestrainontheenvironment
caused bypollutionand noise. In[Bod90] anumberof successfulapplications
madeoverthepast20yearsarementioned.
Inapureroutingproblemthereisonlyageographic component,whilemore
realisticroutingproblemsalsoincludeaschedulingpart,thatis,atimecompo-
nent.
Theproblemsinresearchareoftenmoresimplethanreal-lifeproblems. But
eventhoughanumberofreal-lifeconstraintsareleftout(e.g.constraintsforced
bylegislation,tradeunions ornature) theresearch modelstypicallymodelthe
basicpropertiesand thereby provide thecore resultsused in the analysisand
implementation of systemsin real-life problems. Thereforea numberof basic
models exist thatresearchersagreeare importantinvestigating. Thesemodels
willbrieybeintroducedhere.
Oneofthebestknownroutingproblemisatthesametimethesimplestone
namelytheTravelingSalesmanProblem(orTSP).Anumberofcitieshavetobe
visitedbyasalesmanwhomustreturntothesamecitywherehestarted. The
routehastobeconstructedinordertominimizethedistancetobetraveled. A
typical solutionto a TSP problem isshown in gure1.1. This problem often
acts as a test bed for new ideas or paradigmsbefore moving on to the more
advancedmodels.
v v
v v
v
v
@
@
@
@
@
@
@
@
@
@
@
@
Figure1.1: AtypicalsolutiontoaTSPinstance.
Inthem-TSPproblem,msalesmenhavetocoverthecitiesgiven. Eachcity
must be visited by exactlyone salesman. Every salesmanstarts o from the
samecity(called thedepot)and mustat theend ofhis journeyreturn tothis
city again. We now wantto minimizethe sumof the distances of theroutes.
Both the TSP and m-TSP problems are pure routing problems in the sense
TheVehicle RoutingProblem (or VRP) is the m-TSPwhere ademand is
associatedwitheach city, and each vehiclehaveacertain capacity(not neces-
sarily identical). For asurveyof the VRP refer to [Lap97, Gol84]. Be aware
that during thelater years anumberofauthors have\renamed"this problem
theCapacitatedVehicleRoutingProblem(orCVRP).Thesumofdemandson
aroutecannotexceedthecapacityofthevehicleassignedtothis route. Asin
them-TSPwewantto minimizethesumofdistancesoftheroutes. Note that
theVRP isnotpurelygeographicsincethedemand maybeconstraining. The
VRP is the basic model for a large number of vehicle routingproblems. We
mentionthemostimportanthere. Ingure1.2atypicalsolutiontotheVRPis
shown. Notethatthedirectioninwhichtheroute(s)aredrivenisunimportant
bothfortheTSPandtheVRP .
1 v
v v
v v
@
@
@
@ X
X
X
X
X
X
X
X
X
X
X
X
X
X S
S
S
S
S
S
S
2
v v
v
3 v
v
v
v v
v
Q
Q
Q
Q
Q
Q
@
@
B
B
B
B
B
B
Q
Q
Q
Q
Q
Q
@
@
@
@ 4
v v
v v v
v
v
Q
Q
Q
Q
Q
Q
Figure1.2: AtypicalsolutiontoaVRPinstance(4routes). Thesquaredenotes
thedepot.
IfweaddatimewindowtoeachcustomerwegettheVehicleRoutingProb-
lem with Time Windows(VRPTW). In additionto the capacityconstraint,a
vehiclenowhas to visita customer within acertain time frame. The vehicle
may arrivebefore the time window \opens" but thecustomer cannotbeser-
viceduntilthetimewindows\opens". Itisnotallowedtoarriveafterthetime
window has \closed". Some models allow for early orlate servicing but with
someformofadditionalcostorpenalty. Thesemodelsaredenoted\soft"time
windowmodels (seee.g. [Bal93]). Byfarthemostresearch hasbeenmadeon
ofitemstobedelivered. IntheSplitDeliverymodelthedemandofacustomer
is notnecessarilycoveredby just onevehiclebut maybe splitbetweentwoor
more. Thesolutionsobtainedinasplitdeliverymodelwillalwaysbeatleastas
goodasforthe\normal"VRPandoftenwemaybeabletoutilizethevehicles
betterand therebysavevehicles. FinallywementionthePickup and Delivery
variantwherethevehicles notonlydeliveritemsbut alsopickupitemsduring
the routes. This problem can be variedeven more accordingto whether the
deliveriesmustbecompletedbeforestartingtopickupitemsorthetwophases
canbeinterleaved.
These problems areall \hard"to solve(amoreformal complexityanalysis
is givenin section 2.2). FortheVRPTW exact solutionscanbefound within
reasonable time for some instances up to about 100 customers. A review of
exactmethods fortheVRPTW isgiveninsection2.3.
Asindicatedabove,oftenthenumberofcustomerscombinedwiththecom-
plexityof real-lifedata does notpermit solvingthe problem exactly. Inthese
situationsonecanapplyapproximationalgorithmsorheuristics. Bothapproxi-
mationalgorithmsandheuristicsproduceafeasiblebutnotnecessarilyoptimal
solution. Whereasaworst-casedeviationisknownforapproximationalgorithms
nothingaprioriisknownforheuristics,buttypicallytheycanbetunedtoper-
form verywell. These non-exactmethods fortheVRPTWwill bereviewedin
section2.4.
Iftheterm\vehicle"isconsideredmoreloosely,numerousschedulingprob-
lemscanalsoberegardedasVRPTW.Anexampleisthatforasinglemachine,
we want to schedule a number of jobs where weknow the ow time and the
timetogo fromrunningonejob tothenextone. Thisschedulingproblemcan
beregardedasaVRPTWwithasingledepot,singlevehicleandthecustomers
representsthejobs. Thecostofchangingfromonejobtoanotherisequaltothe
distancebetweenthetwocustomers. Thetimeistakestoperformtheactionis
theservicetimeofthejob.
Forageneralandin-depthdescriptionoftheeldofroutingandscheduling
see[DDSS93,Bre95,CL98].
1.2 Combinatorial Optimization
Theproblemsthat will beinvestigatedin this thesisarealloptimization prob-
lems. An optimization problem cangenerallybe formulatedasminimizing or
maximizing (from now on we will only consider minimization) the value of a
function f calledthe objective function. Thevariables x
i
(fori=1;2;:::;x
k )
arecalleddecision variables(alternativelywewritex=(x
1
;x
2
;x
3
;:::;x
k )). A
solutions space. An optimizationproblemcanthenbestatedas:
minf(x)
subjecttox2S
The solution set S is typically described implicitly by a set of equations
and inequalities to be fullled by feasible solutions. It is important to note
that agivenoptimization problem canbe formulatedin anumberof dierent
ways with respect to objective function, decisionvariables and description of
thesolutionspace. Dierentformulationsof thesame problemcaninpractice
yieldverydierentalgorithmsforsolvingtheproblemandconsequentlydierent
computationaleects.
Combinatorial optimization problems are optimization problems for which
thesetoffeasiblesolutionsarenite,butusually exponentiallylargeorcount-
ably innite, as afunction ofthe problem data. EÆcientalgorithms exist for
someofthese,whileothersseemsolvableonlybymethodsrequiringexponential
time. Problems ofthe lattertypeare called NP-hardproblems (fora further
discussiononcomplexityissuesseesection2.2orreferto[GJ79]).
1.3 Why go parallel?
FortheVRPTW optimalalgorithms oftoday cansolveproblemsupto about
100customers. Inordertopushthelimitfurtherwehaveanumberofmethods
in our tool-box. One of the methods is to use parallel computers, thereby
increasing the computational power beyond what is available with sequential
computers. A parallel computer is a set of processors that are able to work
cooperativelytosolveacomputationalproblem,adenition thatincludesboth
\real"parallel computersbutalsosequentialcomputersin anetwork.
Besidessolvingpreviouslyunsolvedproblemsanotherattractiveaspectisthe
abilitytosolveproblemsfaster. Ifittakesweeksormonthsbeforeasolutionto
aproblemisfounditbecomeshardtousetheresultsinresearchthatdemands
alot of experimentsforexample becauseof tuning ofthe algorithm. But ifit
successfully can be parallelized the runningtime may be cut to daysor even
hourswhichmakesitpossibletorunseveraltests.
Butparallelcomputingisalsointerestingfromtheperspectiveoftheindus-
try. Inhighlytime-criticalenvironmentsprogramsoneventhefastestsequential
computermaynotbefastenough. Heretheparallelcomputermaybeanalter-
nativetocutting downonaccuracy,problemsizeorexibility.
Oneofthemain problemsofparallelcomputingisthat auniformmodelof
computingdoesnotexist,asanumberofnewparametersareintroduced.
Anotherproblem usedtobethateachparallelcomputerhaditsownset of
commandsforcontrollingtheparallelismmakingitverydiÆcultandexpensive
to portto anotherplatform.
From thebeginningof the 90'sanumber ofmessagepassing interfacesfor
parallelcomputersstartedtoemergeasforexampleP4,PARMACSandPICL.
(PVM,see[GBD 94])andMessagePassingInterface(MPI,see[GLS94,Pac95])
this processhasbeenmadeconsiderably moreeasy. As thesebecamede facto
standardsthevendorshaveconstructedportableandeÆcientimplementations
ofthemessagepassingparadigm. With MPIonecanstarto usinganetwork
of workstations as a parallel computer (e.g. at night when nobody else are
using them). If the project then turns out to be a success or the nancial
supportbecomesavailablea\real"parallelcomputercantakeoverthejobwith
aminimal eortinmovingthecode.
The target machine for the parallel programsdeveloped in this thesiswill
beMIMDparallelcomputerswithdistributedmemory(theterminologywillbe
explainedinchapter6).
1.4 Outline of the thesis
Inchapter2amathematicalmodelfortheVRPTWispresented. Furthermore
complexityresultsandareviewofrelevantliteratureispresented.
Thesequentialalgorithmispresentedin thechapters3and4,andinchap-
ter6theparallel algorithmisdescribed.
Chapter 7containsadescriptionof theexperimental setupand theresults
obtainedfor theexperimentsmadewith thesequentialalgorithm,whilechap-
ter 8 contains thetests made using the parallel algorithm. Finally the thesis
endswithaconclusioninchapter9.
1.5 Overview of contribution of this thesis
Thetwomain contributionsof this thesisarethe developmentand implemen-
tation of a parallel algorithm for the VRPTW and a thorough investigation
in thecharacteristicsof the execution of a column-generation-basedVRPTW
algorithm. The analysis resultedin techniques for signicant reductionof the
runningtime. Amongthedevelopedtechniquesarenewmethodsforconstruct-
ingsets for2-pathcuts,removalofunused columnsandpremature stopofthe
routegeneratingsubroutine. Thesecontributionshavemadeitpossibletosolve
instances from the Solomon test-set that have not previously been solved to
optimality.
Other contributions are made on the investigation of resource constrained
branching anduseof aheuristicforsolvingthe\feasibilityTSPTW"asasub-
routineingenerating2-pathcuts.
The Vehicle Routing
Problem with Time
Windows
In this chapter we formalize the loose description of the VRPTW as it was
presentedintheintroduction. Westatetheproblemmathematicallyanddiscuss
complexityissues. Finallywelook brieyat relatedresearchboth foroptimal
algorithms and for heuristics and approximation algorithms. Huge amounts
of resultsexist forthe VRP. Theamountof research done onthe VRPTW is
growingasanacknowledgementtotheimportance oftheproblem.
2.1 A mathematical model of the VRPTW
The VRPTW is given by a eet of homogeneous vehicles (denoted V), a set
of customersC and adirectedgraphG. Thegraphconsistsof jCj+2vertices,
wherethecustomersaredenoted1;2;:::;nandthedepotisrepresentedbythe
vertex0(\the driving-outdepot")andn+1(\thereturningdepot"). Theset
of vertices, that is, 0;1;:::;n+1is denoted N. The set of arcs (denoted A)
represents connections between the depot and the customers and among the
customers. No arc terminates in vertex 0, and no arc originates from vertex
n+1. With eacharc(i;j),where i6=j,weassociateacost c
ij
andatime t
ij ,
whichmayinclude servicetimeatcustomeri.
Each vehicle has a capacity q and each customer i a demand d
i
. Each
customer i hasa time window [a
i
;b
i
]. A vehiclemust arrive at the customer
before b
i
. It canarrivebeforea
i
but thecustomerwill notbeserviced before.
The depot also hasatime window[a
0
;b
0
] (the time windowsfor bothdepots
are assumedto beidentical). [a
0
;b
0
] iscalled thescheduling horizon. Vehicles
maynotleavethedepot before a
0
andmustbebackbeforeorattimeb
n+1 .
Itisassumedthatq;a
i
;b
i
;d
i
;c
ij
arenon-negativeintegers,whilethet
ij 'sare
Themodelcontainstwosetsofdecisionvariablesxands. Foreacharc(i;j),
wherei6=j;i6=n+1;j6=0,andeachvehiclekwedenex
ijk as
x
ijk
=
0; ifvehiclekdoesnotdrivefromvertexito vertexj
1; ifvehiclekdrivesfrom vertexitovertexj
Thedecisionvariables
ik
isdenedforeachvertexiandeach vehiclekand
denotesthetimevehiclekstartstoservicecustomeri. Incasethegivenvehicle
k doesnotservicecustomeri s
ik
doesnotmeananything. Weassumea
0
=0
andtherefores
0k
=0,forallk.
We wantto design aset ofminimal cost routes, onefor each vehicle, such
that
eachcustomerisservicedexactlyonce,
everyrouteoriginatesatvertex0andendsatvertexn+1,and
thetimewindowsand capacityconstraintsareobserved.
WecanstatetheVRPTW mathematicallyas:
min X
k 2V X
i2N X
j2N c
ij x
ijk
s.t. (2.1)
X
k 2V X
j2N x
ijk
= 1 8i2C (2.2)
X
i2C d
i X
j2N x
ijk
q 8k2V (2.3)
X
j2N x
0jk
= 1 8k2V (2.4)
X
i2N x
ihk X
j2N x
hjk
= 0 8h2C;8k2V (2.5)
X
i2N x
i;n+1;k
= 1 8k2V (2.6)
s
ik +t
ij
K(1 x
ijk ) s
jk
8i;j2N;8k2V (2.7)
a
i s
ik b
i
8i2N;8k2V (2.8)
x
ijk
2f0;1g 8i;j2N;8k2V (2.9)
The constraints (2.2) states that each customer is visited exactly once,
and (2.3)means that no vehicle isloaded withmore thanit's capacityallows
itto. Thenextthree equations(2.4),(2.5)and(2.6)ensuresthat each vehicle
nally arrivesat the depot n+1. The inequalities(2.7) statesthat a vehicle
k cannotarriveatj before s
ik +t
ij
ifitis travelingfrom ito j. Here K isa
largescalar. Finallyconstraints(2.8)ensuresthat timewindowsareobserved,
and(2.9)aretheintegralityconstraints. Notethatanunusedvehicleismodelled
bydrivingthe\empty"route(0;n+1).
AsmentionedearlierVRPTW isageneralizationifbothTSPandVRP.In
casethetimeconstraints((2.7)and(2.8))arenotbindingtheproblembecomes
aVRP.Thiscanbeachievedbysettinga
i
=0andb
i
=M (whereMisalarge
scalar)forallcustomersi. Itshould benotedthatthetimevariablesenableus
toformulatetheVRPwithoutsubtoureliminationconstraints(describedlater).
IfonlyonevehicleisavailabletheproblembecomesaTSP.Ifmorevehiclesare
available and additionally c
0j
= 1;j 2 C and c
ij
= 0 otherwise we get the
Bin-packing problem. As the order in which we visit the customers become
unimportant (due to the \free" trips) the objective becomes to \squeeze" as
muchgoodsintoasfewvehicles(bins)aspossible.
Incasethecapacityconstraints(2.3)arenotbindingtheproblembecomes
am-TSPTW(againifonlyonevehicleisavailablewegetaTSPTW).
Finally when we removethe assignmentconstraints(2.2) the problem be-
comesaElementaryShortestPathProblemwithTimeWindowsandCapacity
Constraints(ESPPTWCC)foreveryvehicle,thatis,ndtheshortestpathfrom
the depot and back to the depot that does notviolate the time and capacity
constraints and visits the customers on the route at most one time. As all
vehiclesareidenticalallESPPTWCC'salsobecomeidentical.
2.2 Complexity issues
In this section wediscuss the computational complexity of the VRPTW and
relatedproblems. Firstthoughwegiveasmallreviewofcomplexitytheory.
An algorithmisageneralstep-by-stepprocedure forsolvingproblems. For
our purposes we canthink of it as being a computer program. Generally we
are interested in nding the most \eÆcient" algorithm for a given problem.
The problem is how to measure the eÆciency. Here,as in almost everywhere
in the literature, we focus on eÆciency with respect to the running time of
thealgorithm. Wemeasurethe timerequirementintermsof the\size"ofthe
probleminstance. Soinordertodothisweneedtospecifyanencodingscheme
fortheproblem. Theinputlengthofaninstanceisthendenedtobethenumber
ofsymbolsin thedescriptionoftheinstance. Thetimecomplexity function for
an algorithm expresses the largest time requirement for each possible input
length.
Analgorithmissaidtohavepolynomialtimecomplexityiftherunningtimeis
oforderO(n k
),wherendenotestheinputlengthandkisaconstantindependent
ofn. Ifthetimecomplexityfunction cannotbeboundedbyapolynomialthe
algorithm is said to have exponential time complexity. If the expression g l
,
where l isaconstantand g is thelargestinput value,is partofthe bounding
polynomialalgorithm.
A decision problem isaproblem that canbeansweredwith \yes"or\no".
P denotes the class of decision problems which can be solved in polynomial
time, and NP is the class of decision problems solvable in nondeterministic
polynomial time, that is, the problem can be solved in polynomial time by a
nondeterministic Turing machine (computer). The nondeterministiccomputer
can be viewed as acomputer capable of executing an unbounded (but nite)
numberofcomputations inparallel.
A problem X is said to be NP-complete, if any problem in NP can be
transformedto X in polynomialtime (X is saidto belong to theclass NPC).
So in asense the NP-complete problems constitutes aclass of the \hardest"
problems in NP. If just oneproblem in NPC is solvable in polynomial time
thenbytransitivityeveryproblemcanbesolvedinpolynomialtime. Obviously
P NP, but whether P =NP holds or notis unknown. There are though
manyreasonstobelievethatP 6=NP. FinallyaproblemisNP completein
thestrongsense ifnopseudo-polynomialalgorithmexistsunlessP =NP.
Given adecision problem Y, whether a memberof NP or not. If aNP-
complete problemcanbetransformedtoY,Y cannotbesolvedinpolynomial
time (unless of course P = NP). The problem Y is at least as hard as the
NP-complete problemsandthereforeY iscalledNP-hard.
The VRPTW contains several NP-hard optimization problems implying
that VRPTWis also NP-hard. Among the NP-hard problems contained as
specialcasesareTSP([GJ79,problemND22]and[LK81]),BinPacking([GJ79,
problemSR1])andVRP([LK81]).
EvenndingafeasiblesolutiontoVRPTWwithaxednumberofvehicles
isNP-hardinthestrongsense(see[Koh95]). Ifthenumberofvehiclesavailable
is unlimited feasibility amountsto determine whether asolutionconsisting of
theroutesdepot- i-depot,8i2C,isfeasible. Thisisaneasytaskandcanbe
doneinO(n)time.
Forthe shortestpath problems weknow that the \normal"Shortest Path
Problem(SPP)ispolynomial. ItcanbesolvedinO(nm)bytheBellmann-Ford-
Moorealgorithm(here ndenotesthenumberof verticesandm thenumberof
edges)(seee.g.[?]).
Adding constraints that imposes each vertex must to be visited at most
one time results in the Elementary Shortest Path Problem (ESPP). Adding
capacityconstraintsdenestheproblemdenotedESPPCC,timewindowsgives
us ESPPTW and nally adding both capacity constraints and time windows
resultsintheESPPTWCC.Asthefollowingpropositionshowstheseproblems
areallNP-hardinthestrongsense.
Proposition 2.1 ([Koh95]) TheESPPTWCC,ESPPCC,ESPPTWandESPP
Proof: Let us consider the ESPP. As this problem is a special caseof the re-
mainingproblems itsuÆcestoprove the proposition.
The proposition will beprovenby proving that if a pseudo-polynomial algo-
rithmexistsfortheESPPthenanpseudo-polynomialalgorithmwouldalsoexist
for the DirectedHamiltonian CircuitProblem. Thisproblem isstatedasNP-
completein the strongsense in [GJ79 , problem GT38]. Thereby we would get
P =NP.
TheDirectedHamiltonianCircuit Problem isgiven by adirectedgraphG=
(N;A). The question iswhetherG containsaHamiltoniancircuit.
Consider the instance of ESPP given by the fully connected directed graph
G 0
=(N;A 0
). Letusdenoteonevertexsastheorigin. Nowweassociateacost
c
e
witheach edgee2E 0
as
c
e
=
1; ife2E
0; otherwise
Nowif andonlyif theobjective function valueof the ESPPfroms andbackto
s againis jNj,then G containsaHamiltoniancircuit. 2
We canmake the problems somewhateasier by relaxing the \elementary"
constraintasthefollowingpropositionstates.
Proposition2.2 SPPTWCC,SPPTWandSPPCCareNP-hard,butsolvable
by apseudo-polynomialalgorithm if
1. t
ij
>0; 8i;j2N,and
2. d
i
>0; 8i2C
Proof: In [DS88a ] an algorithm for the SPPTW problem is developed. The
algorithm has a time complexity of O(min fmd;nDg), where n is the num-
ber of vertices and m the number of arcs. The widest time windows, that is,
max
i2N fb
i a
i
+1gisdenotedbyd, andD isthenumberofpossiblelabels. So
this algorithm ispseudo-polynomial. Alongthe samelinesonecanaddanother
constraintandstillgetapseudo-polynomial algorithm.
Notethat for SPPTWCC only one of the conditions has tobesatised, for
the two other problems oneof theconditionsisirrelevant. 2
2.3 Review of optimal algorithms
TherstpaperproposinganexactalgorithmforsolvingtheVRPTWwaspub-
lished back in 1987 in [KRT87]. Since then a number of papers have been
published andalmostallthealgorithms useoneofthreeprinciples:
The method based on column generation is implemented as part of this
Ph.D. project,asatthe momentitlooks tobethebestof theavailablemeth-
ods. Therefore a thorough discussion is presented in chapter 3. It has been
implementedand describedpreviouslyin [DDS92,Koh95].
Mostoftheapproachesrelyonthesolutionofashortestpathsproblemwith
additionalconstraints.
AdierentapproachisdescribedinthePh.D.thesis[Kon97]byKontoravdis.
Thiswillbedescribedlaterinthissection.
The research on the VRPTW has been surveyed in the papers[BGAB83,
SD88,DLSS88,DDSS93].
Presentlyno parallel implementation of thealgorithms for theVRPTW is
knownto theauthor.
2.3.1 Dynamic Programming
ThedynamicprogrammingapproachforVRPTWispresentedfortherst(and
only)timein[KRT87]. Thepaperisinspiredbyaearlierpaper[CMT81]where
Christodeset al.usethedynamicprogrammingparadigmtosolvetheVRP.
Thealgorithm ofKolenetal.useBranch-and-Boundtoachieveoptimality.
Each node in the Branch-and-Bound tree corresponds to three sets: F()
whichisthesetofxedfeasibleroutesstartingandnishingatthedepot,P()
whichisapartiallybuildroutestartingatthedepot,andC()denotestheset
ofcustomersforbiddentobenextonP().
Branching is done by selecting a customer i that is notforbidden, that is
i 62 C(), and that does not appear on any route, that is i 62 F()[P().
Branchingdecisionsaretakenonroute-customerallocations. Thentwobranches
aregenerated:oneinwhichthepartiallybuildrouteP()isextendedbyiand
onewhereiisforbiddenasthenextcustomerontheroute,thatis,iisaddedto
C(). CustomeriischosenasthecustomerthepartialrouteP()wasextended
within thecalculationthatleadtothelowerbound ofnode.
AteachBranch-and-Boundnodedynamicprogrammingisusedtocalculate
alowerbound onallfeasiblesolutionsdened byF();P()andC().
First wediscussthecaseoftherootnode(F()=;;C()=;andP()=
depot ). Here we construct a directed graph with vertices v(i;q;k) for i =
0;1;:::;n, q =0;1;:::;Qand k =0;1;:::;m, where n is the number of cus-
tomers,mthenumberofvehiclesandQisthesumofallcustomerdemandsq
i .
Hence,associatedwitheachBranch-and-Boundnodeisasetofroutes.
Adirectedpathfromv(0;0;0)tov(i;q;k)inthegraphcorrespondstoaset
ofkrouteswithatotalloadofqandwithdierentlastvisitedcustomers(each
oneinf1;2;:::;ig). Thearclengthsinthedirectedgraphwillbedenedasthe
totallengthofthecorrespondingroutes. Thelowerboundisthengivenbythe
minimum overk = 1;2;:::;m of the shortest paths lengths from v(0;0;0) to
toeitherF()orP())tobevisitedbyanyoftheroutesgenerated. Therefore
theresultingminimumisalowerbound.
Dynamicallywetrytoextendasetofkrouteswithloadqandlastcustomers
f1;2;:::;igtolast customersf1;2;:::;i+1g. Herethere aretwopossibilities:
Customer i+1 is not included as endpoint of any of the routes. This
resultsin anarcfrom v(i;q;k)tov(i+1;q;k)withlength0.
Notethatacustomeri+1thatisnotanendpointmightstillbememberof
oneoftheotherroutesgeneratedbythefunctionF(i;q)describedbelow.
Insert customer i+1 as the last customer on a route of load q 0
. This
generatesanarcfromv(i;q;k)tov(i+1;q+q 0
;k+1)oflengthF(i+1;q 0
)for
eachpossiblevalueofq 0
(seegure2.1). Generally,F(i;q)isdenedasthe
minimumlengthofafeasibleroutewithtotalloadqandlast customeri.
Thisproblemisashortestpathproblemwithsideconstraints.Itisrelaxed
to allow a customer to be serviced more than once and is solved by an
\extended"versionoftheDijkstraalgorithm(asexplainedinchapter4).
The routes associated with a given vertex v(i;q;k) are the routes given
fromthecomputationofF(i;q)andtheextensionmadeusingthearcsin
thegraph.
IfweareatanarbitrarynodeintheBranch-and-Boundtreewedistinguish
betweentwocases:
1. P()=;and
2. P()6=;.
IfP()=;wejustadjusttheproblemforthenumberofalreadygenerated
routes
^
k, theirloadq^and theset ofcustomers alreadyused in theseroutes
^
I.
Theabovedescribeddynamicprogrammingalgorithmcanthenbeusedonthis
reducedproblem.
Inthecaseof P() 6=;exactlyoneof theroutesin thelowerbound isan
extensionofP(). Now,let
F(i;q)betheminimumlengthofsuchanextension
(
F(i;q)iscalculatedinthesamewayasF(i;q)). Asbefore,theproblemcanbe
reducedaccordingto
^
k;q^and
^
I. Thedirectedgraphisnowextendedtocontain
verticesv(i;q;k)andv(i;q;k)andthefollowingarcs:
Arcsoflength0fromv(i;q;k)to v(i+1;q;k)andfromv(i; q;k)tov(i +
1;q;k). Thesecorrespondstonotusingthecustomer i+1in theroutes.
ArcsoflengthF(i+1;q 0
)fromv(i;q;k)tov(i+1;q+q 0
;k+1)andfrom
v(i;q;k) to v(i +1;q+q 0
;k+1) v(i +1;q+q 0
;k+1) for each possible
valueofq 0
.
v(i;q;k)
v(i+1;q;k+1)
v(i+1;q+q 0
1
;k+1)
v(i+1;q+q 0
2
;k+1)
v(i+1;q+q 0
p
;k+1)
0
F(i+1;q 0
1 )
F(i+1;q 0
2 )
F(i+1;q 0
p )
Figure2.1: Possibleoutgoingarcsfromavertexv(i;q;k)inthegraphunderlying
thedynamicprogrammingscheme. Noteq 0
1
<q 0
2
<:::<q 0
p .
2.3.2 Lagrange Relaxation-based methods
Thesecondmethodmentionedcontainsanumberofpapersusingslightlydier-
entapproaches. ThereisvariablesplittingfollowedbyLagrangerelaxation[JMS86,
FJM97,Mad88,Hal92],K-treeapproachfollowedbyLagrangerelaxation[FJM97]
andnallyKohletal. in[KM97]presentedshortestpathwithsideconstraints
approachfollowedbyLagrangerelaxation.
In[KM97]Kohlet al.relaxestheconstraintsensuringthat everycustomer
isservedexactlyonce, thatis
X
k 2V X
j2N x
ijk
=1 8i2C
isrelaxedandtheobjectivefunctionwiththeaddedpenaltytermthenbecomes
min X
k 2V X
i2N X
j2N (c
ij
j )x
ijk +
X
j2C
j :
Here
j
is theLagrangemultiplier associatedwiththe constraintthat ensures
foreachvehicle,butasthevehicleare assumedtobeidenticalall thejVjsub-
problems are identical. The resulting subproblem is a shortest path problem
withtimewindowandcapacityconstraintsandasthearccostsaremodiedby
subtractingtherelevantLagrangemultiplierthegraphmayevencontainnega-
tivecycles. Thisshortestpathproblem isverydiÆculttosolve,andasolution
to theproblemis discussedinchapter4.
Themaster problemwhich consistsof ndingthe optimalLagrangemulti-
pliers,i.e.Lagrangemultipliersthat yieldsthebestlowerbound,issolvedbya
methodusingbothsub-gradientoptimizationandabundlemethod. Kohletal.
managed to solveproblemsof 100customersfrom theSolomontest cases(see
reference[?]), amongthemsomepreviouslyunsolvedproblems.
In [FJM97] Fisher et al. presents an algorithm for solving the VRPTW
optimally where the problem is formulated asa K-tree problem with degree
2K on the depot. A K-tree for a graphcontaining n+1 vertices is aset of
n+K edges spanningthe graph. Informally,the VRPTW couldbedescribed
as nding aK-tree with degree 2K on the depot, degree2 on the customers
andsubjecttotimeandcapacityconstraints. AK-treewithdegree2K onthe
depotthereforebecomesequaltoK routes.
In[FJM97]theproblemisdenedasfollows:
min
x2X ;y2Y X
i;j2N;i6=j c
ij x
ij
s.t. (2.10)
X
i2N;i6=j x
ij
= (
1 ifj2C
k else
(2.11)
X
j2N;j6=i x
ij
= (
1 ifi2C
k else
(2.12)
X
i2S X
j2
^
S x
ij
k(S) 8SC;jSj2 (2.13)
X
i2
^
S X
j2S x
ij
k(S) 8SC;jSj2 (2.14)
mp 1
X
h=i x
i
h
;i
h+1
m
p
2 8p2P (2.15)
y
ij
= x
ij +x
ji
8i;j2N (2.16)
x
ij
2f0;1g (2.17)
y
ij
2f0;1g (2.18)
where x
ij
isset to1ifavehicletravelsdirectlyfrom customerito customerj
and 0otherwise. y
ij
is equaltothe numberof arcsjoining customers iand j,
that is x
ij +x
ji
. k(S) isalowerbound onthe number ofvehicles requiredto
servicethecustomers inS. Finally,X is allthex variablesand Y theset of
i+1
P =hi
1
;i
2
;:::;i
m
p
iisanytimeviolatingpath,thatis,thereisnowaytodeliver
thecustomersinthepathgivenwhilesatisfyingthetimewindows.
Allconstraintsexcepttheconstraintsensuringthatatmostonearcisjoining
customersiandjarethenLagrangianrelaxed. Theproblemisthensolvedwith
aminimumdegree-constrainedK-treeproblemassubproblemandtheLagrange
multipliers are set using the sub-gradient approach (these ideas were already
sketchedin[Fis94a]asanextensionofaoptimalalgorithmfortheVRPbutnot
implemented). Since thereareexponentiallymanyconstraintsin (2.13),(2.14)
and (2.15)only asubsetof these aregenerated and dualized. Theconstraints
aregeneratedastheyareviolated.
As mentioned, for given Lagrange multipliers the master subproblem is a
minimumdegreeconstraintK-treeproblem. A polynomialalgorithm forsolv-
ing this problem is given in [Fis94b]. Here rst a minimum spanning tree is
constructed and then the K least cost unused arcs are added to the tree. If
thedepot isnot incidentto 2K arcs,the K-treeismodiedbyaseries of arc
exchangesuntilthedepot hasreacheddegree2K.
This algorithm(depictedin gure2.2)wasabletosolveseveraloftheclus-
teredSolomontestcaseproblemstooptimality,butitwasnotabletosolveany
oftherandomSolomontestcaseproblemsexactly.
1 hInitializelagrangeanmultipliersi
2 hndaminimumspanningtreei
3 hadd thekleastcostunusedarcsi
4 hexchangearcsuntilthedepothasdegree2k i
5 hremovearcsincidenttothedepoti
6 ifhrelaxedconstraintsareviolatedithen
7 hupdate lagrangeanmultipliers i
8 ifhmoreiterationsi
9 goto 1
10 else
11 hBranch-and-Boundi
12 goto 1
13 else
14 hoptimalsolutioni
Figure2.2: TheminimumdegreeconstrainedK-treeprocedure.
Variablesplitting(sometimesalsoreferredtoasLagrangedecomposition,or
Costsplitting[NW88])fortheVRPTWwasrstpresentedinatechnicalreport
here. In[Mad88]fourdierentvariablesplittingapproachesarementionedbut
againnoneareimplementedortested. InthePh.D.thesis[Hal92]ofHalsethree
approachesare analysed and oneof these is implemented(the fourth variable
splitting approach outlinedin [Mad88]seemednotbebecompetitivewiththe
otherthree approachesat all).
In order to decompose the problem we introduce a decision variable y
ik
dened as:
y
ik
=
1; ifvehiclekvisitscustomeri
0; otherwise
Nowtheconstraints
y
ik
= X
j2N x
ijk
8i2N;k2V (2.19)
are introducedto theproblem. Byexpressing someof theconstraintsusingx-
variablesiny-variables,dierentvariablesplittingapproachescanbeobtained.
Firstwerewrite(2.2)and(2.3)byusingy
ik
insteadofx
ijk
andtherebyget:
X
k 2V y
ik
=1 8i2C (2.20)
X
i2C d
i y
ik
q 8k2V: (2.21)
Additionally weintroduce
y
ik
2f0;1g:
Notenowthat(2.19)istheonlyconstraintscoupling(2.20)and(2.21),and(2.4)
to(2.9). Ifonlythecouplingconstraints(2.19)arerelaxedwegettheobjective
function
XX
(c
ij +
ik )x
ijk
XX
ik y
ik
: (2.22)
The problem can now be split into two subproblems: One is based on (2.4)
to (2.9):
min
PP
(c
ij +
ik )x
ijk
subjectto networkconstraints
timeconstraints.
This problem is an Elementary Shortest Path Problem with Time Windows
(ESPPTW), aproblem that with respect to diÆculty is closelyrelated to the
ESPPTWCCproblem which is treatedin chapter 4,and theother problem is
basedon(2.20)and(2.21):
min
PP
ik y
ik
subjectto capacityconstraints
visitingcustomerconstraints
whichis aGeneralAssignmentProblem(GAP). TheGAPis initself arather
Another way of decomposing is moving the capacity constraints from the
secondsubproblemtotherst. Wethenget:
min
PP
(c
ij +
ik )x
ijk
subjectto networkconstraints
timeconstraints
capacityconstraints
which is anElementary Shortest Path Problemwith TimeWindowsand Ca-
pacityConstraints(ESPPTWCC),andthesecondsubproblembecomes
min
PP
ik y
ik
subjectto visitingcustomerconstraints.
ThisproblemiscalledaSemiAssignmentProblem(SAP)andisbasicallyaGAP
withoutcapacityconstraints. TheSAPcaneasilybesolvedbyinspection. This
approach wasimplemented by Halse in [Hal92] and some problems from the
Solomontestcases(seereference[?])with100customersweresolved.
Finallyonemayduplicatethecapacityconstraintsandplacethemineachof
thetwosubproblems. This resultsinan ESPPTWCCand GAP. Eventhough
thisresultsintwotime-consumingproblems,onecouldhopeforsharperbounds
andtherebylesswork.In[Mad90],Madsenreportsonnotsopromisingresults,
althoughnoguresarepresented. Thisapproachhasnotyetbeenimplemented.
As allmethods built onLagrange relaxationuse relaxation(eg.wesolvea
SPPTWorSPPTWCCinsteadofanESPPTWorESPPTWCC)abranch-and-
bound framework has to beimplementedaswell. Kohl [Koh95] shows that if
thereexistsfeasiblesolutionstoaVRPTW problem,thelowerboundachieved
by GAP and ESPPTWCC is not better than the one obtained by SAP and
ESPPTWCC.Hence,solvingthe morediÆcultGAP insteadof theSAP does
notproducebetterbounds.
2.3.3 Other methods
The 3-index formulation of the VRPTW as presented in section 2.1 can be
transformedinto a2-index formulation,ifwedonot careaboutwhich vehicle
visitswhichthecustomers. This2-indexformulationisthebasisofthealgorithm
presentedin thejust recentlypublished Ph.D.ThesisbyKontoravdis[Kon97].
Incontrasttotheotherapproaches(dynamicprogramming,Lagrangerelaxation
andcolumn generation),Kontoravdisworks withtheformulationasitis. The
modelisrelaxedbyremovingtheintegralityconstraints. Thenaseriesofbounds
arecalculatedinaneorttoreducethegap. Themainpartofthealgorithmis
abranch-and-cut-algorithmusingwell-knowninequalities,butalsoasetofnew
inequalities{incompatiblepathinequalitiesandincompatiblepairinequalities
oneworksdirectlywiththeformulationusingx
ij
variables. Aswearegoingto
useadierentformulation,theseinequalitiescannotbeutilizedinouralgorithm
andthereforefurtherdiscussionis omitted.
Additionally, Kontoravdisworks with anobjective function notpreviously
used when the problemsare solved to optimality. His objective function is to
minimize thenumberofvehiclesused. The distancetraveledis secondaryand
is only estimatedby runningaheuristic ontheoptimal solutionfound bythe
branch-and-bound-algorithm. Kontoravdisachievessomeverygood resultson
the standardproblems,but thismayhavesomethingto dowith theobjective
function used.
2.4 Review of approximationalgorithms andheuris-
tics
Theeldofnon-exactalgorithmsfortheVRPTWproblemhasbeenveryactive
{farmoreactivethanthatofexactalgorithms. Alongseriesofpapershasbeen
published overtherecentyears.
Intheeld ofapproximationalgorithmsandheuristicsonesometimes clas-
siesanalgorithmassequentialorparallel. Inasequentialalgorithmoneroute
at a time is constructed, while aparallel algorithm maybuild more routes at
the sametime. This conicts with the notionof a sequentialalgorithm (run-
ningononeprocessor)andaparallelalgorithm(runningonseveralprocessors)
used laterinthethesis. Wewillthereforeavoidtheuseofthisclassicationof
heuristics.
Heuristic algorithms that build a set of routes from scratch are typically
called route-building heuristics, while an algorithm that tries to produce an
improvedsolutiononthebasisofanalreadyavailablesolutionisdenotedroute-
improving.
2.4.1 Route-building heuristics
The rst paper onroute-building heuristics for theVRPTW is[BS86]. Their
algorithmisanextensionofthelegendarySavingsheuristicofClarkandWright
fortheVRP problem([CW64]). Thealgorithmbeginswithallpossiblesingle-
customer routes (depot- i - depot). Ineveryiteration wecalculate which two
routes canbecombinedwith themaximumsaving, where the savingbetween
customersiandj arecalculatedas:
sav
ij
=d
i0 +d
0j Gd
ij
: (2.23)
Here G is sometimesreferredto asthe route form factor. In [BS86], a time-
orientednearestneighbouralgorithm isdevelopedbydening thesavingsasa
combinationof distance, time and \timeuntil feasibility". A similar heuristic
basedonthesavingsalgorithmisdevelopedin[Sol87],butherethetimeaspect
checkforviolationofthe timewindowswhentworoutesarecombined. These
heuristics havetime complexity ofO(n 2
logn 2
). Solomonreportedreasonable
resultsforthis heuristic.
AlsovanLandeghemhaspresentedaheuristicbasedontheSavingsheuristic.
Hisbi-criteria heuristic presentedin [vL88]usesthetime windowsin (2.23)in
order toget ameasurementof howgood alink betweencustomers isin terms
oftiming.
Another heuristic described in the paper by Solomon is a Time-Oriented,
Nearest-Neighbourheuristic. Everyroute in thisheuristicis startedbynding
the unrouted customer that is closest to the depot. The \closeness relation"
tries to take both geographical and temporal closeness of the customers into
account. At every subsequentiteration the customer closest (again using the
samemetricasbefore)tothelastcustomeraddedtotherouteisconsideredfor
insertionto theend of theroute presentlygenerated. Whenthesearchfails a
newrouteisstarted.
TheSolomonpaperalso describesthree Insertion heuristics. Here thebest
feasiblepositionforeachunservicedcustomeriiscomputedusingafunctionf
1 .
Thebest customer forinsertion isthen selectedby anotherfunction f
2 . If no
insertionispossibleanewrouteisstarted. IntheSolomonpaperthreedierent
setsoff
1 andf
2
functionsarepresented,eachweightingdierentaspectsofthe
routes(oneofthesefunctionsetsdescribestheI1heuristicoftenusedtogenerate
theinitialsolutionin improvementheuristics). Thebestofthethreeheuristics
(I1) minimizes aweightedsumof detour (in time units) and delayto identify
thebest insertionplace foreachcustomer. Theselectionofthecustomertobe
insertedisthenbasedonageneralizationoftheSavingsheuristic.
Finally aTime-OrientedSweep Heuristic is presented. Here apopular de-
composition into rstaclustering phase,assigning customerstodierentclus-
ters, and then a scheduling phase, building a route for each cluster is used.
BuildingeachroutethebecomesaTSPTWproblemwhichcanbesolvedusing
theTSPTWheuristicsdevelopedbySavelsberghin [Sav56,Sav90].
Assigningcustomerstoclustersisdonebyusingatechniqueintroducedina
paperbyGilletandMillerfortheVRP.Herea\centerofgravity"iscomputed
andtheclusters arepartitioned accordingto theirpolar angle. Schedulingthe
customers,oneofthepreviouslydevelopedtour-buildingheuristicsareusedto
builda1-routesolution. Due tothetimewindowsand/orcapacityconstraints
somecustomersmaynowbeunscheduled. Inordertoschedulethesethesched-
uledcustomersareremovedandtheprocessisrepeated.
The sweepheuristic typically performs better than the other heuristics in
caseswhere manycustomerscanbeassignedtoeachroute.
In generaltheheuristicsof Solomonand vanLandeghem returnasolution
fast. Theirsolution does howevergenerally lackin quality. Most of the time
thesolutionsaremorethan10percentfromoptimum.
inthelatterpartoftheprocessareofpoorqualityasthelastunroutedcustomers
tendstobescatteredoverthegeographicarea. In[PR93]PotvinandRousseau
tries to overcome this problem of the Insertion heuristics by building several
routes simultaneously. The initialization of the routes is done by using the
insertionheuristicof Solomon. Oneachroutethecustomerfarthestawayfrom
the depot is selected as a \seed customer". Then we proceed by computing
the best feasible insertion place for each unserviced customer and insert the
onewith thelargestdierencebetweenthe best and thesecond best insertion
place. ThismethodisbetterthantheSolomonheuristicsbutstillthesolutions
are quite far awayfrom optimum. Russellelaborates further on theinsertion
approachin[Rus95].
AntesandDerigsdescribesin[AD95]anotherapproachbuildupontheclas-
sical insertion idea. Here everyunrouted customerrequests and receivesfrom
everyrouteinthescheduleaprizeforinsertion(settoinnityifinsertionisnot
possible),dened in asimilar wayasin theSolomon heuristics. Thentheun-
routedcustomerssendaproposaltotheroutewiththebestoer,andnoweach
routeacceptsthebestproposalamongthose customerswith thefewest number
of alternatives. Note that more customers can be inserted in each iteration.
If a certain threshold of routes is violated a certain number of customers are
removedandtheprocessisinitiatedagain. TheresultsofAntesandDerigsare
comparable tothose presentedin [PR93]. Generally buildingseveral routesin
parallelresultsinbettersolutionsthanbuildingtheroutesonebyone.
Likethe route-rst scheduling-second principle mentionedabove, Solomon
in [Sol86] suggestsdoingit theotherwayaroundin theGiant-TourHeuristic.
First the customers are scheduled into one giant route and then this route
is divided into a number of routes (the initial giant tour could for example
be generated as a traveling salesman tour not considering capacity and time
windows). Nocomputationalresultsaregivenin thepaperfortheheuristic.
Theonlyimplementationof aroute-buildingheuristiconparallel hardware
is reported in [FP93] where an insertion heuristic that simultaneously builds
the routesis described using an(unnamed) Solomonheuristic to generatethe
initialseedcustomers.
2.4.2 Route-improving heuristics
The basis of almost everyroute-improvingheuristic is the notion of a neigh-
bourhood. Theneighbourhood of asolutionS is aset N(S) ofsolutions that
canbegeneratedwithasingle\modication"ofS.
Checkingsome or allof the solutionsin a neighbourhood mightreveal so-
lutions that are better with respect to objective function. This idea can be
repeated from the better solution. At some point no better solution can be
foundandanoptimumhasbeenreached. Itisdenitelyalocaloptimumbutit
mightevenbeglobal. Thisalgorithm iscalled local search. Metaheuristics are
typicallybasedonlocalsearchbutwithmethodsaddedforescapinganoptimum
Neighbourhoods forthe VRPTW
Oneof themostused improvementheuristicsin routingand schedulingis the
r-Opt heuristic. Here r arcs are removed and replaced by r other arcs. A
solutionobtainedusingar-Optneighbourhoodthatcannotbeimprovedfurther
iscalled r-optimal. Usually risat most3. Usingthe3-Opt ontheroutesofa
solutionto the VRPTWproblem isnot withoutproblems. Forall possible 2-
Opt interchangesandsomeoftheexchangesinthe3-Optneighbourhood,parts
of the route is reversed. This may verylikely leadto aviolation of the time
windows.
In [PR95], Potvin and Rosseau presents two variants 2-Opt
and Or-Opt
thatmaintainthedirectionoftheroute.
InOr-Optasegmentoftheroute,thatis,lconsecutivecustomers,aremoved
toanotherplaceontheroute. AnexampleoftheOr-Optisshowningure2.3.
It is quiteeasyto see that Or-Opt's are asubsetof 3-Opt's aswe exchange 3
specialarcswith 3others. Thesize of theneighbourhood isalthough reduced
from O(n 3
)to O(n 2
). Generally the size of ar-Opt neighbourhood is O(n r
).
The2-Opt
is exchangingonesegmentof oneroute withasegmentof another
route. This is illustratedin gure2.4. Againthesize of theneighbourhoodis
O(n 2
). Thisneighbourhoodoperatorissometimesdenoted crossoverorsimply
cross.
j
s i
j i
s
i
1
i
l
. ....
j
s i
j i
s
i
1
i
l
.. ...
Figure2.3: AnexampleofanOr-Optexchange. Thegureontheleftpresents
the route before the Or-Opt is performed, and the gure on the right is the
route afterthe exchange. Note that orientationof thecustomers from i
1 to i
l
remainsthesame. Thesquarerepresentsthedepot.
The last partof either route will become the last of the other. Note that
if (i;i
s
) is the rst arc on oneof the routes and (j;j
s
) is the last one on the
otherroutethetworouteswillbemergedintoone. Notealsothatthecrossover
j i
j
s i
s
j i
j
s i
s
Figure 2.4: An example of an 2-Opt
exchange. The squares represent the
depot. Theleftpictureisbeforeand therightisaftertheexchange. Note that
there may beany number of customers on thepath between the depot and i
respectivelyj andagainbetweeni
s
respectivelyj
s
andthedepot.
Therelocateoperatormovesacustomerfromoneroutetoanotherasshown
ingure2.5. Heretheedges(i
p
;i);(i;i
s
)and(j;j
s
)arereplacedby(i
p
;i
s );(j;i)
and(i;j
s ).
j i
p
j
s i
s
i
j i
p
j
s i
s
i
Figure 2.5: An example of an relocate operator. The square represents the
depot. Again the left picture is before and the right is after the relocation.
Note that there may be any number of customers on the path between the
depotandirespectivelyj andagainbetweeni
s
respectivelyj
s
andthedepot.
The exchange operator swapscustomers in dierent routes, thereby inter-
changingtwo customers simultaneously into the other routes (see gure 2.6).
Thisideamaybeextendedto swapsegmentsofroutesbetweentworoutes.
Thek-nodeinterchangeby ChristodesandBeasley is modiedby several
authors to take time windows into account. Sequentially each customer i is
consideredandthesetsM
1 andM
2
areidentied. M
1
isdenedasthecustomer
ianditssuccessorj. Thentheelementsof M arefoundasthetwocustomers
