Resolution of the routing problem of vehicles with simultaneous loading and unloading for a beverage distribution company

Abstract

This article presents an alternative procedure to solve the Homogeneous Fleet Capacity Constrained Vehicle Routing Problem (CVRP). A metaheuristic algorithm is proposed that consists of the combination of two phases: route design and fleet planning. The first phase is composed of heuristic and metaheuristic procedures where an initial solution is built that is improved by tabu search, obtaining non-dominated solutions in polynomial computation time. For the second phase, corresponding to the planning (scheduling) of the fleet, it is proposed to address the problem starting from an analogy with the problem of scheduling identical parallel machines. The objective of this procedure is to minimize the fixed cost caused by the use of installed capacity. This alternative was applied to a randomly generated instance and a real instance, yielding significant results when compared with the evaluated heuristics.

Este artículo presenta un procedimiento alternativo para resolver el problema de enrutamiento de vehículos con limitaciones de capacidad y flota homogénea (CVRP). Se propone un algoritmo metaheurístico que consta de la combinación de dos fases: diseño de rutas y planificación de la flota. La primera fase está compuesta de procedimientos heurísticos y metaheurísticos donde se construye una solución inicial que es mejorada mediante búsqueda tabú obteniendo soluciones no dominadas en tiempo de cálculo polinomial. Para la segunda fase, correspondiente a la planificación (scheduling) de la flota, se propone abordar el problema partiendo de una analogía con el problema de programación de máquinas paralelas idénticas. Este procedimiento tiene como función objetivo minimizar el costo fijo causado por la utilización de la capacidad instalada. Esta alternativa se aplicó sobre una instancia generada aleatoriamente y una instancia real arrojando resultados significativos al compararse con las heurísticas evaluadas.