Cada mañana, frente al centro logístico, varios camiones cargan mercancía y esperan la salida. Hoy hay decenas de lugares donde hacer entregas y hay que decidir qué camión atenderá cada casa y en qué orden hará las visitas. Aunque se lleve la misma mercancía a las mismas casas, la forma de planificar las rutas puede cambiar considerablemente la distancia recorrida durante el día, el gasto en combustible y la hora a la que los conductores terminan su jornada.
En términos sencillos, el problema de enrutamiento de vehículos (Vehicle Routing Problem) consiste en encontrar el conjunto de rutas de menor costo total cuando varios vehículos salen de un almacén, se reparten las visitas a los clientes y regresan al punto de partida. En 1959, George Dantzig y John Ramser lo presentaron por primera vez como un problema de asignación de rutas a camiones que abastecían de gasolina a las estaciones de servicio. Hoy es un cálculo básico en la logística de paquetería y distribución.
En este artículo veremos, en orden, la estructura básica del problema de enrutamiento de vehículos, por qué se dispara el número de posibilidades, qué condiciones añade la realidad y cómo se busca una solución.
Cómo planificar a la vez las rutas de varios camiones
Estructura básica del problema de enrutamiento de vehículos
La estructura del problema de enrutamiento de vehículos se aclara con solo definir unos pocos elementos.
(1) Almacén y vehículos
Todos los vehículos salen de un mismo almacén, que sirve como base de partida, y regresan allí al terminar su trabajo. El número de vehículos y la capacidad de carga de cada uno se conocen desde el principio.
(2) Clientes y demanda
Cada punto de entrega tiene una ubicación y una cantidad de mercancía que debe recibir. Todos los clientes deben recibir su mercancía una sola vez y de un único vehículo.
(3) Costo de desplazamiento
Se calcula de antemano la distancia, el tiempo o el dinero que supone desplazarse entre dos puntos. Si se determina el camino más corto en la red vial real, los costos entre los puntos se pueden manejar como una tabla.
(4) Objetivo
El objetivo más habitual es reducir el costo total de los desplazamientos. Según el caso, también se puede buscar minimizar el número de vehículos o repartir la carga de trabajo de manera uniforme entre ellos.
Por qué se dispara el número de posibilidades
Encontrar el orden de visita que permite a un solo camión recorrer todas las casas en el circuito más corto se conoce como el problema del viajante (Traveling Salesman Problem). El problema de enrutamiento de vehículos extiende el problema del viajante a varios vehículos, por lo que es al menos igual de difícil.
Si hay 10 lugares que visitar, solo el orden de las visitas ya da lugar a unas 362 decenas de miles de posibilidades. Si hay 20 lugares, la cifra asciende a unas 243 decenas de miles de billones de posibilidades. Además, hay que decidir qué vehículo atenderá a cada cliente, así que examinar todas las posibilidades una por una pronto deja de ser viable.
En matemáticas, estos problemas se clasifican como NP-difíciles (NP-hard). Esto significa que, a medida que aumenta el número de clientes, el tiempo necesario para hallar una solución exacta puede crecer tan rápido que resulte inasumible. Por eso, en la práctica suele optarse por encontrar rápidamente una solución lo bastante buena en vez de buscar una perfecta.
Las condiciones que añade la realidad
El reparto real es mucho más complejo que el problema de los libros de texto. Cada condición adicional da lugar a una nueva variante.
- Restricción de capacidad de carga (Capacitated Vehicle Routing Problem). Cada vehículo tiene un límite de peso o volumen que puede transportar, por lo que hay que repartir a los clientes de forma que se respete ese límite.
- Restricción de ventanas de tiempo (Vehicle Routing Problem with Time Windows). Cada cliente dispone de una franja horaria para recibir la mercancía y el vehículo debe llegar dentro de ese intervalo.
- Recogida y entrega (Vehicle Routing Problem with Pickup and Delivery). Se planifican conjuntamente la recogida de mercancía en un lugar y su entrega en otro.
- Múltiples almacenes (Multi-Depot Vehicle Routing Problem). Hay varios almacenes de los que los vehículos pueden salir y a los que pueden regresar.
- Problema de enrutamiento de vehículos eléctricos (Electric Vehicle Routing Problem). Se tienen en cuenta tanto la distancia que permite recorrer la batería como los lugares donde se puede recargar.
También se estudian variantes tan diversas como las situaciones que se dan en la práctica, entre ellas los casos en que los vehículos pueden terminar su recorrido sin regresar al almacén y aquellos en que hacen varios viajes de ida y vuelta al almacén en un mismo día.
Métodos para encontrar una solución
Los métodos para resolver el problema de enrutamiento de vehículos se dividen, a grandes rasgos, entre los que buscan una solución exacta y los que buscan una buena solución con rapidez.
Métodos exactos
Se formula el problema mediante un modelo matemático llamado programación entera y se van descartando de manera selectiva algunas posibilidades hasta encontrar la mejor solución. La calidad de la solución está garantizada, pero el tiempo de cálculo aumenta considerablemente a medida que crece el número de clientes, por lo que estos métodos se usan sobre todo en problemas pequeños.
Algoritmo de ahorros
G. Clarke y J. W. Wright propusieron este método en 1964. Primero se supone que se envía un camión distinto a cada cliente. Luego se calcula cuánto se acorta la distancia al unir a dos clientes en una sola ruta y se van combinando los pares por orden de ahorro, empezando por los que más distancia ahorran. El cálculo es sencillo y los resultados son aprovechables, por lo que el método sigue siendo de uso generalizado.
Metaheurísticas
Son métodos como los algoritmos genéticos, la búsqueda tabú o el recocido simulado, que van modificando poco a poco las rutas iniciales para encontrar mejores soluciones. Se sabe que algunos de los métodos recientes más avanzados reducen la diferencia con respecto a la solución óptima a alrededor del 1 por ciento, incluso en problemas con entre cientos y miles de puntos de visita.
El problema de enrutamiento de vehículos puede parecer un ejercicio de trazar líneas en un mapa, pero detrás hay un cálculo que busca reducir a la vez los costos, el tiempo y el trabajo humano. Los fabricantes de software de planificación de rutas anuncian ahorros de costos de entre el 5 y el 30 por ciento, lo que también muestra el alcance de este cálculo.
Revisar continuamente las rutas para transportar la misma mercancía por trayectos más cortos es el primer paso hacia un reparto eficiente.
