Problemas de Rutas. Taxonomía

Taxonomía de problemas de rutas

El problema de identificar la mejor manera para desplazarse de un sitio a otro ha preocupado a los seres humanos desde la Antigüedad. Y la comunidad científica no ha sido ajena a esa preocupación.

A este problema se enfrentan diariamente muchas empresas de transporte y lo resuelven fundamentalmente con intuición, alguna herramienta básica y muchos años de experiencia. Pero, ¿qué sucede si un planificador con iniciativa decide lanzarse e investigar un poco qué puede ofrecerle la ciencia para resolver su problema de forma optimizada?

Con una búsqueda rápida en cualquier repositorio científico encontrará cientos, sino miles, de artículos que abordan problemas relacionados con la optimización de rutas. Y, probablemente, acabará confundido con la diversidad de problemas abordados y la mezcla de siglas: HFVRP, TWVRP, TWTSP, …, ¿qué significa todo esto? Vamos a ver si somos capaces de aclararlo.

Existen dos modelos básicos de optimización combinatoria para la optimización de rutas, a partir de los cuales se crean muchos más simplemente añadiendo restricciones. Los dos modelos básicos son:

TSP (Traveling Salesman Problem o problema del viajante de comercio)
VRP (Vehicle Routing Problem)

El problema del viajante de comercio (TSP)

El problema del viajante de comercio es, conceptualmente, un problema muy sencillo. Un viajante de comercio debe visitar una serie de ciudades partiendo de una de ellas y regresando a la misma de tal manera que minimice la distancia recorrida. Es un problema clásico de la literatura científica, del cual hay referencias ya en el siglo XIX. A pesar de la sencillez de su definición es muy complejo de resolver, porque el número de posibles soluciones crece exponencialmente con el número de puntos a visitar.

Vehicle Routing Problem (VRP)

El VRP consiste en, dadas una serie de entregas a realizar y una flota disponible para hacerlas, que parte y retorna al mismo lugar, encontrar el conjunto de rutas que minimizan la distancia total a recorrer. Como se puede observar, el VRP es una generalización del TSP, en la que se dispone de una flota de vehículos. Además, los vehículos tienen una serie de restricciones (como tiempo máximo de ruta o capacidad) que tienen que cumplir, lo que hace que no se puedan realizar todas las entregas con el mismo vehículo.

Variaciones de los modelos básicos de optimización de rutas

Del mismo modo que el VRP es una generalización del TSP, hay multitud de modelos que generalizan uno de los dos modelos básicos, normalmente el VRP, con la intención de resolver problemas de optimización de rutas cada vez más cercanos a los problemas logísticos reales a los que se enfrentan las empresas.

Entre otros podemos encontrar:

TWVRP (Time Windows VRP): VRP con restricciones en el horario de entrega en los clientes. Estas ventanas de entrega pueden ser preferentes u obligatorias, por ejemplo, si vienen determinadas por el horario de apertura del local.
HFVRP (Heterogeneous Fleet VRP): VRP con flota heterogénea, es decir, una flota compuesta por vehículos de distinta tipología, capacidad u horario.
VRPPD (VRP with Pick-up and Deliveries): VRP en el que simultáneamente se hacen entregas y recogidas, por ejemplo, se entregan bebidas y se recogen los cascos vacíos.
MDVRP (Multiple Depot VRP): VRP con varios almacenes, de manera que no sólo hay que decidir qué vehículo sirve la mercancía al cliente, sino también desde qué almacén se va a servir. Un ejemplo sería la entrega de un electrodoméstico comprado online a una gran superficie que tiene varios centros en una ciudad, ¿desde qué centro servimos el electrodoméstico?
PVRP (Periodic VRP): VRP con entregas periódicas de mercancía. Por ejemplo, el suministro desde un almacén central a las tiendas de una cadena de perfumería, a las que tiene que ir un número prefijado de veces por semana en función de la capacidad de almacenaje de la tienda y su volumen de venta.
IRP (Inventory Routing Problem): generalización del PVRP en la que se tienen en cuenta los costes de almacenamiento. Siguiendo con el ejemplo anterior, se decide no sólo cómo hacer las rutas para poder servir varias veces a una tienda sino cuántas veces es conveniente ir en función de los costes de transporte y de almacenaje.
OVRP (Open VRP): VRP en el que los vehículos salen del almacén o retornan a él, pero no las dos cosas, no se realizan rutas circulares.
Casi cualquier combinación de los anteriores

La lista anterior no presenta una información exhaustiva de todas las distintas variedades del VRP ni muchísimo menos.

Existen cientos de modelos en los que se combinan distintos aspectos de los problemas de distribución reales a los que se enfrentan las empresas a diario, con el objetivo de obtener modelos que se acercan, cada vez más, a los verdaderos problemas de los sistemas de distribución. Esto es así porque el enfoque para resolver cada uno de los modelos anteriores es diferente.

Por eso, desde nuestra experiencia en investigación y solución de problemas de rutas, nuestra recomendación es, antes de abordar la optimización de rutas en un problema de distribución real, analizarlo con detalle y estudiar qué modelo o combinación de modelos es la más adecuada para ese caso particular.