Universidad de Buenos Aires
Facultad de Ciencias Exactas y Naturales
Departamento de Computación
Solving the capacitated location-routing problem
by a GRASP complemented by a learning process
and a path relinking
Christina Prins, Caroline Prodhon, Roberto Wolfler
Calvo
Institute Charles Delaunay, University of Technology of Troyes, France
Springer-Verlang 2006
Outline
• El problema de Localización y Ruteo
• Definición y Modelo Lineal
• Componentes de la heurística GRASP
•Heurística Greedy randomizada
•Búsqueda Local
•aprendizaje
• Post-Optimización: Path relinking
• Resultados
Location Routing Problems (LRP)
• Dos problemas en uno – Location and Routing
– Cuando estos problemas se resuleven por separado, se puede llegar a
soluciones subóptimas (Salhi and Rand, 1989)
– NP-Hard
• Se tiene un conjunto de posibles ubicaciones para los depósitos
(facilities)
• Vehículos que inician y finalizan sus rutas en los depósitos abiertos.
• Clientes que requieren algún tipo de mercancía o servicio.
• Hay muchas variantes de este problema:
–LRP General
–LRP con depósitos acotados
–LRP dónde los rutas acotadas
–Determiníticos
–Estocásticos
Enfóques
• Métodos exactos – pocos trabajos
– Branch and Bound
– Branch and Price
– Cutting Planes
– Branch and Cut
• Heuristicas y Metaheurísticas
– Hierarchical
– Iterative
– Clustering-based
– Cooperativas
Localización y Ruteo - Definición
• Se tiene un conjunto de ubicaciones potenciales dónde se pueden
abrir depósitos. Cada apertura tiene un costo fijo asociado y puede
tener una capacidad máxima asociada (versión con capacidad).
• Hay un conjunto de clientes que demanda mercaderías. Cada
cliente tiene que ser servido atendido por un único vehículo y se
debe satisfacer el total de su demanda.
• Se tiene una flota de vehículos que inician y terminan sus rutas en
un mismo depósito. La versión con capacidad requiere además que
la capacidad máxima de cada vehículo no sea sobrepasada.
La cantidad de vehículos usados es una variable de decisión. Se
suponen flotas homogéneas.
• Objetivo: minimizar los costos del ruteo (distancias recorridas), el
costo de apertura de depósitos y el costo por vehículo utilizado.
Modelo Lineal
•
I es el conjunto de posibles ubicaciones para los depósitos y J el
conjunto de clientes. Se define el grafo dirigido G=(V, A, C) conV=IJ.
• El grafo contiene todos los ejes excepto los que conectan depósitos
entre sí.
• Para cada eje a=(i, j)  A, se tiene un costo Ca asociado.
• Cada cliente j  J tiene una demanda dj asociada.
• Se tiene además, un costo fijo Oi y una capacidad máxima Wi
asociados a la apertura de un depósito en la ubicación i  I.
• Los vehículos tienen todos la misma capacidad Q, y usar cada
vehículo provoca un costo fijo F.
Modelo Lineal
• Notación:
G = (V, A, C)
I = Clientes
J = Posibles ubicaciones para los depósitos
Variables: yi = 1 si el depósito i es abierto
xak = 1 si el eje a es usado en la ruta del vehículo k
fij = 1 si el cliente j es asignado al depósito i.
Formulación lineal
Heurística GRASP
(Feo, T.,Resende, M.,”Greedy randomized adaptive search procedures”,
Journal of Global Optimization, 1995, pp 1,27)
Esquema de un algoritmo GRASP
-----------------------------------------------------------------------Mientras no se verifique el criterio de parada
ConstruirGreedyRandomizedSolución ( Solución)
Búsqueda Local (Solución)
ActualizarSolución (Solución, MejorSolución)
End
----------------------------------------------------------------
Heurística Greedy Randomized
Se usó una variación del clásico algorítmo de ahorros de Clarke y
Wright (1964).
Esquema básico del algorítmo (CWA) para un solo depósito:
• Inicialmente se arma una ruta por cliente
• Combinar rutas de a pares hasta que no se pueda combinar
ninguna ruta más porque se violarían las capacidades máximas de
los vehículos (se van combinando los mejores ahorros primero).
Se puede implementar este algorítmo en O(n3) y, si se usa un
heapsort con los ahorros precalculados se puede implementar en
O(n2 log n)
Heurística Greedy Randomized
Se usa una versión de Clarke y Wright extendida (ECWA) adaptada a
múltiples depósitos.
• Se crea una ruta inicial para cada cliente eligiendo su depósito
más cercano.
• Después de asignar todos los clientes, los depósitos sin asignar
son cerrados.
• Cuando dos rutas R y S de combinar en ECWA, la ruta resultante
T puede ser reasignada al depósito r de R, al depósito s de S o a
otro depósito t distinto (que puede estar abierto o cerrado).
• Si en el proceso, un depósito queda sin rutas, puede ser cerrado.
Se puede implementar este algorítmo en O(m n3) y, si se usa un
orden precalculado y heapsort en O(m n2 log n).
Ejemplo de combinaciones en CWA y ECWA
Heurística Greedy Randomized
En la heurística se usa una versión randomizada de ECWA.
Se crea una lista restringida de candidatos RCL de tamaño  sobre la
lista de posibles combinaciones. Se elige al azar entre estos
candidatos para determinar la próxima combinación de rutas.
Algunos trabajos muestran que cambiar  durante el GRASP produce
mejores resultados (Prais y Rebeiro 2000; Resende y Rebeiro
2003) -> GRASP Reactivo.
Se aplica esta técnica en la heurística seleccionando  de acuerdo a
una distribución uniforme [1, max] en cada combinación.
Búsqueda Local
Se exploran 3 vecindarios en el siguiente orden:
• MOVE: Se cambia de posición un cliente. Puede ser en la misma
ruta, o en otra. En el mismo depósito o en otro (respetando
capacidades máximas).
• SWAP: se intercambian 2 clientes. Tienen que estar en la misma
ruta o, si las capacidades residuales lo permiten, en rutas
diferentes y/o depósitos diferentes.
• OPT: Movimiento 2-opt. Se reemplazan 2 ejes de la misma ruta o
de rutas diferentes (mismo depósito o no). Se tienen que
satisfacer capacidades. (primer caso de movimientos 2-OPT Lin y
Kernigham 1973).
Búsqueda Local
El algorítmo efectúa el primer movimiento con mejora que encuentra.
Se repite mientras haya mejoras
No se permite abrir nuevos depósitos durante la búsqueda local.
En la implementación se logra efectuar la búsqueda en los 3
vecindarios con un costo O(n2).
Algorítmo básico GRASP
Proceso de aprendizaje
El algoritmo ECWA elegido suele tener problemas para seleccionar
buenos subconjuntos de depósitos abiertos.
Como esto tiene una correlación directa con la calidad de las
soluciones se decidió “ayudar” al algoritmo ECWA.
Para ello se crea un subconjunto SD de depósitos disponibles.
SD varía en cada iteración.
La primer iteración SD contiene todos los posibles depósitos de I
ECWA construye las rutas iniciales usando sólo los depósitos de SD.
Si no alcanzan para satisfacer las demandes se agrega el depósito
cerrado que se encuentra más cerca a SD.
Proceso de aprendizaje
La heurística itera en 2 modos posibles:
Modo diversificación
se aplica durante maxitdiv iteraciones.
Se intenta explorar el espacio de soluciones variando el conjunto
de depósitos abiertos. En cada iteración se genera un SD
aleatorio con 2 depósitos: uno seleccionado iterativamente de I
(para asegurarse que cada depósito seguro se elige al menos 1
vez) y otro al azar entre los restantes.
Modo Intensificación
se aplica durante maxitint iteraciones.
Restringe el nivel de aleatoriedad. Se usan para inicializar ECWA
los depósitos abiertos en la mejor solución encontrada durante el
último período de diversificación (almacenada en bsolndiv).
Post-Optimización: Path relinking
PR se puede aplicar como una forma de intensificación o como una
post-optimización.
En el primer caso, se calcula PR sobre cada uno de los óptimos
locales obtenidos en cada iteración del algoritmo principal.
Post-optimización se efectúa al finalizar la optimización y pretende
mejorar los resultados efectuando PR sobre las mejores soluciones
encontradas (soluciones elite).
En este trabajo se decidió utilizar PR como post optimización.
Post-Optimización: Path relinking
Para aplicar PR se definió a “distance” D(T, U) entre 2 soluciones T y
U.
Se puede definir de la siguiente manera:
Para cada par (i, j) de clientes consecutivos en T se consideran 4
casos:
• Los pares (i, j) o (j, i) se encuentran en U -> No contribuye al
cálculo de la distancia.
• i y j no son más adyacentes en U pero están en una misma ruta
-> suma 1 a la distancia.
• i y j están en rutas diferentes en U, pero en el mismo depósito ->
suman 3.
• i y j están en diferentes depósitos en U -> suman 10.
Además, cada cliente i servido al principio de una ruta en T, suma 10
si i está asignado a otro depósito en U.
Post-Optimización: Path relinking
D no es una función de distancia porque no cumple desigualdad
triangular, pero
D(T, U) >= 0 y T=U  D(T, U)=0 Además, detecta soluciones
equivalentes (renumeraciones de rutas e inversión de rutas).
Post-Optimización: Path relinking
El procedimiento efectuado busca 2 trayectorias entre cualquier par
de soluciones elite -> calcula la trayectoria de U a T y de T a U
NBestSet es el conjunto de las Nbest mejores soluciones encontradas
durante el modo de diversificación.
DistSet es el conjunto de las NMaxDist soluciones usadas para el PR
(grupo elite).
Se introduce en DistSet la mejor solución encontrada. Luego, entre
las NBestSet soluciones, se elige la más lejana con respecto al
conjunto. Para ello se usa la función distancia definida.
Se repite hasta llegar a NMaxDist soluciones.
Post-Optimización: Path relinking
Para un par de soluciones (T, U),
U se transforma en T paso a paso.
para ello, se agregan a U los ejes que reparan pares de clientes (i, j)
“rotos” en el orden en que se encuentran en T.
Para cada par de clientes consecutivos (i, j) en T pero no adyacentes
en U, se dice que el par está “roto”.
Para arreglar un par roto se corre la secuencia completa de clientes
localizados después de i en T.
Esto se repite mientras no se violen las capacidades máximas.
En caso de que se sobrepasen las capacidades máximas se hacen
movidas de corrección para dejar la solución correcta.
Algoritmo
Resultados
Después de testeos empíricos se decidió usar max=7
maxitint = 5 (iteraciones de intensificación).
maxitdiv = 7 (iteraciones de diversificación).
maxit = 60 (cantidad máxima de iteracines) para tener 5 cambios de
modos (diversificación / intensificación)
NBest=10
NMaxDist=3
Descargar

Un algoritmo de Branch&Cut para el problema de Ruteo …