A greedy heuristic for the capacitated minimum spanning tree problem
提出一种结合Prim和Esau-Williams方法的两阶段贪婪启发式算法，通过余弦定律扰动输入数据扩大可行解空间，在基准测试中表现优异且鲁棒性强。
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.