Adaptive Hybrid Heuristic for TSPTW Under Dynamic Real-World Constraints

Abstract

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.