IEEE Computational Intelligence Magazine - November 2023 - 55

TABLE V The characteristics of RoCaSH, RoCaSH*, and
RoCaSH2.
ALGORITHM NEW INITIALIZATION? TMAS GLOBAL OPTIMIZATION?
RoCaSH
RoCaSH*
@
RoCaSH2 @@
TABLE VI The pairwise B-C-W results using Wilcoxon rank
sum test with significance level of 0.05 among RoCaSH,
RoCaSH*, and RoCaSH2.
B-C-W
RoCaSH
RoCaSH*
RoCaSH --
RoCaSH*
RoCaSH2
RoCaSH2
-
23-3-4 --
29-1-0
30-0-0
-
V. Conclusions and Future Work
This paper aims to address the issue ofthe existing divide-andconquer
approaches for LSMDCARP that an inaccurate problem
decomposition can lead to poor local optimization results
of the sub-problems, which will in turn deteriorate the subsequent
re-decomposition. This has been achieved by proposing
a new dynamic decomposition procedure and a new initialization.
The new dynamic decomposition procedure introduces
a new global optimization stage before the re-decomposition,
and thus can reduce the inter-dependency between problem
decomposition and local optimization results, and improve the
decomposition more effectively. The new initialization can
generate better initial solution and problem decomposition to
enhance the subsequent search.
Specifically for LSMDCARP, this paper develops a Task
TABLE VII The W-C-B results using Wilcoxon rank sum test
with significance level of 0.05 between RoCaSH2 and
RoCaSH*.
NAME
mdEGL-G
mdHefei
mdBeijing
Overall
B
10
10
10
30
C
W
but has no global optimization stage. Table V shows the differences
among RoCaSH, RoCaSH*, and RoCaSH2. This way, the
effectiveness ofthe new initialization can be verified by comparing
between RoCaSH and RoCaSH* and the effectiveness of
the TMaS-based global optimization is verified by comparing
RoCaSH2 withRoCaSH*.
RoCaSH* is run on all the test instances with the same
parameter setting as RoCaSH. Then, for each instance, the Wilcoxon
rank sum test with the significance level of 0.05 is conducted
for each pair of RoCaSH, RoCaSH*, and RoCaSH2.
Table VI shows the B-C-W results between the row algorithm
and the column algorithm on all the 30 LSMDCARP instances,
where only the lower triangle was calculated. For example, 291-0
in row 3 and column 1 indicates that RoCaSH2 performed
significantly better than RoCaSH on 29 out ofthe 30 instances,
and noworse thanRoCaSH on any instance.
FromTable VI, one can see that RoCaSH* significantly outperformed
RoCaSH on 23 out ofthe 30 instances, and worse on
only four instances. This demonstrates the effectiveness of the
new initialization scheme proposed in this paper. RoCaSH2
showed the best performance among the three algorithms. It significantly
outperformed RoCaSH* (RoCaSH) on 30 (29) out of
the 30 instances, and never obtained significantly worse result.
Table VII shows the B-C-W results between RoCaSH2 and
RoCaSH* on each dataset separately. From the table, it can be
seen that RoCaSH2 showed significantly better results than
RoCaSH* on all themdEGL-G,mdHefei, and mdBeijing instances.
This particularly verifies the effectiveness ofthe TMaS-based
global optimization inRoCaSH2 on solving large-scale problems.
Moving among Sub-problems (TMaS)-based restricted global
optimization, which can achieve a good balance between
effectiveness and efficiency. The state-of-the-art RoCaSH
[30] algorithm is also adopted for problem re-decomposition
and local optimization. Putting all the above together, a new
RoCaSH2 algorithm is proposed. The experimental studies
show that RoCaSH2 can achieve much better results and converge
much faster than the current state-of-the-art algorithms
for a wide range ofLSMDCARP test instances.
There are a few future directions that can be considered.
One direction is to conduct more valuable movements of the
tasks in promising regions inherited from the sub-problems
and reduce the redundant movements so that the efficiency of
TMaS can be further improved. Another direction is to consider
more practical and complicated models of CARP, such
as the multi-depot periodic CARP (MDPCARP), which contains
challenges ofboth allocating tasks to depots and deciding
which days ofthe period to serve each task.
Acknowledgment
This work was supported in part by Anhui Provincial Natural Science
Foundation under Grants 1808085MF173 and 1908085MF195, in
part by the Natural Science Key Research Project for Higher Education
Institutions ofAnhui Province under Grant KJ2021A0640, and
in part by theHigh-level Personnel Starting Project ofNanjingXiaozhuangUniversity
under Grant 4172322.
References
[1] B. Golden and R. Wong, " Capacitated arc routing problems, " Networks, vol. 11,
no. 3, pp. 305-316, 1981.
[2] M. Dror, Arc Routing: Theory, Solutions and Applications. Boston, MA, USA:
Kluwer Academic Publishers, 2000.
[3] H. Handa, L. Chapman, and X. Yao, " Robust route optimization for gritting/
salting trucks: A CERCIA experience, " IEEE Comput. Intell. Mag., vol. 1, no. 1,
pp. 6-9, Feb. 2006.
[4] M. Polacek, K. Doerner, R. Hartl, and V. Maniezzo, " A variable neighborhood
search for the capacitated arc routing problem with intermediate facilities, " J. Heuristics,
vol. 14, no. 5, pp. 405-423, 2008.
[5] G. Liu, Y. Ge, T. Z. Qiu, and H. R. Soleymani, " Optimization ofsnow plowing
cost and time in an urban environment: A case study for the city ofedmonton, " Can.
J. Civil Eng., vol. 41, no. 7, pp. 667-675, 2014.
[6] J. Campbell and A. Langevin, " Roadway snow and ice control, " in Arc Routing:
Theory, Solutions and Applications. Boston, MA, USA: Kluwer, 2000, pp. 389-418.
[7] H. Handa, D. Lin, L. Chapman, and X. Yao, " Robust solution of salting route
optimisation using evolutionary algorithms, " in Proc. IEEE Congr. Evol. Comput.,
2006, pp. 3098-3105.
NOVEMBER 2023 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE 55

IEEE Computational Intelligence Magazine - November 2023

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