4. RESOLUCIÓN DEL PROBLEMA DE RUTEO DE …bibing.us.es/proyectos/abreproy/5166/fichero/Volumen+1%2FCapítulo... · 4.4. Algoritmos para el VRP Los problemas derivados del transporte

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.




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




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.




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.




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.




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].




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




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.




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.




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.




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.




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.




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.

Documents

4. RESOLUCIÓN DEL PROBLEMA DE RUTEO DE …bibing.us.es/proyectos/abreproy/5166/fichero/Volumen+1%2FCapítulo... · 4.4. Algoritmos para el VRP Los problemas derivados del transporte