apartialroutecontainingbothi
1 andi
2
dominatesothercongurationsaslong
astheydominatewithrespecttodistance/accumulatedcostandtime. Between
the remaining types of partial routes no dominance can be established. The
sameconsiderationshastobeappliedtothebranchwherei
1 andi
2
cannotbe
partofthesameroute.
Theinitial testwithsmallproblems lookedpromising,butwhen weturned
our attentionto medium and large scale problems the running times
deterio-rated drastically. Whenthedepth of theBranch-and-Bound-treebecame5 or
6(which is notunusual)theweakerdominance criteriondecreasedthe
perfor-mancesubstantially,andtheschemewasnotcompetitive.
Wedidnotperformalargetest oftheVRPTWalgorithm usingthe
Ryan-Fosterbranchingrule. The method had problemssolvinginstances where the
Branch-and-Boundtreesweredeepandthereforeitdidnotseemworthto
con-tinuethework. Toillustratetheproblemweconsidertwoinstances. TheR101
with100customershasarelativelysmallBranch-and-Boundtreeandtherefore
therunningtimeofthetwobranchingrules(Ryan-Fosterandarc-branching
al-mostalike). UsingtheRyan-Fosterrule15Branch-and-Boundnodesareneeded
toobtainasolutionin22:24seconds,whilethealgorithmwiththearc-branching
rulereturnedasolutionafter25Branch-and-Boundnodesand27:78seconds. In
thecaseofR103with50customersasolutionwasfoundin 42:16secondsafter
examining 51 Branch-and-Bound nodes using arc-branching. Here the
Ryan-Foster rule needed 312:11 seconds and 41 Branch-and-Boundnodes. Clearly
theaddedstatesinthelabelsweakensthedominancecriteriatoomuch.
Oneoftheimportantdierencesbetweenvehicleroutingandcrewscheduling
is thedepth oftheBranch-and-Boundtrees. The depthin Branch-and-Bound
trees of a crew scheduling problem is typicallysignicantly smallerin vehicle
routing. Another important aspect is that in crew scheduling cycles are not
possible (it is not possibleto y the same leg twice). We havetherefore not
pursuedtheideafurther.
cannot be applied. Hence,wheneverbranchingon timewindowsis possible it
isused. Thebranchingscheme istestedagainstaschemewhich branchesonly
onthenumberofvehicles andarc-branches. Outof21instances,branchingon
time windows performedbest in 17 cases, but only signicantly(more than a
factor2) betterin 9cases. Theseresultsdonotseemimpressive,henceweset
out to try to combine the branching on time window and arc-branching in a
more intelligentway, tryingto develop abranching scheme depending on the
presentgeography,customerdistribution,timewindowsizeetc.
Inmanypapersitseemstobeaforegoneconclusiontouseabest-rsteager
evaluation approach. Before evaluating branching on time windows the two
selectionfunctionsbest-rstanddepth-rstincombinationwiththetwobound
evaluationschemeseager evaluation and lazyevaluation were tested. In eager
evaluation, bounding of the Branch-and-Bound nodes is done before they are
returnedto thedata structure handlingtheselection,while in lazy evaluation
eachBranch-and-Boundnode isinsertedwith the bound value of forexample
theparentandbounding takesplaceimmediatelybeforebranching.
In an initial phase we developed four versions of the branch-and-price
al-gorithmfortheVRPTW:twousingbest-rstfornode-selectionandtwousing
depth-rstfornode-selection. Foreachnode-selectionstrategyweimplemented
alazyandeagerboundevaluationapproach(asdiscussedbyClausenand
Per-regaardin[CP]).
FromtherichsetofinstancesintheSolomontest-setsweselected8instances
(table7.1), which arefairlydiÆcultto solveand havedierentcharacteristics.
These were usedas atest-bedin theinitial phaseof theexperiments. Firstof
all we wantedto conrm theresults of Gelinaset al. We therefore ranthe 4
developedalgorithmswith:
Setup 1:
{ Branchingonthenumberofvehicles.
{ Branchingontimewindows.
{ Branchingonarcs.
Setup 2:
{ Branchingonthenumberofvehicles.
{ Branchingonarcs.
Foreachsetup,4runs ofthetest-bedproblemsweremade. Theresultsare
shown in table 7.2and 7.3. TheNoCo (\No morecolumns")entryindicates
thatthemax.numberof 20000columnsallowedwereexceeded.
Firstthingtonoticeintable7.2isthatthestack-implementationusingeager
evaluationsisneverthebest. Eventhoughthestack-implementationusinglazy
Problem No.of Description
Cust.
R101 100 All timewindowsareofsize10
R103 50 Halfof thetimewindowsareof size10,
theotherhalfalmost notconstraining
R105 100 All timewindowsareofsize30
R107 50 Halfof thetimewindowsareof size30,
theotherhalfalmost notconstraining
R110 50 All timewindowsarebig(atleastsize30)
R111 50 All timewindowsarebig(atleastsize30)
RC104 50 10timewindowsofsize 30,therest
arealmostnotconstraining
RC108 50 All timewindowsarebig(atleastsize50)
Table7.1: Descriptionofthetest-bed. Forallinstancestheschedulinghorizon
is[0;230].
isnotthebestitiswayothebestrunningtimes. Ontheremaininginstances
theheap-implementationusinglazy evaluationperformsbetter. Notethat the
performanceofdepth-rst basedBranch-and-Boundcanbeimprovedbyusing
an initial solution value better than 1. A fast heuristic that can generate
a good qualitysolution cansignicantlyreduce the depth of the
Branch-and-Boundtree. Forabest-rstBranch-and-Boundagoodinitialsolutionvaluecan
help reducethenumberofBranch-and-Boundnodesstoredintheheap.
For thesetupwhere branchingontimewindowsisnotused (table7.3)the
resultsareevenmoreclear. Againthestack-implementationusingeager
evalu-ation isneverthebest. Among theremainingsetupstheheap-implementation
using lazy evaluation edges in front. Fivetimes it is thebest and it is never
worsethanthansecond.
So in our further tests of the time window branching scheme an
imple-mentation using aheapto store unsolvedBranch-and-Boundnodes(best-rst
strategy)andlazyevaluation(storingeachBranch-and-Boundnodeintheheap
accordingtothebound oftheparent).
Nowcomparingourtwochosenimplementationsitisnoteworthythat
branch-ing on time windows is better in 5out of 8 instances, but only in 2of the5
instances is the dierence really signicant (both in R107 with 50 customers
and RC108 with50 customersbranching ontime windows isabout afactor2
faster).
InordertoevaluatethebranchingschemesweselectedthreeinstancesR105,
R107andR111forfurthertests. InR105alltimewindowsareofsize30which
issmallcomparedtotheschedulinghorizon. InR107halfofthetimewindows
are ofsize30 whiletheremaininghalf aresignicantlylargerthansize 30and
in R111alltimewindowsaresignicantlylargerthansize30.
HeapStack LazyEagerLazyEager Problemtime(s)BBtime(s)BBtime(s)BBtime(s)BB CustomersVeh.ArcTWVeh.ArcTWVeh.ArcTWVeh.ArcTW R10110028.794135.512025.334136.6321 1714151317121712 R1035034.243135.821550.198138.2919 1023101310391017 R105100817.563811048.981901432.217892489.84383 802426018390385100372 R1075036.514138.1216696.527971591.77404 202710145239125396 R1105026.871126.0264199.3241932740.84945 105104100619904612886 R11150568.01629525.242541912.27816157522.681144 380386180235641373062101071 RC10450187.749186.305185.339194.1125 103103103103 RC10850354.19167358.4980255.41177414.2683 10112107810871081 able7.2:Usingtimewindows(setup1)onthetest-bed.Therstlineforeachinstancecontainstherunningtime numberofBranch-and-Boundnodesthatwasnecessarytosolvetheproblem.Thesecondlinedisplaysthenum hingsperformedonthenumberofvehicles,onarcsandusingtimewindows.
HeapStack LazyEagerLazyEager Problemtime(s)BBtime(s)BBtime(s)BBtime(s)BB CustomersVeh.ArcTWVeh.ArcTWVeh.ArcTWVeh.ArcTW R10110018.822524.251316.762524.8714 1140111011101120 R1035054.124954.992156.156970.4832 5330317033103280 R105100680.92327920.02166NoCoNoCo 201510171480 R1075075.486795.1134101.33117138.9158 2520231025602550 R1105026.891327.237NoCo9669.231472 250240314680 R11150545.64559713.80275472.83555689.31270 313270142600152620162530 RC10450244.7925242.1513248.1741295.5022 1140111011901200 RC10850712.47341902.78171NoCoNoCo 3235011690 Table7.3:Notusingtimewindows(setup2)onthetest-bed.
r= 10; 5; 3; 1;1;3;5;10andresultsaredepictedin table7.4.
Our rst expectation was that reducing the time windows would lead to
smallerrunning times, and, obviously,enlarging thetime windows would lead
tolargerrunningtimes. Furthermoretheideawasthatasthetimewindowsget
larger,branchingontimewindowswouldbecomemoreeÆcientthanbranching
onarcs. Finallywewantedtoconrmtheresultsof[GDDS95].
Making the time windows smaller did not howeverreduce running times.
Lookingatboththeruns whereweusedbranchingontimewindowsandthose
were wedidnotuse it, therunning timemayactually goup even thoughthe
timewindowsaresmaller,e.g.astimewindowsarereducedbyonethird going
from r=0to r=5inR105runningtimegoesupbyafactor4:5 from823:49
to 3682:59 using branching on time windows, and by around afactor 2 from
665:32to1428:41ifnot. There isnogeneraltrendintherelationshipbetween
sizeoftimewindowandtherunningtimein thesedata.
Thereasonforthisbehaviourmustbefoundelsewhere,andinfactthereason
isquitestraightforward. Table7.3showsthegapinpercentbetweentheinitial
LPrelaxationand theoptimalIPsolution. Asthe timewindowsare changed
weunfortunatelyalsochangethegeneralstructureoftheproblemandthisdoes
insomecasesleadtoaweakerLPrelaxation. InthismodeloftheVRPTWthe
impactissignicantasthegapisusuallyonlyclosedin verysmallsteps.
In the 24 new tests we ran only one (R107, r = 10) did not produce a
resultforanyofthetwobranchingstrategies. Inonly10of23testssomething
isgained usingbranching ontimewindows,andonlyhalf oftheseactuallyled
toasignicantdecrease(bymorethanafactor2)in therunningtime.
Asthechangeofeverytimewindowclearlydidchangetheproblemtoomuch
wetriedonR105andR107toleavethe\big"timewindowsuntouchedandonly
change partoftheremainingones;thephilosophybeingthat changingthebig
time windows withthe relativesmall valuesweareusing does notchange the
structuresignicantly. R111isnotusedinthesetestsbecausealltimewindows
arerelativelylarge. Forthesamesetofpossibler-valueswetriedonlytochange
everysecond and everyfourth \small" timewindow. Theresult ofthese runs
areshownin thetables 7.6and7.7.
Again these results are not encouraging at all. Our problem is still that
we cannot control the gap betweenthe LP and the IP. Therefore, even small
changesmayresultinquitedrasticchangesinrunningtimes. Outofthe32new
instancesbranchingontimewindowsonlyperformedbetterthanbranchingon
owsin12instances(1 instancecouldnotbesolvedbyanysetup).
Theconclusionfromthesetests arethatourinitialhypothesis thatastime
windowsgrowlarger,branchingontimewindowshelps cannotbejustied.
Infact,thepictureisnotclear. Itispresentlynotcleartousinwhich
situ-ationsbranchingontimewindowsyieldsbetterresultsthanbranchingonarcs.
Further investigations have to nd relations between problem characteristics
Problem No.of r UsingTW NotusingTW
Cust. time(s) BB time(s) BB
R105 100 0 823.49 381 665.35 327
R105 100 1 2320.12 1025 1331.28 732
R105 100 3 11959.71 4961 2193.08 1087
R105 100 5 3682.59 1745 1428.41 749
R105 100 10 18.30 29 14.59 21
R105 100 -1 2515.54 1097 2955.46 1177
R105 100 -3 18411.63 4389 8735.96 2523
R105 100 -5 NoCo 6569.79 1723
R105 100 -10 NoCo 8028.87 2675
R107 50 0 39.48 41 74.51 279
R107 50 1 62.74 53 36.51 33
R107 50 3 4080.12 1775 NoCo
R107 50 5 460.64 507 1243.58 891
R107 50 10 26.11 43 38.83 75
R107 50 -1 354.22 321 115.23 111
R107 50 -3 220.78 229 182.96 167
R107 50 -5 138.32 151 176.72 215
R107 50 -10 NoCo NoCo
R111 50 0 561.84 629 550.37 559
R111 50 1 323.14 461 220.69 267
R111 50 3 115.43 123 114.66 111
R111 50 5 24.82 29 48.18 35
R111 50 10 11.83 15 15.20 23
R111 50 -1 1729.87 1487 548.32 587
R111 50 -3 4303.42 2201 NoCo
R111 50 -5 383.18 297 1425.56 589
R111 50 -10 556.49 439 1062.48 591
Table 7.4: Testing branching on time windows on the same geography but
dierenttimewindows.
Problem No.of r LP IP gapin
Cust. %
R105 100 0 13461.422 13553 0.68
R105 100 1 13591.179 13722 0.96
R105 100 3 14043.772 14207 1.16
R105 100 5 14389.533 14547 1.09
R105 100 10 16602.143 16672 0.42
R105 100 -1 13319.500 13431 0.84
R105 100 -3 13030.200 13189 1.22
R105 100 -5 12643.756 12814 1.35
R105 100 -10 12025.317 12144 0.99
R107 50 0 7044.380 7111 0.95
R107 50 1 7111.175 7164 0.74
R107 50 3 7236.800 7397 2.21
R107 50 5 7374.133 7492 1.60
R107 50 10 7899.500 7965 0.83
R107 50 -1 6977.321 7108 1.87
R107 50 -3 6950.300 7057 1.54
R107 50 -5 6874.659 6970 1.39
R107 50 -10 NoCo
R111 50 0 6918.122 7072 2.22
R111 50 1 7047.800 7165 1.66
R111 50 3 7197.714 7276 1.09
R111 50 5 7241.641 7304 0.86
R111 50 10 7395.500 7453 0.78
R111 50 -1 6901.500 7072 2.47
R111 50 -3 6787.745 6980 2.83
R111 50 -5 6515.462 6689 2.66
R111 50 -10 6405.750 6561 2.42
Table7.5: ThegapbetweentheLPrelaxationandtheoptimalIPvalue.
Problem No.of r UsingTW NotusingTW
Cust. time(s) BB time(s) BB
R105 100 0 823.49 381 665.35 327
Everysecondchanged
R105 100 1 85.95 59 56.44 31
R105 100 3 62.60 45 39.52 21
R105 100 5 3546.56 1651 2337.59 1225
R105 100 10 35.26 39 23.24 17
R105 100 -1 7023.80 2505 3482.01 1433
R105 100 -3 1373.31 657 11484.09 3299
R105 100 -5 7473.87 2207 10906.47 3063
R105 100 -10 NoCo NoCo
Everyfourthchanged
R105 100 1 340.35 203 210.29 145
R105 100 3 454.73 273 259.38 167
R105 100 5 135.47 93 123.19 85
R105 100 10 19.98 9 28.71 17
R105 100 -1 5588.24 2177 3782.05 1485
R105 100 -3 2949.82 1167 2574.70 1041
R105 100 -5 759.88 447 779.67 411
R105 100 -10 4072.78 1419 1464.65 697
Table7.6: Not everytimewindowischangedforR105.
Problem No.of r UsingTW NotusingTW
Cust. time(s) BB time(s) BB
R107 50 0 39.48 41 74.51 279
Everysecondchanged
R107 50 1 113.76 115 54.13 51
R107 50 3 214.34 157 242.19 119
R107 50 5 1608.23 887 469.26 379
R107 50 10 25.80 25 43.31 51
R107 50 -1 44.27 43 70.27 63
R107 50 -3 133.51 147 80.76 81
R107 50 -5 22.72 5 22.18 5
R107 50 -10 119.09 141 94.03 103
Everyfourth changed
R107 50 1 51.02 21 40.75 29
R107 50 3 92.60 49 70.25 79
R107 50 5 42.97 19 19.60 11
R107 50 10 791.43 395 788.70 515
R107 50 -1 59.35 31 72.59 67
R107 50 -3 110.42 55 67.37 61
R107 50 -5 37.95 3 29.04 11
R107 50 -10 33.65 5 24.94 13
Table7.7: Not everytimewindowischangedforR107.