Una aproximación MILP a la optimización del trazado de redes de metro en entornos urbanos

Abstract

El presente Trabajo de Fin de Grado se centra en la formulación y resolución de un problema de diseño ´optimo de redes de metro urbanas, utilizando herramientas de Programación Lineal Entera Mixta (MILP) mediante la librería PuLP del lenguaje de programación Python. En particular, se trabaja sobre un entorno simplificado basado en el tablero del juego “Próxima Estación: Londres”. El propósito del trabajo es construir un modelo matemático que, respetando un conjunto amplio y realista de restricciones, permita diseñar rutas eficientes que equilibren costes de construcción y cobertura del servicio. Para manejar esta naturaleza multiobjetivo, se aplica el enfoque del método de las restricciones y la frontera de Pareto. El modelo busca en todo momento ser escalable y adaptable, permitiendo su aplicación en escenarios diversos mediante una parametrización flexible que facilita su reutilización en distintas instancias del problema, ya sea con configuraciones espaciales alternativas o criterios objetivos distintos.

This Degree Final Dissertation focuses on the formulation and resolution of an optimal subway network design problem in urban settings, using Mixed Integer Linear Programming (MILP) techniques implemented through the PuLP library in Python. The study is developed in a simplified environment based on the board of the game Next Station: London. The goal is to build a mathematical model that, while complying with a wide and realistic set of constraints, enables the design of efficient routes that balance construction costs and service coverage. To handle the multi-objective nature of the problem, the Pareto frontier approach is applied. The model is designed to be scalable and adaptable, allowing it to be applied in diverse scenarios through flexible parameterization. This feature facilitates its reuse in different instances of the problem, whether involving alternative spatial configurations or varying objective criteria.