A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem
This addresses a combinatorial optimization problem, likely incremental as it builds on known methods for a specific domain.
The paper tackles the Clustered Shortest-Path Tree Problem by introducing a new algorithm that combines Randomized Greedy Algorithms and Shortest Path Tree Algorithm, showing strengths in experimental evaluations on Euclidean benchmarks compared to existing algorithms.
Randomized Greedy Algorithms (RGAs) are interesting approaches to solve problems whose structures are not well understood as well as problems in combinatorial optimization which incorporate the random processes and the greedy algorithms. This paper introduces a new algorithm that combines the major features of RGAs and Shortest Path Tree Algorithm (SPTA) to deal with the Clustered Shortest-Path Tree Problem (CluSPT). In our algorithm, SPTA is used to determine the shortest path tree in each cluster while the combination between characteristics of the RGAs and search strategy of SPTA is used to constructed the edges connecting clusters. To evaluate the performance of the proposed algorithm, Euclidean benchmarks are selected. The experimental investigations show the strengths of the proposed algorithm in comparison with some existing algorithms. We also analyze the influence of the parameters on the performance of the algorithm.