{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T13:43:30Z","timestamp":1762955010117,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642206610"},{"type":"electronic","value":"9783642206627"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20662-7_27","type":"book-chapter","created":{"date-parts":[[2011,4,20]],"date-time":"2011-04-20T06:05:25Z","timestamp":1303279525000},"page":"315-326","source":"Crossref","is-referenced-by-count":8,"title":["A Branch-Cut-and-Price Algorithm for the Capacitated Arc Routing Problem"],"prefix":"10.1007","author":[{"given":"Rafael","family":"Martinelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diego","family":"Pecin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"Poggi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Humberto","family":"Longo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","unstructured":"Ahr, D.: Contributions to Multiple Postmen Problems. Ph.D. dissertation, Department of Computer Science, Heidelberg University (2004)"},{"key":"27_CR2","unstructured":"Amberg, A., Vo\u00df, S.: A Hierarchical Relaxations Lower Bound for the Capacitated Arc Routing Problem. In: Proceedings of the 35th Anual Hawaii International Conference on System Sciences (2002)"},{"issue":"1,2","key":"27_CR3","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1080\/01966324.1987.10737208","volume":"7","author":"A.A. Assad","year":"1987","unstructured":"Assad, A.A., Pearn, W.L., Golden, B.L.: The Capacitated Chinese Postman Problem: Lower Bounds and Solvable Cases. American Journal of Mathematical Management Sciences\u00a07(1,2), 63\u201388 (1987)","journal-title":"American Journal of Mathematical Management Sciences"},{"key":"27_CR4","unstructured":"Belenguer, J.M., Benavent, E.: Polyhedral Results on the Capacitated Arc Routing Problem, Departamento de Estad\u00edstica e Investigaci\u00f3n Operativa, Universitat de Val\u00e8ncia, Tech. Rep. TR 1-92 (1992)"},{"key":"27_CR5","doi-asserted-by":"publisher","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. Computers & Operations Research\u00a030, 705\u2013728 (2003)","journal-title":"Computers & Operations Research"},{"issue":"3","key":"27_CR6","doi-asserted-by":"publisher","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., Oudheusden, D.V.: A Guided Local Search Heuristic for the Capacitated Arc Routing Problem. European Journal of Operational Research\u00a0147(3), 629\u2013643 (2003)","journal-title":"European Journal of Operational Research"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"1112","DOI":"10.1016\/j.cor.2006.07.007","volume":"35","author":"J. Brand\u00e3o","year":"2008","unstructured":"Brand\u00e3o, J., Eglese, R.: A Deterministic Tabu Search Algorithm for the Capacitated Arc Routing Problem. Computers & Operations Research\u00a035, 1112\u20131126 (2008)","journal-title":"Computers & Operations Research"},{"issue":"2","key":"27_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0167-6377(84)90049-X","volume":"3","author":"L. Chapleau","year":"1984","unstructured":"Chapleau, L., Ferland, J.A., Lapalme, G., Rousseau, J.M.: A Parallel Insert Method for the Capacitated Arc Routing Problem. Operations Research Letters\u00a03(2), 95\u201399 (1984)","journal-title":"Operations Research Letters"},{"key":"27_CR9","doi-asserted-by":"publisher","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 Relaxations. Mathematical Programming\u00a020, 255\u2013282 (1981)","journal-title":"Mathematical Programming"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Doerner, K., Hartl, R., Maniezzo, V., Reimann, M.: An Ant System Metaheuristic for the Capacitated Arc Routing Problem. In: Proceedings of the 5th Metaheuristics International Conference, Tokyo, Japan (2003)","DOI":"10.1007\/978-3-540-28646-2_45"},{"issue":"5","key":"27_CR11","doi-asserted-by":"publisher","first-page":"977","DOI":"10.1287\/opre.42.5.977","volume":"42","author":"M. Dror","year":"1994","unstructured":"Dror, M.: Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW. Operations Research\u00a042(5), 977\u2013978 (1994)","journal-title":"Operations Research"},{"issue":"3","key":"27_CR12","doi-asserted-by":"publisher","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. Discrete Applied Mathematics\u00a048(3), 231\u2013244 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Fu, H., Mei, Y., Tang, K., Zhu, Y.: Memetic algorithm with heuristic candidate list strategy for capacitated arc routing problem. In: IEEE Congress on Evolutionary Computation, pp. 1\u20138 (2010)","DOI":"10.1109\/CEC.2010.5586042"},{"key":"27_CR14","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"1","key":"27_CR15","doi-asserted-by":"publisher","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. Computers and Operations Research\u00a010(1), 47\u201359 (1983)","journal-title":"Computers and Operations Research"},{"key":"27_CR16","doi-asserted-by":"publisher","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\u00a011, 305\u2013315 (1981)","journal-title":"Networks"},{"key":"27_CR17","unstructured":"G\u00f3mez-Cabrero, D., Belenguer, J.M., Benavent, E.: Cutting Plane and Column Generation for the Capacitated Arc Routing Problem. In: ORP3, Valencia (2005)"},{"issue":"1","key":"27_CR18","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1287\/opre.48.1.129.12455","volume":"48","author":"A. Hertz","year":"2000","unstructured":"Hertz, A., Laporte, G., Mittaz, M.: A Tabu Search Heuristic for the Capacitated Arc Routing Problem. Operations Research\u00a048(1), 129\u2013135 (2000)","journal-title":"Operations Research"},{"issue":"2","key":"27_CR19","doi-asserted-by":"publisher","first-page":"119","DOI":"10.15807\/jorsj.35.119","volume":"35","author":"R. Hirabayashi","year":"1992","unstructured":"Hirabayashi, R., Nishida, N., Saruwatari, Y.: Node Dublication Lower Bounds for the Capacitated Arc Routing Problems. Journal of the Operations Research Society of Japan\u00a035(2), 119\u2013133 (1992)","journal-title":"Journal of the Operations Research Society of Japan"},{"key":"27_CR20","first-page":"155","volume":"9","author":"R. Hirabayashi","year":"1992","unstructured":"Hirabayashi, R., Nishida, N., Saruwatari, Y.: Tour Construction Algorithm for the Capacitated Arc Routing Problem. AsiaPacific Journal of Operational Research\u00a09, 155\u2013175 (1992)","journal-title":"AsiaPacific Journal of Operational Research"},{"issue":"3","key":"27_CR21","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1287\/ijoc.1040.0117","volume":"18","author":"S. Irnich","year":"2006","unstructured":"Irnich, S., Villeneuve, D.: The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k \u2265 3. INFORMS Journal on Computing\u00a018(3), 391\u2013406 (2006)","journal-title":"INFORMS Journal on Computing"},{"key":"27_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/3-540-45365-2_49","volume-title":"Applications of Evolutionary Computing","author":"P. Lacomme","year":"2001","unstructured":"Lacomme, P., Prins, C., Ramdane-Ch\u00e9rif, W.: A genetic algorithm for the capacitated arc routing problem and its extensions. In: Boers, E.J.W., Gottlieb, J., Lanzi, P.L., Smith, R.E., Cagnoni, S., Hart, E., Raidl, G.R., Tijink, H. (eds.) EvoIASP 2001, EvoWorkshops 2001, EvoFlight 2001, EvoSTIM 2001, EvoCOP 2001, and EvoLearn 2001. LNCS, vol.\u00a02037, pp. 473\u2013483. Springer, Heidelberg (2001)"},{"key":"27_CR23","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1023\/B:ANOR.0000039517.35989.6d","volume":"131","author":"P. Lacomme","year":"2004","unstructured":"Lacomme, P., Prins, C., Ramdane-Ch\u00e9rif, W.: Competitive memetic algorithms for arc routing problems. Annals of Operations Research\u00a0131, 159\u2013185 (2004)","journal-title":"Annals of Operations Research"},{"key":"27_CR24","unstructured":"Lagan\u00e1, D., Ghiani, G., Musmanno, R., Laporte, G.: A Branch-and-Cut Algorithm for the Undirected Capacitated Arc Routing Problem. The Journal of the Operations Research Society of America, 1\u201321 (2007)"},{"key":"27_CR25","doi-asserted-by":"publisher","first-page":"2320","DOI":"10.1016\/j.cor.2008.09.008","volume":"36","author":"A. Letchford","year":"2009","unstructured":"Letchford, A., Oukil, A.: Exploiting Sparsity in Pricing Routines for the Capacitated Arc Routing Problem. Computers & Operations Research\u00a036, 2320\u20132327 (2009)","journal-title":"Computers & Operations Research"},{"key":"27_CR26","unstructured":"Letchford, A.N.: Polyhedral Results for some Constrained Arc-Routing Problems, Ph.D. dissertation, Lancaster University (1996)"},{"key":"27_CR27","unstructured":"Li, L.Y.O.: Vehicle Routeing for Winter Gritting, Ph.D. dissertation, Department of Management Science, Lancaster University (1992)"},{"key":"27_CR28","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1057\/jors.1996.56","volume":"47","author":"L.Y.O. Li","year":"1996","unstructured":"Li, L.Y.O., Eglese, R.W.: An Interactive Algorithm for Vehicle Routeing for Winter-Gritting. Journal of the Operational Research Society\u00a047, 217\u2013228 (1996)","journal-title":"Journal of the Operational Research Society"},{"key":"27_CR29","doi-asserted-by":"publisher","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. Computers & Operations Research\u00a033, 1823\u20131827 (2006)","journal-title":"Computers & Operations Research"},{"key":"27_CR30","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"M.W. Padberg","year":"1982","unstructured":"Padberg, M.W., Rao, M.R.: Odd minimum cut-sets and b-matchings. Mathematics of Operations Research\u00a07, 67\u201380 (1982)","journal-title":"Mathematics of Operations Research"},{"key":"27_CR31","doi-asserted-by":"publisher","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\u00a018, 181\u2013191 (1988)","journal-title":"Networks"},{"issue":"6","key":"27_CR32","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1016\/0305-0548(89)90044-0","volume":"16","author":"W.L. Pearn","year":"1989","unstructured":"Pearn, W.L.: Approximate Solutions for the Capacitated Arc Routing Problem. Computers & Operations Research\u00a016(6), 589\u2013600 (1989)","journal-title":"Computers & Operations Research"},{"issue":"2","key":"27_CR33","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0305-0548(91)90089-A","volume":"18","author":"W.L. Pearn","year":"1991","unstructured":"Pearn, W.L.: Augment-Insert Algorithms for the Capacitated Arc Routing Problem. Computers & Operations Research\u00a018(2), 189\u2013198 (1991)","journal-title":"Computers & Operations Research"},{"key":"27_CR34","doi-asserted-by":"publisher","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.: An Improved Ant Colony Optimization Based Algorithm for the Capacitated Arc Routing Problem. Transportation Research Part B\u00a044, 246\u2013266 (2010)","journal-title":"Transportation Research Part B"},{"key":"27_CR35","unstructured":"W\u00f8hlk, S.: Contributions to Arc Routing, Ph.D. dissertation, Faculty of Social Sciences, University of Southern Denmark (2005)"},{"issue":"12","key":"27_CR36","doi-asserted-by":"publisher","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. Computers & Operations Research\u00a033(12), 3458\u20133472 (2006)","journal-title":"Computers & Operations Research"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20662-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T01:11:16Z","timestamp":1558573876000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20662-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642206610","9783642206627"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20662-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}