Sistema inteligente para la optimización de rutas de vehículos de transporte basado en sistema de información geográfica y metaheurísticas

El presente Trabajo Fin de Máster tiene como objetivo el desarrollo de un sistema inteligente que determine el conjunto de rutas factibles de una flota de vehículos para el transporte de personal de una entidad u organización. Debe ofrecer una respuesta integrada que tenga en cuenta la ubicación exacta de los pasajeros, determine las paradas requeridas para su recogida y genere las rutas que deben seguir los vehículos, con visualización en mapas interactivos, mediante un sistema de información geográfica (SIG) y el uso de metaheurísticas. El desarrollo del trabajo se dividió en tres Fases: Fase I: Generación de paradas. Tiene como objetivo la determinación de la ubicación exacta de las paradas requeridas para la recogida de los pasajeros. Esta fase recibe como datos de entrada la ubicación de residencia de los pasajeros (dirección o coordenadas geográficas), la ubicación de la entidad u organización destino (dirección o coordenadas geográficas) y la distancia máxima permitida de un pasajero a su parada. Se ha utilizado el análisis de conglomerados jerárquicos con la información real de las distancias entre los pasajeros si se desplazasen caminando y un algoritmo de ajuste que garantiza que el número de individuos asignados a cada parada no supere la capacidad de los vehículos. Fase II: Enrutamiento de vehículos. Tiene como objetivo la optimización de las rutas que seguirán los vehículos para la recogida de los pasajeros en las distintas paradas. Para esto, se ha formulado el problema de enrutamiento de vehículos con capacidad fija de pasajeros y demanda variable de cada uno de los nodos a visitar. Del mismo modo que en la Fase I, con ayuda del SIG se obtiene información real sobre las distancias mínimas entre las distintas paradas y una estimación del tiempo promedio mínimo de desplazamiento, si éste se realizase en coche. Asimismo, se tiene como datos de entrada la ocupación mínima aceptable de los vehículos, sus características básicas (como mínimo: matrícula o código de identificación, capacidad máxima y coste promedio por unidad de distancia), la distancia y duración máxima sugerida por ruta y el tiempo promedio de carga de un pasajero en una parada. Para la obtención de las rutas óptimas, se ha utilizado jMetalPy, un framework desarrollado en Python para la optimización multiobjetivo con metaheurísticas. Del framework se adaptaron al problema de enrutamiento de vehículos las metaheurísticas algoritmos genéticos, recocido simulado y estrategias evolutivas. Fase III: Visualización de resultados. Tiene como objetivo presentar el resumen de los resultados obtenidos en la generación de paradas y de las rutas determinadas por el sistema inteligente en mapas interactivos, así como el desarrollo de su interfaz, pensada en usuarios finales, con o sin experiencia en el uso de metaheurísticas o en SIG. El sistema inteligente implementado es genérico, por lo cual debe tener un comportamiento eficiente para cualquier tamaño de datos de entrada. De esta manera, la selección de los parámetros de la metaheurísticas se sustenta en diversos estudios o recomendaciones realizados en la literatura y, mediante la puesta a prueba para un conjunto de datos de referencia de difícil resolución, se valida y analiza el comportamiento de los algoritmos de optimización construidos.---ABSTRACT---The objective of this Master's Final Project is to develop an intelligent system that determines the set of feasible routes for a fleet of vehicles for the transport of personnel of an entity or organization. It must offer an integrated response that takes into account the exact location of the passengers, determines the stops required for their pick-up and generates the routes to be followed by the vehicles, with visualization on interactive maps, through a geographic information system (GIS) and the use of metaheuristics. The development of the work was divided into three phases: Phase I: Generation of stops. Its objective is to determine the exact location of the stops required for the pick-up of passengers. This phase receives as input data the location of the passenger's residence (address or geographic coordinates), the location of the destination entity or organization (address or geographic coordinates) and the maximum distance allowed for a passenger to their stop. Hierarchical clustering analysis has been used with the real information of the distances between passengers if they are walking and an adjustment algorithm that guarantees that the number of people assigned to each stop does not exceed the capacity of the vehicles. Phase II: Vehicle routing. Its objective is to optimize the routes that the vehicles will take to pick up the passengers at the different stops. To this end, the vehicle routing problem has been formulated with a fixed passenger capacity and variable demand for each of the stops. As in Phase I, with the help of the GIS, the intelligent system obtains real information of the minimum distances between the different stops and an estimation of the average travel time, if this were done by car. Likewise, the minimum acceptable occupation and basic characteristics of the vehicles (at least: registration or license plate, maximum capacity and average cost per unit of distance), the maximum suggested distance and duration per route and the average loading time of a passenger at a stop are taken as input data. The framework jMetalPy developed in Python for multi-objective optimization with metaheuristics has been used to obtain optimal routes. From this framework, genetic algorithms, simulated annealing and evolutionary strategies were adapted to the vehicle routing problem. Phase III: Visualization of results. It aims to present the summary of the results obtained in the generation of stops and vehicles routing determined by the intelligent system in interactive maps, as well as the development of its interface, thought of final users, with or without experience in the use of metaheuristics or GIS. The implemented intelligent system is generic, so it must have an efficient behavior for any size of input data. In this way, the selection of the metaheuristics parameters is supported by various studies and recommendations from the scientific literature and, through a reference dataset, the behavior of the optimization algorithms built is validated and analyzed