A novel genetic algorithm for solving the clustered shortest-path tree problem

The clustered shortest-path tree problem is an extension of the classical single-source shortest-path problem, in which, given a graph with the set of nodes divided into a predefined, mutually exclusive and exhaustive set of clusters, we want to determine a shortest-path spanning tree from a given source to all the other nodes of the graph, with the property that each cluster should induce a connected subtree. The investigated problem proved to be NP-hard and therefore we proposed an efficient genetic algorithm in order to solve it. The preliminary computational results reported on a set of benchmark instances from the literature proved that our proposed solution approach yields high-quality solutions within reasonable running times.