Swarm and Evolutionary Computation 84 (2024) 101425

Contents lists available at ScienceDirect

Swarm and Evolutionary Computation

journal homepage: www.elsevier.com/locate/swevo

A neighborhood comprehensive learning particle swarm optimization for the

vehicle routing problem with time windows
Qichao Wu a,b , Xuewen Xia a,b ,∗, Haojie Song a,b , Hui Zeng c , Xing Xu a,b , Yinglong Zhang a,b ,
Fei Yu a,b , Hongrun Wu a,b
a
College of Physics and Information Engineering, Minnan Normal University, Zhangzhou 363000, Fujian, China
b Key Lab of Intelligent Optimization and Information, Minnan Normal University, Zhangzhou 363000, Fujian, China
c XinJiang Institute of Engineering, Urumqi 830091, Xinjiang Uygur Autonomous Region, China

ARTICLE INFO ABSTRACT

Keywords: Vehicle routing problem with time windows (VRPTW), which is a typical NP-hard combinatorial optimization
Vehicle routing problem with time windows problem, plays an important role in modern logistics and transportation systems. Recent years, heuristic
Particle swarm optimization and meta-heuristic algorithms have attracted many researchers’ attentions to solve the VRPTW problems.
Neighborhood search
As an outstanding meta-heuristic algorithm, particle swarm optimization (PSO) algorithm exhibits very
Longest common sequence
promising performance on continuous problems. However, how to adapt PSO to efficiently deal with VRPTW
is still challenging work. In this paper, we propose a neighborhood comprehensive learning particle swarm
optimization (N-CLPSO) to solve VRPTW. To improve the exploitation capability of N-CLPSO, we introduce a
new remove-reinsert neighborhood search mechanism, which consists of the removed operator and the reinsert
operator. When performing the removed operator, the probability of adjacency between two customers is
calculated by an information matrix (𝐼𝑀), which is constructed based on the customers’ time-space information
and elite individuals’ local information. When executing the reinsert operator, the 𝐼𝑀 and a cost matrix
(𝐶𝑀), which is introduced to record the cost of customer insertion, are used to find an optimal insert
position. Moreover, to enhance the exploration of N-CLPSO, a semi-random disturbance strategy is proposed,
in which elites’ longest common sequences (LCS) are saved, aiming to prevent population degradation. The
N-CLPSO algorithm is tested on 56 Solomon benchmark instances, and it attains the optimal solutions on 29
instances. The simulation results and comparison results illustrate that the proposed algorithm outperforms or
can compete with the majority of other 3 PSO variants as well as other 12 state-of-the-art algorithms.

1. Introduction optimal path of gasoline transportation trucks [2]. Since there is a

high correlation between the VRP and the reality of logistics, it has
With the emergence and fast growing development of electronic attracted much attention from researchers in the logistics field. During
commerce, there are more orders and parcels to be processed in lo- the last few years, various VRP variants, such as the Capacitated
gistics industries [1]. Thus, it has become a research focus of logistics VRP (CVRP) [3] and the Heterogeneous Fleet VRP (HFVRP) [4], have
issues that ensure goods are delivered within a specified time at a lower proposed aiming to imitate different real applications. One of the most
cost. Based on in-depth analyses of logistics problems, one can observe significant variations is the VRP with time windows (VRPTW) [5], in
that the study of Vehicle Routing Problems (VRP) is a feasible and which users’ access time and vehicles’ capacity limits are considered in
way to deal with the problems. Generally, a good VRP solution needs
VRP, aiming to make the problem more realistic.
to consider many constraints, such as completing customer service on
Initially, some deterministic algorithms are adopted to solve VRPTW
time, reducing distribution costs while improving customer satisfaction,
[6,7]. However, due to VRPTW’s NP-hardness, solving large-scale
and so on. Therefore, designing an efficient and reliable algorithm to
VRPTW with deterministic algorithms is exceedingly time-consuming.
deal with VRP problems has become a key research priority in logistics
industries. Thus, in recent years, various heuristic and meta-heuristic algorithms
The VRP, which is a typical combinatorial optimization problem, for solving VRPTW problems have attracted many researchers’ atten-
was first proposed by Dantzig et al. in 1954 when they studied the tion. For example, the Simulated Annealing (SA) [8], Taboo Search

∗ Corresponding author at: College of Physics and Information Engineering, Minnan Normal University, Zhangzhou 363000, Fujian, China.
E-mail address: [email protected] (X. Xia).

https://doi.org/10.1016/j.swevo.2023.101425
Received 1 January 2023; Received in revised form 25 October 2023; Accepted 1 November 2023
Available online 21 November 2023
2210-6502/© 2023 Elsevier B.V. All rights reserved.
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

(TS) [9], Ant Colony Optimization (ACO) [10], Particle Swarm Op- step size of particle 𝑖 in the 𝑡th generation. During the search process,
timization (PSO) [11], and Genetic Algorithm (GA) [12] have been each particle
[ adjusts its flight] path by its own historical best position
proved to be effective in solving VRPTW problems. However, as the 𝑃 𝐵𝑖𝑡 = 𝑝𝑏𝑡𝑖,1 , 𝑝𝑏𝑡𝑖,2 , … , 𝑝𝑏𝑡𝑖,𝐷 and the population’s historical best position
complexity and scale of VRPTW increase, the convergence speed and [ ]
𝐺𝐵𝑖𝑡 = 𝑔𝑏𝑡𝑖,1 , 𝑔𝑏𝑡𝑖,2 , … , 𝑔𝑏𝑡𝑖,𝐷 . The specific update rules of 𝑉𝑖𝑡 and 𝑋𝑖𝑡 are
optimal results of the algorithms are still unsatisfactory. Hence, how to
speed up the convergence and improve the solutions’ accuracy of the defined as Eqs. (1) and (2), respectively.
algorithms need to be further studied. ( ) ( )
PSO algorithm [13], proposed by Kennedy and Eberhart in 1995, 𝑣𝑡+1 𝑡 𝑡 𝑡 𝑡 𝑡
𝑖,𝑗 = 𝑤𝑣𝑖,𝑗 + 𝑐1 𝑟1 𝑝𝑏𝑖,𝑗 − 𝑥𝑖,𝑗 + 𝑐2 𝑟2 𝑔𝑏𝑗 − 𝑥𝑖,𝑗 (1)
has been widely used for continuous function optimization and 𝑥𝑡+1 𝑡 𝑡+1
(2)
𝑖,𝑗 = 𝑥𝑖,𝑗 + 𝑣𝑖,𝑗
achieved many promising achievements in both theoretical studies [14–
18] and engineering applications [19–22]. However, PSO also has some where 𝑤 denotes an inertia weight, which is used to control the
shortcomings, including (1) premature convergence for complicated influence of the current velocity on the latest velocity; 𝑐1 and 𝑐2 are
multimodal problems, and (2) low precision of final solutions. The two constants that determine the learning weight on 𝑃 𝐵𝑖𝑡 and 𝐺𝐵𝑖𝑡
main reason for the former shortcoming in the PSO algorithm is that respectively; 𝑟1 and 𝑟2 are two random numbers uniformly distributed
the population diversity may disappear rapidly during the optimization in the interval [0, 1].
process. Hence, many improvements intending to keep the population To improve the global search capability of the basic PSO, Liang
diversity have been proposed by researchers [23,24]. To overcome the et al. [30] proposed a CLPSO in which a new velocity update rule
latter drawback of the PSO algorithm, various excellent and efficient described as Eq. (3) is used to prevent premature convergence.
local search strategies have been applied to some PSO variants [25,26]. ( )
𝑣𝑡+1 𝑡 𝑡 𝑡
𝑖,𝑗 = 𝑤𝑣𝑖,𝑗 + 𝑐1 𝑟1 𝑝𝑓 (𝑖),𝑗 − 𝑥𝑖,𝑗 (3)
Although these strategies significantly enhance the comprehensive
performance of PSO on continuous problems, they cannot be directly where 𝑓 (𝑖) represents a particle index that guides particle 𝑖 to fly in
applied in combinatorial optimization problems, such as VRPTW. Thus, the 𝑗th dimension, and the particle 𝑓 (𝑖) can be any particle including
in recent years, how to improve these strategies in PSO and adapt them particle 𝑖 itself. To select 𝑓 (𝑖) in each dimension, CLPSO will generate
to VRPTW attract researchers’ attention. a random number 𝑟. Subsequently, 𝑟 is compared with 𝑃 𝑐𝑖 defined as
Based on the analysis mentioned above, this paper proposes a Eq. (4), which is the learning probability of the control particle to learn
neighborhood comprehensive learning PSO (N-CLPSO) algorithm to from itself or others.
solve the VRPTW. Motivations and novelties applied in N-CLPSO are ( ( ) )
briefly introduced as follows. exp 10(𝑖−1)
𝑁−1
−1
𝑃 𝑐𝑖 = 0.05 + 0.45 ∗ 𝑖 = 1, 2, … , 𝑁 (4)
(1) The original CLPSO is mainly used to solve continuous problems. (exp(10) − 1)
To adapt the N-CLPSO to solve VRPTW, we redefine the velocity and
where 𝑁 is the population size.
position of particles and corresponding update rules [11].
If 𝑟 is greater than 𝑃 𝑐𝑖 , the particle 𝑖 learns toward its own personal
(2) Regarding the convergence performance of the algorithm, we
history. On the contrary, the particle 𝑖 selects the particles 𝑓 (𝑖) as its
improve the velocity update strategy [27] of the original CLPSO based
learning exemplar by binary tournament selection. Using this learning
on particles’ fitness values. In addition, we also use the vehicle insertion
strategy, particles can learn not only from themselves but also from the
strategy to reduce the number of vehicles as much as possible and to
optimal features of other particles. These features allow the particles
speed up the algorithm’s convergence.
to have more learnable samples and a larger potential flight space.
(3) Although some local information of individuals can be used to
Thus, CLPSO can utilize helpful information in the population more
guide the search process of a population [28,29], to our knowledge, no
efficiently and then can generate higher-quality solutions. Experimental
studies directly apply local information of nodes to insertion search.
results in [31] manifest that CLPSO has good performance for discrete
Therefore, we propose the concept of a local information matrix that
optimization. Hence, we will use CLPSO as the basic framework to solve
not only considers local information about the customers’ location, time
VRPTW problems in this study.
windows, and elite individuals in each generation but also evaluates the
incremental cost caused by the insertion operator.
2.2. Mathematical definition of VRPTW
(4) To overcome degradations caused by blind random perturba-
tions, we propose a semi-randomly perturbation strategy based on
VRPTW is to find the lowest cost route to serve multiple consumers
the longest common subsequence (LCS) idea. Based on the strategy,
with the same size fleet within a certain time window. The total
some elite sequences in LCS can be preserved while other unpromising
demand for service provided by each vehicle must not exceed the total
sequences are destroyed. Thus, the diversity of the particles can be
capacity of the vehicle, and each customer is served by a vehicle only
enhanced, and the solutions’ quality can be improved.
once during a defined time window. In other words, a vehicle must wait
The rest of this paper is organized as follows. Section 2 provides
until the start of the time window if it approaches a customer before the
a short introduction to the PSO algorithm and the VRPTW model, and
start of the customer’s time window. Similar to this, a customer cannot
Section 3 reviews the study of VRPTW. N-CLPSO and newly introduced
be served if a vehicle arrives at the customer’s location after the end of
strategies are detailed in Section 4. Next, the experimental results and
the customer’s time window.
analyses are reported in Section 5. Finally, the summary and future
VRPTW is a problem in which a fleet of 𝐾 vehicles serve 𝑀
work of this study are presented in Section 6.
customers. Each vehicle has a constant capacity 𝑄. The depot 𝑣0 is the
start and end point of each route. The vertex 𝑣𝑖 is defined as a customer,
2. Related work ( )
𝑖 ∈ {1, 2, … , 𝑀}. The demand of customer 𝑣𝑖 located at 𝑥𝑖 , 𝑦𝑖 is 𝑞𝑖
[ ]
and the delivery time window of it is 𝑏𝑖 , 𝑙𝑖 , where 𝑏𝑖 and 𝑙𝑖 refer
2.1. PSO
to the earliest and latest time when the customer starts the service,
respectively. If a vehicle arrives at the customer 𝑣𝑖 earlier than 𝑏𝑖 , it
In the standard PSO, each particle 𝑖 in the 𝑡th generation
[ can be]
must wait until the start of the time window to serve the customer.
described by two vectors, i.e., a position vector 𝑋𝑖𝑡 = 𝑥𝑡𝑖,1 , 𝑥𝑡𝑖,2 , … , 𝑥𝑡𝑖,𝐷
[ ] On the other hand, if the vehicle does not arrive before 𝑙𝑖 , it cannot
and a velocity vector 𝑉𝑖𝑡 = 𝑣𝑡𝑖,1 , 𝑣𝑡𝑖,2 , … , 𝑣𝑡𝑖,𝐷 , where 𝐷 denotes a serve the customer 𝑣𝑖 . The service time of each customer is 𝑠𝑖 . The
( )
dimension of the problem to be optimized. 𝑋𝑖𝑡 is considered as a depot is located at 𝑥0 , 𝑦0 with demand 𝑞0 = 0 and the time window
[ ( )]
candidate solution, and 𝑉𝑖𝑡 is regarded as the search direction and 0, 𝑙0 ≥ max 𝑏𝑖 . For simplicity, the time cost that a vehicle traveling

2
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

from customer 𝑖( to customer

) is represented by the Euclidean distance Zhang [35] et al. used VRPTW as a research object and proposed
between nodes 𝑐𝑖,𝑗 = 𝑐𝑗,𝑖 , where 𝑖 ≠ 𝑗, 𝑖, 𝑗 ∈ {1, 2, … , 𝑀}. a hybrid multi-objective evolutionary algorithm with fast sampling
Generally, there are two objectives in VRPTW, which are defined strategy-based global search and route sequence difference-based local
as Eqs. (5) and (6), respectively. The primary goal is to minimize the search (HMOEA-GL). Khoo [12] et al. proposed a two-phase distributed
number of vehicles (𝑁𝑉 ) and the secondary goal is to minimize the ruin-and-recreate genetic algorithm (RRGA) to solve VRPTW by a
total distance (𝑇 𝐷) with the same number of routes. VRPTW can be ruin-and-recreate strategy combined with GA. This combination of
mathematically formulated as follows. algorithms harnesses the strength of the search diversification and
The goal of the VRPTW is to minimize intensification, thereby producing very high-quality solutions.
PSO, as a typical swarm intelligence optimization algorithm, im-
min 𝑁𝑉 = 𝐾 (5)
itates the foraging behavior of a flock of birds, and it was mainly
and applied to continuous problems at the beginning of its proposal. In
∑
𝑀 ∑
𝑀 ∑
𝐾 recent years, some scholars have started to adapt the standard PSO to
min 𝑇 𝐷 = 𝑐𝑖,𝑗 ∗ 𝑥𝑘𝑖,𝑗 (6) combinatorial optimization problems. Reong [36] et al. summarized the
𝑖=0 𝑗=0 𝑘=1 last 20 years of PSO algorithms for solving VRP and related variants,
s.t. including solving VRPTW. Saksuriya [37] et al. proposed a novice
∑
𝑀 local search, ruin and recreated procedure, and PSO three-module
𝑥𝑘𝑖,𝑗 = 𝑦𝑘𝑗 ∀𝑘 = 1, … , 𝐾, ∀𝑗 = 1, … , 𝑀 (7) hybrid heuristic algorithm to solve VRPTW. Salehi [38] et al. proposed
𝑖=0 a multi-objective PSO and a multi-objective particle swarm variable
∑𝑀 neighborhood search algorithm to solve the real-time collaborative
𝑥𝑘𝑖,𝑗 = 𝑦𝑘𝑖 ∀𝑘 = 1, … , 𝐾, ∀𝑖 = 1, … , 𝑀 (8) feeder vehicle path problem (RTCFVRP) with flexible time windows
𝑖=0
and achieved better performance. Ding [39] et al. established a time-
∑𝐾
window electric vehicle distribution path problem (EVRPTW-DC) for
𝑦𝑘𝑖 = 1 ∀𝑖 = 1, … , 𝑀 (9)
𝑘=1
driving cycles based on typical driving cycles in suburban and urban ar-
eas, considering vehicle load, driving distance, and speed as objectives.
∑𝑀
𝑦𝑘𝑖 ∗ 𝑞𝑖 ≤ 𝑄 ∀𝑘 = 1, … , 𝐾 (10) Then, an adaptive PSO was designed to solve the problem.
𝑖=0 In studies on VRP-related variants, the local neighborhood search
∑𝐾 strategy has become a critical factor in determining individuals to jump
𝑦𝑘0 = 𝐾 (11) out of the local optimum. Therefore, designing efficient neighborhood
𝑘=1
search strategies has received much attention from researchers recently.
𝑡𝑖 + 𝑤𝑗 + 𝑠𝑖 + 𝑐𝑖,𝑗 = 𝑡𝑗 ∀𝑖, 𝑗 = 1, … , 𝑀, 𝑖 ≠ 𝑗 (12) For instance, Liu [40] et al. designed an efficient algorithm based on
𝑏𝑗 ≤ 𝑡𝑗 ≤ 𝑙𝑗 ∀𝑗 = 1, … , 𝑀 (13) the combination of large-neighborhood search and GA. The algorithm
{ } uses a constrained relaxation scheme to extend the search space by
𝑤𝑗 = max 𝑏𝑖 − (𝑡𝑖 + 𝑠𝑖 + 𝑐𝑖,𝑗 ), 0 ∀𝑖 = 1, … , 𝑀 (14) neighborhood search of existing infeasible solutions. It initiates a GA
where to explore the undiscovered space when the search falls into a local
{ optimum. Yu [10] et al. introduced a neighborhood search operator in
1, if vehicle 𝑘 travels directly from 𝑖 to 𝑗
𝑥𝑘𝑖,𝑗 = the ACO and protected the population diversity by forbidden search.
0, otherwise
Alinaghian [41] et al. presented a mathematical model for a hybrid
{
1, if customer 𝑖 is served by vehicle 𝑘 green vehicle routing problem (TD-FSMGVRP). This study utilizes an
𝑦𝑘𝑖 =
0, otherwise improved adaptive large domain search algorithm to solve the TD-
Constraints Eqs. (7)–(9) mean that each customer will be served by FSMGVRP problem simultaneously considering multiple dimensions of
a vehicle and that each customer can be served by only one vehicle. vehicle fixed cost, driver cost, fuel cost, and greenhouse gas emission
Constraint Eq. (10) means that each vehicle cannot carry more than cost and achieves superior performance.
capacity 𝑄. Constraint Eq. (11) denotes that all routes start from the
depot. Eqs. (12)–(14) define the time window constraint, where 𝑡𝑖 is the 4. Proposed method
vehicle arrival time at node 𝑖; 𝑤𝑗 is the waiting time after the vehicle
arrives at customer 𝑗; 𝑆𝑖 is the service time; and 𝑐𝑖,𝑗 is the time cost In this part, Section 4.1 presents the framework of N-CLPSO, and
between nodes 𝑖 and 𝑗. Section 4.2 describes the details of it. Section 4.3 introduces the vehicle
insertion strategy. Section 4.4 shows the guided reinsertion opera-
3. Literature review tor based on local information, and Section 4.5 details the remove-
reinsert-based neighborhood search strategy. Diversity retention strate-
VRP and its variants have been extensively studied based on dif- gies based on elite fragments are described in Section 4.6.
ferent intelligence algorithms in the past decades. For instance, ACO
inspired by the foraging behavior of real ants is a popular proba- 4.1. Framework of N-CLPSO
bilistic algorithm to solve VRPTW. Considering the customer service
time, Wang [32] et al. designed a multi-ant system with local search, N-CLPSO is a combination of CLPSO and a new proposed local
which combines the Multi_Ant System algorithm and four local search search strategy. Although, CLPSO has a good global search capability
operators to improve the solution quality. Gupta [33] et al. proposed when optimizing continuous problems, the encoding and related oper-
an improved ACO to solve the VRPTW problem, which uses new ators of it need to be redefined according to the distinct characteristics
pheromones to reset and update the function to enhance the global of VRPTW.
search capability of the algorithm, and improve the optimization path We use the vector 𝑋𝑖𝑡 to denote the position of particle 𝑖 in the 𝑡th
by the 2-opt method. Zhang [34] et al. designed a solution strategy generation. 𝑥𝑡𝑖,𝑑 denotes the set 𝑑𝑘,𝑙 = {⟨𝑘, 𝑑⟩, ⟨𝑑, 𝑙⟩} of a set of arcs in
based on ACO and three variational operators to solve a multi-objective the 𝑑-dimension of 𝑋𝑖𝑡 , which indicates that the left and right neighbors
VRP problem with flexible time windows. of node 𝑑 in particle 𝑖 in the 𝑡th generation are 𝑘 and 𝑙, respectively.
GA is a heuristic algorithm that simulates genes, chromosomes, and To ensure that each position is a valid solution, the position 𝑥𝑡𝑖,𝑑 has
the genetic evolution of organisms. Due to its strong search perfor- three constraints: (1) 𝑑 ∈ (0, 1, 2, … , 𝑛), 𝑛 represents the city number;
mance and good extensibility, GA has been widely used in VRPTW. (2) 𝑘, 𝑙 ∈ {0, 1, … , 𝑑 − 1, 𝑑 + 1, … , 𝑛} and (3) 𝑘 ≠ 𝑙. The constraint (1)

3
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

corresponding to particle 𝑋𝑖 , respectively.

( ) ( ) ( ( ))
f itness 𝑋𝑖𝑡 = 𝑁𝑉 𝑋𝑖𝑡 + normalize 𝑇 𝐷 𝑋𝑖𝑡 (15)
arctan(𝑥)
normalize(𝑥) = 𝜋 (16)
2

4.2. Basic operators in N-CLPSO

In N-CLPSO, based on the above definitions of position and veloc-

ity [11], we use Eq. (3) to update the velocity. The related operators in
Eq. (3) are defined as Eqs. (17)–(20), respectively. 𝑐 ∗ 𝑣𝑡𝑖,𝑑 and 𝑣𝑡𝑖,𝑑 + 𝑣𝑡𝑗,𝑑
denotes the probability 𝑝(𝑢, 𝑣) variation of the arc. 𝑥𝑡𝑖,𝑑 − 𝑥𝑡𝑗,𝑑 means the
set solving difference set and 𝑐 ∗ (𝑥𝑡𝑖,𝑑 − 𝑥𝑡𝑗,𝑑 ) stands for converting a
crisp set into a set with probability:
{ }
𝑐 ∗ 𝑣𝑡𝑖,𝑑 = ⟨𝑢, 𝑣⟩∕𝑝′ (𝑢, 𝑣) ∣ ⟨𝑢, 𝑣⟩ ∈ 𝐴𝑑
{
1, if 𝑐 ∗ 𝑝(𝑢, 𝑣) > 1
𝑝′ (𝑢, 𝑣) = (17)
𝑐 ∗ 𝑝(𝑢, 𝑣), otherwise
{ ( ) }
| |
𝑣𝑡𝑖,𝑑 + 𝑣𝑡𝑗,𝑑 = ⟨𝑢, 𝑣⟩ |max 𝑝𝑖 (𝑢, 𝑣), 𝑝𝑗 (𝑢, 𝑣) | ⟨𝑢, 𝑣⟩ ∈ 𝐴𝑑 (18)
| |
{ }
𝑥𝑡𝑖,𝑑 − 𝑥𝑡𝑗,𝑑 = U𝑑 = ⟨𝑢, 𝑣⟩ ∣ ⟨𝑢, 𝑣⟩ ∈ 𝑥𝑡𝑖,𝑑 and ⟨𝑢, 𝑣⟩ ∉ 𝑥𝑡𝑗,𝑑 (19)
{ ′
}
𝑐 ∗ 𝑈𝑑 = ⟨𝑢, 𝑣⟩∕𝑝 (𝑢, 𝑣) ∣ ⟨𝑢, 𝑣⟩ ∈ 𝐴𝑑
⎧ 1, if ⟨𝑢, 𝑣⟩ ∈ 𝑈 and 𝑐 > 1
⎪ 𝑑
𝑝′ (𝑢, 𝑣) = ⎨𝑐, if ⟨𝑢, 𝑣⟩ ∈ 𝑈𝑑 and 0 < 𝑐 < 1 (20)
⎪ 0, if ⟨𝑢, 𝑣⟩ ∉ 𝑈𝑑
⎩
For instance, we assume that 𝑣𝑡𝑖,1 = {⟨1, 2⟩∕0.3, ⟨1, 4⟩∕0.5, ⟨4, 1⟩∕0.6},
𝑥𝑡𝑖,1 = {⟨5, 1⟩, ⟨1, 2⟩}, 𝑝𝑡𝑓 (𝑖),1 = {⟨1, 4⟩, ⟨5, 1⟩}, 𝑤 = 0.4, 𝑐1 = 2.0, 𝑟1 =
0.3. Then, we have 𝑤 ∗ 𝑣𝑡𝑖,1 = {⟨1, 2⟩∕0.12, ⟨1.4⟩∕0.2, ⟨4, 1⟩∕0.24} and
( )
𝑝𝑡𝑓 (𝑖),1 − 𝑥𝑡𝑖,1 = {⟨1, 4⟩} and 𝑐1 ∗ 𝑟1 ∗ 𝑝𝑡𝑓 (𝑖),1 − 𝑥𝑡𝑖,1 = {⟨1, 4⟩∕0.6}.
( )
Finally, the new velocity 𝑣𝑡𝑖,1 = 𝑤 ∗ 𝑣𝑡𝑖,1 + 𝑐1 ∗ 𝑟1 ∗ 𝑝𝑡𝑓 (𝑖),1 − 𝑥𝑡𝑖,1 =
{⟨1, 2⟩∕0.12, ⟨1, 4⟩∕0.6, ⟨4, 1⟩∕0.24} can be obtained.
In order to speed up the algorithm’s convergence, this paper applies
Fig. 1. Framework of N-CLPSO.
a new velocity update strategy [27], which sets the learning probability
according to the particle’s fitness and selects different learning samples
according to the characteristics of the particle itself, shown as Eqs. (21)
ensures that each element is a valid city, the constraint (2) makes each and (22).
city will not be adjacent to itself, and the constraint (3) enables that 𝑠𝑐𝑖
each city’s neighboring points are not duplicated. Taking a VRPTW with 𝑃 𝑐𝑖 = (21)
2∗𝑁
four cities as an example, a route sequence 0 → 2 → 4 → 3 → 1 → ( )
( ) ⎛ 𝑁 ⎞
0, can be represented by 5 arcs: 01,2 , 13,0 , 20,4 , 34,1 , 42,3 . Meanwhile, ⎜ ceil 2 − 2 ⎟
[ ] 𝑛 = 2 + round ⎜ ⎟ (22)
there exists a set of probability sets 𝑣𝑡𝑖,𝑑 = ⟨𝑢, 𝑣⟩∕𝑝(𝑢, 𝑣) ∣ ⟨𝑢, 𝑣⟩ ∈ 𝐴𝑑 ⎜ 𝑁 ∗ 𝑠𝑐𝑖 ⎟
𝑡
in dimension 𝑑 of the velocity vector 𝑉𝑖 , where 𝐴𝑑 denotes the set of ⎝ ⎠
all possible adjacent arcs to node 𝑑 and 𝑝(𝑢, 𝑣) ∈ [0, 1] is the probability where 𝑁 is the size of population, 𝑠𝑐𝑖 is the ranking of particle 𝑖 in terms
corresponding to each arc ⟨𝑢, 𝑣⟩. of its fitness value in the population, and 𝑛 is the number of selected
The framework of N-CLPSO is demonstrated by Fig. 1 exemplars.
N-CLPSO selects CLPSO as a basic frame, and some additional oper- Unlike the traditional CLPSO, in which a particle selects its learning
ators are introduced, i.e., a vehicle insertion strategy (see Section 4.4), exemplar based on its index, a particle in N-CLPSO adjusts its learning
a diversity retention strategy (see Section 4.6), and a neighborhood probability and the number of learning exemplars based on its fitness.
search strategy (see Section 4.5). After the N-CLPSO velocity and From Eqs. (21) and (22), we can observe that the learning probability
position update (see Section 4.2), we use a vehicle insertion strategy 𝑃 𝑐 and the number of selected exemplars can be adapted according to
to minimize the number of vehicles in a feasible solution. Then, the a particle’s fitness and the size of the population. Concretely, the higher
diversity retention strategy and the neighborhood search strategy are fitness a particle has, the smaller the 𝑃 𝑐 and the 𝑛 will be. Thus, elite
executed while 𝐺𝑏𝑒𝑠𝑡 and 𝑃 𝑏𝑒𝑠𝑡 are stagnant, respectively. After that, particles can pay more attention to self-learning, which is beneficial
the global optimal solution of the population 𝐺𝑏𝑒𝑠𝑡 is updated. The for keeping their promising property. On the contrary, if the individual
above steps are repeatedly executed until the stopping conditions are fitness is lower, the 𝑃 𝑐 and the 𝑛 will be larger, so the particle has a
satisfied. greater probability of learning from other particles. Hence, the inferior
It has been pointed out in Section 2 that VRPTW has two objectives. particles have more chances to obtain favorable knowledge from other
In this study, we combine a new decision method [11] to deal with particles.
the number of vehicles (𝑁𝑉 ) and the total distance (𝑇 𝐷) of VRPTW. In N-CLPSO, the original position update process in CLPSO is
To better present the priority of the 𝑁𝑉 objective over the 𝑇 𝐷 objec- replaced by a new process, which is detailed in Algorithm 1. The
tive, we normalize 𝑇 𝐷 in the range of [0,1] weighted with 𝑁𝑉 . The position of the particle can be obtained by three set: 𝑆𝑉 = {𝑚 ∣
( )
objective function of N-CLPSO is defined as Eq. (15), where 𝑁𝑉 𝑋𝑖𝑡 ⟨𝑘, 𝑚⟩ ∈ 𝑉𝑖 , and ⟨𝑘, 𝑚⟩ satisfies 𝛺}, 𝑆𝑥 = {𝑚 ∣ ⟨𝑘, 𝑚⟩ ∈ 𝑋𝑖 , and ⟨𝑘, 𝑚⟩
( 𝑡)
and 𝑇 𝐷 𝑋𝑖 denote the number of vehicles and the total distance satisfies 𝛺}, 𝑆𝑎 = {𝑚 ∣ ⟨𝑘, 𝑚⟩ ∈ 𝐴, and ⟨𝑘, 𝑚⟩ satisfies 𝛺}. It can be

4
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

seen that the arc ⟨𝑘, 𝑚⟩ comes from the sets 𝑉𝑖 , 𝑋𝑖 and 𝐴 must satisfy (see Section 4.4). When all nodes are inserted successfully, as shown in
corresponding constraints. We set a random number 𝑟 ∈ [0,1] in order Fig. 2(a), a new route 𝑟 consisting of two new sub-tours 𝑉 𝑐(1) and 𝑉 𝑐(2)
to ensure that arcs with larger probability are more likely to be selected, can be obtained, and then the path 𝑉 𝑐(1) can be removed. If any node is
and only arcs with probability greater than 𝑟 in 𝑉𝑖𝑡 will be added to 𝑉𝑖 . not inserted in the 𝑟∗ as shown in Fig. 2(b), the route keeps the sub-tour
Then, the set 𝑋𝑖 and 𝐴 represent the set of all possible arcs from the in the state before insertion, and removes path 𝑉 𝑐(2). Such operations
current position 𝑋𝑖𝑡 and the search space. are repeated until all sub-tours are visited. The time complexity of the
As in Algorithm 1, the new position 𝑋𝑖𝑡+1 is set to the empty set vehicle insertion strategy is directly related to the number of sub-tours
before the position update. According to the constraint, each vehicle 𝐾. If the insertion time is 𝑚, the time complexity of this strategy is
departs from the depot and iteratively selects the next customer to be 𝑂(𝐾 ∗ 𝑚).
served. Suppose 𝑘 is the customer being served by the vehicle and the
next customer 𝑚 is to be visited by the vehicle. If there is an available Algorithm 2 Vehicle insertion strategy
node in 𝑆𝑉 , we select 𝑚 from 𝑆𝑉 . Otherwise, we select 𝑚 from 𝑆𝑥 . When
Input: Routing 𝑟, Vehicle Collection 𝑉 𝑐
there is no available node in both 𝑆𝑉 and 𝑆𝑥 , we select 𝑚 from 𝑆𝑎 . After
Output: New Routing 𝑁𝑟
𝑚 is selected, arc ⟨𝑘, 𝑚⟩ is added to 𝑋𝑖𝑡+1 . The search process is repeated
1: 𝑛 = 𝑛𝑢𝑚𝑏𝑒𝑟(𝑉 𝑐); //Record total number of vehicles
until all customers have been visited.
2: 𝑖 = 1;
When there are no available nodes in the sets 𝑆𝑣 , 𝑆𝑥 , and 𝑆𝑎 , the
3: while 𝑖 <= 𝑛 do:
constraints of VRPTW cannot be satisfied. Hence, a new path needs to
be created, i.e., a new sub-tour needs to be opened. Specifically, a depot 4: 𝑖𝑛𝑠 = 𝑉 𝑐(𝑖); //Add the node with vehicle 𝑖 to the set to be
node needs to be inserted after the current customer point 𝑘, and the inserted
next customer point 𝑚 to be served is reselected using the depot as the 5: 𝑟∗ = 𝑟 − 𝑉 𝑐(𝑖); //Remove the vehicle 𝑖 from the path r
starting point, thus ensuring the feasibility of 𝑋𝑖𝑡+1 . Finally, the updated 6: Insert 𝑖𝑛𝑠 into 𝑟∗ using Algorithm 3;//See Section 4.4
𝑋𝑖𝑡+1 will replace the current position 𝑋𝑖𝑡 . In addition, we also use the 7: if 𝑖𝑛𝑠 all inserted successfully then
heuristic selection method NNH [11] to speed up the convergence of 8: 𝑟 = 𝑟∗ ;
the algorithm. 9: 𝑛 = 𝑛 − 1;
10: else
11: 𝑟 = 𝑟;
Algorithm 1 Position update in N-CLPSO 12: 𝑖 = 𝑖 − 1;
Input: 𝑋𝑖 ; 𝑉𝑖 ; 𝐴; 13: end if
Output: 𝑋𝑖𝑡+1 14: end while
1: 𝑋𝑖 = 𝜙;𝑘 = 0; 15: 𝑁𝑟 = 𝑟;
{ }
2: 𝑆𝑉 = 𝑚 ∣< 𝑘, 𝑚 >∈ 𝑉𝑖 , and < 𝑘, 𝑚 > satisfies 𝛺 ;
{ }
3: 𝑆𝑥 = 𝑚 ∣< 𝑘, 𝑚 >∈ 𝑋𝑖 , and < 𝑘, 𝑚 > satisfies 𝛺 ;
4.4. Guided reinsertion operator based on local information
4: 𝑆𝑎 = {𝑚 ∣< 𝑘, 𝑚 >∈ 𝐴, and < 𝑘, 𝑚 > satisfies 𝛺};
5: while Customers do not have complete access do:
The VRPTW problem itself has a very complex time-space distribu-
6: if 𝑺 𝑽 ≠ 𝜙 then
tion, where the customer points are not only distributed in different
7: select m in 𝑆𝑉 , and add < 𝑘, 𝑚 > to 𝑋𝑖𝑡+1
locations in space (i.e., spatial distribution characteristics), but also
8: 𝑘 = 𝑚;
have their distinct time windows (i.e., temporal distribution character-
9: update 𝑆𝑉 ,𝑆𝑥 ,𝑆𝑎 ; istics). If the spatial locations of two customs are close, but their time
10: else if 𝑺 𝒙 ≠ 𝜙 then windows are very different, directly connecting the two customs in a
11: select 𝑚 in 𝑆𝑥 , and add < 𝑘, 𝑚 > to 𝑋𝑖𝑡+1 route may result in a longer waiting time for a vehicle, which makes the
12: 𝑘 = 𝑚; quality of the solution degrade. On the contrary, if the time windows
13: update 𝑆𝑉 ,𝑆𝑥 ,𝑆𝑎 ; of two customers are close, but the distances of them are far, infeasible
14: else if 𝑺 𝒂 ≠ 𝜙 then solutions may be generated if the two customers are severed by the
15: select m in 𝑆𝑎 , and add < 𝑘, 𝑚 > to 𝑋𝑖𝑡+1 same vehicle. Therefore, it is necessary to consider both time and space
16: 𝑘 = 𝑚; factors when solving VRPTW.
17: update 𝑆𝑉 ,𝑆𝑥 ,𝑆𝑎 ; In this section, a guided reinsertion operator based on local informa-
18: else tion is proposed. To create a local information matrix, the space–time
19: 𝑘 = 0; distribution characteristics between customer points, elite segment in-
20: update 𝑆𝑉 ,𝑆𝑥 ,𝑆𝑎 ; formation, and insertion cost are considered. Then, we go through the
21: end if local information matrix to guide customers to reinsert into a path.
22: end while In this study, the local information matrix is mainly divided into two
modules: one is the customer information matrix (𝐼𝑀), and the other is
the route cost matrix (𝐶𝑀) that rises after customer insertion. Details
4.3. Vehicle insertion strategy
of the two modules are introduced as follows.
It is well known that the number of vehicles is one of the crucial
4.4.1. Information matrix
factors determining a VRP’s difficulty. In reality, each additional vehi-
Inspired by the study in [28], we regard that local information
cle is likely to increase the cost significantly. Therefore, in this study,
among customers can be utilized to quickly calculate the probability
a simple insertion scheme is applied to reduce the number of vehicles
of adjacency between two customers, and then help N-CLPSO to obtain
after each particle completes its position update. The vehicle insertion
a higher quality solution set after the crossover operation. Therefore,
strategy is shown in Algorithm 2.
the 𝐼𝑀 proposed in this work is constructed based on the time-space
Take Fig. 2 as an example, where ‘‘1’’ is a depot and ‘‘2’’–‘‘7’’ are
distribution characteristics of nodes and information on elite segments
6 customers. The route 𝑟 = {1, 2, 3, 1, 5, 6, 1, 4, 7, 1} means that there 𝑡 , defined as Eq. (23), denotes
of particles in N-CLPSO. Concretely, 𝐼𝑀𝑖,𝑗
are 3 sub-tours, i.e., 𝑉 𝑐(1) = {1, 2, 3, 1}, 𝑉 𝑐(2) = {1, 5, 6, 1}, and
the probability that customers 𝑖 and 𝑗 can be served by the same car
𝑉 𝑐(3) = {1, 4, 7, 1}. First, we remove sub-tour 𝑉 𝑐(1) from route 𝑟 to
consecutively.
obtain an intermediate route 𝑟∗ . After that, the nodes {2, 3} in 𝑉 𝑐(1)
𝑡
( ) ( )
need to be inserted into the 𝑟∗ through a guided insertion strategy 𝐼𝑀𝑖,𝑗 = 1 − 𝛽𝑡 ∗ 𝐷𝑆𝑇max − 𝐷𝑆𝑇𝑖,𝑗 + 𝛽𝑡 ∗ 𝐶𝑇 (23)

5
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

Fig. 2. Vehicle insertion diagram.

From Eq. (23) we can see that 𝐼𝑀𝑖,𝑗 𝑡 contains two components. where 𝑐𝑡 denotes the total number of times that customer 𝑖 and cus-
The first component is 𝐷𝑆𝑇max − 𝐷𝑆𝑇𝑖,𝑗 , where 𝐷𝑆𝑇𝑖,𝑗 , detailed as tomer 𝑗 are adjacent to each other from the beginning to the current
Eq. (24), represents the distance in time-space between customer 𝑖 generation; 𝑐𝑡𝑚𝑎𝑥 and 𝑐𝑡𝑚𝑖𝑛 denote the maximum and minimum values
and customer 𝑗. 𝐷𝑇𝑖,𝑗 and 𝐷𝑖𝑠𝑖,𝑗 denote the time and space distances of the number of times that all customers are adjacent to each other,
between customer points 𝑖 and 𝑗, respectively. It is obvious that the respectively.
latter can be expressed in terms of the Euclidean distance between two In evolutionary algorithms, individuals with better fitness values are
points. The size of the time window tends to be more likely to reflect more likely to produce superior offspring because elite individuals seem
the probability that two different customer points can be served by the more likely to be closer to the optimal solution. And common fragments
same vehicle. Generally, the probability of two points being served by of these elite individuals are more likely to be part of the optimal
the same vehicle will decrease as the interval between the two time solution. Therefore, if two adjacent customers frequently appear in
windows is very small. For instance, in the condition the vehicle is different elite particles, the probability of their being served by the
likely to exceed the latest time window constraint for the latter node
same vehicle will also be high in the optimal solution.
while finishing the service of the former node. To avoid the problem,
In the iterative process of 𝐼𝑀, the good genes of elite individuals
intuitively, we want the vehicle to have plenty of time to serve the
should gradually spread to the whole population. However, too fast
latter customer. Therefore, we utilize the idea in [42] to select the next
propagation of good genes often leads to premature algorithm conver-
serve customer. Concretely, we measure the time distance based on the
gence. Conversely, too slow a propagation of good genes may cause
amount of time saved when the vehicle arrives before the end of the
time window. poor solution accuracy. Therefore, a linearly decreasing coefficient 𝛽𝑡
( ) ( ) defined in Eq. (28) is introduced to adjust the diffusion rate of the
𝐷𝑇𝑖,𝑗 − min(𝐷𝑇 ) 𝐷𝑖𝑠𝑖,𝑗 − min(𝐷𝑖𝑠)
𝐷𝑆𝑇𝑖,𝑗 = (1 − a) ∗ +a∗ (24) superior genes.
max(𝐷𝑇 ) − min(𝐷𝑇 ) max(𝐷𝑖𝑠) − min(𝐷𝑖𝑠)
𝑡
Suppose there exists customer 𝑖 and customer 𝑗, time windows 𝛽𝑡 = (28)
𝑡max
of them are [𝑎, 𝑏] and [𝑐, 𝑑], respectively, and 𝑘1 and 𝑘2 denote the
cost coefficients of the remaining service time and waiting time of where 𝑡 is the current number of generations and 𝑡𝑚𝑎𝑥 is the maximum
the vehicle, respectively, then the vehicle-saving time can be found number of generations.
according to the time 𝑡′ of the vehicle arriving from 𝑖 to 𝑗, as in It can be seen from Eq. (28) that at the early stage of algorithm
Eq. (25). optimization, a smaller 𝛽𝑡 is conducive to preserving the population
diversity and enhancing the global search ability of the population.
⎧𝑘 ∗ (𝑑 − 𝑐) − 𝑘 ∗ (𝑐 − 𝑡′ ) , 𝑡′ < 𝑐
⎪ 1 2 On the contrary, at the later evolutionary stage, a greater 𝛽𝑡 enables
𝑆𝑖,𝑗 = ⎨ −𝑘1 ∗ 𝑡′ + 𝑘1 ∗ 𝑑, 𝑐 ≤ 𝑡′ ≤ 𝑑 (25) the spread of excellent genes to be faster, which is beneficial to the
⎪ −∞, 𝑡′ >𝑑
algorithm’s convergence.
⎩
As mentioned above, a larger 𝐼𝑀𝑖,𝑗 𝑡 indicates that the probability
When the vehicle arrives early at customer 𝑗, the vehicle needs to
of customer 𝑖 and customer 𝑗 being served by the same car in the 𝑡th
wait until the customer starts service time 𝑐. Therefore, the time saved
generation is larger. It is worth noting that the size of 𝐼𝑀 is determined
𝑆𝑖,𝑗 is equal to the length of the customer’s time window minus the time
the vehicle is waiting. If the vehicle arrives within the time window by the number of customers. Concretely, when the number of customers
at point 𝑗, the saving time 𝑆𝑖,𝑗 is equal to the end time window 𝑗, is 𝑁, the size of 𝐼𝑀 is 𝑁 ∗ 𝑁. Thus, to reduce the computational cost,
subtracting the arrival time 𝑡′ . If the vehicle arrival time exceeds the we only update 𝐼𝑀 when the global optimal solution is updated.
end time 𝑑 of the customer, the customer cannot be served. We can
see that it is easier for customer 𝑖 to go to customer 𝑗 if 𝑆𝑖,𝑗 is larger. 4.4.2. Cost matrix
To be consistent with the spatial distance, we define the time distance To speed up the convergence, we also propose a 𝐶𝑀-assisted infor-
between two customers denoted as Eq. (26). mation matrix for bootstrap repair. 𝐶𝑀 finds the best insertion position
in a path with the help of greedy ideas, i.e., the insertion brings the least
𝐷𝑇𝑖,𝑗 = 𝑘1 max(𝑆) − 𝑆𝑖,𝑗 (26) increase in total cost afterward. As shown in Fig. 3, there exists a point 𝑖
The second component on the right side of Eq. (23) is 𝐶𝑇 , which to be inserted into a path 𝑟 with length 𝐿+1. In the insertion process, we
represents the local information (see Eq. (27)) of the elite individuals. not only need to determine whether node 𝑖 satisfies a constraint after
𝑐𝑡 − 𝑐𝑡min insertion, but also need to calculate the corresponding incremental cost.
𝐶𝑇 = (27) Note that, if the constraint is violated after node 𝑖 has been inserted into
𝑐𝑡max − 𝑐𝑡min

6
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

Algorithm 3 Guided reinsertion operator based on local information

Input:
the current route 𝑟, the node set 𝑖𝑛𝑠 to be inserted, the information
matrix 𝐼𝑀, and the distance matrix 𝐷𝑖𝑠.
Output: 𝑁𝑟
1: 𝑁𝑟 = 𝑟;
2: for 𝑖 = 1 to |𝑖𝑛𝑠| do // |𝑖𝑛𝑠| denotes the number of customers to
be inserted
3: 𝑙 ← Calculate the path 𝑟 length;
4: 𝑠𝑡𝑎𝑦 ← Record the location of the path 𝑟 repository;
5: 𝑃 𝑑 ← 𝑖𝑛𝑠(𝑖);∕∕𝐼𝑛𝑠𝑒𝑟𝑡𝑁𝑜𝑑𝑒
Fig. 3. 𝐶𝑀 building process. 6: 𝐶𝑀 ← Create a two-dimensional matrix with initial value ∞ for
𝑙 ∗ 𝑙;
7: 𝑗 ← 1;
a point in the path, the corresponding cost increment is ∞. It can be 8: while 𝑗 < 𝑙 do //Calculate 𝐶𝑀
seen from the value of 𝐶𝑀 in Fig. 3 that node 𝑖 satisfies the condition 9: if the node 𝑃 𝑑 insertion is overweight then
of insertion positions 𝐿 − 1 and 𝐿. Therefore, the cost increment after 10: 𝑗 = 𝑠𝑡𝑎𝑦(find(𝑠𝑡𝑎𝑦 == 𝑗) + 1); // go to the next path
insertion is saved to 𝐶𝑀. 11: else
From the above definitions of 𝐼𝑀 and 𝐶𝑀, it is clear that a larger 12: if 𝑃 𝑑 can be inserted in the current position then
𝑡 denotes a greater correlation between node 𝑖 and node 𝑗, while
𝐼𝑀𝑖,𝑗 13: 𝑃 𝑖 = 𝑁𝑟(𝑗);// Predecessor Nodes
a smaller 𝐶𝑀𝑙 means a smaller incremental cost of routing when the 14: 𝑃 𝑗 = 𝑁𝑟(𝑗 + 1);// Post nodes
node is inserted into location 𝑙. Therefore, both 𝐼𝑀 and 𝐶𝑀 are 15: // Calculating Cost Increment
considered when inserting node 𝑖 into a certain path. We first perform 16: 𝐶𝑀(𝑗) = 𝐷𝑖𝑠(𝑃 𝑖, 𝑃 𝑑) + 𝐷𝑖𝑠(𝑃 𝑑, 𝑃 𝑗) − 𝐷𝑖𝑠(𝑃 𝑖 − 𝑃 𝑗);
ascending and descending operations on 𝐼𝑀 and 𝐶𝑀, respectively. 17: 𝑗 = 𝑗 + 1;
Then, the insertion position of node 𝑖 is determined based on the 18: end if
contents of the two matrices. Specifically, we base the selection on the 19: end if
sum of the ranking values of the positions to be inserted in the two 20: if 𝑃 𝑑 has no position where it can be inserted then
matrices. For example, if the position to be inserted is ranked 3rd in 21: 𝐼𝑋 = [];
𝐼𝑀 and 8th in 𝐶𝑀, the priority value of the inserted position is equal 22: else
to 11. Finally, according to the priority value of each inserted position, 23: 𝐼𝑀 ← Sorting node 𝑃 𝑑 in ascending order;
the inserted position with the lowest priority value is selected to insert 24: 𝐶𝑀 ← Sort the cost matrix of node 𝑃 𝑑 in descending
node 𝑖. It is worth noting that if node 𝑖 is in the current path and there order;
is no location where it can be inserted, then the node will start a new 25: 𝐼𝑋 ← Find the number of the lowest position in the sum
route from the warehouse. Based on the above discussions, a guided of 𝐼𝑀 and 𝐶𝑀 rankings;
reinsertion operator based on local information is detailed in Algorithm 26: end if
3. From Algorithm 3, we know that the insertion operator operation is 27: if 𝐼𝑋 is empty then
mainly focused on the process of creating 𝑙 of 𝐶𝑀 and inserting one 28: 𝑁𝑟 ← Insert 𝑃 𝑑 and repository at the end of 𝑁𝑟;
by one of the clients 𝐷 to be inserted. Therefore, the time complexity 29: else
is 𝑂(𝑙 ∗ 𝐷). 30: 𝑁𝑟 ← Insert 𝑃 𝑑 at the location of 𝐼𝑋;
31: end if
4.5. Removal-reinsert-based neighborhood search 32: end while
33: end for
When using PSO to solve VRPTW problems, an efficient neigh-
borhood search operator plays a positive and crucial role in helping
particles to jump out of local optima, improving the solution accuracy,
and accelerating the convergence speed [43]. Furthermore, the study where 𝑁 is the number of customers and 𝐼 is the number of generations
in [44] verifies that the neighborhood region of elite particles is more in the population for which the optimal solution has not been updated.
likely to contain high-quality solutions or even global solutions. There- As the number of generations of optimal solution stagnation increases,
fore, to enhance the local search efficiency of N-CLPSO, we perform the number of removed customers also increases. Obviously, in the local
a neighborhood search operation for elite individuals, rather than all search, more removed customs mean a larger perturbation range of a
individuals, in the population. Concretely, the neighborhood search particle. Thus, removing more customers in the local search process
operation only exerts on the individual optimal solution 𝑃 𝑏𝑒𝑠𝑡. can help an individual to jump out of the local optimum. However,
Motivated by the Large Neighborhood Search(LNS) [45], we intro- removing too many customers increases computing costs and may
duce a removal-reinsert-based neighborhood search method. First, we reduce local search efficiency. Conversely, if the number of removed
randomly choose one of the removal methods to remove 𝐷 customers customers is too little, the capability of the individual that jumps out
from the complete route and insert them into the set 𝑁𝑡 of customers to of the local optimum as well as search for more promising regions is
be inserted. Then, we reinsert the route by guided reinsertion operator small. Through extensive experiments, we finally chose ‘‘N/10’’ as the
based on local information(see Section 4.4), i.e., the customer nodes upper bound of 𝐷.
in 𝑁𝑡 are reinserted into the route, forming a route that traverses all
(1) In Section 4.4.1, we define 𝐼𝑀 to measure the probability of
nodes to generate a new solution. Finally, we compare the routes before
being served by the same vehicle successively among customers. With
and after the update, and then keep the better individuals for the next
the help of 𝐼𝑀, we can design an information matrix-based removal
iteration.
strategy, as in Algorithm 4. First, we randomly select a customer point
We determine the number of customers 𝐷 to be removed according
to Eq. (29). 𝑖 and insert it into the customer set 𝑁𝑡. After that, we randomly pick
( ( ) ( )) a point 𝑖′ in 𝑁𝑡 and select 𝑗 points to join 𝑁𝑡 based on 𝐼𝑀, where
𝐼 𝑁
𝐷 = min ceil , ceil (29) node 𝑗 denotes the node that is least likely to be adjacent to node 𝑖′ ,
10 10

7
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

i.e. 𝐼𝑀𝑖𝑡′ ,𝑗 = 𝑚𝑖𝑛(𝐼𝑀𝑖𝑡′ ). Since we are borrowing the 𝐼𝑀 for evaluation,

the time complexity of the operator is 𝑂(𝐷).

Algorithm 4 Removal strategy based on IM

Input:
//Information Matrix and node to be deleted, respectively
𝐼𝑀; 𝐷;
Output: Delete node set 𝑁𝑡
1: 𝑁𝑡 = 𝜙;
2: for 𝑥 = 1 to length of 𝐷 do
3: Randomly select a customer 𝑖 from 𝑁𝑡;
′
4: Find the node 𝑗 that is least likely to be adjacent to customer 𝑖
by 𝐼𝑀;
Fig. 4. Illustrative example of diversity strategy.
5: 𝑁𝑡 = 𝑁𝑡 ∪ {𝑗};
6: end for

(2) We propose a removal operator based on the customer’s removal When using PSO to optimize a VRPTW problem, each particle can
cost, and its pseudo-code is shown in Algorithm 5. The algorithm per- often be represented by a complete route. Therefore, we base on the
forms a removal operation on a customer by calculating the difference elite fragment between the particle and the elite particle, other nodes
in cost incurred by removing each customer point from the original will be inserted into the elite fragment one by one through the guided
path, i.e., the removal cost. We select a customer 𝑖 to insert into 𝑁𝑡 reinsertion strategy to form a new route, and finally, we reserve the
based on the removal cost corresponding to each customer in a roulette better individual. It can be seen that the retention of elite fragments
wheel method. The time complexity of our removal of customer 𝐷 is avoids excessive degradation of particles to some extent, and the strat-
𝑂(𝐷). egy perturbs the current particles while ensuring the performance of
the algorithm. Obviously, when two particles are more similar, their
Algorithm 5 Removal strategy based on removal cost extracted fragments are longer and the set of nodes to be inserted is
Input: smaller. On the contrary, if two particles are more different, their com-
// Enter the route, distance matrix and node to be deleted, mon sequence is shorter and the number of nodes to be removed will
respectively be more, which is more conducive to increasing population diversity as
𝑟;𝐷𝑖𝑠;𝐷; well as helping the algorithm to jump out of the local optimum.
Output: Delete node set 𝑁𝑡 Fig. 4 depicts the process of the proposed diversity retention strat-
egy. For example, the sample particle 𝑟1 is {1, 2, 5, 6, 1, 3, 4, 7, 8, 1}, and
1: 𝑁𝑡 = 𝜙;
the current particle is 𝑟2 is {1, 3, 6, 1, 2, 4, 7, 1, 5, 8, 1}. Then, we can
2: 𝐿 = 𝑟.𝑙𝑒𝑛𝑔𝑡ℎ;
obtain that the LCS of 𝑟1 and 𝑟2 is {1, 6, 1, 4, 7, 8, 1}. Based on the LCS,
3: for 𝑥 = 2 ∶ 𝐿 − 1 do // Calculate the removal cost 𝛥𝑐 for each
the set of nodes to be inserted is {2, 3, 5}. After that, we insert the
customer point removed
customer nodes in the node-set into the LCS to get the new 𝑟3. Note
4: 𝐹 = 𝑟(𝑥 − 1); // Precursor node of node 𝑥
that the finding process of the LCS depends on the length of the 𝑟1 and
5: 𝐶 = 𝑟(𝑥); // Node 𝑥
𝑟2. Thus, the time complexity of it is 𝑂(𝑛 ∗ 𝑚).
6: 𝑅 = 𝑟(𝑥 + 1); // Posterior node of node 𝑥
7: 𝛥𝑐(𝑥) = 𝐷𝑖𝑠(𝐹 , 𝐶) + 𝐷𝑖𝑠(𝐶, 𝑅) − 𝐷𝑖𝑠(𝐹 , 𝑅);
4.7. Complexity analysis of N-CLPSO
8: end for
9: 𝑘 = 0;
In this section, we analyze the overall time complexity of N-CLPSO.
10: while 𝑘 < 𝐷 do
For convenience, we assume that the population size of the particle is
11: Randomly select the customer 𝑖 in 𝛥𝑐 where 𝑁𝑡 does not appear
𝐷, the number of clients is 𝑁, the maximum stopping condition is 𝐼𝑡𝑒𝑟,
by roulette;
the clients to be inserted are 𝑚, and the 𝐶𝑀 length is 𝑛.
12: 𝑁𝑡 = 𝑁𝑡 ∪ {𝑖};
According to Section 4.1, N-CLPSO is the addition of a vehicle in-
13: 𝑘 = 𝑘 + 1;
sertion strategy, diversity retention strategy, and neighborhood search
14: end while
strategy to the framework of CLPSO. After the description of the above
sections, we can easily know that the time complexity of its main body
4.6. Diversity retention strategy based on elite fragments is 𝑂(𝐷 ∗ 𝑁); the time complexity of the vehicle insertion strategy is
𝑂(𝐾 ∗ 𝑚 ∗ 𝑛); the time complexity of the neighborhood search strategy
In order to maintain the population diversity and improve the is 𝑂(𝑛 ∗ 𝑚); the time complexity of the diversity retention strategy is
quality of the solution, a diversity retention strategy based on elite O(N ∗ N). Since the policies in N-CLPSO are invoked only in special
fragments is designed in this study. cases, the time complexity of N-CLPSO is 𝑂(𝐼𝑡𝑒𝑟 ∗ 𝐷 ∗ 𝑁) + 𝑂(𝐷 ∗
In PSO, the diversity of particles disappears as the number of 𝑘 ∗ 𝑚 ∗ 𝑛) + 𝑂(𝑚 ∗ 𝑛) + 𝑂(𝑁 ∗ 𝑁). Clearly, the time complexity of the
iterations rises, which directly leads to the premature convergence of algorithm is approximately equal to 𝑂(𝐼𝑡𝑒𝑟 ∗ 𝐷 ∗ 𝑁) when the number
the algorithm. In order to prevent the particles from converging pre- of iterations is sufficient.
maturely, we need to perturb the particles. However, a large range of
random perturb can easily make the particles degenerate and degrade 5. Experimental evaluation
the algorithm performance, though it is beneficial for improving popu-
lation diversity. Generally, in evolutionary algorithms, elite individuals In this section, Section 5.1 describes the general setup of the ex-
generally contain better genetic fragments. So when perturbing an periments. Section 5.2 describes the parameter tuning of the algo-
individual, if we can also retain some gene fragments shared by other rithm. Section 5.3 presents a sensitivity analysis of each component
elite individuals, we can increase diversity while retaining superior of the algorithm. Sections 5.4 and 5.5 compare N-CLPSO with other
genetic information. Therefore, inspired by the LCS [46], we propose a 3 PSO variants and other 12 state-of-the-art algorithms and draw some
diversity retention strategy based on elite fragments. conclusions.

8
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

5.1. Setup Table 1

Results on R101 and R201 with different parameters.

N-CLPSO is tested on a classical benchmark of 56 VRPTW instances Instances a k1 k2 MNV MTD Mean

proposed by Solomon [47] since the benchmark can reflect various real- 1 19 1652.34
1 2 19 1660.82
life scheduling problems. According to properties, the instances can be
3 19 1655.48
classified into three categories: clients distributed in a clustered manner
1 19 1654.33
(Class C), clients distributed in a random manner (Class R), and test sets
2 2 19 1655.21
with a mixture of clustering and randomness (Class RC). On this basis, 0.3 1656.36
3 19 1653.08
the test set can be further classified into two categories, i.e., problems
1 19 1658.43
with smaller vehicle capacities and more compact time windows (C1, 3 2 19 1660.22
R1 and RC1), and problems with larger vehicle capacities and longer 3 19 1657.32
dispatch cycles (C2, R2 and RC2). 1 19 1652.92
In this study, extensive experiments are conducted to investigate the 1 2 19 1651.15
performance of N-CLPSO. In the experiments, the inertia weight value 3 19 1654.44
𝑤 in Eq. (3) is initialized to 0.9 and decreases linearly from 0.9 to 0.4 1 19 1655.82
during the optimization process, and the acceleration coefficient 𝑐1 is 2 2 19 1652.14
0.5 1655.06
3 19 1654.32
set to 2.0. In this paper, the refresh gap ‘‘𝑟𝑔’’ of CLPSO is set according R101
to [30]. The learning probability 𝑃 𝑐 and the exemplar selection method 1 19 1658.93
3 2 19 1660.42
are used in Eqs. (21) and (22). Except for the experiments of parameter
3 19 1655.38
tuning, the parameters of Eqs. (24)–(25) are set to 𝑎 = 0.5, 𝑘1 = 1 and
1 19 1661.42
𝑘2 = 2, respectively. The population size is set to 𝑁 = 20. Neighborhood 1 2 19 1653.27
search and diversity preservation policies are activated at 10 and 100 3 19 1655.34
generations of 𝑃 𝑏𝑒𝑠𝑡 and 𝐺𝑏𝑒𝑠𝑡 stagnation updates, respectively. The 1 19 1654.48
optimization process will be stopped when 𝐺𝑏𝑒𝑠𝑡 has been stagnant for 2 2 19 1651.32
0.7 1655.63
10,000 consecutive generations. Each trial is performed independently 3 19 1657.44
20 times. 1 19 1658.30
3 2 19 1655.42
5.2. Parameter tuning 3 19 1653.64
1 4 1286.32
1 2 4 1260.37
This section mainly compares the effects of the three parameters
3 4 1273.32
involved in the calculation of the space–time distance (i.e., 𝑎, 𝑘1 and
1 4 1271.44
𝑘2 in Eqs. (24)–(25)) on the N-CLPSO. Table 1 shows the average best
2 2 4 1282.32
solutions obtained by N-CLPSO with different parameters on instances 0.3 1277.39
3 4 1270.48
R101 and R201, where ‘‘MNV’’ and ‘‘MTD’’ denote the results of the
1 4 1284.93
average number of vehicles and average distance, respectively, and 3 2 4 1288.48
‘‘Mean indicates the average distance with the same parameter 𝑎. Note 3 4 1278.87
that the parameter a determines the time-space proportion of customer 1 4 1284.98
distance and time window. Thus, when 𝑎 is larger, the proportion of 1 2 4 1257.68
spatial distance in customer distance information is more significant. 3 4 1290.29
On the contrary, if 𝑎 is smaller, the proportion of temporal distance 1 4 1277.78
in customer distance information is more significant. 𝑘1 and 𝑘2 denote 0.5 2 2 4 1264.38
1273.48
3 4 1269.37
the cost coefficients of remaining vehicle service time and waiting R201
time, respectively, and the difference between them should not be too 1 4 1282.99
3 2 4 1271.35
significant. Otherwise, the quality of the final solution will be affected.
3 4 1262.49
Therefore, the values of 𝑎, 𝑘1 and 𝑘2 are set as follow: 𝑎 ∈ {1, 2, 3},
1 4 1279.32
𝑘1 ∈ {1, 2, 3}, 𝑘2 ∈ {1, 2, 3}. 1 2 4 1277.43
To illustrate the results more clearly, the experimental results are 3 4 1260.32
marked. Concretely, the darker the cell background color is, the better 1 4 1278.84
the result is. On R101 and R201, the average distance is shortest when 2 2 4 1283.81
0.7 1274.57
𝑎 = 0.5, followed by 𝑎 = 0.7 and 𝑎 = 0.3. This may be because N-CLPSO 3 4 1275.33
focuses more on spatial distance when it becomes smaller, which leads 1 4 1259.31
to a shorter average distance. However, the most favorable results 3 2 4 1277.48
of 𝑎 = 0.5 indicate that considering both time and spatial distance 3 4 1279.32

can enable N-CLPSO to have a more comprehensive performance. On

R101 and R201, which have a narrow time window and a wide time
window, respectively, N-CLPSO can offer more promising performance. adding components one by one to the original CLPSO. The strategies
Therefore, it is reasonable to believe that the waiting time may be
proposed in this paper focus on speeding up the convergence and
more important than the remaining service time of the vehicle when
maintaining population diversity.
calculating the time distance. Interestingly, we find that N-CLPSO
achieves the best results when 𝑎 = 0.5, 𝑘1 = 1, 𝑘2 = 2. Therefore, the In N-CLPSO, we use the new velocity selection strategy and vehicle
parameters of N-CLPSO are set to 𝑎 = 0.5, 𝑘1 = 1, 𝑘2 = 2. insertion strategy to velocity up the convergence of N-CLPSO. To this
end, 3 algorithms are adopted as competitors to N-CLPSO, i.e., ‘‘CLPSO’’
5.3. Sensitivity analysis of components in N-CLPSO which does not contain the new proposed strategies, ‘‘add-V’’ which de-
notes that only the new velocity update strategy is involved in CLPSO,
This section aims to clarify the impact of the components proposed and ‘‘add-C’’ which means that only the vehicle insertion strategy is
in N-CLPSO. We attempt to verify the effectiveness of the strategy by added in CLPSO.

9
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

Fig. 5. Contribution of velocity selection strategy and vehicle insertion strategy.

Comparison results shown in Fig. 5 demonstrate that ‘‘N-CLPSO’’ in most instances, in terms of the Percentage Error (PE) and the
shows faster convergence in these experiments and higher accuracy in Average Percentage Error (PEav) of the optimal distance between each
solving at later stages. The convergence velocity and solution accuracy algorithm and the best-known for the minimum number of vehicles, are
of ‘‘add-C’’ are slightly lower than those of ‘‘N-CLPSO’’, but higher shown in Fig. 6. For instance, if the optimal distances corresponding
than those of ‘‘add-V’’ and ‘‘CLPSO’’. Although ‘‘add-V’’ displays similar to the minimum number of vehicles for the proposed algorithm and
performance as ‘‘CLPSO’’, in terms of solution accuracy, it yields sig- the best-known algorithm are 19, 1648 and 19, 1650, respectively, the
nificantly higher convergence velocity than ‘‘CLPSO’’. Meanwhile, we corresponding percentage error is (19 − 19)∕19 + (1648 − 1650)∕1650.
find that the convergence velocity of ‘‘add-C’’ in Fig. 5 is significantly It can be observed that both the addition of the neighborhood search
better than that of ‘‘add-V’’, which is probably because the vehicle module and the diversity retention strategy optimized the optimal
insertion strategy reduces the number of vehicles of the particles as solution to be closer to the global optimal solution. However, the
much as possible. So that the particles are closer to the optimal solution, difference between ‘‘noLV’’ and ‘‘noZ’’ on most of the data sets is
the convergence velocity of ‘‘add-C’’ is faster than that of ‘‘add-V’’. not significant, except that ‘‘noLV’’ is better than ‘‘noZ’’ on the R201
Therefore, we can see that the new velocity update strategy and the and RC201. The results manifest that diversity retention strategies
vehicle insertion strategy play positive performance in improving the may play a more important and more positive performance than the
convergence velocity. neighborhood search strategy on ‘‘2’’ class problems. It is clear that the
In addition, to investigate the advantages of the neighborhood optimal results are obtained by adding both the neighborhood search
search and diversity retention strategies applied in N-CLPSO, 3 vari- and diversity retention strategies to N-CLPSO.
ants of N-CLPSO are selected as peer algorithms. Specifically, ‘‘noLV’’ In N-CLPSO, we used a combination of the 𝐼𝑀 and the 𝐶𝑀 to guide
and ‘‘noZ’’ denote two algorithms in which the neighborhood search the neighborhood reinsertion strategy. To verify the advantages of the
strategy and the diversity retention strategy are removed from N- combination matrix used in N-CLPSO, we implemented three variants
CLPSO, respectively, while ‘‘noLV+noZ’’ means that both the two new of N-CLPSO, i.e., N-CLPSO with 𝐼𝑀 only, N-CLPSO with 𝐶𝑀 only,
proposed strategies are removed from N-CLPSO. The comparison results and N-CLPSO with 𝐼𝑀 and 𝐶𝑀. Experimental results demonstrated

10
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

Fig. 6. Contribution of neighborhood search and diversity retention strategies.

Fig. 8. Performance comparison between HMPSO, HPSO, and N-CLPSO.

Table 3
The Wilcoxon non-parametric test of N-CLPSO and the three competitors.
N-CLPSO vs. S-PSO HMPSO HPSO
𝑅+ 46 28 37
𝑅− 0 12 2
𝑝-value 3.523e−9 0.002 6.6424e−8

complexity in Section 4.7. Although N-CLPSO incorporates various

strategies, the strategies are invoked only under certain conditions.
Thus, the comparison results in the table display that N-CLPSO con-
Fig. 7. Contribution of correlation matrix and cost matrix.
sumes only slightly more time than S-PSO on the R101 and RC101,
while the time consumed in the other instances is the same.
Table 2
Performance comparison between S-PSO and N-CLPSO.
N-CLPSO is compared with HMPSO and HPSO on 56 VRPTW in-
Instances S-PSO(2012) N-CLPSO
stances. Due to space limitation, only the comparison results on six
typical VRPTW instances are shown in Fig. 8. The average PEav of
PE Time (s) PE Time (s)
N-CLPSO is 0.048, much better than 0.171 for HMPSO and 0.375 for
R101 0.080 1.5 0.077 1.7
HPSO. It means that N-CLPSO is significantly better than HMPSO and
R201 0.018 1.2 0 1.2
C101 0 1.2 0 1.2 HPSO.
C201 0 1.1 0 1.1 Furthermore, to verify whether there is a significant difference
RC101 0.039 1.5 0.035 1.6 between N-CLPSO and the 3 competitors, in terms of the PEav, a set
RC201 0.012 1.1 0 1.1
of Wilcoxon signed rank tests are conducted. The comparison results
are presented in Table 3. The table shows that N-CLPSO is significantly
better than all the 3 peer algorithms since the three 𝑅+ values are
in Fig. 7 verify that using 𝐶𝑀 is better than using only 𝐼𝑀 on R101, greater than corresponding 𝑅− values. Although N-CLPSO and S-PSO
R201, RC101, and RC201 problems while using 𝐼𝑀 is better than using share some basic operators, N-CLPSO dominates S-PSO in all the test
only 𝐶𝑀 on the set clustering instance C104 and C204, it is clear that instances. Thus, we can draw a preliminary conclusion that the new
using both 𝐶𝑀 and 𝐼𝑀 has the best performance. proposed strategies enable N-CLPSO to have a favorable performance.

5.4. Comparison with other PSO-based algorithms 5.5. Comparison with other algorithms

Among the PSO-based algorithms, we compare the N-CLPSO algo- To verify the comprehensive performance of N-CLPSO, we com-
rithm with S-PSO [11], HMPSO [48], and HPSO [37]. As discussed pared it with 12 state-of-the-art algorithms, including three GAs [12,
in Section 4.2 in the revised manuscript, S-PSO and N-CLPSO share 49,50], one LNS [51], one ACO [10], one TS [52], six other heuris-
a similar velocity and position update approach. To gain insight into tics [53–58], and finally giving the results of the best average operation
the new proposed strategies in N-CLPSO, we compare S-PSO with N- for each subclass (C1, C2, R1, R2, RC1, and RC2). Moreover, the
CLPSO on 56 VRPTW instances. The average PEav of N-CLPSO is 0.048, best-known solutions are also adopted in experiments. Note that the
smaller than 0.084 of S-PSO. Table 2 shows the simulation results experimental parameters of each peer algorithm are consistent with the
for six instances, where ‘‘Time’’ indicates the average running time corresponding literature.
of the algorithm per generation. The population size and termination In Table 4, we also give a comparison of the proposed algorithm
conditions of S-PSO are the same as those of N-CLPSO. with the best-known results, where ‘‘NV’’ and ‘‘TD’’ denote the best-
Table 2 shows that N-CLPSO achieves better results on all six known results for the best number of vehicles and the corresponding
instances. The results verify that adding local search and diversity minimum distance, respectively. ‘‘BNV’’ denotes the best number of
preservation strategies can significantly improve the algorithm’s per- vehicles, while ‘‘BTD’’ denotes the minimum distance corresponding to
formance. Meanwhile, there are similarities in how the two algorithms the best number of vehicles. ‘‘MNV’’ and ‘‘MTD’’ denote the average
update their positions at the time level, as described by the time number of vehicles and the average distance obtained by the proposed

11
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

Table 4
Comparison with the best-known results.
Best-known N-CLPSO
Instances NV TD Source BNV BTD MNV MTD Deviation Std-N Std-T Time (s)
R101 18 1613.59 Tan et al. [59] 19 1648.08 19 1651.15 – 0 1.9 1.7
R102 17 1486.12 Rochat et al. [60] 17 1486.12 17 1490.97 0 0 4.4 1.5
R103 13 1292.68 Li et al. [61] 13 1292.68 13 1302.36 0 0 7.1 1.8
R104 9 1007.24 Mester [62] 10 996.27 10 1006.23 – 0 6.3 2.1
R105 14 1377.11 Rochat et al. [60] 14 1377.11 14 1379.01 0 0 1.9 1.4
R106 12 1251.98 Mester [62] 12 1252.03 12 1257.34 0.003% 0 4.6 1.3
R107 10 1104.66 Shaw [63] 11 1081.17 11 1088.31 – 0 7.5 1.2
R108 9 960.88 Berger et al. [64] 10 985.76 10 987.19 – 0 2.0 1.2
R109 11 1194.73 Homberger et al. [65] 11 1194.73 11.4 1191.37 0 0.49 8.0 1.5
R110 10 1118.59 Mester [62] 11 1101.49 11 1108.56 – 0 6.7 1.8
R111 10 1096.72 Rousseau et al. [66] 11 1064.67 11 1069.51 – 0 3.7 1.5
R112 9 982.14 Gambardella et al. [67] 10 974.95 10 979.28 – 0 4.3 1.6
R201 4 1252.37 Homberger et al. [65] 4 1252.37 4 1257.68 0 0 7.0 1.2
R202 3 1191.70 Rousseau et al. [66] 3 1225.02 3.5 1167.66 2.72% 0.71 7.5 1.6
R203 3 939.54 Mester [62] 3 962.25 3 970.32 2.36% 0 7.7 1.5
R204 2 825.52 Bent et al. [68] 3 766.13 3 775.29 – 0 8.5 1.7
R205 3 994.42 Rousseau et al. [66] 3 1027.79 3 1049.16 3.25% 0 12.4 1.9
R206 3 906.14 Schrimpf et al. [69] 3 939.46 3 943.78 3.55% 0 3.7 1.7
R207 2 837.20 Bouthillier et al. [70] 3 872.40 3 877.53 – 0 4.6 1.5
R208 2 726.75 Mester [62] 2 726.75 2 742.85 0 0 10.1 2.1
R209 3 909.16 Homberger [71] 3 943.72 3 953.46 3.66% 0 6.9 1.8
R210 3 938.58 Ghoseiri et al. [72] 3 965.88 3 982.01 2.74% 0 9.1 1.7
R211 2 892.71 Bent et al. [68] 3 828.90 3 835.75 – 0 8.0 1.5
C101 10 828.94 Rochat et al. [60] 10 828.94 10 828.94 0 0 0 1.2
C102 10 828.94 Rochat et al. [60] 10 828.94 10 828.94 0 0 0 1.1
C103 10 828.06 Rochat et al. [60] 10 828.06 10 829.77 0 0 1.3 1.3
C104 10 824.78 Rochat et al. [60] 10 824.78 10 828.73 0 0 3.9 1.2
C105 10 828.94 Rochat et al. [60] 10 828.94 10 828.94 0 0 0 1.1
C106 10 828.94 Rochat et al. [60] 10 828.94 10 828.94 0 0 0 1.1
C107 10 828.94 Rochat et al. [60] 10 828.94 10 828.94 0 0 0 1.2
C108 10 828.94 Rochat et al. [60] 10 828.94 10 828.94 0 0 0 1.1
C109 10 828.94 Rochat et al. [60] 10 828.94 10 828.94 0 0 0 1.2
C201 3 591.56 Rochat et al. [60] 3 591.56 3 591.56 0 0 0 1.1
C202 3 591.56 Rochat et al. [60] 3 591.56 3 591.56 0 0 0 1.1
C203 3 591.17 Rochat et al. [60] 3 591.17 3 591.17 0 0 0 1.3
C204 3 590.60 Rochat et al. [60] 3 590.60 3 591.08 0 0 0 1.2
C205 3 588.88 Rochat et al. [60] 3 588.88 3 588.88 0 0 0 1.1
C206 3 588.49 Rochat et al. [60] 3 588.49 3 588.49 0 0 0 1.2
C207 3 588.29 Rochat et al. [60] 3 588.29 3 588.29 0 0 0 1.1
C208 3 588.32 Rochat et al. [60] 3 588.32 3 588.32 0 0 0 1.1
RC101 14 1696.94 Taillard et al. [73] 15 1635.11 15 1636.46 – 0 1.8 1.6
RC102 12 1554.75 Taillard et al. [73] 13 1503.42 13 1507.48 – 0 4.4 2.0
RC103 11 1261.67 Taillard et al. [73] 11 1261.67 11 1269.69 0 0 8.0 1.2
RC104 10 1135.48 Fu et al. [74] 10 1135.48 10 1138.10 0 0 4.1 1.6
RC105 13 1629.44 Berger et al. [64] 14 1542.55 14 1545.24 – 0 4.2 1.8
RC106 11 1424.73 Berger et al. [64] 12 1388.70 12 1391.39 – 0 3.7 2.0
RC107 11 1222.1 Ghoseiri et al. [72] 11 1230.48 11 1234.56 0.68% 0 4.4 1.7
RC108 10 1139.82 Taillard et al. [73] 11 1157.12 11 1161.22 – 0 5.6 1.5
RC201 4 1406.91 Mester [62] 4 1406.91 4 1409.47 0 0 4.6 1.1
RC202 3 1365.65 Czech et al. [75] 4 1169.67 4 1173.16 – 0 6.0 1.5
RC203 3 1049.62 Czech et al. [75] 3 1082.57 3 1089.58 3.04% 0 6.6 1.8
RC204 3 798.41 Mester [62] 3 828.61 3 834.68 3.64% 0 4.6 1.5
RC205 4 1297.19 Mester [62] 4 1297.19 4 1303.73 0 0 5.3 1.9
RC206 3 1146.32 Homberger [71] 3 1146.32 3 1153.74 0 0 7.2 1.6
RC207 3 1061.14 Bent et al. [68] 3 1095.67 3 1106.65 3.15% 0 11.1 1.8
RC208 3 828.14 Ibaraki et al. [76] 3 828.14 3 843.75 0 0 10.4 1.6

algorithm, respectively. ‘‘Deviation’’ = (BTD- TD)/BTD is the percent- and the average ‘‘Std-T’’ of R1, R2, RC1, and RC2 are 4.88, 7.79,
age deviation of the algorithm from the best-known result for the same 4.53, and 6.98, respectively, which are all lower than 10. Moreover,
number of vehicles, which is used to measure the algorithm’s quality. ‘‘Std-N’’ on R109 and R202 are 0.49 and 0.71, while ‘‘Std-N’’ on all
‘‘Std-N’’ and ‘‘Std-T’’ denote the standard deviation of the number of other data sets are 0. The results show that N-CLPSO is stable and has
vehicles and the distance obtained by the algorithm, respectively, and good robustness. Furthermore, it can be seen that N-CLPSO yields more
are used to measure the stability of the solution. Time denotes the favorable performance on the ‘‘1’’ class problems that have narrow
average running time of the algorithm per generation. time windows, while there is a small decrease in the performance of
It can be seen from Table 4 that N-CLPSO reaches 29 optimal N-CLPSO on the ‘‘2’’ class problems that have longer time windows.
solutions. The optimal solution of N-CLPSO is almost in line with the In Table 5, we have selected two recently published state-of-art
best-known solutions reported in the literature. With the same number algorithms as competitors for N-CLPSO. Note that, the data for each
of vehicles, both C1 and C2 find the optimal solution. On R1, only algorithm prioritizes the minimum vehicle, followed by consideration
R106 deviates from the optimal solution, and the average deviation of the shortest path length. The results show that N-CLPSO obtains
is 0.23%, 2.23%, and 1.40% for RC1, R2, and RC2, respectively. the best results on 50 out of the 56 data sets, while ASC-BSO [53]
Regarding the standard deviation of ‘‘Std-T’’, both C1 and C2 are 0, and MOLNS [51] yield the best results on 20 and 17 test problems,

12
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

Table 5
Comparison results between N-CLPSO and other 2 recently published representative algorithms.
Instances ACS-BSO MOLNS N-CLPSO
NV TD Time (s) NV TD Time (s) NV TD Time (s)
R101 19 1671.16 2.1 19 1654.93 1.3 19 1648.08 1.7
R102 17 1504.60 2.1 18 1475.33 1.0 17 1486.12 1.5
R103 14 1245.86 1.9 14 1240.44 1.4 13 1292.68 1.8
R104 11 1010.73 1.9 10 1010.72 1.3 10 996.27 2.1
R105 15 1366.05 1.9 15 1389.85 0.9 14 1377.11 1.4
R106 13 1288.84 2.1 13 1269.14 1.0 12 1252.03 1.3
R107 11 1101.56 2.0 11 1102.72 1.0 11 1081.17 1.2
R108 10 974.17 2.3 10 991.57 1.1 10 985.76 1.2
R109 12 1165.71 2.0 12 1177.76 1.0 11 1194.73 1.5
R110 11 1090.92 2.0 12 1129.60 0.7 11 1101.49 1.8
R111 11 1148.14 2.0 12 1108.70 0.9 11 1064.67 1.5
R112 10 1004.53 2.0 10 964.15 1.1 10 974.95 1.6
R201 4 1336.05 2.1 4 1305.25 1.1 4 1252.37 1.2
R202 4 1128.05 2.4 4 1093.67 1.1 3 1225.02 1.6
R203 3 1020.10 2.3 4 915.43 1.2 3 962.25 1.5
R204 3 834.92 2.2 3 775.99 1.2 3 766.13 1.7
R205 3 1105.38 2.7 3 1075.10 0.8 3 1027.79 1.9
R206 3 949.11 2.4 3 979.21 1.0 3 939.46 1.7
R207 4 812.35 3.0 3 851.89 1.1 3 872.4 1.5
R208 2 940.30 2.9 2 754.99 1.2 2 726.75 2.1
R209 3 1046.73 2.7 4 898.23 0.9 3 943.72 1.8
R210 3 1069.26 2.4 4 941.58 0.9 3 965.88 1.7
R211 3 836.36 2.1 3 838.14 0.8 3 828.90 1.5
C101 10 828.94 1.6 10 828.94 0.9 10 828.94 1.2
C102 10 828.94 1.4 10 828.94 1.1 10 828.94 1.1
C103 10 828.06 1.5 10 828.94 1.0 10 828.06 1.3
C104 10 828.78 1.7 10 828.94 1.0 10 828.78 1.2
C105 10 824.94 1.6 10 828.94 0.9 10 828.94 1.1
C106 10 828.94 1.4 10 828.94 0.9 10 828.94 1.1
C107 10 828.94 1.4 10 828.94 0.7 10 828.94 1.2
C108 10 828.94 1.5 10 828.94 0.9 10 828.94 1.1
C109 10 828.94 1.5 10 828.94 0.9 10 828.94 1.2
C201 3 591.56 1.8 3 591.56 1.0 3 591.56 1.1
C202 3 591.56 1.2 3 591.56 1.0 3 591.56 1.1
C203 3 591.17 1.9 3 591.56 1.0 3 591.17 1.3
C204 3 591.60 1.6 3 590.60 1.0 3 590.60 1.2
C205 3 588.88 1.1 3 588.88 0.9 3 588.88 1.1
C206 3 588.49 1.5 3 588.49 0.8 3 588.49 1.2
C207 3 588.29 1.5 3 588.29 0.8 3 588.29 1.1
C208 3 588.32 1.0 3 588.32 0.8 3 588.32 1.1
RC101 16 1643.78 2.2 15 1662.56 0.8 15 1635.11 1.6
RC102 14 1464.63 1.9 14 1486.35 1.1 13 1503.42 2.0
RC103 11 1275.64 1.5 12 1291.95 1.3 11 1261.67 1.2
RC104 10 1156.92 1.5 10 1162.53 1.2 10 1135.48 1.6
RC105 14 1609.68 1.7 15 1604.53 0.9 14 1542.55 1.8
RC106 13 1378.45 1.6 13 1400.09 1.1 12 1388.70 2.0
RC107 11 1318.69 1.7 12 1259.55 1.2 11 1230.48 1.7
RC108 11 1134.85 1.7 11 1205.13 1.2 11 1157.12 1.5
RC201 4 1514.41 2.5 4 1497.89 0.9 4 1406.91 1.1
RC202 4 1326.71 2.6 4 1199.53 1.3 4 1169.67 1.5
RC203 3 1166.91 2.0 4 985.54 1.7 3 1082.57 1.8
RC204 3 929.94 2.6 3 805.46 1.5 3 828.61 1.5
RC205 4 1360.91 2.4 5 1340.38 1.0 4 1297.19 1.9
RC206 3 1237.21 2.3 3 1316.42 1.0 3 1146.32 1.6
RC207 4 1039.59 2.6 4 1031.62 1.3 3 1095.67 1.8
RC208 3 910.59 2.3 3 859.13 1.0 3 828.14 1.6

respectively. In all three algorithms, N-CLPSO is able to find the min- Table 6
The Wilcoxon non-parametric test of N-CLPSO with ACS-BSO and MOLNS.
imum number of vehicles and has the shortest path length in most
N-CLPSO vs. ACS-BSO MOLNS
of the data sets. Although the running time is directly related to the
encoding method and experimental equipment, we also compare the 𝑅+ 37 39
𝑅− 3 3
average iteration time of the three algorithms as one of the reference
𝑝-value 1.5875e−7 1.9112e−7
metrics. N-CLPSO has an average running time of 1.48 s per arithmetic
case, which is competitive with ASC-BSO’s 1.96 and MOLNS’s 1.04.
Meanwhile, to verify the performance of N-CLPSO in terms of
statistics results, we used the Wilcoxon signed ranks test to compare N-CLPSO dominates the 2 competitors in the Wilcoxon test. Since a
it with ACS-BSO and MOLNS, and the test results are demonstrated in large number of instances have various properties, we can regard that
Table 6. From the statistics test results, we see that, for N-CLPSO and N-CLPSO has a more reliable and comprehensive performance than the
ACS-BSO, the computed 𝑅+ , 𝑅− , and 𝑝-value are 37, 3, and 1.5875e−7 other algorithms.
respectively. For N-CLPSO and ACS-BSO, the computed 𝑅+ , 𝑅− , and In Table 7, the average best results of the given algorithms are given
𝑝-value are 39, 3, and 1.9112e−7 respectively. The results verify that for each subclass (C1, C2, R1, R2, RC1 and RC2). The results are given

13
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

Table 7
Comparison of average levels.
R1 R2 C1 C2 RC1 RC2
Best-known 11.83_1207.20 2.73_946.74 10_828.38 3_589.86 11.50_1383.12 3.25_1119.17
Tabu-ABC(2017) [52] 13.75_1187.90 4.64_891.24 10_828.38 3_589.86 13.13_1361.08 5.50_1017.47
ACO-N(2011) [10] 13.10_1213.16 4.60_952.30 10_841.92 3.3_612.75 12.70_1415.62 5.60_1120.37
HGSADC(2013) [57] 11.92_1210.69 2.73_951.51 10_828.38 3_589.86 11.50_1384.17 3.25_1119.24
D-VND(2021) [54] 12.42_1214.02 3.09_944.71 10_828.38 3_589.86 12.13_1369.00 3.38_1069.53
MAPSO(2019) [58] 11.92_1209.99 2.73_952.06 10_828.38 3_589.86 11.50_1384.18 3.25_1119.60
RRGA(2020) [12] 13.25_1180.66 5.54_878.64 10_828.38 3_589.86 12.75_1341.60 6.25_1004.35
MO TSP(2021) [55] 12.75_1195.77 3.09_953.34 10_846.91 3_598.10 12.88_1373.06 4.00_1106.15
PDVA(2018) [56] 12.92_1228.60 3.45_1033.53 10_828.38 3_591.49 12.75_1362.09 3.75_1068.26
HRRGA(2021) [49] 12.25_1211.89 3.09_966.24 10_828.38 3_590.60 11.88_1360.19 4.00_1055.53
IGA(2023) [50] 11.92_1248.19 2.73_986.95 10_860.05 3_602.57 11.50_1426.84 3.25_1139.32
N-CLPSO 12.42_1205.96 3.00_955.52 10_828.38 3_589.86 12.13_1356.82 3.38_1106.89

Table 8
The Wilcoxon non-parametric test of N-CLPSO and the other eight algorithms.
N-CLPSO vs. Tabu-ABC ACO-N D-VND RRGA MOTSP PDVA HRRGA IGA
Instances 𝑅+ 𝑅− 𝑝-value 𝑅+ 𝑅− 𝑝-value 𝑅+ 𝑅− 𝑝-value 𝑅+ 𝑅− 𝑝-value 𝑅+ 𝑅− 𝑝-value 𝑅+ 𝑅− 𝑝-value 𝑅+ 𝑅− 𝑝-value 𝑅+ 𝑅− 𝑝-value
R1 11 1 0.003 10 2 0.010 11 1 0.028 9 3 0.012 8 2 0.037 7 0 0.018 6 5 0.477 6 6 0.583
R2 11 0 0.003 9 2 0.008 5 6 0.929 11 0 0.003 8 2 0.047 10 1 0.008 8 3 0.041 5 6 0.477
C1 0 0 1.000 3 0 0.109 0 0 1.000 0 0 1.000 4 0 0.068 0 0 1.000 0 0 1.000 9 0 0.008
C2 1 0 0.317 3 1 0.144 0 0 1.000 0 0 1.000 2 2 0.461 4 0 0.127 0 0 1.000 8 0 0.012
RC1 7 1 0.017 8 0 0.012 5 2 0.237 7 0 0.018 7 1 0.017 6 1 0.043 2 5 0.128 4 4 0.889
RC2 8 0 0.012 8 0 0.012 1 6 0.043 8 0 0.012 8 0 0.012 5 0 0.043 7 1 0.025 4 4 0.779

in the form of 𝑁𝑉 _𝑇 𝐷, where 𝑁𝑉 and 𝑇 𝐷 are the averages of the competitors. Concretely, the vehicle insertion allows the particles to
best minimum number of vehicles (𝑁𝑉 ) and the best minimum total reach almost the optimal number of vehicles. Moreover, the introduced
distance (𝑇 𝐷) found in each subclass using the corresponding method, reinsertion operator, which not only considers the insertion cost but
respectively. For instance, the data ‘‘13.10_1213.16’’ in the second row also focuses on the time window information of the client, allows the
of the table indicates that the average number of vehicles and the algorithm to find better quality solutions in the local search. Last, the
average total distance obtained by ACO-N on independent runs are diversity retention strategy based on the LCS of elite fragments can
13.10 and 1213.16, respectively. The best results for each category are guarantee particle quality as well as increase population diversity.
highlighted in bold. Although experimental results have verified that the guided reinser-
As seen from Table 7, N-CLPSO attains the best-known results tion operator in N-CLPSO exhibits significantly positive performance in
on class C1 and C2. On R2 and RC2, N-CLPSO performs lower than small size and medium size VRPTW instances, the curse of dimension-
HGSADC. However, on R1 and RC1, N-CLPSO achieves better results ality of it cannot be ignorable. Concretely, the number of customers
than the optimal solution in terms of 𝑇 𝐷 at the expense of a smaller increases leads to the exponential increase of the local search space,
𝑁𝑉 . Thus, we can say that N-CLPSO performs better in solving the ‘‘1’’ resulting in the inability of the operator to guide the particles to the
class problems than the ‘‘2’’ ones. optimal solution efficiently. In fact, other our studies have indicated
Furthermore, statistics experiments are also conducted in this part. that the guided reinsertion operator does not attain the most favorable
Since HGSADC and MAPSO do not publish individual instance optimal performance on some large scale VRPTW instances, such as large scale
solutions, we compared the PEav of the N-CLPSO algorithm with the instance of Gehring and Hamberger, compared with the SOTA.
other eight algorithms using the Wilcoxon signed ranks test. As shown Thus, in the subsequent research of N-CLPSO, how to extract useful
in Table 8, N-CLPSO significantly outperforms IGA on C1 and C2 and local information from various search properties of specific individuals
is not significantly different from the other seven algorithms. N-CLPSO is a promising method to reduce the local search space, and then to
outperforms all the six algorithms on R1 and RC1 but is not significantly improve the performance of the guided reinsertion operator. Moreover,
different from HRRGA and IGA with no significant difference. Finally, from the problem perspective, there are many other VRP variants, such
on the ‘‘2’’ class problems, N-CLPSO underperforms D-VND only on RC2 as electric VRP with time window (EVRPTW) and Pickup and Delivery
but has some advantages over the remaining seven algorithms. Vehicle Path Problem with Time Window (PDPTW), need to be studied
based on N-CLPSO. In these studies, one needs to redesign some crucial
6. Conclusions and future research operators in N-CLPSO, including the remove-reinsert neighborhood
search mechanism, based on distinct properties of these VRP variants.
In this paper, we propose N-CLPSO algorithm to solve VRPTW, in At last, a diversity retention strategy based on elite fragments also can
which discuss two objectives are considered. The primary objective be applied to other combinatorial optimization problems in our future
is the number of vehicles, while the secondary objective is the total works.
distance traveled by all vehicles. The algorithm is based on improving
the learning probability and learning exemplars of the original CLPSO. Declaration of competing interest
Furthermore, three novel strategies are introduced to improve the
performance of N-CLPSO. The first one is using an insertion strategy The authors declare the following financial interests/personal rela-
to reduce the number of vehicles as much as possible. The second one tionships which may be considered as potential competing interests:
is utilizing the guided reinsertion operator based on local information Xuewen Xia reports financial support was provided by Minnan Normal
proposed in this paper to guide the neighborhood search. The last University.
one is a diversity preservation strategy, the core concept of which
is retaining the LCS elite fragment by comparing elite particles with Data availability
current particles. Extensive experiments show that N-CLPSO yields
more promising and comprehensive performance than the other 15 Data will be made available on request.

14
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

Acknowledgments [21] P. Kanakasabapathy, K.S. Swarup, Evolutionary tristate PSO for strategic bidding
of pumped-storage hydroelectric plant, IEEE Trans. Syst. Man Cybern. C 40
(2010) 460–471, http://dx.doi.org/10.1109/TSMCC.2010.2041229.
The study is funded by the Natural Science Foundation of Xinjiang
[22] R.V. Kulkarni, G.K. Venayagamoorthy, Particle swarm optimization in wireless-
Uygur Autonomous Region, China (Grant No. : 2021D01A67), the sensor networks: A brief survey, IEEE Trans. Syst. Man Cybern. C 41 (2011)
National Natural Science Foundation of China (Grant Nos. : 61663009, 262–267, http://dx.doi.org/10.1109/TSMCC.2010.2054080.
62106092), the Natural Science Foundation of Fujian Province, China [23] S.S.M. Ajibade, M.O. Ogunbolu, R. Chweya, S. Fadipe, Improvement of Popula-
(Grant Nos. : 2021J011008, 2021J011007, 2022J01916), the Science tion Diversity of Meta-Heuristics Algorithm using Chaotic Map, in: Lecture. Notes.
Data Eng. Commun. Tech., 2022, pp. 95–104, http://dx.doi.org/10.1007/978-3-
and Technology Plan Projects of Zhangzhou, China (Grant Nos. : 030-98741-1_9.
ZZ2020J06, ZZ2020J24), and the Natural Science Foundation of Edu- [24] S. Cheng, Y. Shi, Q. Qin, Promoting Diversity in Particle Swarm Optimization
cation Department of Jiangxi Province, China (Grant No. : GJJ200629). To Solve Multimodal Problems, in: Lect. Notes Comput. Sci., 2011, pp. 228–237,
http://dx.doi.org/10.1007/978-3-642-24958-7_27.
[25] S. Chourasia, H. Sharma, M. Singh, J.C. Bansal, Global and local neighborhood
References based particle swarm optimization, in: Adv. Intell. Sys. Comput, 2019, pp.
449–460, http://dx.doi.org/10.1007/978-981-13-0761-4_44.
[1] L. Wei, Z. Ma, N. Liu, Design of reverse logistics system for b2c e-commerce [26] Z. Liu, Z. Qin, P. Zhu, H. Li, An adaptive switchover hybrid particle swarm
based on management logic of internet of things, Int. J. Shipp. Transp. Logist. optimization algorithm with local search strategy for constrained optimization
13 (2021) 484–497, http://dx.doi.org/10.1504/IJSTL.2021.117274. problems, Eng. Appl. Artif. Intell. 95 (2020) 103771, http://dx.doi.org/10.1016/
[2] G.B. Dantzig, J.H. Ramser, The truck dispatching problem, Manage. Sci. 6 (1959) j.engappai.2020.103771.
80–91, http://dx.doi.org/10.1287/mnsc.6.1.80. [27] Z. Wang, Z. Zhan, J. Zhang, An improved method for comprehensive learning
[3] B. Rabbouch, F. Saâdaoui, R. Mraihi, Empirical-type simulated annealing for particle swarm optimization, in: IEEE Symp. Ser. Comput. Intell, 2015, pp.
solving the capacitated vehicle routing problem, J. Exp. Theor. Artif. Intell. 32 218–225, http://dx.doi.org/10.1109/SSCI.2015.41.
(2020) 437–452, http://dx.doi.org/10.1080/0952813X.2019.1652356. [28] H. Jiang, M. Lu, Y. Tian, J. Qiu, X. Zhang, An evolutionary algorithm for solving
[4] D.S. Lai, O.C. Demirag, J.M. Leung, A tabu search heuristic for the heterogeneous capacitated vehicle routing problems by using local information, Appl. Soft
vehicle routing problem on a multigraph, Transp. Res. E 86 (2016) 32–52, Comput. 117 (2022) 108431, http://dx.doi.org/10.1016/j.asoc.2022.108431.
http://dx.doi.org/10.1016/j.tre.2015.12.001. [29] R. Cheng, Y. Jin, M. Olhofer, B. Sendhoff, A reference vector guided evolutionary
[5] L. Cruz-Reyes, et al., Ant colony system with characterization-based heuristics algorithm for many-objective optimization, IEEE Trans. Evol. Comput. 20 (2016)
for a bottled-products distribution logistics system, J. Comput. Appl. Math. 259 773–791, http://dx.doi.org/10.1109/TEVC.2016.2519378.
(2014) 965–977, http://dx.doi.org/10.1016/j.cam.2013.10.035. [30] J.J. Liang, A.K. Qin, P.N. Suganthan, S. Baskar, Comprehensive learning par-
[6] R. Baldacci, A. Mingozzi, R. Roberti, Recent exact algorithms for solving the ticle swarm optimizer for global optimization of multimodal functions, IEEE
vehicle routing problem under capacity and time window constraints, European Trans. Evol. Comput. 10 (2006) 281–295, http://dx.doi.org/10.1109/TEVC.2005.
J. Oper. Res. 218 (2012) 1–6, http://dx.doi.org/10.1016/j.ejor.2011.07.037. 857610.
[7] B. Kallehauge, Formulations and exact algorithms for the vehicle routing problem [31] W. Chen, J. Zhang, H.S. Chung, W. Zhong, W. Wu, Y. Shi, A novel set-based
with time windows, Comput. Oper. Res. 35 (2008) 2307–2330, http://dx.doi.org/ particle swarm optimization method for discrete optimization problems, IEEE
10.1016/j.cor.2006.11.006. Trans. Evol. Comput. 14 (2010) 278–300, http://dx.doi.org/10.1109/TEVC.2009.
[8] Y. Zhong, X. Pan, A hybrid optimization solution to vrptw based on simulated 2030331.
annealing, in: IEEE Int. Conf. Autom. Logist, 2007, pp. 3113–3117, http://dx. [32] Y. Wang, L. Wang, Z. Peng, G. Chen, Z. Cai, L. Xing, A multi ant system
doi.org/10.1109/ICAL.2007.4339117. based hybrid heuristic algorithm for vehicle routing problem with service time
[9] M. Alinaghian, E.B. Tirkolaee, Z.K. Dezaki, S.R. Hejazi, W. Ding, An augmented customization, Swarm Evol. Comput. 50 (2019) 100563, http://dx.doi.org/10.
tabu search algorithm for the green inventory-routing problem with time 1016/j.swevo.2019.100563.
windows, Swarm. Evol. Comput. 60 (2021) 100802, http://dx.doi.org/10.1016/ [33] A. Gupta, S. Saini, An enhanced ant colony optimization algorithm for vehicle
j.swevo.2020.100802. routing problem with time windows, in: Int. Conf. Adv. Comput, 2017, pp.
[10] B. Yu, Z.Z. Yang, B.Z. Yao, A hybrid algorithm for vehicle routing problem with 267–274, http://dx.doi.org/10.1109/ICoAC.2017.8441175.
time windows, Expert Syst. Appl. 38 (2011) 435–441, http://dx.doi.org/10.1016/ [34] H. Zhang, Q. Zhang, L. Ma, Z. Zhang, Y. Liu, A hybrid ant colony optimization
j.eswa.2010.06.082. algorithm for a multi-objective vehicle routing problem with flexible time
[11] Y. Gong, J. Zhang, O. Liu, R. Huang, H.S. Chung, Y. Shi, Optimizing the vehicle windows, Inform. Sci. 490 (2019) 166–190, http://dx.doi.org/10.1016/j.ins.
routing problem with time windows: A discrete particle swarm optimization 2019.03.070.
approach, IEEE Trans. Syst. Man Cybern. C 42 (2012) 254–267, http://dx.doi. [35] W. Zhang, D. Yang, G. Zhang, M. Gen, Hybrid multiobjective evolutionary
org/10.1109/TSMCC.2011.2148712. algorithm with fast sampling strategy-based global search and route sequence
[12] T. Khoo, B.B. Mohammad, V.-H. Wong, Y.-H. Tay, M. Nair, A two-phase difference-based local search for VRPTW, Expert Syst. Appl. 145 (2020) 113151,
distributed ruin-and-recreate genetic algorithm for solving the vehicle routing http://dx.doi.org/10.1016/j.eswa.2019.113151.
problem with time windows, IEEE Access 8 (2020) 169851–169871, http://dx. [36] S. Reong, H. Wee, Y. Hsiao, 20 Years of particle swarm optimization strategies
doi.org/10.1109/ACCESS.2020.3023741. for the vehicle routing problem: A bibliometric analysis, Mathematics 10 (2022)
[13] E.H. Houssein, A.G. Gad, K. Hussain, P.N. Suganthan, Major advances in particle 3669, http://dx.doi.org/10.3390/math10193669.
swarm optimization: theory, analysis, and application, Swarm. Evol. Comput. 63 [37] P. Saksuriya, C. Likasiri, Hybrid heuristic for vehicle routing problem with time
(2021) 100868, http://dx.doi.org/10.1016/j.swevo.2021.100868. windows and compatibility constraints in home healthcare system, Appl. Sci. 12
[14] M. Chih, Stochastic stability analysis of particle swarm optimization with (2022) 6486, http://dx.doi.org/10.3390/app12136486.
pseudo random number assignment strategy, European J. Oper. Res. 305 (2023) [38] M.S. Sarbijan, J. Behnamian, Real-time collaborative feeder vehicle routing
562–593, http://dx.doi.org/10.1016/j.ejor.2022.06.009. problem with flexible time windows, Swarm Evol. Comput. 75 (2022) 101201,
[15] X. Xia, L. Gui, F. Yu, H. Wu, B. Wei, Y. Zhang, Z. Zhan, Triple archives http://dx.doi.org/10.1016/j.swevo.2022.101201.
particle swarm optimization, IEEE Trans. Cybern. 50 (2020) 4862–4875, http: [39] N. Ding, J. Yang, Z. Han, J. Hao, Electric-vehicle routing planning based on
//dx.doi.org/10.1109/TCYB.2019.2943928. the law of electric energy consumption, Mathematics 10 (2022) 3099, http:
[16] X. Xia, L. Gui, G. He, B. Wei, Y. Zhang, F. Yu, H. Wu, Z. Zhan, An expanded //dx.doi.org/10.3390/math10173099.
particle swarm optimization based on multi-exemplar and forgetting ability, [40] R. Liu, Z. Jiang, A hybrid large-neighborhood search algorithm for the cumulative
Inform. Sci. 508 (2020) 105–120, http://dx.doi.org/10.1016/j.ins.2019.08.065. capacitated vehicle routing problem with time-window constraints, Appl. Soft
[17] X. Xia, Y. Tang, B. Wei, Y. Zhang, L. Gui, X. Li, Dynamic multi-swarm global Comput. 80 (2019) 18–30, http://dx.doi.org/10.1016/j.asoc.2019.03.008.
particle swarm optimization, Computing 102 (2020) 1587–1626, http://dx.doi. [41] M. Alinaghian, M. Jamshidian, E.B. Tirkolaee, The time-dependent multi-depot
org/10.1007/s00607-019-00782-9. fleet size and mix green vehicle routing problem: improved adaptive large
[18] X. Xia, H. Song, Y. Zhang, L. Gui, X. Xu, K. Li, Y. Li, A particle swarm neighbourhood search, Optimization 71 (2022) 3165–3193, http://dx.doi.org/
optimization with adaptive learning weights tuned by a multiple-input multiple- 10.1080/02331934.2021.2010078.
output fuzzy logic controller, IEEE Trans. Fuzzy. Syst. 11 (2022) 1–15, http: [42] M. Qi, W. Lin, N. Li, L. Miao, A spatiotemporal partitioning approach for large-
//dx.doi.org/10.1109/TFUZZ.2022.3227464. scale vehicle routing problems with time windows, Transp. Res. E 48 (2012)
[19] D. Yousri, D. Allam, M. Eteiba, P.N. Suganthan, Static and dynamic photovoltaic 248–257, http://dx.doi.org/10.1016/j.tre.2011.07.001.
models’ parameters identification using chaotic heterogeneous comprehensive [43] M. Chih, Three pseudo-utility ratio-inspired particle swarm optimization with
learning particle swarm optimizer variants, Energy Convers. Manage. 182 (2019) local search for multidimensional knapsack problem, Swarm Evol. Comput. 39
546–563, http://dx.doi.org/10.1016/j.enconman.2018.12.022. (2018) 279–296, http://dx.doi.org/10.1016/j.swevo.2017.10.008.
[20] R.V. Kulkarni, G.K. Venayagamoorthy, Bio-inspired algorithms for autonomous [44] J. Shi, Q. Zhang, E.P.K. Tsang, EB-GLS: an improved guided local search based
deployment and localization of sensor nodes, IEEE Trans. Syst. Man Cybern. C on the big valley structure, Memet. Comput. 10 (2018) 333–350, http://dx.doi.
40 (2010) 663–675, http://dx.doi.org/10.1109/TSMCC.2010.2049649. org/10.1007/s12293-017-0242-5.

15
Q. Wu et al. Swarm and Evolutionary Computation 84 (2024) 101425

[45] L. Hong, An improved LNS algorithm for real-time vehicle routing problem with [61] H. Li, A. Lim, Local search with annealing-like restarts to solve the VRPTW,
time windows, Comput. Oper. Res. 39 (2012) 151–163, http://dx.doi.org/10. European J. Oper. Res. 150 (2003) 115–127, http://dx.doi.org/10.1016/S0377-
1016/j.cor.2011.03.006. 2217(02)00486-1.
[46] X. Xia, H. Qiu, X. Xu, Y. Zhang, Multi-objective workflow scheduling based [62] D. Mester, An evolutionary strategies algorithm for large scale vehicle routing
on genetic algorithm in cloud environment, Inform. Sci. 606 (2022) 38–59, problem with capacitate and time windows restrictions, in: Proceedings of the
http://dx.doi.org/10.1016/j.ins.2022.05.053. Conference on Mathematical and Population Genetics, University of Haifa, Israel,
[47] M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with 2002.
time window constraints, Oper. Res. 35 (1987) 254–265, http://dx.doi.org/10. [63] P. Shaw, A New Local Search Algorithm Providing High Quality Solutions to
1287/opre.35.2.254. Vehicle Routing Problems, Technical Report, Department of Computer Science,
[48] D. Wu, M. Dong, H. Li, F. Li, Vehicle routing problem with time windows University of Strathclyde, Scotland, 1997.
using multi-objective co-evolutionary approach, Int. J. Simul. Model. 15 (2016) [64] J. Berger, M. Barkaoui, O. Bräysy, A route-directed hybrid genetic approach for
742–753, http://dx.doi.org/10.2507/IJSIMM15(4)CO19. the vehicle routing problem with time windows, INFOR: Inf. Syst. Oper. Res. 41
[49] T. Khoo, M.B. Bonab, The parallelization of a two-phase distributed hybrid (2003) 179–194, http://dx.doi.org/10.1080/03155986.2003.11732675.
ruin-and-recreate genetic algorithm for solving multi-objective vehicle routing [65] J. Homberger, H. Gehring, Two evolutionary metaheuristics for the vehicle
problem with time windows, Expert Syst. Appl. 168 (2021) 114408, http://dx. routing problem with time windows, INFOR: Inf. Syst. Oper. Res. 37 (1999)
doi.org/10.1016/j.eswa.2020.114408. 297–318, http://dx.doi.org/10.1080/03155986.1999.11732386.
[50] K. Yang, P. Duan, H. Yu, An improved genetic algorithm for solving the heli- [66] L. Rousseau, M. Gendreau, G. Pesant, Using constraint-based operators to solve
copter routing problem with time window in post-disaster rescue, Math. Biosic. the vehicle routing problem with time windows, J. Heuristics 8 (2002) 43–58,
Eng. 20 (2023) 15672–15707, http://www.aimspress.com/aimspress-data/mbe. http://dx.doi.org/10.1023/A:1013661617536.
[51] G.D. Konstantakopoulos, S.P. Gayialis, E.P. Kechagias, G.A. Papadopoulos, I.P. [67] L.M. Gambardella, É. Taillard, G. Agazzi, Macs-vrptw: A multiple ant colony
Tatsiopoulos, A multiobjective large neighborhood search metaheuristic for the system for vehicle routing problems with time windows, in: New Ideas in
vehicle routing problem with time windows, Algorithms 13 (2020) 243, http: Optimization, McGraw Hill, London, UK, 1999, pp. 63–76.
//dx.doi.org/10.3390/a13100243. [68] R. Bent, P. Van Hentenryck, A two-stage hybrid local search for the vehicle
[52] D. Zhang, S. Cai, F. Ye, Y. Si, T.T. Nguyen, A hybrid algorithm for a vehicle routing problem with time windows, Transp. Sci. 38 (2004) 515–530, http:
routing problem with realistic constraints, Inform. Sci. 394 (2017) 167–182, //dx.doi.org/10.1287/trsc.1030.0049.
http://dx.doi.org/10.1016/j.ins.2017.02.028. [69] G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, G. Dueck, Record break-
[53] Y. Shen, M. Liu, J. Yang, Y. Shi, M. Middendorf, A hybrid swarm intelligence ing optimization results using the ruin and recreate principle, J. Comput.
algorithm for vehicle routing problem with time windows, IEEE Access 8 (2020) Phys. 159 (2000) 139–171, https://www.sciencedirect.com/science/article/pii/
93882–93893, http://dx.doi.org/10.1109/ACCESS.2020.2984660. S0021999199964136.
[54] Y. Lan, F. Liu, W.W. Ng, J. Zhang, M. Gui, Decomposition based multi-objective [70] A.L. Bouthillier, T.G. Crainic, A cooperative parallel meta-heuristic for the vehicle
variable neighborhood descent algorithm for logistics dispatching, IEEE Trans. routing problem with time windows, Comput. Oper. Res. 32 (2005) 1685–1708,
Emerg. Top. Comput. Intell. 5 (2020) 826–839, http://dx.doi.org/10.1109/ https://www.sciencedirect.com/science/article/pii/S0305054803003654.
TETCI.2020.3002228. [71] J. Homberger, Verteilt-Parallele Metaheuristiken Zur Tourenplanung, Deutscher
[55] Z. He, K. Zhou, H. Shu, X. Chen, X. Lyu, Multi-objective algorithm based on tissue Universitatsverlag, Wiesbaden, 2000.
p system for solving tri-objective optimization problems, Evol. Intell. (2021) [72] K. Ghoseiri, S.F. Ghannadpour, Multi-objective vehicle routing problem with time
1–16, http://dx.doi.org/10.1007/s12065-021-00658-y. windows using goal programming and genetic algorithm, Appl. Soft Comput. 10
[56] W. Dong, K. Zhou, H. Qi, C. He, J. Zhang, A tissue p system based evolutionary (2010) 1096–1107, http://dx.doi.org/10.1016/j.asoc.2010.04.001.
algorithm for multi-objective vrptw, Swarm Evol. Comput. 39 (2018) 310–322, [73] É. Taillard, P. Badeau, M. Gendreau, F. Guertin, J.-Y. Potvin, A tabu search
https://www.sciencedirect.com/science/article/pii/S2210650216305867. heuristic for the vehicle routing problem with soft time windows, Transp. Sci.
[57] T. Vidal, T.G. Crainic, M. Gendreau, C. Prins, A hybrid genetic algorithm with 31 (1997) 170–186, http://dx.doi.org/10.1287/trsc.31.2.170.
adaptive diversity management for a large class of vehicle routing problems [74] Z. Fu, R. Eglese, L.Y.O. Li, A unified tabu search algorithm for vehicle routing
with time-windows, Comput. Oper. Res. 40 (2013) 475–489, http://dx.doi.org/ problems with soft time windows, J. Oper. Res. Soc. 59 (2008) 663–673,
10.1016/j.cor.2012.07.018. http://dx.doi.org/10.1057/palgrave.jors.2602371.
[58] Y. Marinakis, M. Marinaki, A. Migdalas, A multi-adaptive particle swarm opti- [75] Z. Czech, P. Czarnas, Parallel simulated annealing for the vehicle routing problem
mization for the vehicle routing problem with time windows, Inform. Sci. 481 with time windows, in: Proceedings 10th Euromicro Workshop on Parallel,
(2019) 311–329, http://dx.doi.org/10.1016/j.ins.2018.12.086. Distributed and Network-Based Processing, 2002, pp. 376–383, http://dx.doi.
[59] K.C. Tan, Y.H. Chew, L.H. Lee, A hybrid multiobjective evolutionary algorithm org/10.1109/EMPDP.2002.994313.
for solving vehicle routing problem with time windows, Comput. Optim. Appl. [76] T. Ibaraki, S. Imahori, M. Kubo, T. Masuda, T. Uno, M. Yagiura, Effective
34 (2006) 115–151, http://dx.doi.org/10.1007/s10589-005-3070-3. local search algorithms for routing and scheduling problems with general time-
[60] Y. Rochat, É.D. Taillard, Probabilistic diversification and intensification in local window constraints, Transp. Sci. 39 (2005) 206–232, http://dx.doi.org/10.1287/
search for vehicle routing, J. Heuristics 1 (1995) 147–167, http://dx.doi.org/10. trsc.1030.0085.
1007/BF02430370.

16