A green Vehicle Routing Problem G-VRP
El problema de enrutamiento de un vehículo verde esta formulado y técnicas de resolución
son desarrolladas para ayudar a las organización con flotas vehículos con combustibles
alternativos en superar las dificultades que existen como el resultado de un rango de
conducción vehicular limitado en conjunción con la limitada infraestructura de
reabastecimiento. G-VPR esta formulado como un programa lineal de enteros mixtos. Dos
heuristicas de construccion, “Modified Clark” y “Wright Savings” y el algoritmo de clustering
basado en densidad, y una técnica mejorada a medida, son desarrolladas. Los resultados de
experimentos numéricos muestran que las heuristicas tienen un buen desempeño. Ademas, la
viabilidad del problema depende de el cliente y las configuraciones de locación de las
estaciones.
Introducción:
En estados unidos gran parte de los gases de invernadero vienen de vehículos, y se están
haciendo grandes esfuerzos por explotar fuentes de energía alternativas (biodiesel,
electricidad, etanol, hidrogeno, metanol, gas natural, etc), hay empresas que en este esfuerzo
están convirtiendo sus flotas en vehículos de combustible alternativos (AFVs) ya sea por
cuestiones éticas o legales
Las agencias consideran numerosos factores a la hora de seleccionar un vehiculo, incluyendo:
la disponibilidad del combustible
la distribución geográfica de los centros de abastecimiento en el área,
el rango de conducción vehicular, que seria que tan lejos se puede ir con x cantidad de
combustible,
el costo del vehiculo y del combustible
la eficiencia del combustible
mantenimiento de la flota
La falta de infraestructura para reabastecimiento AFVs presenta un obstáculo significativo en
la adopción de tecnologías de combustibles alternativos
Este paper toma como objeto de estudio las compañías que emplean una flota de vehículos
para servir a los clientes localizadas en una gran región geográfica, estas compañías dependen
de herramientas que ayudan a formular viajes de bajo costo, para ahorrar dinero y tiempo que
resulta de viajar a locaciones de clientes. Estas rutas generalmente empiezan en un almacén,
visitan varios clientes y luego regresan al almacén.
El problema de asignar clientes a vehículos y ordenarlos para formar la ruta de los viajes se
conoce como el Problema de Enrutamiento de Vehiculos, este paper introduce una variable a
este problema que son los desafíos que vienen con la utilización de vehículos verdes
En este paper se desarrollan técnicas para ayudar a organizaciones con su flota de vehículos
verdes para superar desafíos que existen como resultado de una limitada infraestructura de
reabastecimiento. Estas técnicas planean planean el reabastecimiento e incorporan paradas en
estaciones de reabastecimiento para eliminar el riesgo de quedarse sin combustible
manteniendo los bajos costes de las rutas.
El siguiente es un grafico ilustrativo de la solución del G-VRP
Esta solución involucra un camion con un tanque de Q = 50 galones y un rango de consumición
de r=0.2 galones por milla (o 5 millas por galon de eficiencia del combustible). El vehiculo
empieza su trayecto en el depósito D y tiene que recorrer los clientes de C1 al C6 antes de
volver al deposito. Para visitar estos clientes, una distancia mínima de 339 millas debe
seratravesada. Viajar esta distancia consume 67.8 galones, 17.8 galones mas de lo que el
vehiculo puede contener, por lo tanto en vehiculo debe visitar al menos una estación de
reabastecimiento, para hacer todo el recorrido, el G-VPR tiene en cuenta la capacidad de
combustible del vehículo y elige la ruta mas optima para visitar los centros de abastecimiento
durante el recorrido. Por lo tanto, la solución mas optima atraviesa 364 millas, siendo el
recorrido 25 millas mas larga que la distancia mínima
Definición y formulación del problema
El problema G-VPR esta definido en una grafo cerrado no dirigido G=(V,E) donde el vertice V es
una combinación de un set de clientes I = { v1, v2, … , Vn} El deposito V0 y un set de s AFSs
F={Vn+1, Vn+2, … , Vn+s}
Entonces el vertex es la unión de los 3, V = {V0} U I U F
Se asume que, además de las estaciones, el depósito se puede usar como estación de
reabastecimiento y todas las estaciones tienen capacidad ilimitada.
El set E son los bordes del grafo que conectan los los vertices de V. Cada borde esta asociado
con un tiempo de viaje tij que es no negativo, un costo cij y una distancia dij. Se asume que la
velocidad de viaje es constante y no hay un limite de paradas que se pueden hacer para
reabastecimiento y cada parada implica que el tanque se llena hasta el tope
G-VPR busca encontrar m cantidad de viajes, uno por cada vehículo , que empiezan y terminan
en el deposito, tal que se visiten una cantidad de vertices de manera que la distancia total
realizada se minimice.
La formulación distingue entre visitas a las AFSs y al deposito de las visitas a los clientes, esto
es porque cada AFS puede ser visitada mas de una vez o ninguna vez. Además, el deposito es
visitado al comienzo y al final del tour, y puede funcionar cuando sea necesario como centro
de reabastecimiento, por otro lado, los clientes solo deben ser visitados exactamente una vez.
Para permitir múltiples o ninguna visita a los vértices, con el requerimiento de visitar otros
vértices exactamente una vez, el grafo G se aumenta con una serie de vertices falsos s, uno por
vada visita potencial a un AFS o al deposito cuando sirve como AFS
1- El objetivo: busca minimizar la sitancia viajada por la flota en un dia dado. Con las
siguientes restricciones
2- Cada cliente tiene exactamente un sucesor
3- Cada AFS (y sus vértices falsos) van a tener como máximo un sucesor
4- El número de antecesores de cada vértice es el mismo que el cada sucesor
5- M vehículos comienzan su recorrido en el deposito
6- M vehículos terminan su recorrido en el deposito
7- 8 y 9 – los vehículos vuelven al deposito antes de Tmax
8- T0 es antes que Tmax
9- La ruta se completa antes de Tmax
10- Controla el nivel de combustible para saber si hace falta recargar, reduciendo el nivel
del combustible al mínimo teniendo en cuenta el uso de combustible y la distancia
11- Resetea el nivel de combustible al máximo cuando pasa por un AFS
12- Garantiza que habrá suficiente combustible para moverse de un punto a otro
13- Integralidad binaria
Las limitaciones del rango de conducción o capacidad del tanque y la existencia de una serie de
vertices que pueden ser visitados pero que no necesariamente lo son, presenta complicaciones
que no estan presentes en VRPs clásicos, por lo que las heuristicas diseñadas para estos casos
no se pueden aplicar directamente en la resolución de este problema G-VRP, ya que
generarían soluciones pobres o no factibles, Asi que se presentan dos heurísticas modificadas
para solucionar problemas de grandes proporciones, MCWS El Algoritmo de Clarke and Wright
Savings Modificado, originalmente diseñado para VRP clásicos y el algoritmo de densidad
basado en clusters de aplicaciones con sonido DBSCAN creado con el propósito de descubrir
grupos de formas arbitrarias en grandes bases de datos espaciales (imágenes satelitales y
rayos x)
Heurística MCWS
1- Crear n viajes de ida y vuelta (v0-Vi-V0), comenzando en el deposito, visitando un
cliente y volviendo al deposito, y agregar cada tour a la lista de tours
2- Calcular la duración y la distancia de cada viaje en la lista. Revisar la factibilidad de
cada viaje inicial, teniendo en cuenta el rango de conducción del vehículo y la
limitación del tiempo y marcarlos como viable o inviable
3- Para cada viaje inviable, calcular el costo a una estación de reabastecimiento, insertar
en cada recorrido la estacion con menor coste. Si se cumplen las restricciones de rango
de conducción y tiempo se agregan en la lista de viables. Si no, se descarta el recorrido
4- Identifica todos los vertices adyacentes al deposito en un viaje, crear una lista de
ahorro SPL que incluye todos los pares posibles de estos vertices, con la condición de
que cada par esta constituido por nodos de viajes diferentes, ordena los pares en
orden descendente de ahorro
5- Mientras spl no esta vacio, elige y elimina el par de vertices mas alto y fusiona sus
viajes asociados, verifica las limitaciones en el rango de conducción y el tiempo. Si se
satisfacen ambas restricciones se agrega a la lista de factibilidad. Si el tiempo es
menor. Si el resultado solo cumple con la restricción del tiempo, se agrega una
estación de reabastecimiento, si no logra cumplir se descarta el recorrido
Esta heurística es un algoritmo iterativo que termina con una lista de soluciones factibles que
empiezan y terminan en el depósito en donde los nodos no se repiten. El numero puede ser
menor o mayor que m (la cantidad de vehículos disponibles) lo que puede ayudar a la
compañía a decidir la cantidad de vehículos que necesita en la flota para operar de la manera
más eficiente posible.
Una característica intrínseca de las soluciones de las VRP clásicas es la aciclicidad, peor, en la
mayoría de los casos, cada vertice puede ser visitado solo y solo una vez. Sin embargo en G-
RVP los ciclos están permitidos si pasan por una estacion de reabastecimiento, y pueden ser
visitados por múltiples vehículos o por ninguno
El algoritmo de densidad basado en clusters
La ubicación relativa de clientes y su distribución en el espacio, afectan la factibilidad y el
numero de visitas necesarias a estaciones de reabastecimiento.
La idea es que para cada vértice de un cluster, la vecindad de un cierto radio debe contener un
mínimo de vertices.
La figura ilustra un ejemplo con 20 vértices de cliente, 3 AFS, donde los clusters se forman con
un mínimo de 4 vértices y un radio de 30 millas.
Un vecindario de radio eps de un vértice vj, es definido por un set de vértices que están dentro
de un radio eps
Un cluster es una serie de nodos que son alcanzables por densidad directa, es decir, que
satisfacen las condiciones: el nodo pertenece al vecindario y el vecindario tiene mayor o igual
cantidad de vértices que el mínimo.
En este caso se arman los clusters con vertices que están directamente conectados por
densidad o son alcanzables por densidad. Por ejemplo en el cluster 3, el vertice 17 esta
conectado por densidad con el 5, y el vertice y es alcanzable a través de 17
El algoritmo funciona asi
1- Se buscan los vertices base, que son los que satisfacen las condiciones y se le asigna un
ID de cluster
2- Todos los vértices que se encuentran en el vecindario de los vertices raíz se marcan
con el mismo ID que el vértice base
3- Para cada vertice vi con un ID, para cada vertice vj sin ID que esta conectado a Vi,
asignar el mismo ID
4- Para cada vertice vi sin ID, asignar el ID del vertice vj con el ID mas cercano a Vi
Ambas heuristicas se juntan para construir una serie de viajes factibles
Primero se arman los clusters con DBCA y luego se arman los recorridos dentro de cada cluster
con MCWS
