Parametric enhancements of the Esau–Williams heuristic for the capacitated minimum spanning tree problem

T Öncan () and İ K Altınel
Additional contact information
T Öncan: Galatasaray University
İ K Altınel: Boǧaziçi University

Journal of the Operational Research Society, 2009, vol. 60, issue 2, 259-267

Abstract: 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.

Keywords: capacitated minimal spanning tree problem; Esau–Williams heuristic (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2602548 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:60:y:2009:i:2:d:10.1057_palgrave.jors.2602548

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2602548

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().