An Adaptive Hybrid Metaheuristic for Solving the Vehicle Routing Problem with Time Windows under Uncertainty

The Vehicle Routing Problem with Time Windows (VRPTW) presents a significant challenge in combinatorial optimization, especially under real-world uncertainties such as variable travel times, service durations, and dynamic customer demands. These uncertainties make traditional deterministic models inadequate, often leading to suboptimal or infeasible solutions. To address these challenges, this work proposes an adaptive hybrid metaheuristic that integrates Genetic Algorithms (GA) with Local Search (LS), while incorporating stochastic uncertainty modeling through probabilistic travel times. The proposed algorithm dynamically adjusts parameters—such as mutation rate and local search probability—based on real-time search performance. This adaptivity enhances the algorithm’s ability to balance exploration and exploitation during the optimization process. Travel time uncertainties are modeled using Gaussian noise, and solution robustness is evaluated through scenario-based simulations. We test our method on a set of benchmark problems from Solomon’s instance suite, comparing its performance under deterministic and stochastic conditions. Results show that the proposed hybrid approach achieves up to a 9% reduction in expected total travel time and a 40% reduction in time window violations compared to baseline methods, including classical GA and non-adaptive hybrids. Additionally, the algorithm demonstrates strong robustness, with lower solution variance across uncertainty scenarios, and converges faster than competing approaches. These findings highlight the method’s suitability for practical logistics applications such as last-mile delivery and real-time transportation planning, where uncertainty and service-level constraints are critical. The flexibility and effectiveness of the proposed framework make it a promising candidate for deployment in dynamic, uncertainty-aware supply chain environments.