El Problema Dinámico de Rutas de Vehículos

Abstract

En este trabajo se estudiará el Problema de Rutas de Vehículos asociado a un problema de optimización. Comenzaremos dando una definición general y presentando los primeros y más sencillos problemas planteados, así como algunas variantes que se les pueden aplicar. En el segundo capítulo se presenta el Problema Dinámico de Rutas de Vehículos, en el que algunos datos del problema sólo están disponibles una vez los vehículos han comenzado la ruta. Se definen parámetros, propuestos en la literatura, que miden el nivel de dinamismo de un problema y se hace una clasificación del Problema de Rutas de Vehículos en función de la evolución y calidad de la información disponible. Además, se exponen ejemplos de problemas dinámicos de rutas de vehículos presentes en la vida cotidiana. En el tercer capítulo se plantean distintos métodos de resolución del Problema Dinámico de Rutas de Vehículos ofrecidos en la literatura, distinguiendo entre los métodos exactos, en los que se obtiene la solución óptima con mayor coste computacional, y los heurísticos y metaheurísticos, con menor tiempo computacional pero que no necesariamente alcanzan la mejor solución. Finalmente, en el último capítulo se plantea el El Problema de Reequilibrio del Sistema de Bicicleta Pública, en el que se busca que las estaciones de bicicletas públicas de transporte urbano estén debidamente surtidas para ofrecer un buen servicio a los usuarios. Se desarrollará un algoritmo de programación lineal para resolver este problema. Nos centraremos en el Sistema de Bicicleta Pública de la ciudad de Madrid, BiciMAD, que analizaremos y al que aplicaremos el método propuesto.

This work will study the Vehicle Routing Problem associated to an optimization problem. First, we will provide a general definition and introduce the first and simplest problems that have been set out. Futhermore, some variations of these problems will be presented. In the second chapter we introduce the Dynamic Vehicle Routing Problem, in which some data is revealed once the vehicle has already started the route. Parameters that measure the level of dynamism of a problem proposed in the literature will be shown, as well as a classification of the vehicle routing problems according to the evolution and reliability of the avaliable information. In addition, we will give examples of dynamic vehicle routing problems which appear in our day to day life. In the third chapter we will propose different resolution methods of the Dynamic Vehicle Routing Problem suggested in the literature. We will point out the difference between exact methods, that provide optimal solution with a higher computational cost, and heuristic and meta-heuristic problems, with a less computational time but also with a lack of guarantee of finding the best solution. Finally, in the last chapter we will lay out the Bike Sharing Rebalancing Problem, whose objective is to provide the bike stations of an Urban Bike Sharing System with a correct amount of bicycles in order to provide a good service to the users of the system. We will develop a linear programming algorithm so as to solve this problem. We will focus our attention on the Bike Sharing System of the city of Madrid, BiciMAD, that we will analyse and apply the proposed method.