  In literature, Clustered Shortest-Path Tree Problem (CluSPT) is an NP-hard
problem. Previous studies often search for an optimal solution in relatively
large space. To enhance the performance of the search process, two approaches
are proposed: the first approach seeks for solutions as a set of edges. From
the original graph, we generate a new graph whose vertex set's cardinality is
much smaller than that of the original one. Consequently, an effective
Evolutionary Algorithm (EA) is proposed for solving CluSPT. The second approach
looks for vertex-based solutions. The search space of the CluSPT is transformed
into 2 nested search spaces (NSS). With every candidate in the high-level
optimization, the search engine in the lower level will find a corresponding
candidate to combine with it to create the best solution for CluSPT.
Accordingly, Nested Local Search EA (N-LSEA) is introduced to search for the
optimal solution on the NSS. When solving this model in lower level by N-LSEA,
variety of similar tasks are handled. Thus, Multifactorial Evolutionary
Algorithm applied in order to enhance the implicit genetic transfer across
these optimizations. Proposed algorithms are conducted on a series of datasets
and the obtained results demonstrate superior efficiency in comparison to
previous scientific works.
