L. Berbotto, S. García, F. J. Nogales

El problema de Rutas de Vehículos con Entregas Divididas es una variante del problema clásico de Rutas de Vehículos donde se permite que un mismo cliente pueda ser visitado por más de un vehículo. Este trabajo presenta un algoritmo heurístico llamado Randomized Granular Tabu Search que permite la búsqueda local en vecindarios definidos sobre los arcos del grafo que presentan mayor probabilidad de pertenecer a una solución óptima. El algoritmo utiliza una selección aleatoria para elegir el movimiento a introducir en la solución, asignando a los candidatos probabilidades jerárquicas de acuerdo a la mejora en la solución que representa cada uno. Además, se permite la búsqueda local en vecindarios con soluciones infactibles en términos de capacidad del vehículo, infactibilidad que se corrige en una etapa posterior. Los resultados computacionales muestran que el heurístico logra mejorar varias de las mejores soluciones conocidas hasta el momento con tiempos computacionales competitivos.

Palabras clave: problema de rutas de vehículos, entregas divididas, nodos de parada, tabu search, vecindario granular

VB4 Problemas de rutas
20 de abril de 2012  10:30
Sala París

J. A. Moreno Pérez, J. Brito Santana, F. J. Martínez García, A. Expósito Márquez

M. D. Batista Galván, J. Riera Ledesma, J. J. Salazar González