Ruteo de Vehículos desde un Centro de Distribución a una Línea de Supermercados en Barranquilla, Colombia

Vehicle Routing from a Distribution Center to a Supermarket Line in Barranquilla, Colombia

El ruteo de vehículos procura encontrar soluciones cercanas al óptimo (debido a su alta complejidad de acuerdo al número de nodos o clientes) para minimizar los costos de operación o maximizar el número de clientes atendidos. En el presente trabajo presentamos la aplicación del método de ruteo heurístico de Clarke Wright, para el mismo problema abordado en el documento “Localización de bodegas y asignación de clientes (FLP) en supermercados de Barranquilla”. Las técnicas implementadas revelan como resultado un enrutamiento de menor costo a cada cliente.

1. INTRODUCCIÓN

El principal objetivo en problemas de optimización es encontrar el valor óptimo de solución, sin embargo en aquellos problemas denominados NP hard o NP duros, la complejidad de los algoritmos puede ser exponencial debido a la elevada cantidad de posibles soluciones, las cuales deben ser evaluadas para encontrar un óptimo. De tal forma que el tiempo de procesamiento para un ordenador común o incluso muy avanzado, podría ser de años o siglos tratando de resolver un problema sencillo de ruteo. Las heurísticas han facilitado la búsqueda de valores cercanos al óptimo en tiempos razonables.

El problema que se presenta es de enrutamiento directo, donde existe un solo centro de distribución que atiende una demanda de 26 puntos de venta localizados dentro del casco urbano de la ciudad de Barranquilla, con una flota de camiones de capacidad conocida. El objetivo es minimizar los costos de transporte de un producto específico; así mismo, se utilizará el método de ruteo de Clarke Wright (o de ahorros) de vehículos para dar cumplimiento a la demanda diaria de cada uno de los puntos de venta de Supertiendas y Droguerías Olímpica S.A. al menor costo posible.

Al final se presenta el comparativo entre el método del barrido usado anteriormente y nuestra implementación.

2. PROBLEMA DE DISTRIBUCIÓN EN PLANTA Y RUTEO DE VEHÍCULOS CON CAPACIDAD [1]

Las metaheurísticas han sido métodos utilizados en la búsqueda de soluciones para determinar ruteos u otros tipos de problemas, y han tenido muy buenos resultados. Se definen como un método heurístico guiado paso a paso, donde a través de un proceso de búsqueda local, es susceptible de ser mejorado. Estos procesos de metaheurísticas están basados en simulaciones como la de colonia de hormigas y algoritmos de búsqueda tabú [2]