DefinePK

Abstract

This paper aims to present the least cost algorithm finding loop routes between a central node and a large number of end-nodes in the centralized network. End-nodes request service on the loop route originated from a central node. Demands at end-node are deterministic and distance matrix is given. We find a set of minimum cost loops to link end-nodes to a central node satisfying the service requirements at end-nodes. In this paper, we propose a heuristic algorithm which first generates possible routes by applying the space relaxation, and then finds a set of loop routes through matching. The proposed algorithm is easy to implement and enable us to obtain the solution regardless of network configuration in the short computation time for the small network. The computation comparison with previous algorithms is also presented. Our algorithm can be applied find the broadcasting loops in centralized network.