Un enfoque matheurístico para la resoluci on del problema de los caminos disjuntos

Abstract

The Edge-disjoint Paths Problem has the objective of maximizing the number of terminal pairs connected in a network by means of paths with disjoint arcs. This is a classic problem NP-complete with wide applications in diverse areas, such as the telecommunications networks or the design of integrated circuits, among others. In order to solve optimization problems, we can nd exact and metaheuristic resolution methods, both of them with di erent strengths and associated weaknesses. To take advantage of the use of these techniques, matheuristics were developed, which aim to encompass the merits of both methods by means of a hybrid resolution procedure. In this thesis, it is proposed a two-phase matheuristic which solves the aforementioned problem: in the rst step, an integer linear programming model is developed; in the second one, it is executed a population metaheuristic, which aims to improve the solution reached by the rst step. This two-step hybrid algorithm improves the results calculated by previous resolution methods found in the state of the art. On the one hand, the original procedure proposed in this document connects a greater number of pairs; and on the other hand, it consumes a smaller amount of computing time than the rest of the methods found in the literature.