Estudio del problema de ruteo de vehículos de dos escalones

Abstract

Avances recientes en la investigación de problemas de ruteo, han permitido dar con extensiones del clásico Problema de Ruteo de Vehículos (VRP), como lo es el Problema de Ruteo de Vehículos de Dos Escalones (2E-CVRP), en el cual se extiende la búsqueda de rutas que minimicen el costo asociado al transporte de los vehículos, para dos escalones. El primero de ellos que conecta la carga desde un depósito central hasta su consolidación en depósitos intermedios denominados satélites, y el segundo que enlaza la carga de los satélites con el cliente final, para satisfacer de esta forma su demanda. El interés por estudiar esta clase de problemas radica en el impacto positivo de un diseño adecuado de las rutas en los sistemas de distribución de las cadenas de suministro, el cual afecta la calidad de vida de las personas al incidir en aspectos como la congestión y contaminación, entre otros. Para la solución del 2E-CVRP se optó por implementar un híbrido metaheurístico, la primera técnica denominada GRASP se enfoca en la formación de una solución inicial del problema al hacer uso de un procedimiento de división; para dar lugar al segundo método designado como recocido simulado, en el que por medio de los operadores de construcción de vecindades 2-opt, Or-opt y Exchange, se intensifica la inquisición de mejora de la solución inicial. La forma en la que trabaja el método híbrido permitió proponer una extensión la cual encuentra soluciones favorables respecto del método inicial, al ser probada sobre las instancias encontradas en la literatura para el 2E-CVRP. 1