Open Access

ARTICLE

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

Manuel J. C. S. Reis^*

Engineering Department & IEETA, University of Trás-os-Montes e Alto Douro, Vila Real, 5000-801, Portugal

* Corresponding Author: Manuel J. C. S. Reis. Email:

(This article belongs to the Special Issue: Algorithms for Planning and Scheduling Problems)

Computers, Materials & Continua 2025, 85(2), 3023-3039. https://doi.org/10.32604/cmc.2025.066390

Received 07 April 2025; Accepted 15 August 2025; Issue published 23 September 2025

Abstract

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.

---

Keywords

---