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


Oencan T., ALTINEL İ. K.

Journal of the Operational Research Society, cilt.60, sa.2, ss.259-267, 2009 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 60 Sayı: 2
  • Basım Tarihi: 2009
  • Doi Numarası: 10.1057/palgrave.jors.2602548
  • Dergi Adı: Journal of the Operational Research Society
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Sayfa Sayıları: ss.259-267
  • Galatasaray Üniversitesi Adresli: Evet

Özet

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.