Biography
Enrique Benavent (Ph.D. Mathematics University of Valencia, 1982) is Titular Professor of Statistics and Operations Research at the University of Valencia, where he has taught for thirty-four years. He has conducted numerous research projects related to vehicle routing problems and carried out several contracts with companies to develop optimization algorithms in the same area. He is author or coauthor of a number of research papers that have been published in prestigious journals in the field. His main research interests are vehicle routing problems, with a special emphasis in arc routing, and other combinatorial optimization problems. His research has been mainly addressed to exact algorithms using different approaches.
Abstract
Exact methods for Arc Routing Problems Arc Routing Problems consist of determining the optimal traversal of a subset of arcs or edges of a given graph. The field of arc routing started with the celebrated Königsberg bridges problem in the eighteenth century but its development came mainly from 1950 and it was motivated by the variety and importance of the practical situations in which it appears, such as: garbage collection, road or street maintenance, mail delivery, etc. We will focus in this talk on the development of exact methods devised for these problems. Most of the relevant arc routing problems are NP-hard, and this fact has motivated the development of a lot of efficient heuristic and metaheuristic methods that have been successfully applied to large instances of these problems. Nevertheless, although these methods may produce near optimal solutions, they are not able to give any guarantee on the quality of the provided solutions. On the other hand, exact methods may fail in solving to optimality a given instance in a reasonable amount of computing time, but they can be used to compute tight bounds that give this guarantee. We aim to provide an overview of the main tools and procedures that have been devised to allow the exact resolution of arc routing problems, without considering similar procedures that have been applied to similar variants of the same problem. Thus, we do not try to be exhaustive, but to highlight the core of the methods that can be used to solve these problems. We start with the Chinese Postman Problem, where a least cost route has to be found that traverses all the edges or arcs of an undirected or a directed graph, respectively. These are the only relevant arc routing problems that can be polynomially solved, and the corresponding procedures have often been used to compute tight bounds for harder arc routing problems. The same problem defined on a mixed or on a windy graph is NP-hard and both have been solved by branch-and-bound and branch-and-cut. In the Rural Postman Problem only a subset of arcs/edges has to be traversed. This problem is NP-hard regardless of the type of graph where it is defined. A rich and deep study of the associated polyhedron has been carried out along the last twenty years giving rise to efficient Branch-and-cut methods to solve it. Arc routing problems where several routes have to be constructed seem to be much harder. The reference problem here is the Capacitated Arc Routing Problem, where routes have to satisfy a capacity restriction. A great variety of methods have been proposed for this problem in the last years, including transformations into node routing problems, methods based on computing combinatorial bounds, cutting plane and branch-and-cut methods based on different integer formulations, and column generation and branch-and-price methods. Despite of these efforts there is still much room for the development of efficient methods for this problem. We will also review the methods recently proposed for arc routing problems with min-max objective and for profitable arc routing problems.