IEEE Computational Intelligence Magazine - November 2023 - 48

ðS00
1; ...; S00
jVðDÞjÞ is obtained. Each new sub-problem is determined
by the new subset of routes associated with the corresponding
depot. The re-decomposition stage will be further
described in Section III-E. Finally, the local optimization is conducted
on each sub-problem (lines 8-10) to obtain an improved
solution ðR1; .. .; RjVðDÞjÞ. The details of LocalOpt will be
given in Section III-F. The search process terminates ifthe maximum
number of cycles MaxCyc is reached or there are
MaxNoImp cycles without improvement.
Algorithm 2. The new initialization procedure.
1: procedure Init (The LSMDCARP instance with task set T,
depot set VðDÞ, number of trials k)
2: Assign the tasks to the depots by the nearest-neighbour
heuristic;
3: for d ¼ 1 !jVðDÞj do
4:
Set Rd ¼ðxðDÞ
5:
6:
7:
8:
9:
10:
d ;xðDÞ
while Td 6¼; do
Calculate the best insertion cost of each task t 2 Td;
Select the task t with the minimal best insertion cost;
Insert t at its best position in Rd, remove t from Td;
end while
Split Rd using Ulusoy's splitting procedure to obtain Sd;
11: end for
12: Let S =(S1; .. .; SjVðDÞj);
13: for k ¼ 1 ! k 1 do
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
d ;xðDÞ
end for
T0 ¼ T;
while T0 6¼; do
Select a task t from T0 randomly, and remove t from T0;
Assign t to the closest depot d;
Insert t at its best position in Rd
;
end while
Apply Ulusoy's splitting procedure on each Rd ðd ¼ 1; :::;
jVðDÞjÞ, and obtain a candidate solution S0 =(S0
1; ...; S0
if S0 is better S then
S ¼ S0;
end if
27: end for
28: return S;
29: end procedure
C. Initialization
Algorithm 2 shows the pseudo code of the new initialization.
First, a solution is generated in a greedy way (lines 2-12). Specifically,
the tasks are allocated to the depots using the nearestneighbour
(NN) heuristic, i.e., each task is allocated to its closest
depot. Then, for each depot, a giant route is generated by the
best insertion heuristic. Starting with a depot loop, at each step,
the insertion cost of each task to each candidate position of the
giant route is calculated, i.e., the difference in the cost after inserting
it. The task with the best insertion cost is selected and inserted
to the best position. Then, the giant route is split into a set offeasible
routes by Ulusoy's splitting procedure.
After the first greedy solution is generated, a number of
k 1 additional solutions are generated in a random way (lines
48 IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | NOVEMBER 2023
jVðDÞj);
for d ¼ 1 !jVðDÞj do
Set Rd ¼ðxðDÞ
d Þ;
d Þ, Td ¼ {the tasks allocated to vðDÞ
d };
13-27). The main difference from the greedy generation is
that at each step of task insertion, the next task is selected randomly
rather than with the minimal insertion cost. Finally, the
best solution among the k generated initial solutions is
returned. The framework of the initialization procedure is
shown in Figure 2 for easier and better grasp ofthe process.
The new initialization is inspired by that ofMDMA [26],
but modified from a population initialization to a single-solution
initialization. By quickly generating a number ofdifferent
solutions in a relatively greedy way, RoCaSH2 can obtain a
good initial solution efficiently.
Algorithm 3. The Task Moving among Sub-problems process.
1: procedure TMaS (A solution S1; ...; SjVðDÞj, parameter NR)
2: Set the remaining routes R ¼fR j R 2 S1 [ ... [ SjVðDÞjg;
3: for d ¼ 1 !jVðDÞj do
4:
S0
d ¼ðÞ;
5: end for
6: N ¼f1; .. .; jVðDÞjg;
7: while R 6¼; do
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
Randomly select k uniformly fromN, and remove it fromN;
Remove all the routes in Sk from R;
while Sk 6¼; do
Randomly select a route R from Sk;
Remove R from Sk;
Set C ¼fRg;
if jRnSkj > NR 1 then
Select NR 1 closest routes to R from RnSk, using the
distance measure (10);
Remove the selected routes from R;
Add the selected routes to C;
else
Add all the routes in RnSk to C;
Remove these added routes from R;
end if
Apply restricted local search to C;
Add all the routes in C to S0
k;
if RnSk ¼; then
Add all the routes in Sk to S0
returnðS0
1; .. .; S0
end if
end while
29: end while
30: returnðS0
1; .. .; S0
31: end procedure
jVðDÞjÞ;
jVðDÞjÞ;
k, S0
k ¼ S0
k [ Sk;
D. Task MovingAmong Sub-Problems
Algorithm 3 describes the proposed TMaS process. It takes a
solution ðS1; .. .; SjVðDÞjÞ and a parameter NR and returns a new
solution ðS0
1; ...; S0
jVðDÞjÞ. Initially, all the routes ofthe new solution
are set to empty (line 4). Then, the routes ofdifferent depots
in ðS1; ...; SjVðDÞjÞ are re-grouped as follows. In each iteration, a
random depot vk is selected (line 8), and each route in Sk is regrouped
with at most NR 1 other routes, which must belong
to different depots (lines 10-28). Specifically, for each route
R 2 Sk, ifthere are more than NR 1 remaining routes from a
different depot, then NR 1 closest routes to R
are selected
IEEE Computational Intelligence Magazine - November 2023

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