{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,14]],"date-time":"2024-04-14T10:41:07Z","timestamp":1713091267272},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,11,3]],"date-time":"2011-11-03T00:00:00Z","timestamp":1320278400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2013,2]]},"DOI":"10.1007\/s10107-011-0497-4","type":"journal-article","created":{"date-parts":[[2011,11,2]],"date-time":"2011-11-02T16:02:50Z","timestamp":1320249770000},"page":"409-452","source":"Crossref","is-referenced-by-count":33,"title":["Improved lower bounds and exact algorithm for the capacitated arc routing problem"],"prefix":"10.1007","volume":"137","author":[{"given":"Enrico","family":"Bartolini","sequence":"first","affiliation":[]},{"given":"Jean-Fran\u00e7ois","family":"Cordeau","sequence":"additional","affiliation":[]},{"given":"Gilbert","family":"Laporte","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,11,3]]},"reference":[{"key":"497_CR1","first-page":"1","volume-title":"Proceedings of the 35th Hawaii International Conference on System Sciences, vol. 3","author":"A. Amberg","year":"2002","unstructured":"Amberg A., Vo\u00df S.: A hierarchical relaxations lower bound for the capacitated arc routing problem. In: Sprague, H.R. (eds) Proceedings of the 35th Hawaii International Conference on System Sciences, vol. 3., pp. 1\u201310. IEEE Computer Society, Washington DC (2002)"},{"key":"497_CR2","doi-asserted-by":"crossref","unstructured":"Assad, A.A., Golden, B.L.: Arc routing methods and applications. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds.) Network Routing, North-Holland, Amsterdam (1995)","DOI":"10.1016\/S0927-0507(05)80109-4"},{"key":"497_CR3","first-page":"63","volume":"7","author":"A.A. Assad","year":"1987","unstructured":"Assad A.A., Pearn W.L., Golden B.L.: The capacitated postman problem: lower bounds and solvable cases. Am. J. Math. Manage. Sci. 7, 63\u201388 (1987)","journal-title":"Am. J. Math. Manage. Sci."},{"key":"497_CR4","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s10107-007-0178-5","volume":"115","author":"R. Baldacci","year":"2008","unstructured":"Baldacci R., Christofides N., Mingozzi A.: An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Program. A 115, 351\u2013385 (2008)","journal-title":"Math. Program. A"},{"key":"497_CR5","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1002\/net.20091","volume":"47","author":"R. Baldacci","year":"2006","unstructured":"Baldacci R., Maniezzo V.: Exact methods based on node-routing formulations for undirected arc-routing problems. Networks 47, 52\u201360 (2006)","journal-title":"Networks"},{"key":"497_CR6","doi-asserted-by":"crossref","unstructured":"Baldacci, R., Mingozzi, A., Roberti, R.: New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. (2011, to appear)","DOI":"10.1287\/opre.1110.0975"},{"key":"497_CR7","doi-asserted-by":"crossref","unstructured":"Baldacci, R., Mingozzi, A., Roberti, R.: New state space relaxations for solving the traveling salesman problem with time windows. INFORMS J. Comput. doi: 10.1287\/ijoc.1110.0456 (2011)","DOI":"10.1287\/ijoc.1110.0456"},{"key":"497_CR8","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1023\/A:1018316919294","volume":"10","author":"J.M. Belenguer","year":"1998","unstructured":"Belenguer J.M., Benavent E.: The capacitated arc routing problem: valid inequalities and facets. Comput. Optim. Appl. 10, 165\u2013187 (1998)","journal-title":"Comput. Optim. Appl."},{"key":"497_CR9","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/S0305-0548(02)00046-1","volume":"30","author":"J.M. Belenguer","year":"2003","unstructured":"Belenguer J.M., Benavent E.: A cutting plane algorithm for the capacitated arc routing problem. Comput. Oper. Res. 30, 705\u2013728 (2003)","journal-title":"Comput. Oper. Res."},{"key":"497_CR10","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1002\/net.3230220706","volume":"22","author":"E. Benavent","year":"1992","unstructured":"Benavent E., Campos V., Corber\u00e1n A., Mota E.: The capacitated arc routing problem: lower bounds. Networks 22, 669\u2013690 (1992)","journal-title":"Networks"},{"key":"497_CR11","unstructured":"Beullens, P., Muyldermans, L.: Personal communication (2010)"},{"key":"497_CR12","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1016\/S0377-2217(02)00334-X","volume":"147","author":"P. Beullens","year":"2003","unstructured":"Beullens P., Muyldermans L., Cattrysse D., Van Oudheusden D.: A guided local search heuristic for the capacitated arc routing problem. Eur. J. Oper. Res. 147, 629\u2013643 (2003)","journal-title":"Eur. J. Oper. Res."},{"key":"497_CR13","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1057\/palgrave.jors.2601590","volume":"54","author":"M. Blais","year":"2003","unstructured":"Blais M., Laporte G.: Exact solution of the generalized routing problem through graph transformations. J. Oper. Res. Soc. 54, 906\u2013910 (2003)","journal-title":"J. Oper. Res. Soc."},{"key":"497_CR14","unstructured":"Bode, C., Irnich, S.: Cut-first branch-and-price-second for the capacitated arc-routing problem. Technical Report LM-2011-01 (preliminary version), Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University, Mainz, Germany (2011)"},{"key":"497_CR15","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1016\/0305-0483(73)90089-3","volume":"1","author":"N. Christofides","year":"1973","unstructured":"Christofides N.: The optimum traversal of a graph. Omega 1, 719\u2013732 (1973)","journal-title":"Omega"},{"key":"497_CR16","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01589353","volume":"20","author":"N. Christofides","year":"1981","unstructured":"Christofides N., Mingozzi A., Toth P.: Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation. Math. Program. 20, 255\u2013282 (1981)","journal-title":"Math. Program."},{"key":"497_CR17","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1002\/net.20347","volume":"56","author":"A. Corber\u00e1n","year":"2010","unstructured":"Corber\u00e1n A., Prins C.: Recent results on arc routing problems: an annotated bibliography. Networks 56, 50\u201369 (2010)","journal-title":"Networks"},{"key":"497_CR18","volume-title":"ILOG CPLEX 12.1 Callable Library","author":"CPLEX","year":"2008","unstructured":"CPLEX: ILOG CPLEX 12.1 Callable Library. ILOG, Nevada (2008)"},{"key":"497_CR19","volume-title":"Arc Routing: Theory, Solutions and Applications","year":"2000","unstructured":"Dror, M. (eds): Arc Routing: Theory, Solutions and Applications. Kluwer, Boston (2000)"},{"key":"497_CR20","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0166-218X(92)00003-5","volume":"48","author":"R.W. Eglese","year":"1994","unstructured":"Eglese R.W.: Routeing winter gritting vehicles. Discr. Appl. Math. 48, 231\u2013244 (1994)","journal-title":"Discr. Appl. Math."},{"key":"497_CR21","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1287\/opre.43.2.231","volume":"43","author":"H.A. Eiselt","year":"1995","unstructured":"Eiselt H.A., Gendreau M., Laporte G.: Arc routing problems, part I: The Chinese postman problem. Oper. Res. 43, 231\u2013242 (1995)","journal-title":"Oper. Res."},{"key":"497_CR22","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1287\/opre.43.3.399","volume":"43","author":"H.A. Eiselt","year":"1995","unstructured":"Eiselt H.A., Gendreau M., Laporte G.: Arc routing problems, part II: The rural postman problem. Oper. Res. 43, 399\u2013414 (1995)","journal-title":"Oper. Res."},{"key":"497_CR23","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/s10107-005-0644-x","volume":"106","author":"R. Fukasawa","year":"2006","unstructured":"Fukasawa R., Longo H., Lysgaard J., Poggi de Arag\u00e3o M., Reis M., Uchoa E., Werneck R.F.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. A 106, 491\u2013511 (2006)","journal-title":"Math. Program. A"},{"key":"497_CR24","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/S0377-2217(99)00073-9","volume":"122","author":"G. Ghiani","year":"2000","unstructured":"Ghiani G., Improta G.: An efficient transformation of the generalized vehicle routing problem. Eur. J. Oper. Res. 122, 11\u201317 (2000)","journal-title":"Eur. J. Oper. Res."},{"key":"497_CR25","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0305-0548(83)90026-6","volume":"10","author":"B.L. Golden","year":"1983","unstructured":"Golden B.L., DeArmon J.S., Baker E.K.: Computational experiments with algorithms for a class of routing problems. Comput. Oper. Res. 10, 47\u201359 (1983)","journal-title":"Comput. Oper. Res."},{"key":"497_CR26","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1002\/net.3230110308","volume":"11","author":"B.L. Golden","year":"1981","unstructured":"Golden B.L., Wong R.T.: Capacitated arc routing problems. Networks 11, 305\u2013315 (1981)","journal-title":"Networks"},{"key":"497_CR27","unstructured":"G\u00f3mez-Cabrero, D., Belenguer, J.M., Benavent, E.: Cutting plane and column generation for the capacitated arc routing problem. Presented at ORP3 MEETING, Valencia, Spain (2005)"},{"key":"497_CR28","doi-asserted-by":"crossref","first-page":"119","DOI":"10.15807\/jorsj.35.119","volume":"35","author":"R. Hirabayashi","year":"1992","unstructured":"Hirabayashi R., Nishida N., Saruwatari Y.: Node duplication lower bounds for the capacitated arc routing problems. J. Oper. Res. Soc. Jpn 35, 119 (1992)","journal-title":"J. Oper. Res. Soc. Jpn"},{"key":"497_CR29","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1287\/opre.1070.0449","volume":"56","author":"M. Jepsen","year":"2008","unstructured":"Jepsen M., Petersen B., Spoorendonk S., Pisinger D.: Subset-row inequalities applied to the vehicle routing problem with time windows. Oper. Res. 56, 497\u2013511 (2008)","journal-title":"Oper. Res."},{"key":"497_CR30","unstructured":"Kiuchi, M., Shinano, Y., Hirabayashi, R., Saruwatari, Y.: An exact algorithm for the capacitated arc routing problem using parallel branch and bound method. In: Abstracts of the 1995 Spring National Conference of the Operations Research Society of Japan, pp. 28\u201329 (1995)"},{"key":"497_CR31","doi-asserted-by":"crossref","first-page":"2320","DOI":"10.1016\/j.cor.2008.09.008","volume":"36","author":"A.N. Letchford","year":"2009","unstructured":"Letchford A.N., Oukil A.: Exploiting sparsity in pricing routines for the capacitated arc routing problem. Comput. Oper. Res. 36, 2320\u20132327 (2009)","journal-title":"Comput. Oper. Res."},{"key":"497_CR32","first-page":"217","volume":"47","author":"L.Y.O. Li","year":"1966","unstructured":"Li L.Y.O., Eglese R.W.: An interactive algorithm for vehicle routing for winter-gritting. J. Oper. Res. Soc. 47, 217\u2013228 (1966)","journal-title":"J. Oper. Res. Soc."},{"key":"497_CR33","doi-asserted-by":"crossref","first-page":"1823","DOI":"10.1016\/j.cor.2004.11.020","volume":"33","author":"H. Longo","year":"2006","unstructured":"Longo H., Poggi de Arag\u00e3o M., Uchoa E.: Solving capacitated arc routing problems using a transformation to the CVRP. Comput. Oper. Res. 33, 1823\u20131837 (2006)","journal-title":"Comput. Oper. Res."},{"key":"497_CR34","unstructured":"Lysgaard, J.: CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. Technical Report Working paper 03-04, Department of Management Science and Logistics, Aarhus School of Business, Denmark (2003)"},{"key":"497_CR35","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/s10107-003-0481-8","volume":"100","author":"J. Lysgaard","year":"2004","unstructured":"Lysgaard J., Letchford A.N., Eglese R.W.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program. A 100, 423\u2013445 (2004)","journal-title":"Math. Program. A"},{"key":"497_CR36","unstructured":"Martinelli, R., Pecin, D., Poggi de Arag\u00e3o, M., Longo, H.: Column generation bounds for the capacitated arc routing problem. Presented at XLII SBPO, Bento Gon\u00e7alves, Brazil (2010)"},{"key":"497_CR37","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"1","author":"M.W. Padberg","year":"1982","unstructured":"Padberg M.W., Rao M.R.: Odd minimum cut-sets and b-matchings. Math. Oper. Res. 1, 67\u201380 (1982)","journal-title":"Math. Oper. Res."},{"key":"497_CR38","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1002\/net.3230180305","volume":"18","author":"W.L. Pearn","year":"1988","unstructured":"Pearn W.L.: New lower bounds for the capacitated arc routing problem. Networks 18, 181\u2013191 (1988)","journal-title":"Networks"},{"key":"497_CR39","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/j.trb.2009.07.004","volume":"44","author":"L. Santos","year":"2010","unstructured":"Santos L., Coutinho-Rodrigues J., Current J.R.: An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transport. Res. B 44, 246\u2013266 (2010)","journal-title":"Transport. Res. B"},{"key":"497_CR40","unstructured":"Win, Z.: Contributions to Routing Problems. PhD thesis, University of Augsburg, Germany (1987)"},{"key":"497_CR41","doi-asserted-by":"crossref","first-page":"3458","DOI":"10.1016\/j.cor.2005.02.015","volume":"33","author":"S. W\u00f8hlk","year":"2006","unstructured":"W\u00f8hlk S.: New lower bound for the capacitated arc routing problem. Comput. Oper. Res. 33, 3458\u20133472 (2006)","journal-title":"Comput. Oper. Res."},{"key":"497_CR42","volume-title":"The Vehicle Routing Problem: Latest Advances and New Challenges","author":"S. W\u00f8hlk","year":"2008","unstructured":"W\u00f8hlk S.: A decade of capacitated arc routing. In: Golden, B.L., Raghavan, S., Wasil, A. (eds) The Vehicle Routing Problem: Latest Advances and New Challenges, Springer, New York (2008)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-011-0497-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-011-0497-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-011-0497-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,14]],"date-time":"2024-04-14T10:21:06Z","timestamp":1713090066000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-011-0497-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,3]]},"references-count":42,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["497"],"URL":"https:\/\/doi.org\/10.1007\/s10107-011-0497-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,3]]}}}