×

zbMATH — the first resource for mathematics

Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. (English) Zbl 0461.90067

MSC:
90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
05C35 Extremal problems in graph theory
90C39 Dynamic programming
05C05 Trees
Software:
VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M.L. Balinski and R.E. Quandt, ”On an integer program for a delivery problem”,Operations Research 12 (1964) 300. · doi:10.1287/opre.12.2.300
[2] R. Bellman, ”On a routing problem”,Quarterly Journal of Applied Mathematics (1958) 87. · Zbl 0081.14403
[3] N. Christofides,Graph theory, an algorithmic approach (Academic Press, London, 1975). · Zbl 0321.94011
[4] N. Christofides, ”The vehicle routing problem”,Revue Française d’Automatique, Informatique et Recherche Opérationnelle 10 (1976) 55.
[5] N. Christofides, ”The travelling salesman problem”, in: N. Christofides, A. Mingozzi, P. Toth and C. Sandi, eds.,Combinatorial optimization (John Wiley and Sons, London, 1979). · Zbl 0415.90057
[6] N. Christofides, A. Mingozzi and P. Toth, ”The vehicle routing problem”, in: N. Christofides, A. Mingozzi, P. Toth and C. Sandi, eds.,Combinatorial optimization (John Wiley and Sons, London, 1979). · Zbl 0413.90075
[7] N. Christofides, A. Mingozzi and P. Toth, ”State-space relaxations for combinatorial problems”, Imperial College internal report IC, OR, 79, 09, July 1979.
[8] C. Clarke and J.Q. Wright, ”Scheduling of vehicles from a central depot to a number of delivery points”,Operations Research 12 (1964) 568. · doi:10.1287/opre.12.4.568
[9] S. Eilon, C. Watson-Gandy and N. Christofides,Distribution management, mathematical modelling and practical analysis (Griffin, London, 1971).
[10] T.J. Gaskell, ”Bases for vehicle fleet scheduling”,Operational Research Quarterly 18 (1967) 281. · doi:10.1057/jors.1967.44
[11] B.E. Gillet and L.R. Miller, ”A heuristic algorithm for the vehicle dispatch problem”,Operations Research 22 (1974) 340. · Zbl 0274.90013 · doi:10.1287/opre.22.2.340
[12] B.L. Golden, ”Vehicle routing problems: formulations and heuristic solution techniques”, ORC technical report 113, Massachusetts Institute of Technology (August 1975).
[13] B.L. Golden, ”Recent developments in vehicle routing”, Presented at the Bicentennial Conference on Mathematical Programming (November 1976). · Zbl 0424.90032
[14] R. Hays, ”The delivery problem”, Carnegie Institute of Technology Management Science Research, report 106 (1967).
[15] M. Held and R. Karp, ”The TSP and minimum spanning trees I”,Operations Research 18 (1970) 1138. · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138
[16] M. Held and R. Karp, ”The TSP and minimum spanning trees II”,Mathematical Programming 1 (1971) 6–25. · Zbl 0232.90038 · doi:10.1007/BF01584070
[17] D. Houck, J.C. Picard, M. Queyranne and R.R. Vemuganti, ”The travelling salesman problem and shortestn-paths”, University of Maryland (1977). · Zbl 0446.90084
[18] S. Lin and B.W. Kernighan, ”An effective heuristic algorithm for the TSP”,Operations Research 21 (1973) 498. · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[19] C. Miller, A.W. Tucker and R.A. Zemlin, ”Integer programming formulation of the travelling salesman problem”,Journal of the Association for Computing Machinery 7 (1960). · Zbl 0100.15101
[20] J.F. Pierce, ”A two-stage approach to the solution of vehicle dispatching problems”, Presented at the 17th T.I.M.S. International Conference London (1970).
[21] F.A. Tillman and H. Cochran, ”A heuristic approach for solving the delivery problem”,Journal of Industrial Engineering 19 (1969) 354.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.