Una Heurística de Clusterización para el Problema del Ruteo de Vehículos Multidepósito

Resumen

El problema VRP (Vehicle Routing Problem) es uno de los problemas de optimización mas importantes y desafiantes en el campo de la Investigación de Operaciones, consiste en la construcción de un conjunto óptimo de rutas para una flota de vehículos que deberán satisfacer la demanda de un conjunto de clientes, el problema está clasificado como un problema combinatorio computacionalmente difícil (NP-Hard). En las aplicaciones prácticas, diferentes versiones del VRP han ido apareciendo tal como el problema MDVRP (Multi Depot Vehicle Routing Problem) (1], cuando un problema NP-Hard no puede ser resuelto de manera exacta se buscan soluciones aproximadas obtenidas mediante heurísticas. En el presente trabajo estudiamos, formulamos y resolvemos (por medio de heurísticas) el problema MDVRP, la solución aproximada se trata desde el punto de vista práctico a través de la formulación e implementación (en el lenguaje de programación JULIA 1.0.5) de las heurísticas de construcción y mejora (siendo ésta la contribución del trabajo de investigación). En cuanto a la heurística de construcción, se presentan dos propuestas de agrupamiento o clusterización basadas en la ubicación geográfica de los clientes y los almacenes, así como de su proximidad entre sí, en cuanto a las heurísticas de mejora, las estrategias del vecino más cercano y de separación fueron usados. Finalmente, se presentan los resultados y comparaciones con respecto a la solución BKS (Best Know Solution) disponible en la literatura.