Landscape analysis for multicast routing

In recent years, methods based on local search have been utilized in off-line algorithms for multicast routing in communication networks. In multicast routing, several point-to-multipoint requests have to be scheduled under constraints associated with each link of the underlying network such as capacity and transmission costs. We propose a landscape analysis technique to solve this problem, where each particular request is routed by a Steiner tree heuristic. The landscape analysis employs simulated annealing with a logarithmic cooling schedule, which has been proved to be an appropriate tool to tackle hard problems from Combinatorial Optimisation and Computational Biology. We present results from computational experiments performed on three instances from the OR library. Emphasis is placed on algorithmic aspects of off-line routing, in particular, on approximations of optimal parameter settings, rather than on implementations of fast online network protocols. Furthermore, we investigate the impact of capacity noise on parameter settings and we perform a comparison to genetic algorithms based upon PMX crossover.