{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,26]],"date-time":"2026-04-26T01:37:46Z","timestamp":1777167466437,"version":"3.51.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1981,12,1]],"date-time":"1981-12-01T00:00:00Z","timestamp":376012800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1981,12]]},"DOI":"10.1007\/bf01589353","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T12:22:39Z","timestamp":1114690959000},"page":"255-282","source":"Crossref","is-referenced-by-count":359,"title":["Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations"],"prefix":"10.1007","volume":"20","author":[{"given":"N.","family":"Christofides","sequence":"first","affiliation":[]},{"given":"A.","family":"Mingozzi","sequence":"additional","affiliation":[]},{"given":"P.","family":"Toth","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1287\/opre.12.2.300","volume":"12","author":"M.L. Balinski","year":"1964","unstructured":"M.L. Balinski and R.E. Quandt, \u201cOn an integer program for a delivery problem\u201d,Operations Research 12 (1964) 300.","journal-title":"Operations Research"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"R. Bellman, \u201cOn a routing problem\u201d,Quarterly Journal of Applied Mathematics (1958) 87.","DOI":"10.1090\/qam\/102435"},{"key":"CR3","volume-title":"Graph theory, an algorithmic approach","author":"N. Christofides","year":"1975","unstructured":"N. Christofides,Graph theory, an algorithmic approach (Academic Press, London, 1975)."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1051\/ro\/197610V100551","volume":"10","author":"N. Christofides","year":"1976","unstructured":"N. Christofides, \u201cThe vehicle routing problem\u201d,Revue Fran\u00e7aise d'Automatique, Informatique et Recherche Op\u00e9rationnelle 10 (1976) 55.","journal-title":"Revue Fran\u00e7aise d'Automatique, Informatique et Recherche Op\u00e9rationnelle"},{"key":"CR5","volume-title":"Combinatorial optimization","author":"N. Christofides","year":"1979","unstructured":"N. Christofides, \u201cThe travelling salesman problem\u201d, in: N. Christofides, A. Mingozzi, P. Toth and C. Sandi, eds.,Combinatorial optimization (John Wiley and Sons, London, 1979)."},{"key":"CR6","volume-title":"Combinatorial optimization","author":"N. Christofides","year":"1979","unstructured":"N. Christofides, A. Mingozzi and P. Toth, \u201cThe vehicle routing problem\u201d, in: N. Christofides, A. Mingozzi, P. Toth and C. Sandi, eds.,Combinatorial optimization (John Wiley and Sons, London, 1979)."},{"key":"CR7","unstructured":"N. Christofides, A. Mingozzi and P. Toth, \u201cState-space relaxations for combinatorial problems\u201d, Imperial College internal report IC, OR, 79, 09, July 1979."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1287\/opre.12.4.568","volume":"12","author":"C. Clarke","year":"1964","unstructured":"C. Clarke and J.Q. Wright, \u201cScheduling of vehicles from a central depot to a number of delivery points\u201d,Operations Research 12 (1964) 568.","journal-title":"Operations Research"},{"key":"CR9","volume-title":"Distribution management, mathematical modelling and practical analysis","author":"S. Eilon","year":"1971","unstructured":"S. Eilon, C. Watson-Gandy and N. Christofides,Distribution management, mathematical modelling and practical analysis (Griffin, London, 1971)."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1057\/jors.1967.44","volume":"18","author":"T.J. Gaskell","year":"1967","unstructured":"T.J. Gaskell, \u201cBases for vehicle fleet scheduling\u201d,Operational Research Quarterly 18 (1967) 281.","journal-title":"Operational Research Quarterly"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1287\/opre.22.2.340","volume":"22","author":"B.E. Gillet","year":"1974","unstructured":"B.E. Gillet and L.R. Miller, \u201cA heuristic algorithm for the vehicle dispatch problem\u201d,Operations Research 22 (1974) 340.","journal-title":"Operations Research"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"B.L. Golden, \u201cVehicle routing problems: formulations and heuristic solution techniques\u201d, ORC technical report 113, Massachusetts Institute of Technology (August 1975).","DOI":"10.21236\/ADA013639"},{"key":"CR13","unstructured":"B.L. Golden, \u201cRecent developments in vehicle routing\u201d, Presented at the Bicentennial Conference on Mathematical Programming (November 1976)."},{"key":"CR14","unstructured":"R. Hays, \u201cThe delivery problem\u201d, Carnegie Institute of Technology Management Science Research, report 106 (1967)."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held and R. Karp, \u201cThe TSP and minimum spanning trees I\u201d,Operations Research 18 (1970) 1138.","journal-title":"Operations Research"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"M. Held and R. Karp, \u201cThe TSP and minimum spanning trees II\u201d,Mathematical Programming 1 (1971) 6\u201325.","journal-title":"Mathematical Programming"},{"key":"CR17","unstructured":"D. Houck, J.C. Picard, M. Queyranne and R.R. Vemuganti, \u201cThe travelling salesman problem and shortestn-paths\u201d, University of Maryland (1977)."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S. Lin","year":"1973","unstructured":"S. Lin and B.W. Kernighan, \u201cAn effective heuristic algorithm for the TSP\u201d,Operations Research 21 (1973) 498.","journal-title":"Operations Research"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"C. Miller, A.W. Tucker and R.A. Zemlin, \u201cInteger programming formulation of the travelling salesman problem\u201d,Journal of the Association for Computing Machinery 7 (1960).","DOI":"10.1145\/321043.321046"},{"key":"CR20","unstructured":"J.F. Pierce, \u201cA two-stage approach to the solution of vehicle dispatching problems\u201d, Presented at the 17th T.I.M.S. International Conference London (1970)."},{"key":"CR21","first-page":"354","volume":"19","author":"F.A. Tillman","year":"1969","unstructured":"F.A. Tillman and H. Cochran, \u201cA heuristic approach for solving the delivery problem\u201d,Journal of Industrial Engineering 19 (1969) 354.","journal-title":"Journal of Industrial Engineering"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01589353.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01589353\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01589353","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T04:02:04Z","timestamp":1586232124000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01589353"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,12]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1981,12]]}},"alternative-id":["BF01589353"],"URL":"https:\/\/doi.org\/10.1007\/bf01589353","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,12]]}}}