Building a capacitated minimum spanning tree using simulated annealing

A. Ipatov

Ural State University

Abstract: In this paper we consider capacitated minimum spanning tree problem (CMST) which is NP-hard. We have developed enhanced simulated annealing method, which allows getting better solutions for CMST than the classical one. Computational results on the benchmark instances are reported.

Keywords: capacitated minimum spanning tree; simulated annealing; metaheuristic; neighborhood.

UDC: 519.854.2