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 capacitated electric vehicle routing problem (CEVRP) has drawn much attention from researchers in the recent decade against the background of the rising electric transportation industry. Existing studies have found the CEVRP more difficult to address than the typical CVRP since the CEVRP needs to simultaneously optimize routing plans and charging decisions at a high computational budget. Given a certain routing plan, it takes much computational cost to exhaustively or approximately achieve the accurate optimal charging decision under the routing plan. This paper proposes that it is unnecessary to search for the accurate optimal charging decisions for potentially low-quality routing plans found during the CEVRP optimization, and instead obtaining acceptable charging decisions significantly reduces the computational cost and helps maintain fast convergence. A multifidelity-based ant colony optimization (MFACO) algorithm is then proposed to flexibly search charging decisions based on the potential quality of routing plans so that CEVRPs can be addressed at high efficiency. The proposed MFACO employs a low-fidelity search strategy to obtain coarse charging decisions for potentially low-quality routing plans, whereas for potentially high-quality routing plans MFACO employs three high-fidelity search strategies to local search in different regions of decision space and provide accurate optimal charging decisions. Experimental results demonstrate that the proposed multifidelity method enhances the efficiency of ACO in solving CEVRPs and the proposed MFACO significantly outperforms four state-of-the-art algorithms for CEVRPs, providing a competitive performance in terms of both solution quality and computational cost.

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.

Multitasking multiobjective evolutionary algorithms (MMEAs) have been extensively studied in the past decade, which mainly concentrate on multitasking multiobjective optimization problems (MMOPs) with dozens of decision variables. Nevertheless, many real-world MMOPs have thousands of decision variables and are of sparse nature, which are regarded as large-scale MMOPs (LSMMOPs) in this study. To address LSMMOPs, a sparsity knowledge transfer-based evolutionary multiobjective algorithm, termed EMO-SKT, is proposed for efficiently finding high-quality sparse solutions of LSMMOPs. For each target optimization task, a sparsity knowledge transfer strategy extracts sparse distribution information from a source task and incorporates the information into the target task for two types of sparsity knowledge: 1) variable importance and 2) sparse degree. The variable importance is utilized to produce high-quality sparse solutions during the evolutionary search for EMO-SKT, while the sparse degree facilitates the reduction of search space and thus speeds up the convergence of the evolutionary search. Experimental results on eight benchmark problems and six practical LSMMOPs demonstrate the effectiveness of the sparsity knowledge transfer strategy. Furthermore, the proposed EMO-SKT is capable of efficiently finding high-quality sparse solutions on an LSMMOP with over 1000 decision variables. In comparison with five state-of-the-art multitasking or sparse optimization algorithms, the proposed EMO-SKT exhibits superior performance in terms of both solution quality and search efficiency.

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.

The pneumonia caused by COVID-19 is spreading worldwide, threatening human health and life. In the last three years, China has taken a series of effective measures to prevent the spread of the virus, where a core measure is the stay-home quarantine imposed in infected communities. The quarantine can effectively reduce physical contacts and transmission risk, however, it encounters several difficulties especially the guarantee of living materials. In order to ensure the quantity and freshness of living materials such as vegetables and fruits, it is necessary to construct multi-level logistics distribution centers, where the selection of locations for these centers becomes a vital issue. Such facility location problems are challenging in terms of both modeling and optimization, especially when facing the millions of residents and thousands of communities in a city commonly existing in China. In this study, we build a large-scale multi-objective optimization model for the distribution center location problem, and solve it via state-of-the-art sparse evolutionary algorithms. The experimental results verify that the center locations obtained by our approach can save human resources while reducing the risk of virus propagation.

Evolutionary algorithms and mathematical programming methods are currently the most popular optimizers for solving continuous optimization problems. Owing to the population based search strategies, evolutionary algorithms can find a set of promising solutions without using any problem-specific information. By contrast, with the assistance of gradient and other information of the functions, mathematical programming methods can quickly converge to a single optimum. While these two types of optimizers have their own advantages and disadvantages, the performance comparison between them is rarely touched. It is known that gradient descent methods generally converge faster than evolutionary algorithms, but when can evolutionary algorithms outperform gradient descent methods? How is the scalability of them? To answer these questions, this paper first gives a review of popular evolutionary algorithms and mathematical programming methods, then conducts several experiments to compare their performance from various aspects, and finally draws some conclusions.

Dynamic vehicle routing problems (DVRPs) have become a hot research topic due to their significance in logistics, although it is still very challenging for existing algorithms to solve DVRPs due to the dynamically changing customer requests during the optimization. In this paper, we propose a pairwise proximity learning-based ant colony algorithm, termed PPL-ACO, for tackling DVRPs. In PPL-ACO, a pairwise proximity learning method is suggested to predict the local visiting order of customers in the optimal route after the occurrence of changes, which is on the basis of learning from the optimal routes found before the changes occur. A radial basis function network is used to learn the local visiting order of customers based on the proximity between each pair of customer nodes, by which the optimal routes can be quickly tracked after changes occur. Experimental results on 22 popular DVRP instances show that the proposed PPL-ACO significantly outperforms four state-of-the-art approaches to DVRPs. More interestingly, the results on five large-scale DVRP instances demonstrate the superiority of the proposed PPL-ACO in solving large-scale DVPRs with up to 1000 customers. The results on a real case of Nankai Strict, Tianjin, China also verifies that the proposed PPL-ACO is more effective and efficient than the four compared approaches in solving real-world DVRPs.

The shelter location is very important for evacuation planning in natural disasters, and evolutionary algorithms (EAs) have demonstrated their effectiveness in solving this challenging problem. However, few EAs have been reported focusing on the shelter location problem under uncertainty of road networks due to the expensive cost of calculating the evacuation distance for individual evaluation. To address this issue, in this article, we propose a clustering-based surrogate-assisted multiobjective EA, termed AR-MOEA+SA, in the framework of a recently developed EA AR-MOEA. In AR-MOEA+SA, a surrogate model, the radial basis function (RBF), is adopted to approximately calculate the evacuation distance under uncertainty of road networks. Due to the fact that there often exist a large number of communities needing to be considered in shelter location, a clustering strategy is suggested to convert the surrogate of high-dimensional problem into the one of low-dimensional problem in the proposed AR-MOEA+SA for efficiently building the RBF network. A population initialization strategy is also suggested in AR-MOEA+SA to enhance the quality of training data in the early stages of evolution. Experimental results on a variety of test instances demonstrate the superiority of the proposed AR-MOEA+SA over the original version of AR-MOEA in terms of both computational efficiency and solution quality.

The effectiveness of evolutionary algorithms have been verified on multi-objective optimization, and a large number of multi-objective evolutionary algorithms have been proposed during the last two decades. To quantitatively compare the performance of different algorithms, a set of uniformly distributed reference points sampled on the Pareto fronts of benchmark problems are needed in the calculation of many performance metrics. However, not much work has been done to investigate the method for sampling reference points on Pareto fronts, even though it is not an easy task for many Pareto fronts with irregular shapes. More recently, an evolutionary multi-objective optimization platform was proposed by us, called PlatEMO, which can automatically generate reference points on each Pareto front and use them to calculate the performance metric values. In this paper, we report the reference point sampling methods used in PlatEMO for different types of Pareto fronts. Experimental results show that the reference points generated by the proposed sampling methods can evaluate the performance of algorithms more accurately than randomly sampled reference points.