Adaptive Hybrid Heuristic for TSPTW Under Dynamic Real-World Constraints

Abstract

Listen in: English (British) Español (España) Name: Loading voices… ▶ Listen to Abstract Pause Stop Speed: 0.75x1x 1.25x1.5x

Heurística híbrida adaptativa para TSPTW bajo restricciones dinámicas del mundo real Autores: Cezar Marian Papara - Alexandru Ioan Cuza University, Iasi; Vasile Alecsandri University of Bacău (RO) Valer Niminet - Vasile Alecsandri University of Bacău (RO) Resumen Este artículo presenta una heurística híbrida para optimizar redes de transporte, combinando elementos del problema del viajante de comercio (TSP) y de la planificación por intervalos. Partiendo de una ruta heurística inicial, el algoritmo se adapta dinámicamente a restricciones de tiempo, recursos y capacidad, modeladas como disponibilidad de nodos dentro de ventanas temporales. El método prioriza los nodos inmediatamente disponibles y rentables frente a otros más cercanos pero no disponibles, con el objetivo de minimizar el coste de la ruta y evitar retrasos. Diseñado para redes reales a gran escala, el método integra adaptabilidad y eficiencia. Las pruebas realizadas sobre conjuntos de datos TSP con indisponibilidad frecuente de nodos —concretamente, un 20 % de los nodos no disponibles en sus tiempos estimados de llegada para las soluciones clásicas del TSP— muestran que nuestro enfoque supera de forma consistente a los métodos existentes en términos de coste monetario, logrando mejoras de aproximadamente entre un 9 % y un 31 % en todas las instancias evaluadas.

This paper presents a hybrid heuristic for optimising transportation networks, combining elements of the TSP and Interval Scheduling. Starting from an initial heuristic route, the algorithm adapts dynamically to time, resource, and capacity constraints—modelled as node availability within time windows. It prioritises immediately available, cost-effective nodes over closer but unavailable ones, aiming to minimise route cost while avoiding delays. Designed for large-scale, real-world networks, the method integrates adaptability with efficiency. Tests on TSP datasets with frequent node unavailability—specifically, 20 % of nodes unavailable at their estimated arrival times for classical TSP solutions—show that our approach consistently outperforms existing methods in terms of monetary cost, achieving improvements ranging from approximately 9 % to 31 % across all tested instances.