The capacitated arc routing problem (CARP) has attracted much attention for its many practical applications. The large-scale multidepot CARP (LSMDCARP) is an important CARP variant, which is very challenging due to its vast search space. To solve LSMDCARP, we propose an iterative improvement heuristic, called route clustering and search heuristic (RoCaSH). In each iteration, it first (re)decomposes the original LSMDCARP into a set of smaller single-depot CARP subproblems using route cutting off and clustering techniques. Then, it solves each subproblem using the effective Ulusoy’s split operator and local search. On one hand, the route clustering helps the search for each subproblem by focusing more on the promising areas. On the other hand, the subproblem solving provides better routes for the subsequent route cutting off and clustering, leading to better problem decomposition. The proposed RoCaSH was compared with the state-of-the-art MDCARP algorithms on a range of MDCARP instances, including different problem sizes. The experimental results showed that RoCaSH significantly outperformed the state-of-the-art algorithms, especially for the large-scale instances. It managed to achieve much better solutions within a much shorter computational time.
17 October 2023 in IEEE Computational Intelligence Magazine
The Multi-Depot Capacitated Arc Routing Problem (MDCARP) is an important combinatorial optimization problem with wide applications in logistics. Large Scale MDCARP (LSMDCARP) often occurs in the real world, as the problem size (e.g., number of edges/tasks) is usually very large in practice. It is challenging to solve LSMDCARP due to the large search space and complex interactions among the depots and the tasks. Divide-and-conquer strategies have shown success in solving large-scale problems by decomposing the problem into smaller sub-problems to be solved separately. However, it is challenging to find accurate decomposition for LSMDCARP. To address this issue and alleviate the negative effect of inaccurate problem decomposition, this article proposes a new divide-and-conquer strategy for solving LSMDCARP, which introduces a new restricted global optimization stage within the typical dynamic decomposition procedure. Based on the new divide-and-conquer strategy, this article develops a problem-specific Task Moving among Sub-problems (TMaS) process for the global optimization stage and incorporates it into the state-of-the-art RoCaSH algorithm for LSMDCARP. The resultant algorithm, namely, RoCaSH2, was compared with the state-of-the-art algorithms on a wide range of LSMDCARP instances, and the results showed that RoCaSH2 can achieve significantly better results than the state-of-the-art algorithms within a much shorter time.
16 January 2026 in IEEE Transactions on Evolutionary Computation
The weighted vehicle routing problem (WVRP) is a very important extended vehicle routing problem during post-disaster scenarios for it considers not only the arrival time but also the urgency for each customer. In this paper, we tackle the multi-depot WVRP (MDWVRP), a more practical WVRP since a customer can be assigned to an appropriate depot. For MDWVRP, the number of vehicles located at each depot is restrained, and the number of the total vehicles used for all depots is also limited. To address this problem effectively, we propose a novel memetic algorithm (MA), in which an initializing scheme, a contribution-based crossover operator, and a local search method with different sizes are developed. The designed crossover operator can adjust the proportion of the arcs inserted into offspring from parents according to their fitness. In this sense, the better parent contributes more arcs to child, and vice verse. Moreover, two repair operators are applied to infeasible solution with violation of the number constraints of used vehicles so that the search can be conducted in large space. To demonstrate the effectiveness of the proposed algorithm, it is compared with several state-of-the-art algorithms on two benchmark datasets. The results show that the algorithm outperforms the leading algorithms on all instances, and updates all best-known solutions with an exception which is yet reached by the proposed algorithm. It is noticeable that most best-known solutions are improved by the algorithm with a significant level, the largest gap is over 25%.
1 January 2026 in IEEE Transactions on Automation Science and Engineering
The capacitated electric vehicle routing problem is a complex optimization problem consisting of two types of decisions: (1) deciding the routes for the electric vehicle fleets to complete the customer service; and (2) determining when to visit the charging stations. When the problem size grows, the problem becomes particularly challenging due to the large search space. To address this issue, we develop a cooperative co-evolution algorithm, containing novel problem decomposition and charging scheduling strategies. Two adaptive schemes are adopted to divide the problem into a reasonable number of subproblems with tractable sizes and select the customers with closeness beyond the threshold degree between two routes to measure their relationship. Based on the problem decomposition strategy, a memetic algorithm is designed as an optimizer for each subproblem, and the best sub-solutions are concatenated into an entire solution. The proposed algorithm is verified by comparing it with a number of state-of-the-art algorithms on two popular benchmark datasets as well as their enhanced forms. The experimental results show that our proposed algorithm outperforms the compared algorithms on nearly all instances. In particular, it successfully updated the majority of best-known solutions to the large instances.