A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem

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.