{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T03:39:14Z","timestamp":1772941154207,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1995,12]]},"DOI":"10.1007\/bf02098280","type":"journal-article","created":{"date-parts":[[2005,9,13]],"date-time":"2005-09-13T21:52:12Z","timestamp":1126648332000},"page":"21-43","source":"Crossref","is-referenced-by-count":53,"title":["A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxations"],"prefix":"10.1007","volume":"61","author":[{"given":"Eleni","family":"Hadjiconstantinou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicos","family":"Christofides","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aristide","family":"Mingozzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02098280_CR1","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1287\/opre.12.2.300","volume":"12","author":"M. Balinski","year":"1964","unstructured":"M. Balinski and R. Quandt, On an integer program for a delivery problem, Operations Research 12(1964)300\u2013304.","journal-title":"Operations Research"},{"key":"BF02098280_CR2","unstructured":"N. Christofides and A. Mingozzi, Vehicle routing: practical and algorithmic aspects, in:Logistics: Where Ends Have to Meet, ed. C.F.H. van Rijn (Pergamon Press, 1989) pp. 30\u201348."},{"key":"BF02098280_CR3","first-page":"431","volume-title":"The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization","author":"N. Christofides","year":"1985","unstructured":"N. Christofides, Vehicle routing, in:The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization, eds. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys (Wiley, Chichester, 1985) pp. 431\u2013448."},{"key":"BF02098280_CR4","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01589353","volume":"10","author":"N. Christofides","year":"1981","unstructured":"N. Christofides, A. Mingozzi and P. Toth, Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Mathematical Programming 10(1981)255\u2013280.","journal-title":"Mathematical Programming"},{"key":"BF02098280_CR5","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/net.3230110207","volume":"11","author":"N. Christofides","year":"1981","unstructured":"N. Christofides, A. Mingozzi and P. Toth, State space relaxation procedures for the computation of bounds to routing problems, Networks 11(1981)145\u2013164.","journal-title":"Networks"},{"key":"BF02098280_CR6","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1057\/jors.1969.75","volume":"20","author":"N. Christofides","year":"1969","unstructured":"N. Christofides and S. Eilon, An algorithm for the vehicle dispatching problem, Operational Research Quarterly 20(1969)309\u2013318.","journal-title":"Operational Research Quarterly"},{"key":"BF02098280_CR7","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, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research 12(1964)568\u2013581.","journal-title":"Operations Research"},{"key":"BF02098280_CR8","unstructured":"G. Cornu\u00e9jols and F. Harche, Polyhedral study of the capacitated vehicle routing problem, Management Science Research Report No. 553, Carnegie Mellon University (1989)."},{"key":"BF02098280_CR9","volume-title":"Distribution Management, Mathematical Modelling and Practical Analysis","author":"S. Eilon","year":"1971","unstructured":"S. Eilon, C.D.T. Watson-Gandy and N. Christofides,Distribution Management, Mathematical Modelling and Practical Analysis (Griffin, London, 1971)."},{"key":"BF02098280_CR10","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1287\/opre.42.4.626","volume":"42","author":"M.L. Fisher","year":"1994","unstructured":"M.L. Fisher, Optimal solution of vehicle routing problems using minimumK-trees, Operations Research 42(1994)626\u2013642.","journal-title":"Operations Research"},{"key":"BF02098280_CR11","doi-asserted-by":"crossref","unstructured":"M.L. Fisher and R. Jaikumar, A Generalized Assignment heuristic for vehicle routing, Networks 11(1981).","DOI":"10.1002\/net.3230110205"},{"key":"BF02098280_CR12","unstructured":"M. Gendreau, A. Hertz and G. Laporte, A tabu search heuristic for the vehicle routing problem, Report CRT No. 777, University of Montreal (1992), Management Science, to appear."},{"key":"BF02098280_CR13","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1287\/opre.22.2.340","volume":"22","author":"E. Gillet","year":"1974","unstructured":"E. Gillet and L.R. Miller, A heuristic algorithm for the vehicle dispatch problem, Operations Research 22(1974)340\u2013349.","journal-title":"Operations Research"},{"key":"BF02098280_CR14","unstructured":"E. Hadjiconstantinou, C.P.A. Weston and N. Christofides, An efficient implementation of an algorithm fork-shortest simple paths, Management School Research Paper, Imperial College (1995)."},{"key":"BF02098280_CR15","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/BF01580223","volume":"6","author":"M. Held","year":"1974","unstructured":"M. Held, P. Wolfe and H.P. Crowder, Validation of subgradient optimization, Mathematical Programming 6(1974)62\u201388.","journal-title":"Mathematical Programming"},{"key":"BF02098280_CR16","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1002\/net.3230120406","volume":"12","author":"N. Katoh","year":"1982","unstructured":"N. Katoh, T. Ibaraki and H. Mine, An Efficient Algorithm fork-shortest simple paths, Networks 12(1982)411\u2013427.","journal-title":"Networks"},{"key":"BF02098280_CR17","first-page":"147","volume":"31","author":"G. Laporte","year":"1987","unstructured":"G. Laporte and Y. Nobert, Exact algorithms for the vehicle routing problem, Annals of Discrete Mathematics 31(1987)147\u2013184.","journal-title":"Annals of Discrete Mathematics"},{"key":"BF02098280_CR18","doi-asserted-by":"crossref","first-page":"1050","DOI":"10.1287\/opre.33.5.1050","volume":"33","author":"G. Laporte","year":"1985","unstructured":"G. Laporte, Y. Nobert and M. Desrochers, Optimal routing under capacity and distance restrictions, Operations Research 33(1985)1050\u20131073.","journal-title":"Operations Research"},{"key":"BF02098280_CR19","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 L. Kernighan, An effective heuristic algorithm for the travelling salesman problem, Operations Research 21(1973)498\u2013516.","journal-title":"Operations Research"},{"key":"BF02098280_CR20","unstructured":"A.P. Lucena, Exact solution approaches for the vehicle routing problem, Ph.D Thesis, Department of Management Science, Imperial College, University of London (1986)."},{"key":"BF02098280_CR21","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1002\/net.3230230804","volume":"23","author":"E. Taillard","year":"1993","unstructured":"E. Taillard, Parallel iterative search methods for vehicle routing problems, Networks 23(1993)661\u2013673.","journal-title":"Networks"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02098280.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02098280\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02098280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T14:29:29Z","timestamp":1557844169000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02098280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["BF02098280"],"URL":"https:\/\/doi.org\/10.1007\/bf02098280","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}