Solving the Problem of Vehicle Routing Problem With Time Window via Dual Adaptive Genetic Algorithm

To address the Vehicle Routing Problem with Time Windows (VRPTW), this paper presents a novel Dual Adaptive Genetic Algorithm (DAGA). While numerous metaheuristic algorithms have been proposed to solve VRPTW, most existing approaches either rely on fixed cost functions or incorporate local search heuristics without adaptive control. To the best of our knowledge, there is a lack of research on simultaneously integrating adaptive cost evaluation and adaptive local search strategies within the genetic algorithm framework for solving VRPTW. This paper aims to fill this gap. The proposed DAGA integrates two adaptive strategies: an adaptive cost function and an adaptive local search operator, designed to enhance both exploration and exploitation capabilities. To assess its effectiveness, DAGA is evaluated on the widely used Solomon100 benchmark dataset. Experimental results indicate that DAGA achieves the best-known solutions (BKS) in 14 out of 56 problem instances, with the remaining results exhibiting only minor deviations from the BKS. On average, the deviation in total travel distance is 2.3%, while the deviation in the number of vehicles used is 4%. Compared to other state-of-the-art algorithms, DAGA delivers competitive performance with a favorable balance between solution quality and computational effort. These findings demonstrate that the proposed method is a promising and practical tool for optimizing complex logistics and supply chain problems.