El Problema del Enrutamiento del Vehículo con Entrega Dividida

[pic 1][pic 2]

[pic 3]

The Split Delivery Vehicle Routing Problem

Josué Gajardo

Abstract

This report aims to understand The Split Delivery Vehicle Routing Problem. An optimized algorithm is analyzed in order to minimize the distances and costs of the routes of each vehicle that has made a delivery to the clients from the results obtained from the tabu search.

Resumen

El presente informe tiene como objetivo comprender El Problema del Enrutamiento del Vehículo con Entrega Dividida. Se analiza un algoritmo optimizado con el fin de minimizar las distancias y los costos de los recorridos de cada vehículo que ha realizado una entrega a los clientes a partir de los resultados obtenidos de la búsqueda tabú.

1. INTRODUCCIÓN

El problema del enrutamiento del vehículo (llamado VRP por sus siglas en inglés [Vehicle Routing Problem]) es uno de los problemas más interesantes y más discutidos de la optimización combinatoria. Básicamente, con el VRP se intenta resolver los problemas de una flota de vehículos que pretende realizar una entrega a una determinada cantidad de clientes distribuidos en distintas locaciones. De hecho, fue Dantzig y Ramser quien propuso esta problemática por primera vez en 1956. Los VRP se consideran como NP-Difícil, es decir, se pueden resolver mediante un modelo matemático, o sea, a partir de una función objetivo.

Por otro lado, desde el año 1956 se han formulado una cantidad notable de nuevas variaciones de VRP (Gendreau, Laporte, & Potvin, 2002). Se encuentran entre ellos el problema del vehículo con múltiples ruteos, Multiple Depot Vehicle Routing Problem (MDVRP); el problema del ruteo con descarga simultánea, VRP with Simultaneous Pick-up and Delivery (VRPSPD); el problema del ruteo con ventanas de tiempo, vehicle Routing Problem with Time Windows (VRPTW). (Matías Ebensperger, 2009, p.13-14).

Una de ellas es el denominado “The Split Delivery Vehicle Routing Problem”, introducido por Dror y Trudeau (1989) por primera vez. Básicamente, el problema del SDVRP “consiste en encontrar  un conjunto de rutas de vehículos  que sirven a todos los clientes, de modo que, la suma de cantidades entregadas en cada recorrido no exceda la capacidad de un vehículo y la distancia total recorrida se minimice.” (C. Archetti y M. G. Speranza, 2008, pp. 103).

A partir de lo anterior, este informe tiene como objetivo comprender el problema de la heurística basada en la optimización del SDVRP; es por ello que en la parte 2 se establece y define el problema, para luego, en la parte 3, explicar el modelo matemático y su algoritmo propuesto; en la parte 4 se muestra el resultado del experimento matemático de la programación entera. Finalmente, en la conclusión se mencionan los aprendizajes obtenidos a partir de lo presentado en este informe.

1. DEFINICIÓN DEL PROBLEMA

El problema del enrutamiento del vehículo con entrega dividida, como se mencionó, consiste en encontrar la mejor ruta y, que la suma de las cantidades de entregas a los clientes no excedan la cantidad de vehículos disponibles en una flota, esto con el fin de que la distancia y el costo puedan ser minimizados.  Por otro lado, el SDVRP permite reducir los costos con respecto al costo del VRP con el fin de permitir la entrega dividida (C. Archetti, M. G. Speranza y M. Savelsbergh, 2008).

Para la discusión  y solución de esta problemática se han escrito tres artículos académicos proponiendo en cada uno de ellos un algoritmo más optimizado. Así, por ejemplo en Dror y Trudeau (1989) se propuso una heurística de búsqueda local, “Savings by split delivery routing”; por su parte, Archetti, Hertz y Speranza (2006) establecieron una heurística de búsqueda tabú en “A tabu search algorithm for the split delivery vehicle routing problem”; y finalmente, en “An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem” de los autores Archetti, Speranza y Savelsbergh (2008) se propone una heurística basada en la optimización.

Un ejemplo gráfico con una entrega dividida por tres en el SDVRP se ve reflejada en la Figura 1, donde r es el recorrido del vehículo e i es cada cliente.

[pic 4]

Figura 1.

Así, la heurística basada en la optimización surge a partir de la búsqueda tabú presentada en 2006 por Archetti, Hertz y Speranza. El algoritmo de la búsqueda tabú se basa principalmente en tres fases (Archetti, Hertz y Speranza, 2006):

1. Construcción de una primera solución factible;
2. Fase de la búsqueda tabú; y
3. mejora final de la solución encontrada en la búsqueda tabú.

A partir de ello es como surge la heurística basada en la optimización, es decir, a partir de la información obtenida en la búsqueda tabú se construye un conjunto de buenas rutas mediante la programación entera.

La búsqueda tabú es un  método de optimización matemático que permite realizar un análisis local mediante el uso de estructuras de memoria. Estas estructuras de memoria se refieren a que una vez que se encuentra una solución, ésta se guarda en dicha memoria y es considerada como  tabú. Por ende, el algoritmo presentado por Archetti, Hertz y Speranza en 2006 permite, primero, construir una solución factible para luego estructurar las soluciones en memoria y así finalmente mejorar la solución tabú. Es a partir de este algoritmo que el SDVRP con una optimización heurística es propuesta. Esta optimización heurística consta de dos pasos, el primero es usar la búsqueda tabú y el segundo en usar la programación entera, la cual busca declarar algunas o todas las variables y restricciones como enteras.

1. MODELO MATEMÁTICO: PROGRAMACIÓN ENTERA

La función objetivo de la optimización heurística del SDVRP consta de C(r) que denota el conjunto de clientes que son visitados en una ruta r.

[pic 5]

Figura 2.

Las variables se definen de la siguiente forma:

• c: corresponde al costo.
• r: corresponde a la ruta que debe tomar el vehículo.
• i: se refiere a los clientes.
• di: Demanda con respecto al cliente.
• C: es el conjunto de clientes.
• Q: capacidad de vehículos disponibles.
• R: el conjunto de rutas r.

La función objetivo minimiza el costo total de las rutas seleccionadas. Por ende, la primera restricción (2) formula que una entrega a un cliente en una ruta r sólo puede tener un lugar de capacidad Q; y la tercera restricción (3) manifiesta que la demanda di del cliente i pueda ser satisfecha.

...