Optimización de viajes compartidos en taxis utilizando algoritmos evolutivos.

Abstract

Este proyecto estudia el problema de planificación de viajes compartidos en taxis para el caso de pasajeros viajando desde un mismo origen a múltiples destinos. Se estudian dos variantes del problema: una variante monoobjetivo donde se busca minimizar el costo total de un grupo de pasajeros y una variante multiobjetivo del problema, donde además de minimizar el costo, se plantea minimizar simultáneamente la demora percibida por cada usuario. Se implementan cuatro algoritmos evolutivos diferentes: dos para cada una de las variantes del problema. Los algoritmos evolutivos implementados son evaluados utilizando un conjunto de instancias realistas del problema, generadas a partir de datos obtenidos de trazas de GPS instaladas en taxis de la ciudad de Beijing, China. Además, se generan y utilizan instancias de prueba específicas para la ciudad de Montevideo, Uruguay. Los resultados experimentales muestran que para la variante monoobjetivo, los algoritmos evolutivos implementados alcanzan mejoras de hasta un 41.0% en costo, respecto a una estrategia ávida que resuelve el mismo problema. Para la variante multiobjetivo del problema, los resultados experimentales muestran que los algoritmos evolutivos implementados logran mejorar hasta un 105.2% la demora alcanzada por un algoritmo ávido que busca optimizar el costo y hasta en un 75.1% el costo alcanzado por un algoritmo ávido que busca minimizar la demora. Finalmente se presenta el planificador de viajes compartidos en línea, un componente de software que incluye una aplicación web y una aplicación móvil, que permite a los usuarios resolver instancias realistas del problema de viajes compartidos en taxis de forma eficiente y amigable.

This project studies the taxi sharing optimization problem, where a group of passengers are travelling from the same origin to multiple destinations. Two different variants of the problem are studied: a single objective variant with the goal of minimizing the total cost spent by the group of passengers and a multiobjective variant, which proposes the simultaneous minimization of the total cost spent by the group of passengers and the delay experienced by each passenger. Four different evolutionary algorithms are implemented: two for each one of the problem variants. The evolutionary algorithms implemented are evaluated using a set of real problem instances, generated using GPS data from taxis in the city of Beijing, China. Furthermore, a set of instances for the city of Montevideo, Uruguay, is generated and used in the experimental evaluation. The experimental results show that the evolutionary algorithms developed for the single objective variant of the problem are able to improve up to 41.0% upon the cost computed using a greedy algorithm. Regarding the multiobjective variant of the problem, the experimental results show that the evolutionary algorithms are able to compute solutions that improve up to 105.2% upon the delay computed by a greedy algorithm that optimizes the cost, and improve up to 75.1% upon the cost computed by a greedy algorithm that minimizes the delay. Finally, the online taxipooling scheduler is introduced, which is a software component including a web application and a mobile application, which allows end{users to solve real instances of the taxi sharing problem in an efficient and friendly manner.