Técnicas de Múltiple Generación de Soluciones Iniciales en Problemas de PRVC

Abstract

En este trabajo se presenta una metodología para la búsqueda de soluciones iniciales en problemas que incluyen la construcción del conjunto de rutas óptimas, que se describe como un problema de ruteo de vehículos con restricciones de capacidad (PRVC). El PRVC puede ser formulado como un problema de programación lineal entera mixta (MILP) y está catalogado como NP-duro. Se propone obtener un grupo de soluciones factibles mediante técnicas metaheurísticas que son refinadas por algoritmos exactos donde las mismas pueden ser utilizadas por aquellos algoritmos que lo requieran. Por ejemplo: “Búsqueda Tabú”, “Recocido Simulado”, entre otros. Se presenta la metodología y su desempeño para resolución de diferentes problemas test extraídos de la literatura.