Metodología de algoritmos meméticos para el problema de ruteo de vehículos con entregas parciales y tiempos de viaje dependientes con ventanas de tiempo

Abstract

El problema de ruteo de vehículos VRP es uno de los problemas más estudiados en investigación de operaciones, dada su relevancia en los campos del transporte y la logística. En los últimos años ha aumentado el interés en minimizar la contaminación por la emisión de gases efecto invernadero a causa del consumo de combustibles fósiles. El sector transporte representa una parte importante en esas emisiones. En el transporte, situaciones como los embotellamientos en las horas pico, por ejemplo, conducen a una red vial dinámica en la que varían los tiempos de viaje y consecuentemente el consumo de combustible. Por lo anterior el problema de enrutamiento de vehículos con tiempos dependientes TDVRP es una representación más cercana la vida real que los modelos tradicionales de enrutamientos de vehículos, VRP. Por otro lado, el problema de enrutamiento de vehículos con partición de entregas, SDVRP permite asignar múltiples rutas a un mismo cliente, propiciando ahorros en las mismas. El objetivo de esta tesis es desarrollar un método para el uso de los recursos de transporte, con el fin de atender a los clientes de manera eficiente respecto al costo total de la distancia recorrida y al tiempo total de viaje requerido. El problema consiste en programar un recorrido durante un día dividido en intervalos o zonas horarias, con ventanas de tiempo para atender a cada cliente, vehículos homogéneos con capacidad fija Q y un depósito único. Para ello se propone en este trabajo un Algoritmo Memético (MA) capaz de encontrar soluciones que respetan las restricciones del problema, teniendo en cuenta la posibilidad de hacer particiones en las entregas. Mediante el Diseño de Experimentos se evaluó la calidad de las soluciones generadas respecto a un Algoritmo Genético (GA) desarrollado también para el propósito, teniendo como criterio de evaluación el porcentaje de mejores soluciones alcanzado por cada algoritmo. Los experimentos permiten afirmar que el Algoritmo Memético propuesto supera el Algoritmo Genético, resultando más robusto ante cambios en los parámetros de ambos métodos. La solución propuesta representa un modelo más cercano a la realidad de las redes viales y genera rutas tendientes a disminuir la cantidad, recorrido y tiempo de permanencia de los vehículos en la red vial, conllevando a la disminución de las emisiones de gases efecto invernadero.

Abstract: The vehicle routing problem VRP is one of the most studied problems in operations research, given its relevance in the fields of transport and logistics. In recent years, interest in minimizing pollution due to the emission of greenhouse gases, as a result of the consumption of fossil fuels, has increased. The transport sector represents an important part of those emissions. In transport, situations such as traffic jams during peak hours, for example, lead to a dynamic road network in which travel times and consequently fuel consumption vary. Therefore, the time dependent vehicle routing problem, TDVRP, is a closer representation of real life than the traditional vehicle routing models, VRP. On the other hand, the split delivery vehicle routing problem, SDVRP, allows assigning multiple routes to the same client, promoting savings in them. The objective of this thesis is to develop a method for the use of transportation resources, in order to serve customers efficiently with regard to the total cost of the distance traveled and the total traveled time required. The problem consists of scheduling a trip for a day which is divided into intervals or time zones, with time windows to serve each customer, homogeneous vehicles with fixed capacity Q and a single deposit. In order to do so, a Memetic Algorithm (MA) is proposed in this work, capable of finding solutions that respect the constraints of the problem, taking into account the possibility of splitting the deliveries. By using Design of Experiments, the quality of the solutions generated by the Memetic Algorithm was evaluated with respect to a Genetic Algorithm (GA) also developed for the purpose, having as the evaluation criterion the percentage of best solutions reached by each algorithm. The experiments show that the proposed memetic algorithm surpasses the genetic algorithm, being more robust to changes in the parameters of both methods The proposed solution represents a model that is closer to the reality of road networks and generates routes that tend to reduce quantity, travel length and time spent by vehicles on the road network, leading to a reduction in greenhouse gas emissions.