Problema de m-Rutas

Dentro de la denominación de Problemas de Rutas de Vehículos (Vehicle Routing Problem - VRP) realmente se engloba todo un amplio conjunto de variantes y personalizaciones de problemas. Desde aquellos más sencillos hasta algunos mucho más complejos que incluso hoy en día son materia de investigación. Grafos puede ser utilizado para la resolución y optimización de Problemas de m-Rutas.

El Problema de m-Rutas trata de determinar los recorridos de m vehículos de capacidad homogénea que partiendo de un origen común deben pasar por un conjunto de lugares de interés para recoger o distribuir mercancías, y volver de nuevo al origen de manera que la distancia total recorrida (el coste o el tiempo empleado) por el conjunto de vehículos sea mínima. En el tipo de problema más sencillo no se tiene en cuenta la capacidad de carga de los vehículos ni la demanda o cantidad de producto a recoger o entregar en cada lugar de interés; sin embargo, se añade la restricción de que como máximo un vehículo no podrá visitar más de p lugares de interés.

Este problema, es en realidad una combinación del Problema de Rutas y del Problema de los m-Viajantes de Comercio (m-Traveling Salesman Problem m-TSP). Siga leyendo sobre los dos problemas anteriores, para comprender cómo se formula y resuelve la combinación de ambos. Al igual que la mayoría de los problemas VRP, el problema de m-Rutas es de complejidad NP-completo. Esto es así, porque el número de posibles soluciones crece exponencialmente con el número de nodos del grafo (ciudades o puntos de paso), y rápidamente sobrepasa las capacidades de cálculo de los ordenadores más potentes.

Su aplicación es visible y de gran importancia para la resolución de problemas reales en la Dirección de Operaciones y Logística. Por ejemplo: problemas de preparación de pedidos en un almacén (picking), de rutas de vehículos, planificación de transporte urbano, planificación de recogida de residuos o de aprovisionamiento, problemas de reparto o distribución, sistemas de navegación GPS, planificación de movimientos de robots, vehículos autoguiados (AGV), etc.

ejemplo: ambulancias

Las siguientes ilustraciones muestran un ejemplo práctico, donde un conjunto de 3 ambulancias deben pasar por diferentes poblaciones cercanas a recoger pacientes de diálisis. La restricción principal es que las ambulancias no pueden pasar por más de 5 poblaciones.

Como se ha comentado anteriormente, en este tipo de problema simplificado, todavía no se tienen en cuenta la capacidad de carga de las ambulancias ni el número de pacientes. Sólo se consideran las rutas y el número de poblaciones. El resultado óptimo muestra las tres rutas solución, los núcleos de población de paso y las distancias (costes o tiempos) necesarios. La distancia total = 214 unidades.

Ruta ambulancia 1 = 63
Alcoi, Banyeres, Alfafara, Agres, Muro, Cocentaina, Alcoi

Ruta ambulancia 2 = 89
Alcoi, Benifallím, Penaguila, Benilloba, Gorga, Millena, Benillup, Benimarfull, Planes, Margarida, Vall d'Alcalá, Margarida, Planes, Beniarrés, Gaianes, Cela de Nuñez, Muro, Cocentaina, Alcoi

Ruta ambulancia 3 = 62
Alcoi, Ibi, Castalla, Onil, Ibi, Alcoi

 

Fuente: A. Rodríguez

más información

- Solving Traveling Salesman Problems (Princeton University)
- Traveling Salesman Problem (Kevin Ruland - W. Univ.)
- Vehicle Routing Problem (VRP)