A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products

Abstract

This paper considers a practical variant of the Vehicle Routing Problem (VRP) known as the Heterogeneous Vehicle Routing Problem with Time Windows and Multiple Products (HVRPTWMP). As the problem is NP-hard, the resolution approach proposed here is a sequential Ant Colony System (ACS)—Tabu Search algorithm. The approach introduces a two pheromone trail strategy to accelerate agents’ (ants) learning process. Its convergence to good solutions is given in terms of fleet size and travel time while completing tours and service to all customers. The proposed procedure uses regency and frequency memories form Tabu Search to further improve the quality of solutions. Experiments are carried out using instances from literature and show the effectiveness of this procedure.

Este documento considera una variante práctica del problema de enrutamiento del vehículo (VRP) conocido como el problema de enrutamiento heterogéneo del vehículo con ventanas de tiempo y múltiples productos (HVRPTWMP). Como el problema es NP-hard, el enfoque de resolución propuesto aquí es un algoritmo de búsqueda secuencial de sistema de colonias de hormigas (ACS). El enfoque introduce una estrategia de rastro de dos feromonas para acelerar el proceso de aprendizaje de los agentes (hormigas). Su convergencia con buenas soluciones se da en términos del tamaño de la flota y el tiempo de viaje al completar los recorridos y el servicio a todos los clientes. El procedimiento propuesto utiliza memorias de frecuencia y regencia de Tabu Search para mejorar aún más la calidad de las soluciones. Los experimentos se llevan a cabo utilizando ejemplos de la literatura y muestran la efectividad de este procedimiento.