Topological design of ring networks

Topological design of ring networks

0.00 Avg rating0 Votes
Article ID: iaor19942090
Country: United Kingdom
Volume: 21
Issue: 4
Start Page Number: 421
End Page Number: 431
Publication Date: Apr 1994
Journal: Computers and Operations Research
Authors:
Keywords: vehicle routing & scheduling, heuristics, computers, programming: travelling salesman
Abstract:

In this paper the shortcomings of conventional ring networks are discussed and how these shortcomings are solved by the enhanced ring architecture is explained. Enhanced ring architecture is a two level ring network connecting the local rings by a backbone ring. Studied is the ring network design problem-the formation of local loops with a size restriction connected to a backbone ring. The Parallel Savings Algorithm which generates good feasible solutions is presented. The K Iterated Travelling Salesman Tours Partitioning is studied and analyzed for its worst case error. This algorithm is based on partitioning a multi-center travelling salesman tour in order to generate a feasible solution to the ring network design problem. It has a worst case error bound of 4-3/2K where K is the size of the local rings when K≥3. The heuristic solution cost is at most 4-3/2K times the optimum value. It is based on the Christofides’ extended heuristic for the multi-center travelling salesman problem which makes the procedure a polynomial one.

Reviews

Required fields are marked *. Your email address will not be published.