Second-Order Greedy Algorithms for Centralized Teleprocessing Network Design

We consider the problem of designing a centralized telecommunication network comprised of multipoint lines given a set of terminal locations, traffic requirements, and a common central site. The optimal solution to this problem is a capacitated minimal spanning tree. We develop a class of heuristic algorithms for the solution of this problem by imbedding existing heuristics, referred to as first-order greedy algorithms, inside a loop where small, carefully chosen sets of arcs are alternately forced in and out of the solution. The resultant procedure is shown to be superior to existing techniques, producing solutions typically 2 percent better, while requiring only a modest amount of additional computer time.