Modelos y algoritmos para el problema del viajante: Una aplicación en planificación socio sanitaria

Abstract

[ES] El problema del viajante de comercio y su extensión, el problema de rutas de vehículos, son dos de los problemas de optimización combinatoria de clase NP-duros más estudiados a lo largo del tiempo. Su importancia se debe a que estos problemas cuentan con una gran cantidad de aplicaciones prácticas y el hecho de que sean problemas fáciles de entender pero con una resolución compleja ha motivado su gran investigación. El objetivo de este trabajo es abordar el estudio de ambos problemas. En el primer capítulo se realizará una revisión bibliográfica de conceptos importantes sobre la teoría de grafos. A continuación, en el segundo capítulo se estudia el TSP así como sus múltiples aplicaciones y métodos de resolución, tanto exactos como heurísticos. Por otro lado, en el tercer capítulo se estudia el VRP de manera similar. En el capítulo final, se presenta una aplicación práctica de todo lo expuesto anteriormente. Nos centramos en el estudio de un problema que presenta un centro de día de la ciudad de Lugo y que se puede modelar siguiendo el esquema de una variante del TSP. Para su resolución se hace uso del modelador AMPL y del solucionador Gurobi a través del servidor de optimización NEOS.[EN] The travelling salesman problem (TSP) and its extent, the vehicle routing problem (VRP) are two of the most studied problems in the combinatorial optimization of NP-hard class throughout time. Its importance is due to their wide range of practical applications and the fact that they are easy to understand. However, their complex resolution has motivated research in this field. The aim of this paper is analysing the study of both problems. In the first chapter, important graph theory concepts will be reviewed. In the second chapter, the TSP will be studied alongside with its multiple applications as well as exact and heuristic resolution methods. In the third chapter, the VRP will be studied likewise. In the final chapter, a practical application of the previous will be represented. The focus will be the study of a problem in a day care centre in the city of Lugo. This problem will be solved following a scheme of a TSP variant. For its resolution we use the model AMPL and its solver Gurobi through the NEOS optimization server.