Journal
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
Volume 68, Issue 10, Pages 1223-1235Publisher
PALGRAVE MACMILLAN LTD
DOI: 10.1057/s41274-016-0146-7
Keywords
capacitated minimum spanning tree problem; Esau-Williams heuristic; Prim's algorithm
Ask authors/readers for more resources
This paper develops a greedy heuristic for the capacitated minimum spanning tree problem (CMSTP), based on the two widely known methods of Prim and of Esau-Williams. The proposed algorithm intertwines two-stages: an enhanced combination of the Prim and Esau-Williams approaches via augmented and synthetic node selection criteria, and an increase of the feasible solution space by perturbing the input data using the law of cosines. Computational tests on benchmark problems show that the new heuristic provides extremely good performance results for the CMSTP, justifying its effectiveness and robustness. Furthermore, excluding the feasible space expansion, we show that we can still obtain good quality solutions in very short computational times.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available