Problema de Rutas

Grafos puede ser utilizado para la resolución y optimización de Problemas de Rutas o Recorridos. Siga leyendo para saber más sobre la importancia de este tipo de problemas y la utilidad de Grafos para su resolución y análisis.

Dentro de la denominación de Problemas de Rutas o Recorridos realmente se engloba todo un amplio conjunto de variantes y personalizaciones de problemas. Desde aquellos más sencillos (como el que se comentará en este apartado) hasta algunos mucho más complejos que incluso hoy en día son materia de investigación. Todos ellos sin embargo, además del reto computacional que representan, tienen en común su gran importancia en investigación operativa por su aplicación práctica en la realidad. En futuras versiones de Grafos, se resolverán otro tipo de problemas más complejos pertenecientes al conjunto de Problemas de Rutas de Vehículos (Vehicle Routing Problem - VRP).

Al igual que el Problema del Viajante de Comercio (Traveling Salesman Problem - TSP), la mayoría de los problemas VRP son 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.

 

Ver la explicación paso a paso del proceso de resolución del Problema de Rutas...

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)