El problema del viajante en la era moderna

Formulado por primera vez en el siglo XIX, el estudio del problema del viajante (TSP, por sus siglas en inglés) avanzó notablemente gracias al matemático estadounidense Merrill M. Flood en los años treinta, cuando se propuso resolver un problema de rutas de autobuses escolares. El TSP es un problema matemático en el que hay que encontrar la ruta más corta posible que pase por un conjunto de puntos (en este caso, paradas de autobús). La ruta definida debe pasar por cada punto una sola vez antes de volver al punto de partida.

En general, el orden en que se visita cada parada o punto no es un factor principal, siempre que el viajante pase por todos ellos una vez. A pesar de la extraordinaria sencillez de su formulación, el TSP es un problema NP-difícil de optimización combinatoria y puede utilizarse como modelo para probar técnicas de optimización aplicadas a problemas muy diversos, incluido el despacho dinámico de vehículos compartidos.

En un plano más abstracto, el TSP puede describirse mediante la teoría de grafos como una red ponderada no dirigida, cuyos nodos representan ciudades y cuyos enlaces tienen pesos que indican las distancias entre ellas. En este contexto, encontrar la solución óptima del TSP significa encontrar el camino más corto que conecte todos los nodos de la red. En la literatura existen diversos algoritmos que analizan las propiedades estructurales de una red buscando sus caminos más cortos, y son el núcleo de la teoría de grafos tradicional. La aplicación de estos algoritmos a redes complejas se da en campos consolidados como las matemáticas, la biología y las ciencias sociales.

Resulta asombroso que, aunque estos algoritmos se basan en un problema relativamente sencillo y se desarrollaron para resolverlo, hoy su capacidad predictiva también se aprovecha para facilitar operaciones industriales complejas. Sectores de enorme importancia en nuestra vida diaria, como el reparto de mercancías a escala local, nacional e internacional, el sector marítimo, las redes aeroportuarias o las redes de transporte público de las grandes áreas metropolitanas, son solo algunos ejemplos que utilizan variantes de los algoritmos del TSP para hacernos la vida más fácil.

El camino más corto en una variante del TSP puede encontrarse calculando todas las combinaciones de rutas posibles. Este enfoque de fuerza bruta funciona cuando N es lo bastante pequeño, pero es prácticamente inviable para valores grandes de N. En este último caso, los algoritmos de búsqueda heurística ofrecen excelentes soluciones aproximadas. Su principal ventaja es su capacidad de obtener soluciones de la variante del TSP que, aunque no sean exactas, son mucho más prácticas y, sobre todo, se obtienen rápidamente y con un bajo coste computacional. Esto hace que los algoritmos de búsqueda heurística sean populares y adecuados para servicios de software en los que los recursos de computación son limitados y la respuesta en tiempo real es crucial, sobre todo cuando la demanda crece.

La tecnología de Shotl utiliza métodos científicos modernos que permiten aprovechar la investigación pasada y actual sobre redes complejas y algoritmos de optimización. El servicio, respaldado por un diseño de ingeniería ágil, se construye en torno a un sólido núcleo algorítmico que encuentra soluciones óptimas en una variante del TSP formulada según las restricciones de cada situación concreta.

Nuestra solución algorítmica agrupa a varios pasajeros que van en la misma dirección en un vehículo en movimiento, minimizando las distancias recorridas y los tiempos de espera, y ofrece así un mejor servicio y una mejor experiencia de transporte.