Desarrollo de un algoritmo de optimización basado en búsqueda local guiada para el problema de minimización en la huella de carbono en el ruteo de vehículos heterogéneos

Abstract

El objetivo de este trabajo es la construcción de un algoritmo basado en búsqueda local guiada para la minimización de las emisiones equivalentes de CO2 a través de la minimización del consumo de combustible para una flota de vehículos heterogénea. Para lograr este objetivo se construye un conjunto de métricas o características que permitan distinguir entre soluciones “óptimas” de aquellas no optimas. Considerando diferentes valores de parámetros, se crean diversas instancias para las soluciones “optimas” y aquellas que no lo son. Luego, por medio de un árbol de decisiones se obtiene la caracterización de las métricas que reflejan la diferencia entre las soluciones. Posteriormente se analiza el impacto de un grupo definido de operadores de búsqueda local en la mejora de las métricas de las soluciones, de acuerdo con la caracterización hecha por el árbol de decisiones y se propone una versión de algoritmo búsqueda local guiado por la ordenada secuencia de los operadores que mejores resultados obtuvieron en la caracterización de esas métricas. Por último, se evalúa las soluciones entregadas por estos algoritmos respecto a otras soluciones. (Texto tomado de la fuente)

The objective of this work is the construction of an algorithm based on guided local search for the minimization of CO2 equivalent emissions through the minimization of fuel consumption for a heterogeneous fleet of vehicles. To achieve this goal, a set of metrics or features is constructed to distinguish between "optimal" solutions and non-optimal ones. Considering different parameter values, several instances are created for "optimal" and non-optimal solutions. Then, by means of a decision tree, the characterization of the metrics that reflect the difference between the solutions is obtained. Subsequently, the impact of a defined group of local search operators on the improvement of the metrics of the solutions is analyzed, according to the characterization made by the decision tree, and a version of the local search algorithm is proposed, guided by the ordered sequence of the operators that obtained the best results in the characterization of those metrics. Finally, the solutions provided by these algorithms are evaluated with respect to other solutions.