1. ¹Galatasaray University, Ortaköy, stanbul, Türkiye
2. ²Boaziçi University, Bebek, stanbul, Türkiye

Correspondence: T Öncan, Department of Industrial Engineering, Galatasaray University, Ciragan Cad., Ortaköy, stanbul 34357, Turkey. E-mail: ytoncan@gsu.edu.tr

Received October 2006; Accepted October 2007; Published online 9 January 2008.

Abstract

The Capacitated Minimum Spanning Tree Problem is NP-hard and several heuristic solution methods have been proposed. They can be classified as classical ones and metaheuristics. Recent developments have shown that metaheuristics outperform classical heuristics. However, they require long computation times and there are difficulties in their parameter calibration and coding phases. This explains the popularity of the Esau–Williams (EW) heuristic in practice, and its use in many successful metaheuristics and second-order greedy methods. In this work, we are concerned with the EW heuristic and we propose simple new enhancements. Based on our computational experiments, we can say that they considerably improve its accuracy with minor increase in computation time, and without harming its simplicity.