Improved bounds for large scale capacitated arc routing problem.

*(English)*Zbl 1348.90476Summary: The Capacitated Arc Routing Problem (CARP) stands among the hardest combinatorial problems to solve or to find high quality solutions. This becomes even more true when dealing with large instances. This paper investigates methods to improve on lower and upper bounds of instances on graphs with over 200 vertices and 300 edges, dimensions that, today, can be considered of large scale. On the lower bound side, we propose to explore the speed of a dual ascent heuristic to generate capacity cuts. These cuts are next improved with a new exact separation enchained to the linear program resolution that follows the dual heuristic. On the upper bound, we implement a modified Iterated Local Search procedure to Capacitated Vehicle Routing Problem (CVRP) instances obtained by applying a transformation from the CARP original instances. Computational experiments were carried out on the set of large instances generated by Brandão and Eglese and also on the regular size sets. The experiments on the latter allow for evaluating the quality of the proposed solution approaches, while those on the former present improved lower and upper bounds for all instances of the corresponding set.

##### MSC:

90C10 | Integer programming |

05C90 | Applications of graph theory |

90C35 | Programming involving graphs or networks |

PDF
BibTeX
XML
Cite

\textit{R. Martinelli} et al., Comput. Oper. Res. 40, No. 8, 2145--2160 (2013; Zbl 1348.90476)

Full Text:
DOI

##### References:

[1] | Wøhlk S. Contributions to arc routing. PhD thesis. Faculty of Social Sciences, University of Southern Denmark; 2005. |

[2] | Golden, B. L.; Wong, R. T., Capacitated arc routing problems, Networks, 11, 305-315, (1981) · Zbl 0459.90083 |

[3] | Belenguer, J. M.; Benavent, E., A cutting plane algorithm for the capacitated arc routing problem, Computers & Operations Research, 30, 705-728, (2003) · Zbl 1026.90014 |

[4] | Ahr D. Contributions to multiple postmen problems. PhD thesis. Department of Computer Science, Heidelberg University; 2004. · Zbl 1103.90388 |

[5] | Li Lyo. Vehicle routeing for winter gritting. PhD thesis. Department of Management Science, Lancaster University; 1992. |

[6] | Li, L. Y.O.; Eglese, R. W., An interactive algorithm for vehicle routeing for winter-gritting, Journal of the Operational Research Society, 47, 217-228, (1996) |

[7] | Bartolini E, Cordeau JF, Laporte G. Improved lower bounds and exact algorithm for the capacitated arc routing problem. Technical Report CIRRELT-2011-33, Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation; 2011. · Zbl 1262.90100 |

[8] | Bode C, Irnich S. Cut-first branch-and-price-second for the capacitated arc routing problem. Technical Report LM-2011-01, Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University, Mainz, Germany; 2011. · Zbl 1257.90008 |

[9] | Martinelli, R.; Pecin, D.; Poggi, M.; Longo, H., A branch-cut-and-price algorithm for the capacitated arc routing problem, (Pardalos, P.; Rebennack, S., Experimental algorithms. Lecture notes in computer science, vol. 6630, (2011), Springer Berlin/Heidelberg), 315-326 |

[10] | Brandão, J.; Eglese, R., A deterministic tabu search algorithm for the capacitated arc routing problem, Computers & Operations Research, 35, 1112-1126, (2008) · Zbl 1179.90031 |

[11] | Golden, B. L.; DeArmon, J. S.; Baker, E. K., Computational experiments with algorithms for a class of routing problems, Computers & Operations Research, 10, 1, 47-59, (1983) |

[12] | Mei, Y.; Tang, K.; Yao, X., A global repair operator for capacitated arc routing problem, IEEE Transactions on Systems, Man and Cybernetics, 39, 3, 723-734, (2009) |

[13] | Letchford, A.; Oukil, A., Exploiting sparsity in pricing routines for the capacitated arc routing problem, Computers & Operations Research, 36, 2320-2327, (2009) · Zbl 1158.90321 |

[14] | Padberg, M. W.; Rao, M. R., Odd minimum cut-sets and b-matchings, Mathematics of Operations Research, 7, 67-80, (1982) · Zbl 0499.90056 |

[15] | Gomory, R. E.; Hu, T. C., Multi-terminal network flows, Journal of the Society for Industrial and Applied Mathematics, 9, 4, 551-570, (1961) · Zbl 0112.12405 |

[16] | Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM, 19, 248-264, (1972) · Zbl 0318.90024 |

[17] | Fukasawa, R.; Longo, H.; Lysgaard, J.; Poggi de Arag ao, M.; Reis, M.; Uchoa, E., Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Mathematical Programming, 106, 3, 491-511, (2006) · Zbl 1094.90050 |

[18] | Fischetti, M.; Lodi, A., Optimizing over the first chvátal closure, Mathematical Programming, 110, 3-20, (2007) · Zbl 1192.90125 |

[19] | Wong, R., A dual ascent approach for Steiner tree problems on a directed graph, Mathematical Programming, 28, 271-287, (1984) · Zbl 0532.90092 |

[20] | Kruskal, J. B., On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, 7, 1, 48-50, (1956) · Zbl 0070.18404 |

[21] | Lourenço, H. R.; Martin, O. C.; Stützle, T., Handbook of metaheuristics, iterated local search, (2003), Kluwer Academic Publishers, Chap. p. 321-53 |

[22] | Penna PHV, Subramanian A, Ochi LS. An iterated local search heuristic for the heterogenous fleet vehicle routing problem. Journal of Heuristics; 2011; http://dx.doi.org/10.1007/s10732-011-9186-y. In press |

[23] | Pearn, W. L.; Assad, A.; Golden, B. L., Transforming arc routing into node routing problems, Computers & Operations Research, 14, 4, 285-288, (1987) · Zbl 0614.90060 |

[24] | Longo, H.; Poggi de Aragão, M.; Uchoa, E., Solving capacitated arc routing problems using a transformation to the CVRP, Computers & Operations Research, 33, 1823-1827, (2006) · Zbl 1087.90054 |

[25] | Baldacci, R.; Maniezzo, V., Exact methods based on node-routing formulations for undirected arc-routing problems, Networks, 47, 1, 52-60, (2006) · Zbl 1090.90030 |

[26] | Mladenović, N.; Hansen, P., Variable neighborhood search, Computers & Operations Research, 24, 11, 1097-1100, (1997) · Zbl 0889.90119 |

[27] | Subramanian, A.; Drummond, L.; Bentes, C.; Ochi, L.; Farias, R., A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 37, 11, 1899-1911, (2010) · Zbl 1188.90041 |

[28] | 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 operational research society of Japan; 1995. p. 28-9 [In Japanese]. |

[29] | DeArmon JS. A comparison of heuristics for the capacitated Chinese postman problem. Master’s thesis. University of Maryland, College Park, MD; 1981. |

[30] | Benavent, E.; Campos, V.; Corberan, A.; Mota, E., The capacitated arc routing problemlower bounds, Networks, 22, 669-690, (1992) · Zbl 0762.90077 |

[31] | 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, 147, 3, 629-643, (2003) · Zbl 1026.90015 |

[32] | Polacek, M.; Doerner, K.; Hartl, R.; Maniezzo, V., A variable neighborhood search for the capacitated arc routing problem with intermediate facilities, Journal of Heuristics, 14, 405-423, (2008) · Zbl 1211.90314 |

[33] | Tang, K.; Mei, Y.; Yao, X., Memetic algorithm with extended neighborhood search for capacitated arc routing problems, Transactions on Evolutionary Computation, 13, 5, 1151-1166, (2009) |

[34] | Santos, L.; Coutinho-Rodrigues, J.; Current, J., An improved ant colony optimization based algorithm for the capacitated arc routing problem, Transportation Research Part B, 44, 2, 246-266, (2010) |

[35] | Usberti FL, França PM, França ALM. Grasp with evolutionary path-relinking for the capacitated arc routing problem. Computers and Operations Research; 2011 10.1016/j.cor.2011.10.014 |

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.