IEEE Computational Intelligence Magazine - November 2023 - 47

FIGURE 1 The newly proposed dynamic decomposition procedure.
problem by a local optimization method, such as local search and
genetic algorithm. The local optimization modifies only the values
ofthe decision variables involved in the sub-problem, fixing
all the other decision variables.
The main difference between the newly proposed
dynamic decomposition and the existing approaches is the
additional global optimization stage. Most existing studies
directly re-decompose the problem after obtaining the solution
to the original problem without fine-tuning it. On the
contrary, the newly proposed dynamic decomposition further
improves the solution to the original problem before the redecomposition,
so that the subsequent re-decomposition
becomes less dependent on the previous problem decomposition
and local optimization results. This way, the decomposition
can be improved more effectively in each cycle.
B. The RoCaSH2 Algorithm
Based on the new dynamic decomposition procedure, new
divide-and-conquer approaches can be developed for
LSMDCARP. The following design issues have been considered:
1) How to define the problem decomposition and sub-problems
for LSMDCARP;
2) How to initialize the solution(s) and problem decomposition
to assist the subsequent search;
3) How to conduct the local optimization for each subproblem;
4)
How to conduct the global optimization.
Based on our domain knowledge and preliminary studies,
the above design issues are addressed as follows:
1) Considering the characteristics of MDCARP, each subproblem
is naturally defined as the subset of routes associated
with a single depot. Thus, the problem decomposition
naturally generates jVðDÞj sub-problems, where jVðDÞj is
the number of depots. The dth sub-problem is associated
with the vðDÞ
d 2 VðDÞ.
2) A new initialization scheme is presented, which can obtain a
better initial solution to the large-scale problems in a short
time. The initialization will be described in Section III-C.
3) A current state-of-the-art RoCaSH [30] algorithm is
employed to single-depot CARP for the local optimization
ofeach sub-problem.
4) A new TMaS process is developed for a restricted global
optimization. The TMaS process can achieve a good balance
between effectiveness and efficiency. It will be
described in Section III-D.
Taking all the above into account, the new RoCaSH2 is
proposed. Algorithm 1 gives the pseudo code of RoCaSH2.
At first, a solution is initialized by S ¼ðS1; ...; SjVðDÞjÞ¼
initðT;VðDÞ; kÞ, where Sd represents the subset of routes
associated with the depot vðDÞ
d
d
.
. Naturally, each sub-problem is
defined as a single-depot CARP for serving the tasks served in
Sd with the depot vðDÞ
Algorithm 1. The newly proposed RoCaSH2.
1: procedure RoCaSH2 (The LSMDCARP instance with task set
T and depot set VðDÞ, number of trials k, maximum cycles
MaxCyc, maximum cycles without improvement MaxNoImp,
TMaS parameter NR)
2:
Initialize S ¼ðS1; .. .; SjVðDÞ jÞ¼ InitðT; VðDÞ; kÞ;
3: cycle ¼ 0, noimp ¼ 0;
4: while cycle MaxCyc and noimp MaxNoImp do
5:
6:
7:
8:
9:
cycle ¼ cycle þ 1;
ðS0
1; ...; S0
ðR1; .. .; RjVðDÞjÞ = RedecomposeðS0
for d ¼ 1 !jVðDÞj do
S00
d = LocalOptðRd);
10:
11:
12:
13:
14:
15:
end for
if (ðS00
else
end if
16: end while
17: return the best feasible solution S;
18: end procedure
During the search, in each cycle, the TMaS-based global opti1;
...; S0
1; ...; S0
mization is first carried out to further improve S and obtain an
improved solution ðS0
given in Section III-D. Then, the problem is re-decomposed
(line 7) based on ðS0
1; ...; S00
S ¼ððS00
1; .. .; S00
jVðDÞjÞ) is better than S then
jVðDÞ jÞÞ, noimp ¼ 0;
noimp ¼ noimp þ 1;
jVðDÞjÞ = TMaSðS1, ..., SjVðDÞj, NR);
1; ...; S0
jVðDÞj);
jVðDÞjÞ. The details ofTMaS will be
jVðDÞjÞ, and a new solution
NOVEMBER 2023 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE 47
IEEE Computational Intelligence Magazine - November 2023

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - November 2023
