Algorithms for the design of network topologies with balanced disjoint rings

作者：Uester Halit; Kumar Sarath K S

来源：Journal of Heuristics, 2010, 16(1): 37-63.

DOI：10.1007/s10732-008-9085-z

• Network design
• Randomized algorithms
• Combined neighborhoods
• Disjoint rings

We define the Balanced Disjoint Rings (BDR) problem as developing a method to partition of the nodes in a network to form a given number of disjoint rings of minimum total link length in such a way that there is almost the same number of nodes in each ring. The BDR problem has potential applications in the design of survivable network structures in telecommunications as well as in the identification of local distribution/collection routes in logistics. The BDR problem can also be considered a generalization of the traveling salesman problem since we are interested in multiple tours instead of a single tour. We develop an efficient heuristic solution methodology that involves various GRASP-based randomized solution construction routines that allow a multi-start framework and a n effective combination of cyclic-exchange and single-move neighborhoods in a local search improvement procedure. The algorithms perform very well in our numerical studies, providing encouraging optimality and lower bound gaps with very reasonable runtimes.

• 出版日期2010-2