Problema de rutas de vehículos

El problema de rutas de vehículos (VRP por sus siglas en inglés) es uno de los problemas combinatorios más importantes y ampliamente estudiados, debido a que tiene su aplicación en la logística de reparto y transporte1. Este problema es de gran importancia en sistemas de distribución, ya que el proceso de transporte representa entre el 10 y el 20% del costo final de los bienes2. Además, se estima que los costos de distribución equivalen a casi la mitad del costo total de la logística3.

El VRP se puede definir como sigue. Se tiene un conjunto de clientes distribuidos geográficamente, quienes tienen cierta demanda de producto. Se tiene también un almacén en donde se encuentra centralizado el producto. Para satisfacer la demanda de los clientes, se cuenta con un una flotilla de vehículos cuya base es el almacén. El problema consiste en diseñar un conjunto de rutas de costo mínimo para proveer el producto a los clientes, de tal forma que:
  • cada ruta comienza y termina en el almacén,
  • cada vehículo se encarga de recorrer un ruta,
  • cada cliente es atendido por exactamente un vehículo y
  • la demanda de todos los clientes es satisfecha.
El VRP tiene muchas variantes que toman en cuenta diferentes restricciones, las cuales se pueden categorizar como operacionales y de precedencia. Algunas de estas variantes son:
  • Problema de rutas de vehículos con capacidad limitada (CVRP por sus siglas en inglés), en donde se considera una flotilla homogénea de vehículos, los cuales tienen una capacidad limitada.
  • Problema de rutas de vehículos con ventanas de tiempo (VRPTW), en donde cada cliente tiene un horario predeterminado durante el cual debe ser atendido.
  • Problema de rutas de vehículos con recolecciones (VRPB), en donde existen dos tipo de clientes: los clientes que requieren el producto y los clientes que lo devuelven.
  • Problema de rutas de vehículos con recolecciones y entregas (VRPPD), también conocido como problema de recolecciones y entregas (PDP), en donde se consideran órdenes de transporte que involucran un cliente origen, un cliente destino y una cantidad a transportar. Es decir, esta variante no considera que el producto está en el almacén, sino en algunos de los clientes.

1 R. Baldacci, M. Battarra y D. Vigo. Routing a heterogeneous fleet of vehicles. En B.L. Golden, S. Raghavan y E.A. Wasil, eds., The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 3-27. Springer, 2008.
2 P. Toth y D. Vigo. An overview of vehicle routing problems. En P. Toth y D. Vigo, eds., The vehicle routing problem, pp. 1-26. SIAM, 2001.
3 B. De Backer, V. Furnon, P. Kilby, P. Prosser y P. Shaw. Local search in constraint programming: Application to the vehicle routing problem. En 1997 Workshop on Industrial Constraint Directed Scheduling, pp. 1–15. 1997.