Metaheuristics for computing the forwarding index of a graph

In this paper we present two algorithms, based on Greedy Randomized Adaptive Search Procedure and Tabu Search, for computing upper bounds for the forwarding index of a graph. A typical problem in the design of communication networks is determining how to interconnect each pair of nodes, without overloading any one of them. The forwarding index of a graph is a parameter that measures the load or congestion of the network seen as the number of interconnecting paths that pass through each node. The proposed algorithms have been tested on different sets of graphs for which theoretical values are known and also on randomly generated graphs of variable size and density. Experiments show that the algorithms find the optimal solution or a solution very close to the optimum in all cases. Our results are furthermore compared with the other heuristics for which computational results are available in the literature, showing that our algorithms behave as well as or better than these.