Resolución del Multi Depot Cumulative Capacitated Vehicle Routing Problem mediante computación evolutiva.

Abstract

El Multi Depot Cumulative Capacitated Vehicle Routing Problem es un problema de optimización de rutas de vehículos de reciente formulación. En él se busca minimizar el tiempo de llegada de una flota de vehículos a los clientes establecidos, ajustándose a la capacidad de los vehículos. Este problema puede resultar muy útil aplicado a situaciones de catástrofes naturales, donde el tiempo de llegada para socorrer a las posibles víctimas es crucial. La computación evolutiva nos proporciona mecanismos para resolver este tipo de problemas de optimización, pudiendo así, aportar nuevos resultados a los estudios previos. Es por ello que se ha optado por implementar un algoritmo memético para resolver el problema, realizando el estudio correspondiente sobre los resultados, así como la creación de una aplicación web para mostrar su funcionamiento. Para implementarlo, se ha extendido la librería GeneticsJS para adaptarla a las necesidades del problema.

The Multi Depot cumulative Capacitated Vehicle routing Problem is an optimization problem for vehicle routes which was recently formulated. Its objective is to minimize the arrival time of a fleet of vehicles to a group of clients, taking into account the capacity of the vehicles. This problem can be very useful when applied to natural disaster situations, where the arrival time to the possible victims is crucial. Evolutionary Computation gives us the tools to solve this type of optimization problem, being able to bring new results to the previous studies of this problem. It is for this reason that we decided to implement a memetic algorithm to solve the problem, performing the corresponding study of the results, and creating a web application to show its functioning. In order to implement it, the library GeneticsJS was extended to adapt it to the needs of the problem.