Memory Adaptive Reasoning & Greedy Assignment Techniques for the Capacitated Minimum Spanning Tree Problem

It is the purpose of this paper to investigate effects of adding randomization to a memory-based heuristic. The algorithms we propose are applied to the Capacitated Minimum Spanning Tree problem (CMST), and we study the combined effects of simultaneously applying a memory-based and a randombased heuristic to the CMST. This paper uses the Adaptive Reasoning Technique (ART) and concepts from the greedy randomized adaptive search procedure for solving the CMST. The resulting hybrid procedure is tested against the stand-alone Esau-Williams heuristic procedure, as well as the stand-alone greedy assignment technique. We find that randomization does not constructively add to the memory-based procedure, as ART alone typically outperforms all other approaches in terms of solution quality, while expending a modest amount of computational effort.