RT Generic
T1 Modelos y algoritmos para el problema del viajante: Una aplicación en planificación socio sanitaria
A1 Arias Vilaboa, Dafne Lucía
AB [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 estudiadosa lo largo del tiempo. Su importancia se debe a que estos problemas cuentan con una grancantidad de aplicaciones prácticas y el hecho de que sean problemas fáciles de entenderpero 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 primercapítulo se realizará una revisión bibliográfica de conceptos importantes sobre la teoría degrafos. A continuación, en el segundo capítulo se estudia el TSP así como sus múltiplesaplicaciones y métodos de resolución, tanto exactos como heurísticos. Por otro lado, enel tercer capítulo se estudia el VRP de manera similar. En el capítulo final, se presentauna aplicación práctica de todo lo expuesto anteriormente. Nos centramos en el estudio deun problema que presenta un centro de día de la ciudad de Lugo y que se puede modelarsiguiendo el esquema de una variante del TSP. Para su resolución se hace uso del modeladorAMPL y del solucionador Gurobi a través del servidor de optimización NEOS.
AB [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-hardclass throughout time. Its importance is due to their wide range of practical applicationsand the fact that they are easy to understand. However, their complex resolution hasmotivated 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 bestudied alongside with its multiple applications as well as exact and heuristic resolutionmethods. 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 aproblem in a day care centre in the city of Lugo. This problem will be solved following ascheme of a TSP variant. For its resolution we use the model AMPL and its solver Gurobithrough the NEOS optimization server.
YR 2021
FD 2021-07
LK http://hdl.handle.net/10347/28774
UL http://hdl.handle.net/10347/28774
LA spa
NO Traballo Fin de Grao en Matemáticas. Curso 2020-2021
DS Minerva
RD 28 abr 2026