VRP (Vehicle Route
Problem)
Sandra Gonzales Cueto
VRP (Vehicle Route Problem)
El problema de enrutamiento de vehículos VRP (Vehicle Routing Problem) es un
problema complejo de optimización combinatorial, constituye un problema importante
de transporte que consiste en determinar el número de vehículos y las rutas que
seguirán cada uno de estos vehículos con el fin de distribuir unos productos entre una
serie de clientes. El objetivo es minimizar el costo de transportar estos productos.
VRP
Es un problema clásico de la optimización combinatorial, propuesto por Dantzing
y Ramser (1959), cuyo objetivo era encontrar las rutas óptimas de camiones
cisternas, desde un gran depósito hacia un gran número de estaciones de servicio.
En su forma general el objetivo es diseñar un conjunto de rutas a bajo costo,
atendiendo clientes dispersos geográficamente y cumpliendo con limitantes del
problema específico.
CLASIFICACION
VRP con recolección y entrega (VRPPD).
Estudia el caso donde una empresa debe recolectar y entregar bienes en cantidades
específicas para cada cliente visitado.
Ejemplos:
• Alshamrani et. al. Tratan un problema de logística reversa inspirado en la situación
real de distribución de sangre del American Red Cross, en este problema se debe
planear la entrega de los contenedores por los camiones mientras que de manera
simultanea se debe estimar la cantidad de contenedores que deben ser recogidos por
los camiones en cada parada.
• Repoussis et. al, Trata también un problema de logística reversa en la recolección y
reciclaje de desperdicios de aceites lubricante
VRP con flota heterogénea.
Es un problema muy común, donde los vehículos de la empresa tienen
diferentes capacidades de carga.
La variante VRP para flotas heterogéneas (HFVRP, Heterogeneous Fleet VRP),
aparece cuando los diferentes vehículos que conforman la flota difieren en
equipamiento, capacidad, antigüedad, estructura de costes o incluso nivel de
emisiones, si éstas son consideradas.
EJEMPLOS
• • Los primeros ejemplos del HFVRP se deben a los problemas FSM (“Fleet Size and Mix”),
propuestos por Golden et al. (1984). Dichos autores proponen dos heurísticas, donde la primera de
ellas se basa en el algoritmo de ahorros de Clarke & Wright, (1964), y la segunda utiliza un esquema
de ruta gigante (Beasley, 1983). Formularon 20 problemas que posteriormente han sido tomados
como referencia por muchos autores para la presentación de los resultados de sus algoritmos en
flotas heterogéneas. Los problemas 1-12 disponen de 12-30 clientes, mientras que los problemas
13-20 son mayores, con 50-100 clientes. En cuanto a la flota, según el problema, se dispone de 3-6
tipos diferentes de vehículos. Los problemas 3-6 y 13-20, al contrario que los 1,2 y 7-12, se definen
por distancias euclídeas, para cuya resolución se facilita las coordenadas de todos los nodos.
• Otras variantes del HFVRP fueron los problemas con un número limitado de
vehículos HVRP, introducidos por primera vez por Taillard (1999) que presentó un
método heurístico basado en la generación de columnas. Este método comienza
resolviendo el problema VRP homogéneo para cada tipo de vehículo, utilizando un
algoritmo de búsqueda tabú.
• Todas las rutas obtenidas se almacenan en un conjunto de posibles rutas finales y, a
continuación, a través de un proceso iterativo, se extraen y se combinan en una
solución parcial con el criterio de no repetición de clientes. El conjunto final de rutas
óptimas se obtiene mediante la resolución de un problema de optimización lineal,
minimizando los costes totales y asegurando que cada cliente es servido por sólo una
ruta. Este método se utiliza para resolver los problemas FSMF y FSMD del segundo
conjunto de problemas propuestos por Golden et al. (1984), y también resolvió la
versión HVRPD, para lo cual tuvo que especificar, para cada problema, un número
limitado de vehículos por categoría. Este conjunto de 8 problemas se considera
como punto de referencia en los problemas HVRP.
CVRP (Capacited Vehicle Routing
Problem)
En el CVRP una flota fija y homogénea de vehículos se encuentra estacionada en un
almacén central para atender a la demanda de unos clientes conocidos. El CVRP
consiste en el diseño de un conjunto de rutas hamiltonianas de menor coste de tal
manera que cada cliente ha de ser visitado una única vez por un único vehículo y todas
las rutas de los vehículos han de comenzar y finalizar en el almacén.
el objetivo es minimizar la flota de vehículos y la suma del tiempo de viaje, y a la vez la
demanda total para cada ruta no puede exceder la capacidad del vehículo que realiza
esa ruta.
Una solución es factible si la cantidad total asignada a cada ruta no excede la capacidad
del vehículo que realizara la ruta
EJEMPLO
• Algunos de los trabajos relacionados son por ejemplo, The Capacitated
Vehicle Routing Problem (CVRP) [6] en este problema se tiene un conjunto
de puntos en un espacio métrico, un grupo de vehículos de cierta capacidad y
una colección de rutas de vehiculos empezando en un origen, los cuales cada
uno deben visitar un punto determinado. Otro de los trabajos es The
Preceden - Gonstrained TSP [7] que implica la existencia de un número
finito de puntos que se deben visitar antes de visitar un punto definido. Estos
problemas son muy importantes, y las soluciones planteadas en este articulo
son muy interesantes.
El Problema del Vendedor Viajero - TSP
El Problema del Vendedor Viajero (conocido también como Travelling
Salesman Problem o simplemente TSP) consiste en encontrar el circuito
óptimo (en términos del viaje más corto) que deberá seguir un vendedor en un
caso con n ciudades, en el que cada ciudad se visita exactamente una vez.
Básicamente es una adaptación del Problema de Asignación que considera
restricciones adicionales que garantiza la exclusión de subcircuitos en la
solución óptima.
EJEMPLO
• El planteamiento es el siguiente: un vendedor que quiere encontrar la ruta
más corta posible, partiendo desde su casa y llegando a la misma, y visitando
a todos sus clientes sólo una vez, es decir sin pasar dos veces por el mismo
punto. Desde el punto de vista práctico, el problema no está resuelto y desde
el punto de vista teórico, las técnicas empleadas son sólo 4 aproximaciones.
No suponen una resolución real del TSP y sólo ofrecen soluciones
aproximadas suficientemente aceptables.
• La solución más directa es la que aplica la fuerza bruta: evaluar todas las posibles
combinaciones de recorridos y quedarse con aquella cuyo trazado utiliza la menor
distancia. El problema reside en el número de posibles combinaciones que viene
dado por el factorial del número de ciudades (N!) y esto hace que la solución por
fuerza bruta sea 20 impracticable para valores de N incluso moderados con los
medios computacionales actualmente a nuestro alcance. Por ejemplo, si un
ordenador fuese capaz de calcular la longitud de cada combinación en un
microsegundo, tardaría algo más de 3 segundos en resolver el problema para 10
ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y...
77.146 años en resolver el problema para solo 20 ciudades.
Times Windows VRP (TWVRP)
Plantea que cada cliente tiene que ser atendido de manera obligada dentro de
un cierto horario o “ventana de tiempo” específico.
El objetivo es minimizar la flota de vehículos, el tiempo total de viaje y el
tiempo necesario para abastecer a todos los clientes en sus respectivos horarios.
EJEMPLO
Una aproximación heurística robusta es propuesta en G. de Tomi G. B. Alvarenga, G. R. Mateus. Finding near optimal
solutions for vehicle routing problems with time windows using hybrid genetic algorithm para el problema de rutas de
vehículos con ventanas de tiempo, usando un algoritmo genético. El principal objetivo del artículo es minimizar la
distancia viajada. En los resultados propuestos, el comportamiento de métodos heurísticos fue comparado con métodos
exactos en términos de encontrar un óptimo global, robustez y esfuerzo computacional, usando las mismas
suposiciones para la precisión del cálculo y la definición de la función objetivo.
Un algoritmo de optimización de colonia de hormigas ACO es propuesto como solución a este problema, el cual es
basado en el sistema de Hormigas, que fue inspirado sobre el comportamiento real delas hormigas. El objetivo es
minimizar el costo total, el cual consiste de costos en la cantidad de vehículos utilizados y la distancia total viajada. Para
ello usan una función objetivo de pesos para minimizar el tamaño
del conjunto de vehículos necesarios. Finalmente se presentan unos
resultados de la simulación para los cuales usaron un algoritmo heurístico y una implementación- secuencial del ACO
hibrido para ver el desempeño del ACO HIBRIDO Frente a los otros
VRP con depósitos múltiples (MDVRP)
Implica que la empresa posee diversos depósitos desde los cuales puede abastecer a los
clientes.
Una compañía puede tener varios depósitos desde donde abastece a sus clientes. Si los
clientes se encuentran agrupados alrededor de los depósitos, entonces el problema de
distribución-n se puede modelar como varios VRP independientes, No obstante, si los
clientes Y los depósitos se localizan entremezclados tenemos en problema de MDVRP.
en este tipo de problema se consideran varios depósitos, donde en cada uno de ello se
existe una flota de vehículos y cada deposito tiene a su cargo a un numero de clientes,
los cuales son atendidos por los vehículos asignado al deposito y el objetivo de este
problema, junto al ya mencionado de reducir la distancia recorrida, es minimizar la
flota de vehículos asignados a cada deposito.
EJEMPLO
En Libertad Tansini, Maria Urquart, and omar viera. Comparing assignment
algorithms for the multi-depot VRP se enfoca principalmente en la asignación
(agrupamiento) de los clientes a los almacenes, y compara los resultados obtenidos por
seis heurísticas con asignación (asignación a través de urgencias,
asignación paralela, asignación simplificada y barrido de asignación) obtenidos para
resolver un problema de transporte para los mismos
casos. Estos resultados fueron obtenidos utilizando una herramienta llamada STAAR),
desarrollada basado el software ArcView 3.0, plataforma GIS. Con estas pruebas,
se concluye que los algoritmos de urgencia son los mas recomendables en problemas
grandes de la vida real
