PROBLEMA DE RUTEO DE VEHCULOS

MODELOS DEL VRP

El problema de ruteo de vehculos (VRP) consiste en efectuar el reparto de mercanca

de la forma ms eficiente, satisfaciendo la demanda de todos los clientes, considerando

la capacidad del vehculo y todas las posibles combinaciones de rutas (Suarez, 2009).

Dentro de las variantes del VRP encontramos las siguientes:

1. CVRP (Capacitated VRP) (Olivera, 2004): Es el caso ms general, consiste en

uno o varios vehculos con capacidad limitada y constante encargados de

realizar el reparto a los clientes. Es la extensin del problema del agente viajero

(TSP) en el que las rutas permitidas son limitadas tanto por la capacidad de los

vehculos como por la demanda que se debe satisfacer.

En este tipo de problema se parte de un depsito de donde los vehculos deben

partir a realizar su recorrido y al cual deben regresar. Las restricciones son:

satisfacer la demanda, visitar a todos los clientes y no sobrepasar la capacidad

del vehculo.

El objetivo es minimizar el nmero de vehculos y el recorrido total que efectan

estos (Benavente & Bustos, 2010).

2. Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)

(Miguel, Tohm, & Frutos, 2013): Representa el mismo caso que el CVRP con

una restriccin adicional de ventana del tiempo sobre cada cliente.

Las restricciones son que cada cliente reciba lo que demand dentro del tiempo

establecido, sin exceder la capacidad de los vehculos y teniendo un depsito

como origen y destino para los vehculos.

En este caso el objetivo, adems de minimizar los costos asociados al ruteo es

minimizar las sanciones por las violaciones a las ventanas de tiempo.

3. Periodic VRP (Hernndez, Olivares, Martnez, & Nuo, 2011): El caso del

problema de transporte peridico consiste en planificar las rutas para un periodo

de das establecido, donde en cada da se vara tanto el nmero de clientes a

atender como la demanda de cada uno, restringido por la capacidad de los

vehculos.

El objetivo es encontrar un conjunto de rutas para cada vehculo que minimice el

costo total del viaje satisfaciendo todas las restricciones operacionales.

4. Periodic VRP with Time Windows (Hernndez, Olivares, Martnez, & Nuo,

2011): El mismo problema anterior pero sumando las restricciones de las

ventanas de tiempo para cada cliente e incluyendo en el objetivo la

minimizacin de las sanciones por el incumplimiento de los tiempos.

5. Heterogeneus Fleet Vehicle Routing Problem (HF-VRP) (FSMVRP)

(Olivera, 2004): En el problema de flota heterogenea los costos y las

capacidades de los vehculos, varan segn el tipo de vehculo, los costos y los

tiempos de viaje son funcin de la capacidad de los vehculos.

Las restricciones indican que todos los clientes deben ser visitados, la demanda

satisfecha y las capacidades de cada tipo de vehculo no pueden ser

sobrepasadas. La cantidad de vehculos disponibles de cada tipo es limitada.

El objetivo es minimizar los costos totales, no slo se debe decidir la ruta sino la

composicin de los vehculos a utilizar en la flota.

6. Vehicle Routing Problem with Time Windows (VRPTW)

(Desrochers et al., 1988): El VRPTW es la extensin del CVRP donde el

servicio a cada cliente debe comenzar dentro de una ventana de tiempo

especificado y el vehculo debe permanecer en la ubicacin del cliente durante el

servicio.

Las restricciones indican que el cliente debe ser atendido por un solo vehculo, el

vehculo debe permanecer quieto durante el instante de tiempo que se demora el

servicio a cada cliente y la ruta de cada vehculo, se conecta con un nico

cliente.

El objetivo es minimizar los costos totales, representados por la distancia

recorrida y tiempo total de viaje.

7. Vehicle Routing Problem with Pick-up and Deliveries (VRPPD)

(Daneshzand, 2011): En VRPPD, los vehculos tienen dos conjuntos de tarea,

una correspondiente a la entrega de mercancas a los clientes y el otro la

seleccin de mercancas hacia las instalaciones del cliente. En el VRPPD, una

flota de vehculos heterogneos debe satisfacer un conjunto de peticiones de

transporte y cada solicitud se define por un punto de recogida, un punto de

entrega correspondiente, y una demanda para ser transportado entre estos

lugares.

(Cepeda & San Lucas, 2012): Las restricciones del modelo consisten en que la

tarea de entrega y recoleccin de productos se debe hacer de manera simultnea,

cada cliente es visitado por un vehculo una vez, comenzando y terminando en

el mismo punto (deposito), teniendo en cuenta la capacidad del vehiculo.

El objetivo es minimizar los costos totales reflejados en la distancia total

recorrida.

8. Capacitated VRP with Pick- up and Deliveries and Time Windows

(CVRPPDTW)

(Karlaftis et al., 2009): El modelo CVRPPDTW, incluye la capacidad del

vehculo y la ventana de tiempo para realizar las entregas y recoleccin de

mercancas a los clientes. Los clientes requieren simultnea recogida y entrega

del servicio y la capacidad de carga del vehculo es muy variable y con

frecuencia como oposicin a una disminucin monotnica (entrega) o un

aumento monotnico (pick - up), en cortos plazos de entrega.

Las restricciones del modelo consisten en que la tarea de entrega y recoleccin

de productos se debe hacer de manera simultnea, teniendo en cuenta la

capacidad total del vehculo y que durante el servicio, el vehculo debe

permanecer quieto. Cada cliente es visitado por un vehculo una vez,

comenzando y terminando en el mismo punto (deposito).

El objetivo es minimizar los costos totales reflejados en la distancia recorrida y

el tiempo total de viaje.

9. Multiple Depot VRP (MDVRP)

(Ho et al, 2008): En este modelo se considera la posibilidad de una empresa de

distribucin con mltiples depsitos, el nmero y la ubicacin de los depsitos

estn predeterminados y cada uno es lo suficientemente grande para almacenar

todos los productos ordenada por los clientes. Se tiene una flota de vehculos

con capacidad limitada que se utiliza para transportar los productos desde los

almacenes a los clientes.

En las restricciones se tiene que cada vehculo comienza y termina en el mismo

deposito, la ubicacin y la demanda de cada cliente es tambin conocida de

antemano, cada cliente recibe la visita de un vehculo exactamente una vez, los

tomadores de decisiones primero deben agruparse en un conjunto de clientes

para ser atendidos por el mismo depsito, es decir, el problema de agrupamiento.

Luego tienen que asignar a los clientes los mismos depsitos a varias rutas para

que la restriccin de capacidad del vehculo no se viole. El objetivo del MDVRP

es reducir al mnimo la entrega total de minimizar la distancia de entrega total o

el tiempo pasado en el servicio a todos los clientes y as aumentar la eficiencia

de la entrega.

10. Multiple Depot VRP with Time Windows (MDVRPTW)

(Afshar-Nadja & Afshar-Nadja, 2014): En este modelo se asume que una

flota de vehculos con capacidades y gastos de viajes diferentes est disponible

para servir a las solicitudes de transporte. Adems, el tiempo de viaje entre

lugares se asume en funcin del tiempo de salida, los vehculos no tienen que

devolver a un depsito central, aunque el nmero mximo de vehculos en los

depsitos est restringido para evitar la agregacin de vehculo en algunos

depsitos. Todos los clientes deben ser visitados en una franja de tiempo

especfica y si el vehculo alcanza una de estas ubicaciones antes del inicio de la

ventana de tiempo, tiene que esperar.

El objetivo de este modelo es minimizar el costo total para el funcionamiento de

los servicios. Teniendo en cuenta que se debe escoger una ruta factible del

vehculo que debe regresar al mismo deposito o a un deposito diferente, pasando

por los clientes en los tiempos establecidos y teniendo en cuenta la limitacin

del nmero de vehculos mximos en espera y en el depsito.

MTODOS DE SOLUCION DEL VRP (Ler, Benavente, Bustos, & Venegas, 2009)

1. Mtodos Exactos: Parten de una formulacin como modelos de programacin

lineal y obtienen una solucin, gracias al acotamiento de conjuntos de

soluciones factibles.

2. Heursticas: Es un algoritmo que permite obtener soluciones de buena calidad

pero sin asegurar que sean soluciones ptimas. Se clasifican en:

- Constructivas: Van elaborando una solucin factible durante su progreso, no

parten de una como tal.

- De mejora: Necesariamente parten de una solucin factible

- Tcnicas de relajacin: Son mtodos asociados a la programacin lineal

entera.

3. Metaheursticas: Es una estrategia de solucin para problemas que no cuentan

con un algoritmo confiable ya sea por su complejidad o por la falta de estudios

sobre el problema. Las ms comnmente utilizadas son:

- Algoritmos Genticos: Son algoritmos evolutivos.

- Bsqueda de Vecindarios Variables: Parte de una solucin inicial aleatoria y

se realiza una bsqueda de vecindarios ms lejanos hasta encontrar una

mejor solucin y se comienza una nueva bsqueda.

- Recocido Simulado: Se basa en el proceso de manufactura del metal donde

un material es calentado a altas temperaturas para luego ser enfriado

lentamente.

- Bsqueda Tab: Se buscan soluciones aproximadas a la actual, en caso de

que se encuentre una mejor, se marcan las anteriores como tab, para evitar

caer en ciclos de bsqueda.

- Colonia de Hormigas: Basada en el proceso de las hormigas en la bsqueda

de comida, dejando un rastro de feromonas en las rutas ms utilizadas y

donde ms comida se encuentra.

- Enjambre de partculas: Busca simular las bsquedas realizadas por colonias

simulando la manera como colaboran entre s, hacia una bsqueda eficiente.

4. Algoritmos Hbridos: Se combinan los mejores aspectos de cada uno de los

mtodos anteriores para encontrar una solucin.

REFERENCIAS Afshar-Nadja, B., Afshar-Nadja, A. (2014). A constructive heuristic for time-dependent multi-

depot vehicle routing problem with time-windows and heterogeneous eet. Journal of King

Saud University Engineering Sciences. Pag 1-6

Benavente, M., & Bustos, J. (2010). Estado del Arte en el Problema de Ruteo de Vehculos

(VPR). Universidad de la Frontera.

Cepeda, G., & San Lucas, M. (2012). Diseo e implementacin de una heurstica para el

problema de ruteo vehicular con recoleccin y entrega de mercadera (vrppd). Escuela

superior politcnica del litoral.

Daneshzand, F. (2011). 8 The Vehicle-Routing Problem. Logistics Operations and

Management. Pag 127153

Desrochers, M., Lenstra J., Savelsbergh, M., Soumis, F. (1988). Vehicl Routingwuth time

windows: Optimation and approximation. Elsevier Science Publishers. Pag 6588

Garaviz, M. (2009). PROPUESTA PARA EL DESARROLLO DE UN CLUSTER LOGSTICO PARA UN

CORREDOR LOGISTICO NACIONAL E INTERNACIONAL COMPETITIVO EN COLOMBIA.

BOGOTA: UNIVERSIDAD DEL ROSARIO.

Ho, W., Ho, G., Ji, P., Lau, H. (2008). A hybrid genetic algorithm for the multi-depot vehicle

routing problem. Engineering Applications of Articial Intelligence. pag 548557

Karlaftis, M., Kepaptsoglou K., Sambracos, E. (2009). Containership routing with time deadlines

and simultaneous deliveries and pick-ups. Transportation Research Part E. Pag 210221

Hernndez, R., Olivares, E., Martnez, J., & Nuo, J. (2011). Mejoramiento de rutas de

distribucin de productos para lograr una ventaja competitiva. Taller Latino de

Investigacin de Operaciones.

Ler, A., Benavente, M., Bustos, J., & Venegas, B. (2009). El problema de rutas de vehculos:

Extensiones y mtodos de resolucin, estado del arte. WorkShop Internacional

EIG2009.

Miguel, F., Tohm, F., & Frutos, M. (2013). Modelado del BPP/CVRPTW y su resolucin a travs

de una meta heurstica evolutiva. VI CONGRESO DE INGENIERIA INDUSTRIAL COINI.

Olivera, A. (2004). Heursticas para problemas de ruteo de vehculos. Montevideo: Universidad

de la Repblica de Montevideo.

Sheffi, Y. (2010). LOGISTICS CLUSTERS DELIVERING VALUE AND DRIVING GROWTH.

poca/Epoch p. 265-297.

Suarez, J. G. (2009). Anisis, diseo e implmentacin de un algoritmo meta heurstico GRASP

que permita resolver el problema de rutas de vehculos con capacidad. Lima: Pontificia

Universidad Catlica del Per.