El Problema del Enrutamiento del Vehículo con Entrega Dividida

...

Esta solución está expresada en el siguiente algoritmo:

[pic 6]

Figura 3.

Primero calculamos el nodo de las rutas de un total de n clientes, luego se calculan los contadores de borde para finalmente inicializar la mejor solución por medio de la búsqueda tabú. Así se genera un total de rutas guiadas por el nodo y se ordenan las rutas en base a la medida de deseabilidad. Finalmente el ciclo itera mientras el tiempo no haya sido alcanzado o bien el número máximo de soluciones posibles no haya sido alcanzado. Gráficamente esto podría expresarse de la siguiente forma en la Figura 4.

[pic 7]

Figura 4

- EXPERIMENTO COMPUTACIONAL

Se testearon 42 instancias, de las cuales son las mismas instancias que se encuentran en la búsqueda tabú de Archetti, Hertz, y Speranza (2006). En cada una de ellas se encuentran en un rango de 50 a 199 clientes y la capacidad de los vehículos está dada en un rango entre 140 a 200.

Cada nueva instancia (p) se caracteriza por estar en el menor rango de la demanda del cliente; se denomina por tanto, a. Mientras que el límite del rango de la demanda del cliente está en la variable, g; lo cual se expresa en la capacidad del vehículo Q. Así, [a=0, g=1] es a g. Es decir, la demanda di del cliente i esta caracterizada matemáticamente como:

[pic 8]

En el análisis computacional, la demanda di de un cliente i es elegida aleatoriamente en el intervalo dado, es decir, [aQ, gQ]. En la siguiente tabla (Figura 5) se muestra las iteraciones con cada instancia p, en base a la cantidad de clientes n caracterizados por la demanda a de clientes y el límite de demanda g de los clientes.

[pic 9]

Figura 5.

La heurística basada en la optimización puede ser acomodada a un límite de números de visitas expresadas de la siguiente forma:

[pic 10]

Los resultados demuestran un porcentaje de mejora del 2.34% para la instancia p11 con 120 clientes y la demanda a[0.7], g[0.9]. Es decir, “estos resultados apoyan nuestra creencia que el uso de técnicas de optimización en conjunto con búsquedas heurísticas pueden, en efecto, llevar a una mejor solución que focalizándose solamente en una búsqueda heurística” (Archetti, Speranza y Savelsbergh, 2008, p. 28).

- CONCLUSIÓN

Mucho se ha discutido sobre el problema de enrutamiento del vehículo (VRP), en específico, nos hemos enfocamos en el problema del enrutamiento del vehículo con entrega dividida. Básicamente, el SDVRP pretende minimizar el costo y la cantidad de entregadas en cada recorrido y no exceder la capacidad del vehículo y la distancia recorrida. Es así como mediante los resultados obtenidos de la búsqueda tabú, la heurística basada en optimización pretende minimizar los costos y la demanda con respecto del cliente en cada conjunto de ruta mediante la programación entera proponiendo un algoritmo para su ejecución.

El SDVRP permite que un cliente pueda ser visitado por más de un vehículo, esto puede ser notablemente beneficioso cuando la demanda de los clientes (di) es excesivamente grande en relación a la capacidad de los vehículos de la empresa. Por ende, al aplicar una búsqueda heurística con los métodos de optimización se puede minimizar el costo de la ruta con respecto a la demanda del cliente.

Se pudo apreciar en base a los análisis computacionales que la búsqueda tabú sumada a las técnicas de optimización, o más específico, la programación entera, se pudo mejorar los tiempos de entrega de acuerdo a la demanda de n clientes dentro de los rangos establecidos por la optimización.

- BIBLIOGRAFÍA

C. Archetti, Speranza, M.G., Savelsbergh, M. “An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem”. Transportation Science Vol. 42, No. 1, February 2008, pp. 22-31.

C. Archetti and M. G. Speranza, “The Split Delivery Vehicle Routing Problem: A Survey,” The Vehicle Routing Problem: Latest advances and new challenges, eds. Golden, Bruce L., Raghavan, S., Wasil, Edward A., 2008, pp. 103-127.

C. Archetti, M. Savelsbergh and A. Hertz, “A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem,” Transportation Science, Vol. 40, No. 1, 2006, pp. 64-73.

M. Dror and P. Trudeau, “Savings by Split Delivery Routing,” Transportation Science, Vol. 23, No. 2, 1989, pp. 141-145.

G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science, Vol. 6, No. 1, 1959, pp. 80-91.

Matías Ebensperger (2009), “Una formulación para el problema de ruteo de vehículo con tiempos de viaje dependientes del tiempo para la actualización de rutas con información en tiempo real”, Tesis del Magíster en Ciencias de la Ingeniería, Pontificia Universidad Católica de Chile, Santiago, Chile.