Una nueva heurística de construcción y mejoramiento basada en ahorros para instancias grandes del problema de ruteo de vehículos

Abstract

En la literatura, el problema de ruteo de vehículos (VRP) ha sido intensamente estudiado desde el año 1959, tras ser propuesto por George Dantzig y John Ramser en 1959. En la actualidad, existen muchas variaciones de dicho problema, con el objetivo de poder generar soluciones que se hagan cargo de las distintas restricciones que presenta el VRP en la realidad. De hecho, en los últimos años la investigación se ha basado en como poder adaptar heurísticas y algoritmos para instancias de gran tamaño, considerando miles de clientes y cientos de vehículos, en especial para su uso en aplicaciones logísticas. Esta tesis presenta una nueva forma de resolver el problema de ruteo de vehículos con ventanas horarias (tanto para los clientes como los vehículos) cuando se cuenta con una flota heterogénea (en cuanto a capacidad y ventana horaria de los vehículos) y con un número fijo de vehículos, así como también, agregando la posibilidad de poder realizar más de un viaje desde y hacia el depósito, si lo anterior es factible en términos del tiempo disponible y de esta manera pudiendo atender más clientes a lo largo del día. Todo lo mencionado anteriormente se realiza mediante una heurística basada en ahorros (savings) para la creación de rutas, una heurística similar al bin packing para la asignación de rutas a vehículos y finalmente una heurística de mejoramiento de rutas mediante movimientos de búsqueda local. Este problema será denotado como VRPTW con Flota Fija Heterogénea y Multi Viajes y dada la implementación escogida, la heurística desarrollada genera soluciones competentes en cuanto a distancia recorrida y utilización de vehículos, así como también una gran rapidez para la generación de dichas soluciones, pudiendo resolver instancias con aproximadamente 2.000 clientes en 4 minutos. Lo anterior significa generar ahorros en tiempo de ejecución de aproximadamente 80% al compararse con soluciones actuales entregadas por empresas como SimpliRoute (las cuales se demoran entre 20 a 30 minutos en resolver dichas instancias) y manteniendo la calidad de sus soluciones, es decir, obteniendo ahorros en los kilómetros recorridos a costa de un leve aumento en la utilización de los vehículos. Cabe mencionar que se generó una heurística que pudiera entregar soluciones de manera rápida, con el fin de atender las reglas de negocios de empresas del área logística, como por ejemplo SimplirRoute, en la que se busca entregar soluciones a todo tipo de instancia en menos de 15 minutos. No obstante, es posible generar modificaciones a la heurística de mejoramiento mencionada con el fin de obtener soluciones aún más competitivas y poder así generar nuevas "mejores soluciones conocidas"(best known solutions) a instancias estudiadas en la literatura.