Xiaoshu Xiang

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.

The Dynamic Vehicle Routing Problem with Time Windows (DVRPTW) is a widespread real-world challenge, and numerous algorithms have been proposed to address it. However, in the context of an emerging logistics paradigm, namely the instant delivery, the performance of existing algorithms tailored for DVRPTW degrades significantly, as instant delivery allows only very limited computational time for solving DVRPTW instances. Owing to the periodic nature of customer orders, this paper proposes a data-driven evolutionary algorithm (DDEA) for solving DVRPTW under limited computation time. In the offline phase, a set of generalized solutions is derived from historical data via a dedicated evolutionary algorithm. These solutions are then directly employed in the online phase to construct high-quality solutions for new problem instances. By leveraging these precomputed generalized solutions, DDEA effectively operates within tight time constraints. Extensive experiments using synthetic and real-world data demonstrate that DDEA outperforms five state-of-the-art algorithms designed for DVRPTW under limited computation time, particularly under extremely short time constraints.

The Multi-depot Vehicle Routing Problem with Uncertain Demand (MD-VRPUD) can be modeled as a bi-level optimization problem (BLOP), because it requires both assigning customers to different depots and determining the routes for servicing customers, where the optimization of these two parts is coupled with each other. Although the bi-level evolutionary algorithm is a fitting approach for tackling the MD-VRPUD, its nested structure often leads to computational inefficiency. To this end, this paper tailors a surrogate-assisted bi-level evolutionary algorithm (SABLEA) to achieve highly efficient nested algorithms tailored for solving the MD-VRPUD. To deal with the combinatorial property of MD-VRPUD, two groups of continuous features are first extracted to help the surrogate model to effectively distinguish the superiority and inferiority of schemes. Then, a management strategy is designed to adaptively build the surrogate models in different subspaces so as to alleviate the performance bottleneck faced by the model. Finally, an adaptive computing resource allocation strategy is integrated into the lower-level optimization, to allocate more resources to promising customer assignment schemes, enabling the discovery of better routes and improving the overall accuracy of models. The comprehensive experimental results demonstrate the effectiveness of the SABLEA in handling MD-VRPUD, outperforming four existing algorithms in terms of both computational efficiency and solution quality.