Vehicle Routing References

This is just a brief list of relevant references. These cover both the VRP and some relaxations. Someday, I hope to have it expanded with BibTeX entries. For now, I hope it's useful as a starting point. The topical areas are

Polyhedral and Separation
Branch and Cut
Miscellaneous
Traveling Salesman Problem
Capacitated Minimum Spanning Tree

Polyhedral and Separation

J.R. Araque, Contributions to the Polyhedral Approach to Vehicle Routing, Discussion Paper 90-74, CORE, University of Louvain La Neuve (1990).
P. Augerat, Approche Polyhédrale du Probléme de Tournées de Véhicules, Ph.D. Dissertation, Institut Polytechnique de Grenoble (1995).
P. Augerat, J.M. Belenguer, E. Benavent, A. Corberán, D. Naddef, Separating Capacity Constraints in the CVRP Using Tabu Search, European Journal of Operations Research, 106 (1998), 546.
V. Campos, A. Corberán, and E. Mota, Polyhedral Results for a Vehicle Routing Problem, European Journal of Operations Research 52 (1991), 75.
G. Cornuéjols and F. Harche, Polyhedral Study of the Capacitated Vehicle Routing Problem, Mathematical Programming 60 (1993), 21.
A. De Vitis, M. Queyranne, and G. Rinaldi, Separating the Capacity Inequalities of the Vehicle Routing Problem in Polynomial Time, in preparation.
L. Kopman, A New Generic Separation Algorithm and Its Application to the Vehicle Routing Problem, Ph.D. Dissertation, Field of Operations Research, Cornell University, Ithaca, N.Y., U.S.A. (1999).
G. Laporte and Y. Nobert, Comb Inequalities for the Vehicle Routing Problem, Methods of Operations Research 51 (1981), 271.
A.N. Letchford, R.W. Eglese, and J. Lysgaard, Multistars, partial multistars and the capacitated vehicle routing problem, Mathematical Programming 94 (2003), 21.

Branch and Cut

Y. Agarwal, K. Mathur, and H.M. Salkin, Set Partitioning Approach to Vehicle Routing, Networks 7 (1989), 731.
J.R. Araque, G. Kudva, T.L. Morin, and J.F. Pekny, A Branch-and-Cut Algorithm for Vehicle Routing Problems, Annals of Operations Research 50 (1994), 37.
P. Augerat, J.M. Belenguer, E. Benavent, A. Corberán, D. Naddef, G. Rinaldi, Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem, Research Report 949-M, Universite Joseph Fourier, Grenoble, France.
U. Blasum and W. Hochstattler, Application of the Branch and Cut Method to the Vehicle Routing Problem, Zentrum fur Angewandte Informatik Koln Technical Report zpr2000-386 (2000).
J. Lysgaard, A.N. Letchford, and R.W. Eglese, A New Branch-and-cut Algorithm for Capacitated Vehicle Routing Problems, submitted to Mathematical Programming (2003).
D. Naddef and G. Rinaldi, Branch and Cut, in P. Toth and D. Vigo, eds., Vehicle Routing, SIAM (2000).
T.K. Ralphs, L. Kopman, W.R. Pulleyblank, and L.E. Trotter Jr., On the Capacitated Vehicle Routing Problem, Mathematical Programming Series B 94 (2003), 343.
T.K. Ralphs, Parallel Branch and Cut for Vehicle Routing, Parallel Computing 29 (2003), 607.

Miscellaneous

R. Baldacci, A. Mingozzi, and E. Hadjiconstantinou, An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a two-commodity network flow formulation, Technical Report 16, Department of Mathematics, University of Bologna (1999).
M.L. Balinski and R.E. Quandt, On an Integer Program for a Delivery Problem, Operations Research 12 (1964), 300.
N. Christofides and S. Eilon, An Algorithm for the Vehicle Dispatching Problem, Operational Research Quarterly 20 (1969), 309.
N. Christofides, A. Mingozzi and P. Toth, Exact Algorithms for Solving the Vehicle Routing Problem Based on Spanning Trees and Shortest Path Relaxations, Mathematical Programming 20 (1981), 255.
F.H. Cullen, J.J. Jarvis and H.D. Ratliff, Set Partitioning Based Heuristic for Interactive Routing, Networks 11 (1981), 125.
G.B. Dantzig and J.H. Ramser, The Truck Dispatching Problem, Management Science 6 (1959), 80.
M.L. Fisher, Optimal Solution of Vehicle Routing Problems Using Minimum k-Trees, Operations Research 42 (1988), 141.
M.L. Fisher and R. Jaikumar, A Generalized Assignment Heuristic for Solving the VRP, Networks 11 (1981), 109.
B.A. Foster and D.M. Ryan, An Integer Programming Approach to the Vehicle Scheduling Problem, Operational Research Quarterly 27 (1976), 367.
G. Laporte, Y. Nobert and M. Desrouchers, Optimal Routing with Capacity and Distance Restrictions, Operations Research 33 (1985), 1050.
C. Martinhon, A. Lucena, and N. Maculan, A Relax and Cut Method for the Vehicle Routing Problem, working paper.
H. Nagamochi and T. Ibaraki, Computing Edge Connectivity in Multigraphs and Capacitated Graphs, SIAM Journal of Discrete Mathematics 5 (1992), 54.
P. Toth and D. Vigo, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications (2002).

Traveling Salesman Problem

D. Applegate, R. Bixby, V. Chvátal, W. Cook, On the solution of traveling salesman problems, Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians (1998), 645-656.
D. Applegate, R. Bixby, V. Chvátal, and W. Cook, CONCORDE TSP Solver, available at www.keck.caam.rice.edu/concorde.html .
D. Applegate, R. Bixby, V. Chvátal, and W. Cook, Finding Cuts in the TSP, DIMACS Technical Report 95-05 (1995).
H. Crowder and M. Padberg, Solving Large Scale Symmetric Traveling Salesman Problems to Optimality, Management Science 26 (1980), 495.
G. Finke, A. Claus, and E. Gunn, A two-commodity network flow approach to the traveling salesman problem, Congress Numerantium 41 (1984), 167.
M. Held and R.M. Karp, The Traveling Salesman Problem and Minimal Spanning Trees, Operations Research 18 (1969), 1138.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, New York (1985).
D. Naddef and G. Rinaldi, The Symmetric Traveling Salesman Polytope and its Graphical Relaxation: Composition of Valid Inequalities, Mathematical Programming 51 (1991), 359.
D. Naddef and G. Rinaldi, The Graphical Relaxation: A New Framework for the Symmetric Traveling Salesman Polytope, Mathematical Programming 58 (1993), 53.
D. Naddef and S. Thienel, Efficient Separation Routines for Symmetric Traveling Salesman Problem I: General Tools and Comb Separation, Technical Report, Universitat Koln (1998), to appear.
D. Naddef and S. Thienel, Efficient Separation Routines for Symmetric Traveling Salesman Problem II: Separating Multi-handle Inequalities, Technical Report, Universitat Koln (1998), to appear.
M. Padberg and G. Rinaldi, A Branch-and-Cut Algorithm for the Resolution of Large-Scale Traveling Salesman Problems, SIAM Review 33 (1991), 60.

Capacitated Minimum Spanning Tree

A. Amberg, W. Domschke, S. Voss, Capacitated Minimum Spanning Trees: Algorithms Using Intelligent Search, to be published in Combinatorial Optimization: Theory and Practice.
J.R. Araque, L. Hall, and T. Magnanti, Capacitated Trees, Capacitated Routing and Associated Polyhedra, Discussion paper 9061, CORE, Louvain La Nueve (1990).
K.M. Chandy and T. Lo, The Capacitated Minimal Spanning Tree, Networks 3 (1973), 173.
B. Gavish, Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem, Journal of ACM 30 (1983), 118.
B. Gavish, Topological Design of Centralized Computer Networks, Networks 12 (1982), 355.
B. Gavish, Augmented Lagragian Based Algorithms for Centralized Network Design, IEEE Transactions on Communication COM-33 (1985), 1247.
L. Gouveia, A 2n-Constraint Formulation for the Capacitated Minimal Spanning Tree, Operations Research 43 (1995), 130.
L. Hall, Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem, INFORMS Journal on Computing 3 (1996), 219.
F.J. Vasko, R.S. Barbieri, K.L. Reitmeyer, K.L. Scott, The Cable Trench Problem: Combining the Shortest Path and Minimum Spanning Tree Problems, Research Report, Kutztown University, Kutztown, PA.

This page maintained by Ted Ralphs (ted@branchandcut.org)

Last updated August 1, 2002