HEURÍSTICA DE PROGRAMACIÓN DE RUTAS PARA EMPRESA 3M

Abstract

Para poder diseñar una heurística de programación de rutas para 3M se investigan siete modelosde ruteo que difieren en factores como la inclusión de ventanas de tiempo, el uso de flota homogénea oheterogénea, realizar entrega, recolección o ambos, utilizar uno o varios depósitos y la opción de tener más deun repartidor. Además se investigan las heurísticas: búsqueda tabú, colonia de hormigas, algoritmos genéricos,recocido simulado y GRASP, los cuales buscan encontrar la ruta más corta a través de distintos métodos.Finalmente se escoge el GRASP, por ser una heurística simple que logra buenos resultados.Al analizar la logística de 3M, se observa que utiliza distintos tipos de vehículos para repartir losproductos, estos vehículos se diferencian en la capacidad que pueden llevar y en su costo de arriendo. Porotro lado, realizan sólo entrega de productos desde un único depósito y pueden visitar a los clientes enhorarios definidos. Se determina que el modelo que mejor se adapta a estos datos es el VRPTW, con dosmodificaciones principales, se considera sólo costo fijo, pues la empresa transportista sólo cobra costo dearriendo por cada vehículo, y se añade además una restricción de factibilidad, pues algunos clientes puedenser visitados por vehículos específicos.Para la programación de la heurística GRASP, se programa primero el algoritmo que busca unasolución inicial factible, el cual consiste en ordenar los vehículos según capacidad, para luego elegir algunode los N1 primeros. Luego se definen los clientes que pueden ser visitados por dicho vehículo y se ordenanpor distancia al centro de masa de los clientes ya asignados al vehículo de forma ascendente y se seleccionauno de los N2 primeros. Para definir N1 y N2 se prueban distintas combinaciones donde N1 = 3 y N2 = 1resultan ser la mejor.Luego se programa el algoritmo de búsqueda local, donde se prueban cinco métodos de movimientosde arcos: 2-opt, 2-opt*, 2-opt/2-opt*, 3-opt y or-opt-1. Posteriormente se mejora con cada movimiento unconjunto de soluciones iniciales. Se obtiene que los movimientos que logran el menor número de rutasson 2-opt*, 2-opt/2-opt* y 3-opt, y el que obtiene menor tiempo de rutas es 3-opt, pero tiene un tiempode ejecución muy alto que no compensa la diferencia de tiempo en rutas en comparación al movimiento2-opt/2-opt*, por lo que se elige éste último como movimiento para la búsqueda local.Una vez programada la heurística, se ejecuta para comparar las rutas realizadas por 3M en 11 días,donde los resultados demuestran que el sistema actual de programación de rutas es ineficiente. En los díasestudiados se llevaron a cabo 293 rutas, que implican un costo de $22,234,749, mientras que la heurísticapara los mismos días programa un total de 241 rutas, que tienen asociadas un costo de $18,007,929. Por lotanto, la heurística obtiene un ahorro potencial de $4,226,820 equivalente a un 19% de los costos de arriendode vehículos.Se observa además que la heurística logra mayores ahorros potenciales cuando el número de clientes que se debe visitar en el día es menor, mientras que cuando el número de clientes es mayor, el número de rutasobtenido con la heurística es similar al número de rutas hechas. Esto se da porque en 3M no se programan lasrutas en función de los clientes, si no en función de las comunas, por lo tanto, cuando hay un bajo número declientes no se alcanza a llenar la capacidad del camión ni ocupar todo su tiempo disponible, ya que no sevisitan más clientes por pertenecer a otros grupos de comunas.Además, se determina que los tiempos de servicios son muy relevantes en la programación de rutas,en especial cuando la cantidad a visitar de clientes es alta. Al aumentar en 15 minutos el tiempo de servicio,el número de rutas llega a aumentar en 6, y al disminuir el tiempo de servicio en 15 minutos, se utilizan hasta5 vehículos menos.Resultado similar, pero en menor magnitud, se obtiene al variar las ventanas de tiempo. Al aumentaren 30 minutos el tiempo disponible para entregar la mercancía a los clientes se puede, en el mejor de los casos,ocupar un vehículo menos. Mientras que cuando se aumenta en una hora las ventanas de tiempo, entonces lasrutas pueden disminuir en tres.A partir de los resultados se plantean propuestas para poder disminuir los costos de transporte: 1)Implementar la heurística, donde previamente se debe evaluar si los días estudiados pueden representar lademanda para los demás días del año, o en caso contrario, definir una demanda representativa y determinarlos resultados potenciales al aplicar la heurística, con los cuales se podrá realizar una correcta una evaluacióndel proyecto para el largo plazo. Luego, costear su implementación, evaluada en $10,033,000. 2) Utilizar unsistema de programación de rutas dinámico, donde las comunas que visiten los vehículos no sean siemprelas mismas, si no que vayan cambiando de acuerdo a los clientes y sus demandas, con el objetivo que losvehículos alcancen su límite ya sea en capacidad o tiempo. 3) Aumentar la cantidad de vehículos de menorcapacidad en la flota fija, pues en la mayoría de los días se deben contratar como vehículos extra, teniendoque pagar más por su arriendo. 4) Disminuir los tiempos de servicio mejorando la comunicación con losclientes o aplicando un sistema de beneficios y penalidades para incentivar la disminución de los tiemposde espera. 5) Evaluar la entrega de mercancía antes o después de las ventanas de tiempo según las multasasociadas y considerar entregar productos días antes de su fecha de promesa. 6) Finalmente, se recomiendaevaluar cambiar el sistema de pago por peso volumétrico entregado, de esa forma la cantidad de vehículos noafectaría en los costos de 3M y la empresa transportista se preocuparía de la optimización de sus rutas.Como observación final, se debe considerar que la aplicación de algunas propuestas para diminuirla cantidad de vehículos que utiliza la empresa podría traer como consecuencia el aumento de los costosde arriendo, pues la empresa transportista necesitaría solventar mayores costos variables. Por lo tanto, serecomienda conversar con la empresa transportista y buscar una tarifa conveniente a ambas partes.