Oneof thepresentproblems with theparallelalgorithm is thedependencyon
the time used to solve the root node. The root node contains the rst calls
of the SPPTWCC routinethat are oftenverytime consuming relative to the
remainingcallsofthesubroutine. ABranch-and-Boundtreeisoftencalledslim
ifonlyafewBranch-and-Boundnodesarealiveoneachlevelofthetreedepth.
IftheBranch-and-Boundtreeisveryslim,aconsiderableamountoftimemay
beused before theparallel phasecan be started. An idea would be to apply
a heuristic instead of SPPTWCC in the rst sequential part of the parallel
algorithm. Then instead of only branching once we branch enough times to
give everyprocessorat leastone Branch-and-Bound node to work on. As the
parallelphaseisstartedagainweusetheSPPTWCCsubroutine.
notabletoachievethesamepositiveresultsfortheVRPTW.Thereforefurther
developmentofadvanced branching strategiesbasedonbranchingon resource
constraintswerenotcarriedout. Itwouldbeinterestingtoanalyzewhat
charac-teristicsofthebackhaulingschememadebranchingonresourcewindowsbehave
well.
Experiments with the Ryan-Fosterbranching rule showed that due to the
largenumberofpossibleextensionsofthepartialroutesintheSPPTWCCthis
ideadoesnotworkfortheVRPTW.
ThenewschemefordetectingS setsgeneratesgoodresults. Byusing
geo-graphicalinformationweareabletogeneratecutsfaster. Theimplementation
ofaheuristicforthe\feasibilityTSPTW" doesonlyhaveminor eectsonthe
performance. FortheR1,C1andRC1instancesthesetsthatneedtobechecked
are seldomly solargethat thealgorithm used byKohl hasproblems. Forthe
R2, C2and RC2instances afewlarge setsare generatedbut notchecked due
toanupperlimitonthesetsize. Ifthisupperlimitwasremovedthealgorithm
used byKohlwouldhavetroublesolvingsomecases. Here theheuristiccould
beusedinstead.
Thetriviallowerboundwastested. Itdoesnotseemtohaveanysignicant
eect. Ontheotherhand itgenerallydoesnotslowdownthealgorithmeither,
and it is fast to perform. Generatingcuts in other Branch-and-Bound nodes
besidetherootnodeseemsgenerallynottobeworthwhile. Onlyafew
Branch-and-Bound nodes can beremovedand thecuts generated cannotbeinserted
astheyarenotgloballyvalid.
Thecolumnreductionschemeperformsreallywell. Thetimesavedremoving
columns not likely to be used againoutweighsthe administrationcostsof the
scheme. Theperformanceresultsareveryencouraging. Inordertoobtaineven
better performance the number of Branch-and-Bound nodes between calls of
thereductionsubroutinemustbemadedependentofthebreathofthe
Branch-and-Boundtree. Foreach\live"branchthe\good"routesareworthkeepingso
ideallyweshould keeptrackofwhichbranchesarealive. Inthiswaya\good"
route belongingto abranchthat isnolongeralivecanbedeletedwith agood
chanceofnotaectingperformance. InsteaditissimplertohaveanestimateB
onthenumberof\live"branchesandthencallthereductionsubroutineevery
timeB Branch-and-Boundnodeshavebeenprocessed.
Random selection did not contribute to faster execution time, but forced
early stopreducedtherunningtime, sometimesdrastically. Further
investiga-tionsshoulddetermineunderwhichconditionthebestperformanceisobtained.
The experiments undertaken have added valuable knowledge on structure
and properties of solvingVRPTW instances. It has identied bottlenecks in
computationthatneedstobeinvestigatedinthefuture. Furthermoreinstances
not previously solved to optimality has been solved, including a number of
R2,C2 andRC2instances(as reported insection7.8) butalsoR103with100
customers,R106with100customersandR107with100customers(thesolutions
canbefoundin appendixA). Inaneortto solvetheR109,R110andRC102
with 100 customersthe limit onthe number of Branch-and-Bound nodes was
solvedin[Koh95]therunningtimefor5processorswas882:42secondsandfor
10processorstherunningtimewascutto350:19seconds,thatis,weexperience
aspeed-up anomaly. Furthermore the parallel algorithm solved R112with 50
customersin4501:50secondsusing10processors.Thisinstancehasneverbeen
solved to optimality before. Again the load-balancing was excellent and the
parallelphasewasinitiatedafter approximately500seconds.
Wehavedevelopedaparallelalgorithmthat exhibits goodspeedup
perfor-mance. The load-balancingstrategy leadsto good resultsas weget the work
quitewellbalanced bothon4processorsandon8processors. This parallel
al-gorithmtogetherwiththenewlydesignedstrategiesfromchapter7couldsolve
several of the Solomon problems not yet solved. Unfortunately access to the
SP2isasparseresource,andthejob-queuesforjobsthat areestimatedtorun
formorethan1hourarepermanentlycongested.
Still, the main weakness of the parallel algorithm is the time it takes to
generate kp unexplored subspaces. In particular the time it takes to solve
theroot nodecan beaserious problem. Furtherimprovementsoftheparallel
algorithm shouldfocusonusing parallelismin initialsequentialphase. Here a
parallelversionof theSPPTWCCsubroutinemightbefruitful,when thetime
windowsaretoowidetoallowthesequentialSPPTWCCtoexplorethedynamic
programming-treefast.
[ABMS94] R. Alasdair, A. Bruce, James G. Mills, and A. Gordon Smith.
CHIMP/MPIuserguide.Technicalreport,EdinburghParallel
Com-putingCentre,UniversityofEdinburgh,1994. AvailableviaWWW
atwww.epcc.ed.ac.uk/epcc-tec/documents.
[ACD +
96] Cristiana Amza, Alan L. Cox, Sandhya Dwarkadas, Pete
Kele-her,HonghuiLu,RamakrishnanRajamony,WeiminYu, andWilly
Zwaenepoel. TreadMarks: Sharedmemorycomputingonnetworks
ofworkstations. IEEEComputer, pages18{28,February1996.
[AD95] Jurgen Antes andUlrich Derigs. A newparallel tourconstruction
algorithmforthevehicleroutingproblemwithtimewindows.
Tech-nical report, Lehrstuhl fur Wirtschaftsinformatik und Operations
Research,UniversitatzuKoln,March1995.
[AFG97] NorbertAscheuer,MatteoFischetti,andMartinGrotschel.A
poly-hedral study of the asymmetric travelling salesman problem with
timewindows.AvailableviaWWWatwww.zib.de,February1997.
Preprint.
[AMS89] YogeshAgarwal, KamleshMathur, and HarveyM. Salkin. A
set-partitioning-basedexactalgorithmforthevehicleroutingproblem.
Networks,19:731{749,1989.
[Ant96] Mario Antonioletti. Scalable computing { from workstations to
MPPs. Available via WWW at
www.epcc.ed.ac.uk/epcc-tec/-documents,July1996.
[Bal93] NagrajBalakrishnan.Simpleheuristicsforthevehiclerouting
prob-lem with soft time windows. Journal of the Operational Research
Society,44(3):279{287,1993.
[BGAB83] Lawrence Bodin, Bruce Golden, Arjang Assad, and MichaelBall.
Routing and scheduling of vehicles and crews - the state of art.
Computers &Operations Research,10(2):62{212,1983.
95-84,Centrederecherchesurlestransports, December1995.
[BJN +
94] CynthiaBarnhart,EllisL.Johnson,GeorgeL.Nemhauser,Martin
W. P. Savelsbergh,andPamela H. Vance. Branch-and-price:
Col-umn generation for solvinghugeintegerproblems. In J. R. Birge
andK.G.Murty,editors,Mathematical Programming: Stateofthe
art 1994.Braun-Brumeld,1994.
[BJN +
98] Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser,
Mar-tin W. P. Savelsbergh, and Pamela H. Vance. Branch-and-price:
Column generation for solvinghugeinteger programs. Operations
Research,46(3):316{329,1998.
[Bod90] LawrenceD. Bodin. Twenty years ofroutingand scheduling.
Op-erationsResearch,38(4):571{579,July-August1990.
[Bre95] AlexVanBreedam. Vehiclerouting: Bridgingthegapbetween
the-oryandpractice.BelgianJournalofOperationsResearch,Statistics
andComputer Science,35(1):63{80,1995.
[BS86] Edward K. Baker and Joanne R. Schaer. Solution improvement
heuristicsforthevehicleroutingandschedulingproblemwithtime
windowconstraints. AmericanJournal of Mathematical and
Man-agement Science,6(3,4):261{300,1986.
[Ca93] N. Christodesand J.Paixao. Algorithmsfor largescaleset
cov-eringproblems. AnnalsofOperationsResearch,43:261{277,1993.
[CCPS98] WilliamJ.Cook,WilliamH.Cunningham,WilliamR.Pulleybank,
and AlexanderSchrijver. Combinatorial Optimization. Integerand
CombinatorialOptimization.WileyInterscience,1998.
[CJR81] FrankH. Cullen, JohnJ.Jarvis, andH. DonaldRatli. Set
parti-tioningbasedheuristicsforinteractiverouting.Networks,11(2):125
{143,1981.
[CKP +
96] DavidE.Culler,RichardM.Karp,DavidPatterson,AbhijitSahay,
Eunice E.Santos,KlausErikSchauser,RameshSubramonian,and
Thorsten vonEicken. LogP: Apracticalmodel ofparallel
compu-tation. Communications ofthe ACM,39(11):78{85,1996.
[CL98] TeodorGabrielCrainicandGilbertLaporte.FleetManagementand
Logistics. Kluwer,1998.
[Cla90] Jens Clausen. Solving diÆcult combinatorical optimization
prob-lems {can parallel computershelp? Working Paper- in Danish,
[Cla96] JensClausen. Parallelsearch-basedmethodsinoptimization. draft,
1996.
[Cla97] JensClausen. Parallelbranchand bound {principlesandpersonal
experiences.InAthanasiosMigdalas,PanosM.Pardalos,andSverre
Story,editors,Parallel ComputinginOptimization,Applied
Opti-mization.KluwerAcademicPublishers,1997.
[CMT79] Nicos Christodes, Aristide Mingozzi, and Paolo Toth. The
ve-hicle routing problem. In Nicos Christodes, Aristide Mingozzi,
PaoloToth, and Claudio Sandi, editors, Combinatorial
Optimiza-tion,chapter11,pages315{338.JohnWiley&Sons,1979.
[CMT81] NicosChristodes,AristideMingozzi,andPaoloToth. Exact
algo-rithmsforthevehicleroutingproblem,basedonspanningtreeand
shortestpath relaxation. Mathematical Programming, 20(3):255{
282,1981.
[CP] JensClausenandMichaelPerregaard. Onthebest searchstrategy
inparallelbranch-and-bound-best-rst-searchvs.lazy
depth-rst-search. toappearinAnnalsof Operations Research.
[CR96] Wen-Chyuan Chiang and Robert A. Russell. Simulated annealing
metaheuristicsforthe vehicleroutingproblemwith timewindows.
Annals of Operations Research,63:3{27,1996.
[CR97] Wen-ChyuanChiangandRobertA.Russell. Areactivetabusearch
metaheuristic for the vehicle routing problem with time windows.
INFORMSJournalof Computing,9(4):417{430,1997.
[CT96] AlanChalmersandJonathanTidmus.PracticalParallelProcessing.
InternationalThomsonComputerPress,1996.
[CW64] G. Clarke and W. Wright. Scheduling of vehicles from a central
depot to anumberof deliverypoints. Operations Research,12:568
{581,1964.
[DDS92] Martin Desrochers, Jacques Desrosiers, and Marius Solomon. A
new optimization algorithm for the vehicle routing problem with
time windows. Operations Research, 40(2):342{354, March-April
1992.
[DDSS93] Jacques Desrosiers, Yvan Dumas, Marius M. Solomon, and
F. Soumis. Time constrained routing and scheduling. Technical
report,GERAD,September1993.
[Des88] MartinDesrochers.Analgorithmfortheshortestpathproblemwith
resourceconstraints.TechnicalReportG-88-27,GERAD,
Ecoledes
Hautes
Etudes Commerciales, Universite de Montreal, September
[DLSS88] MartinDesrochers,JanK.Lenstra,MartinW.P.Savelsbergh,and
FrancoisSoumis. Vehicleroutingwithtimewindows: Optimization
and approximation. Vehicle Routing: Methods and Studies, pages
65{84,1988. Edited byGoldenandAssad.
[dRT88] A.deBruin,A.H.G.RinnooyKan,andH.Trienekens.Asimulation
toolfor theperformanceof parallel branch and bound algorithms.
Mathematical Programming,42:245{271,1988.
[DS88a] Martin DesrochersandFrancoisSoumis. Ageneralizedpermanent
labelling algorithm for the shortest path problem with time
win-dows. INFOR,26(3):191{212,1988.
[DS88b] MartinDesrochersandFrancoisSoumis.Areoptimizationalgorithm
fortheshortestpathproblemwithtimewindows.EuropeanJournal
of Operational Research,35:242{254,1988.
[DS96] Jack J. Dongarra and Horst D. Simon. High performance
com-puting in the u.s. in 1995 { an analysis on the basis of the TOP
500list. Technical Report uk-cs-96-318,Departmentof Computer
Science, University of Tennessee, 1996. Available via WWW at
www.cs.utk.edu/~library/TechReports.html.
[DSD84] JacquesDesrosiers,FrancoisSoumis,andMartinDesrochers.
Rout-ing withtimewindowsbycolumn generation. Networks,14(4):545
{565,1984.
[DSDS85] JacquesDesrosiers,FrancoisSoumis,MartinDesrochers,andMichel
Sauve. Routing and schedulingwith time windowssolvedby
net-workrelaxationandbranch-and-boundontimevariables.Computer
Scheduling of PublicTransport 2,pages451{469,1985.
[Dun90] Ralph Duncan. Asurveyofparallel computerarchitectures. IEEE
Computer, pages5{16,February1990.
[dVDH99] OlivierduMerle,DanielVilleneuve,JacquesDesrosiers,andPierre
Hansen. Stabilized column generation. Discrete Mathematics,
194:229{237,1999.
[FD96] Graham E. Fagg and Jack J. Dongarra. PVMPI: An integration
of the PVM and MPI systems. Technical report, Department of
Computer Science, Universityof Tennessee, April 1996. Available
[Fis94a] Marshall L. Fisher. Optimal solutionof vehicle routing problems
usingminimumk-trees.OperationsResearch,42(4):626{642,
July-August1994.
[Fis94b] Marshall L. Fisher. A polynomial algorithm for the
degree-constrained minimum k-tree problem. Operations Research,
42(4):775{779,July-August1994.
[Fis97] Marshall Fisher. Vehiclerouting. InM. O. Ball,T. L.Magnanti,
C. L. Monma, and G. L. Nemhauser, editors, Network Routing,
volume 8 of Handbooks in Operations Research and Management
Science,chapter1,pages1{79.North-Holland,1997.
[FJM94] MarshallL.Fisher,KurtO.Jornsten,andOliB.G.Madsen.Vehicle
routingwithtimewindows-twooptimization algorithms. T
echni-calReport IMM-REP-1994-28,Departmentof Mathematical
Mod-elling,TechnicalUniversityofDenmark,1994.
[FJM97] MarshallL.Fisher,KurtO.Jornsteen,andOliB.G.Madsen.
Vehi-cleroutingwith timewindows: Twooptimizationalgorithms.
Op-erations Research,45(3):488{492,May-June1997.
[Fos94] Ian Foster. Designing and Building Parallel Programs. Addison
Wesley,1994.
[FP93] ChristianFoisyand Jean-YvesPotvin. Implementing aninsertion
heuristic for vehicle routing on parallel hardware. Computers &
Operations Research,20(7):737{745,1993.
[GBD +
94] AlGeist, Adam Beguelin, JackDongarra,WeichengJiang,Robert
Manchek, and Vaidy Sunderam. PVM: Parallel Virtual Machine
{A Users' Guideand Turorialfor NetworkedParallel Computing.
MITPress,1994.
[GC94] Bernard Gendron and Teodor Gabriel Crainic. Parallel
branch-and-bound algorithms: Surveyandsynthesis. Operations Research,
42(6):1042{1066,November-December1994.
[GDDS95] Sylvie Gelinas, Martin Desrochers, Jacques Desrosiers, and
Mar-ius M. Solomon. A new branching strategy for time constrained
routingproblemswithapplicationtobackhauling. Annals of
Oper-ationsResearch,61:91{109,1995.
[GJ79] MichaelR.GareyandDavidS.Johnson.ComputersandIntr
actabil-ity{ AGuide tothe Theory of NP-Completeness. W. H. Freeman
andCompany,1979.
[GKP] Ananth Grama, Vipin Kumar, and Panos Pardalos. Parallel
pro-routing methods. In M. Florian, editor, Transportation Planning
Models,pages383{418.ElsevierSciencePublishersB.V.,1984.
[GPR94] Bruno-LaurentGarcia,Jean-YvesPotvin,andJean-MarcRousseau.
A parallel implementation of the tabu search heuristic for vehicle
routingproblemswithtimewindowconstraints. Computers&
Op-erationsResearch,21(9):1025{1033,1994.
[GTA99] Luca Maria Gambardella,
Eric Taillard, and Giovanni Agazzi.
MACS - VRPTW: A multiple ant colonysystem for vehicle
rout-ing problems with time windows. Technical Report IDSIA-06-99,
IDSIA,1999.
[Hal92] Karsten Halse. Modeling and Solving Complex Vehicle Routing
Problems. PhD thesis, Department for Mathematical Modeling,
TechnicalUniversityofDenmark,1992.
[HTd95] Alain Hertz, Eric Taillard, and Dominique de Werra. A
tuto-rial on tabu search. Technical report, EPFL, Departement de
Mathematique, MA-Ecublens, 1995. Available via WWW on
www.idsia.ch/~eric/.
[JaJ92] Joseph JaJa. An Introduction to Parallel Algorithms.
Addison-Wesley PublishingCompany,1992.
[JMS86] Kurt O. Jornsten, Oli B. G. Madsen, and Bo Srensen. Exact
solution of the vehicle routing and scheduling problem with time
windowsby variable splitting. Technical Report 5, Departmentof
MathematicalModelling,TechnicalUniversityofDenmark,1986.
[KB95] GeorgeKontoravdisandJonathanF.Bard. Agraspforthevehicle
routingproblemwithtimewindows.ORSAJournalonComputing,
7(1):10{23, 1995.
[KDM +
99] Niklas Kohl, Jacques Desrosiers, Oli B. G. Madsen, Marius M.
Solomon, and Francois Soumis. 2-path cuts for the vehicle
rout-ingproblem withtimewindows. TransportationScience,33(1):101
{116,1999.
[KL86] G.A. P.Kindervaterand J.K.Lenstra. An introductionto
paral-lelismincombinatorialoptimization.DiscreteAppliedMathematics,
14:135{156,1986.
[KLK89] G. A. P. Kindervater, J. K. Lenstra, and A. H. G. Rinnooy Kan.
Perspectivesonparallelcomputing. OperationsResearch,37(6):985
[KM97] NiklasKohland OliB.G.Madsen. Anoptimization algorithmfor
thevehicleroutingproblemwithtimewindowsbasedonlagrangean
relaxation. OperationsResearch,45(3):395{406,May-June1997.
[Koh95] NiklasKohl. Exactmethodsfor Time ConstainedRoutingand
Re-latedScheduling Problems. PhDthesis,Departmentof
Mathemati-calModelling,TechnicalUniversityofDenmark, 1995.
IMM-PHD-1995-16.
[Kon97] Georgios Athanassio Kontoravdis. The Vehicle Routing Problem
withTimeWindows.PhDthesis,TheUniversityofTexasatAustin,
August1997.
[KPS97] PhilipKilby,PatrickProsser,and PaulShaw. Guided localsearch
forthevehicleroutingproblem. InMIC97, 2ndInternational
Con-ferenceon Metaheuristics.INRIA&PRiSM,1997.
[Kri95] Jens Kanstrup Kristensen. Route planning and set partitioning.
Master'sthesis,DepartmentofMathematicalModelling, Technical
UniversityofDenmark,1995. [indanish].
[KRT87] A. W. J. Kolen, A. H. G. Rinnooy Kaan, and H. W. J. M.
Trienekens. Vehicle routing with time windows. Operations
Re-search,35(2):266{273,March-April1987.
[Kwa93] Renata KrystynaKwatera. Clustering heuristics for set covering.
Annals of Operations Research,43:295{308,1993.
[Lap97] Gilbert Laporte. Recentadvancesinroutingalgorithms. Technical
Report G-97-38, GERAD and
Ecole des Hautes
Etudes
Commer-ciales,May1997.
[Lau94a] PerS. Laursen. Generaloptimizationheuristics { anintroduction.
Technical report, Department of Computer Science, University of
Copenhagen,1994. [inDanish].
[Lau94b] PerS. Laursen. Parallel Optimization Algorithms - EÆciency vs.
Simplicity. PhD thesis,Departmentof ComputerScience,
Univer-sityofCopenhagen,1994.
[LK81] J. K. Lenstraand A. H. G. Rinnooy Kan. Complexity of vehicle
routingandschedulingproblems. Networks,11:221{227,1981.
[LO95] GilbertLaporteandIbrahimH.Osman. Routingproblems: A
bib-liography. Annalsof OperationsResearcg,61:227{262,1995.
[LRT95] B.LeCun,C.Roucairol,andThePNNTeam.BOB:aunied
plat-formforimplementingbranch-and-boundlikealgorithms. Technical
[Mad90] Oli B. G. Madsen. Lagrangean relaxation and vehicle routing.
Technicalreport,DepartmentofMathematicalModelling,Technical
UniversityofDenmark,1990.
[Mal96] JoelMalard. Mpi: Amessage-passinginterfacestandard.Technical
report, Edinburgh Parallel Computing Center, The University of
Edinburgh,1996. Available viaWWWatwww.epcc.ed.ac.uk/.
[MDF +
95] Burkhard Monien, Ralf Dieckmann, Rainer Feldmann, Ralf
Klas-ing,ReinhardLuling,KnutMenzel, ThomasRomke,andUlf-Peter
Schroeder. EÆcient use of parallel & distributed systems: From
theorytopractice.AvailableviaWWWat
www.uni-paderborn.de/-pc2/services/public/,1995.
[MJ] Oli B. G.Madsen and SrenKruse Jacobsen. Notes to
mathmat-ical programming2{largesystems. Departmentof Mathematical
Modelling,TechnicalUniversityofDenmark. [indanish].
[MMHB] Neil MacDonald, ElspethMinty, Tim Harding, andSimon Brown.
Writing message-passing parallel programswith MPI {a twoday
course. Available viaWWWathttp://www.epcc.ed.ac.uk/.
[NW88] George L.Nemhauserand Laurence A.Wolsey. Integer and
Com-binatorial Optimization. Discrete Mathematics and Optimization.
Wiley Interscience,1988.
[Ols88] BrianOlsen. Route-planningwith timerestrictions. Technical
Re-port 2/88,Departmentof MathematicalModelling,Technical
Uni-versityofDenmark,1988. [indanish].
[Pac95] Peter S. Pacheco. A user'sguideto MPI. Available viaWWWat
www.usfca.edu/mpi/,March1995.
[Pan96] Cherri M. Pancake. Is parallelism for you? IEEE Computational
Science&Engineering,3(2):18{37, 1996.
[PB96] Jean-Yves Potvin and Sam Bengio. The vehicle routing problem
with time windows{partII : Geneticsearch. INFORMS Journal
of Computing,8(2):165{172,Spring 1996.
[PC98] MichaelPerregaardand JensClausen. Parallel branch-and-bound
methodsforthejob-shopschedulingproblem. AnnalsofOperations
Research,83:137{160,1998.
[PDR96] Jean-Yves Potvin, Danny Dube, and Christian Robillard. A
hy-bridapproachto vehicleroutingusingneuralnetworksandgenetic
[PKGR96] Jean-Yves Potvin, Tanguy Kervahut, Bruno-Laurent Garcia, and
Jean-MarcRousseau. Thevehicleroutingproblem with time
win-dows { part I : Tabu search. INFORMS Journal of Computing,
8(2):158{164,Spring1996.
[PL90] Panos Pardalos and Xiaoye Li. Parallel branch-and-bound
algo-rithmsforcombinatorialoptimization.Supercomputer,39(VII-5):23
{30,September1990.
[PR93] Jean-YvesPotvinandJean-MarcRousseau. Aparallelroute
build-ingalgorithm for thevehicleroutingand schedulingproblem with
timewindows. EuropeanJournalofOperational Research,66:331{
340,1993.
[PR95] Jean-YvesPotvinandJean-MarcRousseau. Anexchangeheuristic
for routeringproblems with time windows. Journal of the
Opera-tionalResearchSociety,46(12):1433{1446,1995.
[PR99] Jean-YvesPotvin and Christian Robillard. Clustering for vehicle
routingwith acompetitiveneuralnetwork. Neurocomputing, 8:125
{139,1999.
[RF81] D. M. Ryan and B.A. Foster. An integerprogrammingapproach
to scheduling. InA. Wren, editor, Computer Scheduling of Public
Transport, pages 269 { 280. North-Holland Publishing Company,
1981.
[RF88] D.M.RyanandJ.C.Falkner.Ontheintegerpropertiesof
schedul-ing set partitioning models. European Journal of Operational
Re-search,35:442{456,1988.
[Rou96] CatherineRoucairol. Parallelprocessingfor diÆcultcombinatorial
optimizationproblems. EuropeanJournalof Operational Research,
92:573{590,1996.
[RT95] Yves Rochar and
Eric D. Taillard. Probalistic diversication and
intensicationinlocalsearchforvehiclerouting.Journalof
Heuris-tics,1:147{167,1995.
[Rus95] RobertA.Russell. Hybridheuristicsforthevehicleroutingproblem
withtime windows. Transportation Science, 29(2):156{166,May
1995.
[Rya92] DavidM.Ryan.Thesolutionofmassivegeneralizedsetpartitioning
problemsinaircrewrostering. Journal ofthe Operational Research
Society,43(5):459{467,1992.
[Sal75] HarveyM.Salkin. Integer Programming. Addison-Wesley