Una aplicación de la metaheurística Búsqueda Dispersa al problema de ruteo de vehículos con restricciones de capacidad y tiempo máximo de rutas

Maquera-Sosa Nélida Gladys (1), Galvão D. Roberto (1)

e-mails: gladys@pep.ufrj.br, galvao@pep.ufrj.br

(1) Programa de Engenharia de Produção
COPPE - Universidade Federal de Rio de Janeiro, RJ

Resumen

En este artículo presentamos una aplicación de la metaheurística Búsqueda Dispersa (BD) para solucionar el Problema de Ruteo de Vehículos con Restricciones de Capacidad y Tiempo Máximo de Rutas (PRV). En este problema los vehículos inician sus rutas a partir de un depósito central, con restricciones de capacidad y tiempo máximo de rutas, los clientes están asociados a tiempos de servicio y sus demandas tienen que ser atendidas exactamente por un vehículo.

Presentamos una heurística para encontrar las soluciones iniciales, una heurística de mejoría que realiza inserción e intercambios de clientes entre rutas y una aplicación de BD al problema. Son mostrados resultados computacionales cuando se aplica la BD a problemas encontrados en la literatura del PRV. Experimentos computacionales demuestran que la BD es robusta y competitiva en términos de tiempo computacional y calidad de las soluciones obtenidas para el PRV.

PDF de este artículo

PDF de JPC2006 (incluye todos los artículos)