Minimum Labelling Steiner Tree problem
Since the early years of Operational Research (OR), there has been much interest in combinatorial optimization (CO) problems formulated on graphs and their practical applications. Most of these problems are NP-hard; thus there is a need for heuristics and approximate solution approaches with performance guarantees.
The minimum labelling Steiner tree (MLSteiner) problem belongs to this class of problems. Given a graph with labelled (or coloured) edges, one seeks a spanning tree covering a subset of nodes (basic nodes) of the graph, whose edges have the least number of distinct labels (or colours). The MLSteiner problem is an extension of the well-known Steiner tree (Steiner) problem and of the minimum labelling spanning tree (MLST) problem.
As with the MLST problem, the MLSteiner problem has many applications in real-world problems. For example, in telecommunications networks, a node may communicate with other nodes by means different types of communications media. Define a set of basic nodes that must be connected each other. In some situations, connecting the basic nodes with the smallest number of communications types may reduce the construction cost and the complexity of the network. Another example is given by multimodal transportation networks. The multimodal transportation network is represented by a graph where each edge is assigned a colour, denoting a different company managing that edge, and each node represent a different location. It is desirable to provide a complete service between a basic set of locations, without cycles, using the minimum number of companies, in order to minimize the costs.
The MLSteiner problem is formally defined as a network or graph problem as follows. Let G = (V,E,L) be a labelled, connected, undirected graph, where V is the set of nodes, E is the set of edges, that are labelled on the set L of labels (or colours). Let Q ⊆ V be a set of nodes that must be connected (basic nodes). The objective is to find an arbitrary spanning tree T of the subgraph connecting all the basic nodes Q such that |LT| is minimized (where LT is the set of colours used by T).
Figure 1: Example of an input graph and its optimal MLSteiner solution.
Figure 1 shows an example of an input graph of the MLSteiner problem and its optimal MLSteiner solution, where the solid vertices represent the basic nodes. In order to solve the MLSteiner problem, it is easier to work firstly with feasible solutions instead of spanning trees. A feasible solution is defined as a set of colours C ⊆ L, such that all the edges with labels in C represent a connected subgraph of G which spans all the basic nodes Q. If C is a feasible solution, then any spanning tree of C has at most |C| labels. Thus, in order to solve the MLSteiner problem it is preferable to seek first a feasible solution with the smallest number of colours. The next section reports the literature review on the problem.
Literature review
The minimum labelling Steiner tree problem is a graph combinatorial optimization problem extending the well-known Steiner tree problem and the minimum labelling spanning tree problem.
Given a graph with positive-weighted edges, and with a subset of basic nodes (or termi- nals), the Steiner tree problem consists of finding a minimum-weight tree spanning all the basic nodes. This problem dates back to Fermat, who formulated it as a geometric problem: find a point p in the Euclidean plane minimizing the sum of the distances to three given points. This was solved before 1640 by Torricelli and, subsequently Steiner worked on the general problem for n points. More details appears in (Hwang et al., 1992).
The MLSteiner problem was first considered by Cerulli et al. (2006). They also compared their Pilot Method with some other metaheuristics for the MLSteiner problem: Tabu Search, Simulated Annealing, and some implementations of Variable Neighbourhood Search. From their analysis, the Pilot Method was shown to be the best performing heuristic for the problem (Cerulli et al., 2006).
Afterwards, the success of the heuristic solution approaches for the MLST problem proposed by Consoli et al. (2008a; 2009b) provided the motivation for considering the implementation of similar approaches for the MLSteiner problem. In (Consoli et al., 2008b; 2009a; 2010), the following metaheuristics for the MLSteiner problem were presented: a Greedy Randomized Adaptive Search Procedure, a Discrete Particle Swarm Optimization, a Variable Neighbourhood Search, and a hybrid local search method obtained by combining Variable Neighbourhood Search with Simulated Annealing. Considering a wide range of problem instances, these metaheuristics were compared to the Pilot Method by Cerulli et al. (2006), the most popular MLSteiner heuristic in the literature. Based on this experimental analysis, all the proposed procedures clearly outperformed the Pilot Method. In particular, it was shown that Variable Neighbourhood Search is the most effective approach to the problem, thanks to the following features: ease of implementation, user-friendly code, high-quality of the solutions, and shorter computational running times.
Test datasets for the MLSteiner problem
The following link allows to download some instances of the minimum labelling Steiner tree problem.
These are the instances used in the computations by the authors of (Consoli et al., 2008b; 2009a; 2010). They considered 48 different datasets, each one containing 10 instances of the problem (yielding a total of 480 instances), with n = 100, 500 nodes, l = 0.25 n, 0.5 n, n, 1.25 n labels, and q = 0.2 n, 0.4 n basic nodes. The number of edges, m, is obtained indirectly from the density d of edges whose values are chosen to be 0.8, 0.5, and 0.2.
References
Cerulli, R., Fink, A., Gentili, M., Voß, S., 2006. Extensions of the minimum labelling spanning tree problem. Journal of Telecommunications and Information Technology 4:39-45.
Hwang, F.K., Richards, D.S., Winter, P., 1992. The Steiner Tree Problem. North-Holland, Amsterdam.