GTEA: A Game-Theoretic Evolutionary Algorithm for Solving Vehicle Routing Problem With Time Windows Under Uncertain Travel Times

The Vehicle Routing Problem with Time Windows under Uncertain Travel Times (VRPTW-UT) is a challenging and practically significant combinatorial optimization problem. Although evolutionary algorithms (EAs) have shown potential in solving VRPTW-UT, they often struggle to balance robustness and convergence. Conventional EA approaches evaluate solutions across multiple disturbance scenes and discard those that become infeasible under any scenario. This often leads to the premature elimination of solutions that are only infeasible in a limited number of scenes, hindering the ability to effectively explore the trade-off between robustness and convergence. To address this issue, this paper proposes a Game-Theoretic Evolutionary Algorithm (GTEA) that models the search process as a game between two adversarial components: a perturbation generation part that constructs high-impact uncertainty scenes, and a robustness enhancement part that improves solutions under those critical conditions. This antagonistic process forces the population to evolve toward solutions that possess both high robustness and convergence, so that GTEA can efficiently produce solutions with high robustness and convergence. Extensive experiments on four benchmark datasets demonstrate that GTEA outperforms five state-of-the-art algorithms designed for VRPTW-UT, achieving superior convergence and robustness.