El problema de ruteo de vehículos multidepósito abordaje por diferentes heurísticas

Abstract

l problema del ruteo de vehículos VRP (Vehicle Routing Problem) es uno de los pro blemas de optimización mas importantes y desafiantes en el ámbito de la Investiga ción de Operaciones, fue planteado e introducido por Dantzing y Ramser en 1959, el cual consiste en construir 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á cataloga do como un problema combinatorio computacionalmente duro, ha sido intensamente estudiado en los últimos 50 años y continúa el interés dado que por su naturaleza NP −Hard aún no se ha logrado una solución eficiente. La importancia de su estudio se debe al importante beneficio económico que se puede lograr al encontrar la ruta óptima. En la práctica han ido apareciendo diferentes necesidades que obligaron a formular ampliaciones o variantes del problema VRP, como por ejemplo el problema MDVRP (Multi Depot Vehicle Routing Problem). Cuando un problema combinato rio computacionalmente duro como el mencionado no se puede resolver de manera exacta se recurre a las soluciones aproximadas obtenidas por métodos heurísticos. En el presente trabajo de investigación, estudiamos, formulamos y resolvemos (mediante la propuesta de heurísticas) el problema MDVRP, la solución exacta es tra tada desde un punto de vista teórico utilizando la relajación de restricciones (relaja ción lagrangiana) y la optimización subgradiente. En tanto que la solución aproxima da es tratada desde el punto de vista práctico mediante la formulación e implementa ción (en el lenguaje de programación JULIA 1.0.5) de las heurísticas de construcción y de mejora (aquí se encuentra el aporte del trabajo de investigación). En cuanto a las heurísticas de construcción se presentan dos propuestas de clusterización basadas en la ubicación geográfica de los clientes y depósitos y sus cercanías entre si, teniendo en cuenta además la limitación de capacidad de los vehículos; como un subproceso importante se ha formulado y resuelto un subproblema combinatorio de asignación de clústeres a depósitos pero de tamaño menor cuya solución exacta es posible de terminar. En cuanto a las heurísticas de mejora se utilizaron las estrategias del vecino más cercano (nearest neighbor) y de separación (split). Se presentan finalmente los resultados y las comparaciones respecto a la mejor solución conocida BKS (Best Know Solution) disponible en la literatura.