Problema de enrutamiento de vehículos

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Una figura que ilustra el problema de enrutamiento del vehículo

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]

Instalando el problema[editar]

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[editar]

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.

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.

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

Métodos de solución exacta[editar]

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

  1. 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]
  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]
  3. 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 cúal es la colección de rutas con coste mínimo que satisface las restricciones del VRP.[2]

Formulaciones de flujo del vehículo[editar]

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

sujeto a

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]

Software libre para solucionar VRP[editar]

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

Ver también[editar]

Referencias[editar]

  1. Dantzig, George Bernard; Ramser, John Hubert (October 1959).
  2. a b c d e f g h The vehicle routing problem.
  3. a b editors, Geir Hasle, Knut-Andreas Lie, Ewald Quak,; Kloster, O (2007).
  4. Comtois, Claude; Slack, Brian; Rodrigue, Jean-Paul (2013).
  5. Beck, J.C.; Prosser, P.; Selensky, E. (2003).