Aplicación de Algoritmos Genéticos para la optimización de problemas combinatorios

Abstract

[ES] El problema tratado en el presente trabajo consiste en la minimización del tiempo y del consumo energético utilizado por un vehículo eléctrico durante un recorrido. Este problema se encuentra motivado por la reducida autonomía de los vehículos eléctricos y la búsqueda de ahorro por parte de los conductores, que se beneficiarían de un método de conducción eficiente que les permitiese recorrer mayores distancias sin tener que detenerse a recargar el vehículo. Las principales dificultades son dos: Por una parte, la búsqueda de una solución óptima requiere un tiempo de cómputo elevado debido a que el número de soluciones al problema aumenta exponencialmente con la cantidad de diferentes tramos que conforman una carretera; Adicionalmente, los objetivos de minimizar tiempo y consumo resultan conflictivos pues aumentar la velocidad acorta la duración del recorrido a cambio de aumentar el consumo, pero reducirla tiene el efecto contrario. La forma de afrontar estos problemas pasa por la utilización de algoritmos genéticos, dentro de los cuales se encuentra NSGA II: Un algoritmo bioinspirado que trata problemas multiobjetivo realizando la búsqueda inteligente de una solución compromiso. La implementación del NSGA II se realiza tras el desarrollo de un algoritmo genético simple (SGA) ya que constan de elementos similares. El tener un algoritmo simple y uno especializado motiva la realización de comparaciones, sin embargo, los SGA tratan un solo objetivo por lo que es adaptado para tener en cuenta tiempo y consumo. La comparación se lleva a cabo en 20 carreteras diferentes en las cuales NSGA II consigue mejores valores de tiempo y consumo que SGA permitiendo concluir que su uso es recomendable cuando se busca un mayor beneficio.

[EN] The problem addressed in this paper is to minimize the time and energy consumption used by an electric vehicle during a journey. This problem is caused by the reduced autonomy of electric vehicles and the search for savings by drivers, who would benefit from an efficient driving method that would allow them to travel longer distances without having to stop to recharge the vehicle. The main difficulties are two: On one hand, the search for an optimal solution requires a high computational time because the number of solutions to the problem increases exponentially with the number of distinct sections that make up a road; On the other hand, minimizing time and consumption is difficult since increasing the speed shortens the duration of the journey in exchange for increasing consumption, but reducing it has the opposite effect. The way to face these problems is using genetic algorithms, including NSGA II: A bio-inspired algorithm that addresses multi-objective problems by intelligently searching for a compromise solution. The implementation of NSGA II is done after the development of a simple genetic algorithm (SGA) as they have similar elements. Having a simple and specialized algorithm motivates comparisons, however, SGA treats only one objective, so it must be adapted to consider time and consumption. The comparison is carried out on 20 different roads on which NSGA II achieves better time and consumption values than SGA, allowing us to conclude that its use is recommended when looking for greater benefit.