Hill-climbing, simulated annealing and the Steiner problem in graphs

This paper considers the use of local optimization or improvement heuristics on the Steiner problem in graphs. By considering any Steiner tree as a disjoint union of paths we show it is possible to define a neighbourhood structure on the set of feasible solutions which can be used in a k-opt exchange heuristic. These ideas are then extended to a simulated annealing method. Computational experience, comparing these new methods with one of the best existing heuristics is presented.