Problema de enrutamiento de vehículos

Posible artículo duplicado: Problema de rutas de vehículos

El problema de enrutamiento de vehículos (VRP, por su siglas en inglés) es un problema de optimización combinatoria y de programación de entero qué pregunta "¿Cuál es el conjunto óptimo de rutas para una flota de vehículos que debe satisfacer las demandas de un conjunto dado de clientes?". Es una generalización del conocido Problema del Viajante (TSP, por sus siglas en inglés). La primera definición aparece en una artículo de George Dantzig y John Ramser en 1959, en donde plantea una aproximación algorítmica y fue aplicado para entregas de gasolina.^[1] El problema, requiere la entrega de cierto producto, almacenado en un único local, a los clientes los cuales poseen cierta demanda; el objetivo fundamental es minimizar el coste total de las rutas trazadas. En 1964, Clarke y Wright mejoraron la aproximación de Dantzig y Ramser utilizando una aproximación “greedy” conocido como algoritmo de ahorros.

Determinar la solución óptima es un problema NP-duro de optimización combinatoria.^[2] Las implementaciones más utilizadas para resolver el problema se basan en heurísticas debido a que para grandes instancias del problema, que como sucede en ejemplos reales, producen buenos resultados. El VRP tiene muchas aplicaciones obvias en industrias. De hecho el uso de programas de optimización puede dar ahorros de 5% a una compañía cuando el transporte es normalmente un componente significativo del coste de un producto (10%) - de hecho el sector de transporte hace 10% de PIB de la UE.^[3]^[4] Consiguientemente, cualesquier ahorros crearon por el VRP, incluso aún, de un 5%, es significativo.^[3]

Existen principalmente tres elementos involucrados en el VRP, que son los clientes, las bodegas o depósitos y la flota de vehículos.En los problemas reales de VRP aparecen muchas restricciones, entre las que cabe citar:

Cada vehículo tiene una capacidad limitada.
Cada cliente tiene que ser visitado dentro de una determinada franja horaria (problema VRP con ventanas de tiempo)
Varios puntos de suministro (problema VRP con múltiples depósitos)
Los clientes pueden ser atendidos por varios vehículos (problema VRP con suministro dividido)
Algunas variables del problema son aleatorias, tales como el número de clientes, sus demandas, etc. (problema VRP estocástico)
Las entregas se deben realizar en determinados días (problema VRP periódico)

Instalando el problema

El VRP se encarga del servicio de una compañía de entrega, un depósito y un conjunto dado de vehículos, los cuales se mueven en una red de carretera dada, para entregar los productos a un conjunto de clientes. Determina un conjunto de rutas, S, (una ruta para cada vehículo que inicia y termina en el depósito) tal que todas las demandas de los clientes son satisfechas y el coste de la transportación total está minimizado. Esto cuesto puede ser monetario, distancia, tiempo, etc.^[2]

La red de carretera puede ser descrita utilizando un grafo donde los arcos son las carreteras y los vértices representan la localización de los clientes y del depósito. Los arcos pueden ser dirigidos o no, debido a costes diferentes en cada dirección o alguna variante del problema. Cada arco tiene un coste asociado.^[2]

La función objetiva de un VRP puede ser muy diferente dependiendo de la aplicación particular del resultado, unos de los objetivos más comunes son:^[2]

Minimizar el coste total del transporte basado en la distancia total recorrida con los vehículos utilizados.
Minimizar el número de vehículos utilizados satisfacer a todos los clientes.
Minimizar la variación entre el tiempo de viaje y la carga del vehículo.
Minimizar las penalizaciones por servicio de baja calidad.

Variantes del VRP

Un mapa que muestra la relación entre común VRP subproblems.

Ejemplos de variaciones y las especializaciones sobre problema de enrutamiento del vehículo:

Problema de Enrutamiento del Vehículo con Recogida y Entrega (VRPPD, por sus siglas en inglés): Un número de productos necesita ser movido de cierta ubicación de recogida hacia otras ubicaciones de entrega. El objetivo es encontrar las rutas óptimas para una flota de vehículos para visitar las ubicaciones de recogida y entregar los productos en sus correspondientes ubicaciones.
Problema de Enrutamiento del Vehículo con Ventanas de Tiempo (VRPTW, por sus siglas en inglés): Las ubicaciones de entrega tienen ventanas de tiempo, dentro del cual las entregas (o visitas) tiene que ser realizadas.
Problema de Enrutamiento del Vehículo con Capacidad (CVRP, por sus siglas en inglés): Los vehículos han limitado llevando capacidad de los bienes que tiene que ser entregado.
Problema de Enrutamiento del Vehículo con Viajes Múltiples (VRPMT, por sus siglas en inglés): Los vehículos pueden hacer más de una ruta.
Problema de Enrutamiento de Vehículo Abierto (OVRP, por sus siglas en inglés): Las rutas de los vehículos no necesitan terminar en el depósito.
Problema de Enrutamiento de Vehículo de Flota mixta (MFVRP, por sus siglas en inglés): es un tipo de VRP que difiere de la versión clásica en el uso de una flota de vehículos heterogénea que tienen diversas capacidades y costos variables. El costo de enrutamiento es la suma de los costos fijos y variables, y este último está dado en proporción a la distancia recorrida.^[5]

Problema de Enrutamiento de Vehículo con Múltiples Depósitos (MDVRPR, por sus siglas en inglés): este problema consta de varios depósitos con una flota de vehículos por cada depósito, los cuales deben atender la demanda de todos los clientes. Este modelo fue desarrollado mediante la técnica de clusterizar primero - rutear después.^[5]^[6]
Problema de Enrutamiento de Vehículo Periódico (PVRP, por sus siglas en inles): tiene en cuenta un periodo de tiempo durante el cual los clientes deben ser atendidos, este modelo fue propuesto por Francis resuelto mediante relajación lagrangiana,^[5] como es descrito por Hernández Ortiz Y. A. (2016).^[6]
Problema de Enrutamiento de Vehículo con Entrega Dividida (SDVRP, por sus siglas en inglés): es un derivado del VRP en el cual el mismo cliente puede ser servido por diferentes vehículos si se reducen los costos generales^[5]^[6]..
VRP estocástico: En la definición clásica del VRP, los parámetros asociados, tales como costos, demanda de los clientes y tiempos de viaje del vehículo, son determinísticos.^[5]

A pesar de que VRP está relacionado al Problema Planificación de una Tienda de Trabajo, los dos problemas son típicamente solucionados utilizando técnicas diferentes.^[7]

Métodos de solución

Hay tres diferentes aproximaciones principales a la modelización el VRP

Formulaciones de flujo del vehículo - esto utiliza variables de entero asociado con cada arco que cuenta el número de veces que la arista es recorrida por un vehículo. Es generalmente utilizado para el básico VRPs. Esto es bueno para casos donde el coste de la solución puede ser expresado como la suma de los costes asociado con los arcos. Aun así puede no ser usado en muchas aplicaciones prácticas.^[2]
Formulaciones de flujo de la mercancía - variables de entero adicional están asociadas con los arcos o aristas qué representan el flujo de las mercancías a lo largo de los caminos recorrido por los vehículos. Esto sólo ha sido utilizado recientemente encontrar una solución exacta.^[2]
Particionar el problema en conjuntos - tienen un número exponencial de variables binarias qué es asociado con una ruta factible diferente. El VRP es entonces formulado como un problema qué pregunta cual es la colección de rutas con coste mínimo que satisface las restricciones del VRP.^[2]

Formulaciones de flujo del vehículo

La formulación del TSP por Dantzig, Fulkerson y Johnson fue extendido para crear el flujo de dos índices para el VRP

${\text{min}}\sum _{i\in V}\sum _{j\in V}c_{ij}x_{ij}$

sujeto a

${\begin{aligned}&\sum _{i\in V}x_{ij}=1~~~~\forall j\in V\backslash \left\{0\right\}&(1)\\&\sum _{j\in V}x_{ij}=1~~~~\forall i\in V\backslash \left\{0\right\}&(2)\\&\sum _{i\in V}x_{i0}=K&(3)\\&\sum _{j\in V}x_{0j}=K&(4)\\&\sum _{i\notin S}\sum _{j\in S}x_{ij}\geq r(S)~~~~\forall S\subseteq V\backslash \left\{0\right\},S\neq \emptyset &(5)\\&x_{ij}\in \{0,1\}~~~~\forall i,j\in V&(6)\\\end{aligned}}$

Las restricciones 1 y 2 plantean que exactamente un arco entra y exactamente uno deja cada vértice asociado con un cliente, respectivamente. Las restricciones 3 y 4 dice que el número de los vehículos que dejan el depósito es igual al número que entra. La restricción 5 es la restricción de corte de la capacidad, la cual imponen que las rutas tienen que ser conectadas y que la demanda en cada ruta no tiene que superar la capacidad de vehículo. Finalmente, la restricción 6 define el dominio de las constantes.^[2]

HEURÍSTICAS APLICADAS AL RUTEO DE VEHÍCULOS

Las heurísticas son procedimientos simples que exploran el espacio de búsqueda de una forma limitada, generando soluciones aceptables, por lo regular en tiempos cortos de ejecución. Las soluciones obtenidas con estos procedimientos pueden ser mejoradas utilizando métodos de búsqueda más complejos como las metaheurísticas, que conllevan mayores tiempos de cálculo.^[6]

Algunas de las heurísticas utilizadas para resolver el VRP son las siguientes:^[6]

El Algoritmo de Ahorros -
Heurísticas de Inserción -
Métodos de asignación elemental -
Métodos Asignar Primero – Rutear Después -
Método Rutear Primero – Asignar Después -
Algoritmos de Pétalos -
Procedimientos de Búsqueda Local -

METAHEURÍSTICAS APLICADAS AL RUTEO DE VEHÍCULOS

A pesar de que se ha demostrado las ventajas de utilizar las heurísticas en problemas relacionados con el ruteo de vehículos, en muchas ocasiones estos procedimientos generan óptimos locales que pueden estar muy alejados de las soluciones óptimas globales. Para resolver este inconveniente se han desarrollado las denominadas "metaheurísticas", que son “estrategias maestras que permiten resolver de manera inteligente un problema”.^[6] Las metaheurísticas modifican a otras heurísticas combinando diferentes conceptos para producir mejores soluciones que las encontradas por ellas. Con la utilización de las metaheurísticas no se asegura la exploración completa del espacio de soluciones; sin embargo, estos procedimientos exploran aquellas regiones en las que es factible encontrar buenas soluciones. Una metaheurística puede evitar los problemas de óptimos locales y secuencias repetitivas de soluciones. Las metaheurísticas incluyen métodos tan populares como:

Optimización por colonia de hormigas (ACO) -
Algoritmos evolutivos (EA), donde se incluyen los algoritmos genéticos (GA) y los algoritmos meméticos (MA)n -
Procedimientos de búsqueda miope (constructiva, voraz o ávida), aleatorizados y adaptativos (GRASP) -
Búsqueda local iterativa (ILS) -
Re-encadenamiento de trayectorias (PR) -
Recocido simulado (SA) -
Búsqueda dispersa (SS) -
Búsqueda tabú (TS) -

Software libre para solucionar VRP

Varios vendedores de software han construido productos de software para solucionar variantes del VRP. Numerosos artículos están disponibles para más detalles del contenido de la búsqueda y resultados de estas variantes.

Nombre(alfabéticamente)	Licencia	API Lengua	Breve info
jsprit	LGPL	Java	Ligero, java basó, código abierto toolkit para solucionar rico VRPs. Enlace Un Excel-interfaz de usuario compatible para jsprit es disponible con mapeo, informando y la ruta que edita funcionalidad. Enlace
Abierto-VRP	LLGPL	Lisp	Abierto-VRP para Lisp, hosted en Github. Enlace
OptaPlanner	Licencia de apache	Java	Código abierto Java constreñimiento solver (optaplanner.org) con VRP ejemplos.
SINFONÍA	Licencia Pública común 1.0	Abierto-fuente solver para mixto-entero programas lineales (MILPs) con soporte para VRPs. Enlace Archivado el 28 de febrero de 2014 en Wayback Machine.
VRP Spreadsheet Solver	Creativo Commons Atribución 4.0 Licencia Internacional	Microsoft Excel y VBA basó código abierto solver, con un enlace a público GIS para datos retrieval. Vídeo de enlace enlace preceptoral
vrphlibrary (VRPH)	Licencia Pública común 1.0	Página de casa de código abierto VRPH enlace de software y hosting página encima MONEDA-O enlace.
vroom	?	Bibliotecas de código abierto para el VRP y dinámicos VRP. Enlace

Véase también

Problema de cartero chino
Problema de viajante
Problema de reprogramación del vehículo

Referencias

↑ Dantzig, George Bernard; Ramser, John Hubert (October 1959).
↑ ^a ^b ^c ^d ^e ^f ^g ^h The vehicle routing problem.
↑ ^a ^b editors, Geir Hasle, Knut-Andreas Lie, Ewald Quak,; Kloster, O (2007).
↑ Comtois, Claude; Slack, Brian; Rodrigue, Jean-Paul (2013).
↑ ^a ^b ^c ^d ^e Arboleda Zuñiga, Jairo; Lopez, Astrid; Lozano, Lorena (2016).
↑ ^a ^b ^c ^d ^e ^f Hernandez Ortiz, Yimi Alexander (2016).
↑ Beck, J.C.; Prosser, P.; Selensky, E. (2003).

Datos: Q944041

[DantzigRamser1959-1] Dantzig, George Bernard; Ramser, John Hubert (October 1959).

[toth-2] ↑ ^a ^b ^c ^d ^e ^f ^g ^h The vehicle routing problem.

[Springer_Verlag-3] tors, Geir Hasle, Knut-Andreas Lie, Ewald Quak,; Kloster, O (2007).

[4] Comtois, Claude; Slack, Brian; Rodrigue, Jean-Paul (2013).

[Arboleda,Lopez,Lozano,2016-5] Arboleda Zuñiga, Jairo; Lopez, Astrid; Lozano, Lorena (2016).

[Hernandez,2016-6] ↑ ^a ^b ^c ^d ^e ^f Hernandez Ortiz, Yimi Alexander (2016).

[Beck2003-7] Beck, J.C.; Prosser, P.; Selensky, E. (2003).

[1]

[2]

[3]

[4]

[5]

[6]

[7]