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, ss.259-267, 2009 (SCI Expanded İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 60 Konu: 2
  • Basım Tarihi: 2009
  • Doi Numarası: 10.1057/palgrave.jors.2602548
  • Dergi Adı: Journal of the Operational Research Society
  • Sayfa Sayıları: ss.259-267

Ö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.