4. resoluciÓn del problema de ruteo de...
Post on 07-Oct-2018
220 Views
Preview:
TRANSCRIPT
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
27 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
4. RESOLUCIÓN DEL PROBLEMA DE RUTEO DE
VEHÍCULOS (VRP)
4.1. Introducción al Problema de Ruteo de Vehículos
Para comprender el mecanismo de los algoritmos de cálculo de rutas, primero
se deben entender los problemas para los que están diseñados, además de
comprender las diferentes variantes que pueden surgir. Por esta razón se realiza
una ligera introducción a este tipo de problema más conocido por su
denominación en inglés “Vehicule Routing Problem” (VRP).
El principal objetivo del problema de ruteo de vehículos [25] es suministrar los
pedidos a un grupo de clientes que por lo general se encontrarán dispersos a lo
largo de una zona geográfica de manera que se minimice el coste.
Principalmente las características de este problema son:
1. Se cuenta con demanda determinista (conocida), exceptuando a la
variante del problema que sufre demandas estocásticas.
2. Las entregas deben realizarse con el mínimo coste, para ello se deben
optimizar las rutas de los vehículos que tienen origen y final en el
depósito o almacén.
Los clientes solo pueden ser atendidos una vez, por lo tanto, el vehículo que le
suministre el pedido deberá tener una capacidad mayor que la demanda total
del cliente.
Todos los clientes deben ser atendidos una sola vez, por lo que a cada uno le
visitara un vehículo con una capacidad de carga mayor que la demanda del
cliente. Todas las variantes de un problema de ruteo de vehículos tienen tres
aspectos comunes:
1. Los clientes:
Un cliente tiene siempre una demanda que tendrá que ser satisfecha por
un solo vehículo. Para la mayoría de los problemas, la demanda es un
producto o un bien que tiene asignado un volumen dentro del vehículo.
Pero a veces, la demanda no se entiende como un bien o un producto,
sino como simplemente la realización de un servicio que dura cierto
tiempo, así, en estos casos el vehículo solo deberá visitar al cliente.
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
28 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
A lo largo del capítulo, se mostrarán los diferentes VRP en los cuales los
clientes tienen restricciones temporales, por ejemplo, sobre cuando
pueden ser atendidos y cuando no. Se crean las denominadas ventanas
temporales.
2. El depósito o almacén:
Tanto los bienes a distribuir vehículos como los vehículos suelen
encontrarse ubicados en depósitos o almacenes. Generalmente las rutas
seguidas por los vehículos de reparto empiezan y finalizan en el
depósito. Se puede dar el caso de tener varios depósitos con una flota
determinada de vehículos.
Pueden existir restricciones temporales asociadas a la carga de los bienes
en los vehículos, es decir, ventanas temporales sobre el depósito, con el
objetivo de evitar que varios vehículos acudan a la vez a cargar la
mercancía al depósito.
3. Los vehículos:
La “capacidad” de un vehículo de transporte puede expresarse en
términos de volumen, de peso, de número visitas máximas a clientes,
etc. y en ciertos problemas es deseable que la capacidad soportada por
cada vehículo sea más o menos pareja.
Cada vehículo, por lo general, se asume que recorrerá una única ruta
durante el horizonte temporal, pero en los últimos años se han realizado
estudios de modelos en los que el número de rutas de un vehículo puede
ser mayor.
4.2. El VRP en la práctica.
Debido a la importancia que ha cobrado en los últimos siglos el transporte de
mercancías como una necesidad de una sociedad moderna, el VRP se ha
desarrollado con velocidad, obteniendo una capacidad de aplicación fuerte en
múltiples sectores.
Un factor muy importante para el desarrollo económico de una región es contar
con una buena red de transporte, donde la relación y la comunicación entre los
diferentes sistemas de transporte son básicas. A lo largo de la historia, se ha
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
29 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
demostrado que las regiones con mejores redes de transporte han prosperado
más que las que no lo poseen, y eso entre otros factores se debe a que su
existencia facilita las relaciones comerciales entre las empresas.
Para una empresa, la reducción de costes es una de las tareas que siempre está
en continua gestación. Una buena política de logística por parte de la empresa
permitirá a ésta una disminución muy considerable de los costes asociados y
repercutirá directamente en el margen de beneficio de ésta. Para una empresa
que preste servicios de entrega comprometidos en tiempo, el VRP se convierte
en un problema fundamental a resolver con el mejor resultado posible, puesto
que competirán con las demás empresas ofreciendo un mejor servicio [14].
El VRP es motivo de estudios continuados ya que es un reto resolver el modelo
de una manera óptima. Para casos en los que el problema no consta de muchos
nodos (clientes), es posible encontrar soluciones exactas numéricamente en
tiempos razonables. Sin embargo, a medida que el problema aumenta de
tamaño, los tiempos se van haciendo muy grandes y llega a ser inviable su
resolución tanto por tiempo de resolución como por lo complicado del modelo.
Matemáticamente el VRP se dice que es un problema del tipo NP.
Llegar a saber a qué grupo pertenece cada problema es primordial, ya que
permite no intentar resolver el problema con un algoritmo exacto y optar por
aplicar métodos no exactos de resolución que sin embargo pueden obtener un
resultado muy aproximado al óptimo. Estos métodos no exactos son las
heurísticas y metaheurísticas. El alcanzar una solución cercana al óptimo, en la
mayoría de los casos reales donde se aplican estos métodos, es ya considerado
como un buen resultado. Aplicar heurísticas o metaheurísticas proporciona
estas soluciones y disminuyen considerablemente el tiempo empleado para ello
con respecto a los métodos exactos [18].
La variedad de VRP existentes hace que la función objetivo de estos problemas
no sea siempre alcanzar la ruta más corta posible, sino que se debe buscar la
solución óptima respetando las restricciones impuestas intentando obtener el
menor coste posible.
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
30 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
4.3. Variantes del VRP
La base del problema es siempre el VRP original, pero en los casos reales, los
diferentes VRP tienen una serie de restricciones con aspectos muy
característicos que hacen que cada uno se enfoque de manera diferente.
A continuación se encuentran expuestas algunas de las variantes principales del
Vehicule Routing Problem, cuyos modelos pueden ser resueltos por algoritmos
cada vez más avanzados en la búsqueda conjunta de mejorar la función objetivo
mientras se respetan las restricciones del problema. En la figura 2 se muestra la
relación entre ellas:
Figura 2: Variantes principales de VRP
1. Capacited VRP (CVRP): Para esta variante del VRP se tiene una capacidad
de carga uniforme en los vehículos y se debe minimizar el coste de
transporte de atender las demandas conocidas de los clientes [8].
Así, sobre el problema original VRP se añade la restricción de capacidad de
que los vehículos poseen una capacidad de carga uniforme de un solo
producto.
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
31 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
2. Multiple Depot VRP (MDVRP): Se dispone de varios depósitos desde los
que pueden ser atendidos los clientes. Si es posible separar grupos de
clientes que estén cerca de cada depósito, podría resolverse el problema
como un conjunto de problemas independientes VRP.
En el MDVRP se requiere una asignación de cada cliente a un depósito,
además de conocer el número de vehículos establecidos en cada depósito.
Un vehículo inicia su ruta en un depósito, atiende a sus clientes y regresa al
depósito.
3. Periodic VRP (PVRP): Es la variante que tiene en cuenta que el periodo se
extiende a varios días, y por lo tanto su planificación. En el VRP original, el
periodo de planificación es de un día.
4. Split Delivery VRP (SDVRP): En esta variante la restricción que limita la
visita de un cliente a una sola vez es eliminada, y por lo tanto, un vehículo
pasa a poder visitar a un cliente más de una vez a lo largo del horizonte
temporal.
5. Stochastic VRP (SVRP): En este caso, uno o más de los datos que en el VRP
original eran conocidos serán en este caso aleatorios. Podrían ser los
clientes, las demandas…
6. VRP with Backhauls (VRPB): La particularidad de esta variante es que
existe la posibilidad de que se produzca una recogida o entrega de bienes a
los clientes.
7. VRP with Pick-Up and Delivering (VRPPD): Como su propio nombre
indica, se realiza una recogida de mercancía de ciertos clientes y se reparte
en otros.
8. VRP with Satellite Facilities (VRPSF): Es un caso especial ya que se permite
el reabastecimiento de vehículos sin necesitar que vuelvan al depósito.
9. VRP with Time Windows (VRPTW): Esta variante introduce las ventanas
temporales. Se establece o puede establecerse un intervalo de tiempo en el
que se permite o se restringe la entrega de mercancía a los clientes, también
pudiendo tener restricciones temporales el acceso de los vehículos al
depósito.
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
32 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
10. VRP with Access Time Windows (VRPATW): En el VRPATW se agrega una
restricción temporal relacionada con el acceso a ciertas zonas de las
ciudades. Este tipo de problemas surge de la restricción por parte de las
administraciones locales de acceder a ciertas zonas de la ciudad
(principalmente el centro de la ciudad) durante una franja horaria del día
determinada debido a razones sociales, ambientales y económicas.
En general, cada problema VRP de la vida real supone en sí mismo una variante
del problema original, ya que cada caso tiene sus características y restricciones
propias. Es por esto que necesitan “adaptarse” los algoritmos existentes al
problema concreto.
4.4. Algoritmos para el VRP
Los problemas derivados del transporte de mercancías están relacionados de
manera directa con el VRP, pero éste a su vez no solo se ha desarrollado en ese
ámbito, sino en muchos otros, por lo que se convirtió pronto en un problema
importante de optimización, para el que se han desarrollado diversas
soluciones a lo largo de las últimas cinco décadas.
Fueron Dantzing y Ramser quienes en 1959 propusieron un método de
resolución para un modelo que representaba una situación real. Se modeló el
abastecimiento de las gasolineras de combustible, y éste método se convirtió en
la primera formulación matemática para solucionarlo.
G. Clarke y J.M. Wright [4] presentaron en 1964 un método heurístico capaz de
mejorar la solución conseguida por Dantzing y Ramser. A partir de ahí, han
aparecido una gran cantidad de métodos para resolver las diversas variantes
del VRP. En algunos casos se intenta encontrar la solución óptima, en otros
simplemente una buena aproximación a ella. Las metodologías de resolución se
agrupan según la finalidad y el modo de intentar obtener la solución.
Se va a proceder a presentar algunos de los métodos más importantes en la
resolución de problemas VRP hasta la fecha. La mejora de estos métodos es
continua y acaban existiendo muchas posibilidades a la hora de afrontar una
familia de problemas. Las distintas necesidades de recursos de cada algoritmo
de resolución provocan que existan ventajas e inconvenientes relacionadas con
los tiempos de computación necesarios para resolver los problemas [18].
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
33 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
Se distinguen tres familias de algoritmos utilizados para resolver el VRP, las
cuales se listan a continuación:
1. Los métodos Exactos
2. Los métodos Heurísticos. Dentro de ellos, se explican brevemente los
siguientes algoritmos:
a) Clarke & Wright.
b) Método del barrido.
c) Búsqueda local (Lin y Kernighan)
3. Los métodos Metaheurísticos. De los cuales, los más destacados son los
siguientes:
a) GRASP.
b) Algoritmos Genéticos (GA).
c) Búsqueda Tabú.
d) Simulated Annealing (SA).
4.4.1. Métodos Exactos
Debido a la complejidad de los modelos matemáticos, solo los problemas con
hasta 100 clientes (aproximadamente) pueden ser resueltos mediante métodos
exactos. En estas metodologías, la resolución suele aplicarse a problemas
relajados y suelen utilizarse variantes del método Branch and Bound
(ramificación y poda). Además, se han desarrollado algoritmos de
programación dinámica, los cuales se ven acelerados los cálculos a partir de
una relajación del espacio de estados. Sobresale también el método de
generación de columnas, que resulta ser muy efectivo en problemas con
ventanas temporales muy ajustadas.
Destacamos dos métodos exactos para resolver problemas VRP: El método de
Branch and Bound (Ramificación y Poda) y el método de Branch and Cut
(Ramificación y Corte) [3]:
1. Branch and Bound (Ramificación y poda): Este método se basa en la idea
de “divide y vencerás”. Con dividir se refiere a ramificar el conjunto de
soluciones enteras en subconjuntos separados cada vez de menor
tamaño. Posteriormente se determina el valor de la mejor solución del
subconjunto. En base a una cota superior o inferior establecida el
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
34 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
algoritmo elimina (poda) la rama del árbol que no puede contener la
solución óptima.
2. Branch and Cut (Ramificación y Corte): Es una mezcla de métodos en sí
mismo basado en el método de Branch and Bound y también en el
método de planos de corte en los nodos. Primero se comienza eligiendo
un nodo al que evaluar (inicialmente el nodo raíz). Posteriormente
decide si se van a generar planos de corte o no. Finalmente se aplican los
criterios del método de ramificación y poda.
Debido a que generalmente los métodos exactos se aplican solo a problemas con
una pequeña cantidad de nodos, son desarrollados en su mayoría para fines
académicos, ya que en los problemas reales de VRP se tiene una estructura
nodal muy amplia y por lo tanto no son recomendables porque requerirían
mucho tiempo de computación.
4.4.2. Métodos Heurísticos
1. Algoritmo de Clarke & Wright (Método de los ahorros)
Este algoritmo se diseñó para un problema donde existe un depósito central y
se cuenta con uno o más vehículos de entrega para n clientes, cada una
demanda conocida previamente. El objetivo principal es proporcionar las rutas
de los vehículos que hagan que se cumpla la demanda de cada cliente
respetando las restricciones de minimización de costes.
G. Clarke y J.M. Wright en “Scheduling of Vehicles from a Central Depot to a
Number of Delivery Points” [4], proponen un algoritmo para resolver el
problema. Este algoritmo de Clark & Wright consigue soluciones aceptables, y
es bastante utilizado en la práctica, por su simplicidad de aplicación y por el
poco tiempo que se precisa para resolver el problema.
Se identifica el depósito en la localización 0, y los clientes en las localizaciones
posteriores hasta n, y se consideran conocidos los costes por trayecto desde el
depósito a cada cliente; esto es:
coj = Coste de realizar el trayecto desde el depósito hasta el cliente.
Para desarrollar el método, es fundamental conocer el coste del trayecto entre
todos los clientes, lo que significa que se considera que se conocen todos los
costes de cada trayecto.
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
35 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
cij = Coste de realizar el trayecto desde el cliente i al cliente j.
En la práctica, se hace la consideración de que cij = cji, para todo i>=1 y n>=j.
Se expone una explicación de cómo procede el algoritmo a continuación:
Primero debe suponerse que hay una asignación de vehículos hecha para cada
cliente. Es una solución inicial compuesta por n rutas desde el depósito hasta
cada cliente. Así el coste total derivado de todas las rutas en este caso es:
∑
Posteriormente, se realiza el enlace entre los clientes i y j, lo que provoca que
ahora el vehículo se dirija desde el depósito a i, después a j y finalmente regrese
al depósito.
Tras realizar esto, se ha conseguido un ahorro en el coste de:
( ) ( )
El algoritmo calcula para cada posible pareja de combinaciones (i,j) el ahorro Sij
ordena los resultados en orden decreciente. El número total de combinaciones
posibles viene determinado por el número combinatorio:
( )
2. Método del Barrido.
En este método, se representa el mapa de clientes y el depósito como puntos
sobre un plano en coordenadas polares (r,), siendo r la distancia en línea recta
entre el depósito y el cliente, y el ángulo formado entre los dos
Se procede haciendo rotar una recta con origen en el depósito y “barrer” el
plano hasta que las demandas de los clientes que han sido barridos sean igual a
la capacidad máxima permitida por el vehículo.
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
36 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
Así, obtenemos diversos conjuntos de clientes donde la suma de la demanda
total requerida por cada conjunto es menor o igual a la que un vehículo es
capaz de suplir debido a su limitación de capacidad.
Para obtener la mejor ruta dentro de cada conjunto debe emplearse un
algoritmo destinado a esté a fin, como podría ser el anteriormente comentado
“Método de los ahorros”, consiguiendo así la ruta más económica posible para
cada conjunto.
La figura 3 muestra el modo en el que se forman los conjuntos de clientes
donde la demanda total es menor o igual que la que es capaz de proporcionar
un vehículo limitado por su capacidad.
Figura 3: Ejemplo Método de Barrido
3. Técnicas de búsqueda local
En este caso, el algoritmo también parte del conocimiento de una solución
inicial que deberá mejorar progresivamente. En cada iteración, el algoritmo se
mueve hacia una solución mejor que la anterior y el proceso global finaliza
cuando no es posible encontrar el movimiento que hace que la solución mejore.
Debido al procedimiento de las técnicas de búsqueda local, es normal que
lleguen a obtener la solución correspondiente de un óptimo local.
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
37 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
Para resolver esta problemática, tendría que existir la posibilidad de que el
algoritmo pudiese moverse hacia soluciones “peores” para intentar encontrar
otra vía de avance hacia otro óptimo diferente del anterior. Esta posibilidad
conllevaría un algoritmo algo más complejo.
Lin y Kernighan desarrollaron un algoritmo que se basa en este hecho y
proponen movimientos compuestos, donde puede ocurrir un movimiento
simple que no mejore exclusivamente, pero que sin embargo, el global de todos
los movimientos si consiga mejorar la solución original.
La idea es la de realizar movimientos de mejora y de empeoramiento de forma
consecutiva, pero respetando la finalidad del algoritmo de manera que no se
pierda nunca el control sobre la mejora global de la búsqueda.
4.4.3. Métodos Metaheurísticos
Los métodos metaheurísticos están ligados a los procedimientos heurísticos ya
que intentan proporcionar mejoras sobre estos últimos. Se puede hacer una
clasificación según el tipo de heurística que se aborde, en este caso los métodos
metaheurísticos se clasifican en:
a) Métodos constructivos.
Aquellos donde se introducen elementos a una solución inicial vacía (algoritmo
GRASP).
b) Métodos Evolutivos.
Estos métodos construyen grupos de soluciones completas, realizan una
selección basándose en el valor de ciertos atributos, posteriormente se
combinan algunas de las soluciones seleccionadas y se remplazan finalmente el
grupo de soluciones (Algoritmo Genético, Búsqueda Dispersa).
c) Métodos de búsqueda.
Los métodos de búsqueda dan por hecho que debe existir una solución óptima
y ejecutan un procedimiento que no llega a la solución del óptimo global del
problema pero sí a una solución muy cercana a ésta. El riesgo más común de
estos métodos es el de obtener la solución de un óptimo local y quedar atrapado
en él.
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
38 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
Los métodos de búsqueda local más importantes se desarrollan según la
manera que tienen de salir del óptimo local. Hay tres maneras de proceder:
I. Retornar a una solución inicial diferente y volver a comenzar. (Multi
start)
II. Variación de la estructura de entornos. (Metaheurística de búsqueda de
entornos variables)
III. Realizar movimientos que empeoren la solución para salir del óptimo
local. Simulated annealing y Búsqueda Tabú.
1. GRASP. Greedy Randomized Adaptive Search Procedure
El algoritmo GRASP (en español puede traducirse como “Procedimiento de
Búsqueda Voraz Aleatorio y Adaptativo) fue desarrollado por (T.A. Feo and
M.G.C. Resende en 1995 [9] y se presentó como una metaheurística con
propósito general. En este método, cada iteración o paso, tiene dos fases:
construcción y mejora.
Durante la construcción se ejecuta una heurística constructiva de la que se
obtiene una solución inicial. Posteriormente en la fase de mejora, esta solución
inicial es tratada con un algoritmo de búsqueda local para ser mejorada.
El componente particular de este algoritmo es una función que se encarga de
seleccionar al elemento a incluir en la solución actual que proporciona el mejor
resultado sin llevar en consideración otros puntos de vista (de aquí la
característica de voraz)
El concepto de que es adaptativo viene de que tras cada iteración es actualizado
el beneficio conseguido tras la adición del elemento a la solución.
2. Algoritmo Genético
El algoritmo genético genera en cada iteración un grupo de soluciones. Las
soluciones posteriores resultantes son una mezcla de las soluciones anteriores.
Así, a diferencia de otros algoritmos, aquí no se produce la transformación de
una única solución.
La teoría de la evolución de las especies de Darwin es la base de este algoritmo.
Las soluciones generadas a partir de otras conservarán algunas características
de éstas dependiendo del grado de mutación que se quiera conseguir en cada
iteración.
Proyecto Final de Carrera - Francisco Vázquez Delgado 2012
39 Escuela Técnica Superior de Ingenieros
Universidad de Sevilla
La mutación es el aspecto aleatorio de este algoritmo, y gracias a esta
característica queda resuelta la problemática de los óptimos locales
anteriormente comentada.
3. Simulated Annealing (Algoritmo de Recocido Simulado)
Básicamente es un método donde se construyen nuevas soluciones de un modo
aleatorio basado en determinadas reglas probabilísticas.
Es un algoritmo denominado Hill-Climbing y está basado en el recocido de los
metales donde se "calienta" a alta temperatura el sistema que se quiere
optimizar, para después rebajar la temperatura lentamente, hasta que ya no
ocurran modificaciones en el sistema. Aunque los cambios de temperatura
durante el proceso real se dan de forma continua, en el algoritmo sólo se
producen de forma escalonada.
4. Búsqueda Tabú
El algoritmo búsqueda tabú está basado en el concepto de movimientos
prohibidos (movimientos tabú) dentro de la solución que se quiere mejorar.
Estos movimientos tabú permiten al algoritmo moverse por una zona más
amplia de posibles soluciones sin caer en soluciones anteriormente ya
encontradas. Es lo que se conoce como “memoria”, y en la búsqueda tabú se
encuentra el desarrollo de memoria tanto a corto plazo como a largo plazo.
Debido a esto, se dice que es una búsqueda inteligente que aprende a medida
que itera el algoritmo a partir de la solución inicial. El modo de salir de óptimos
locales encontrados es mediante técnicas de diversificación aleatorias pero
inteligentes, es decir, respetando a la memoria a largo plazo, que es la que guía
a la diversificación hacia zonas inexploradas.
top related