A Column Generation Approach to the SONET USHR Based Ring Routing and Capacitating Problem

摘要

We consider to design a single-hubbed network with the unidirectional self-healing ring (USHR) architecture, given (ⅰ) a network topology consisting of a set of nodes and links, (ⅱ) a traffic matrix, and (ⅲ) a hop limit on the ring route to be established. This, we will call it Ring Routing and Capacitating Problem(RRCP), is a decision problem which determines both the USHR ring routes covering all of the given nodes without violating the hop limit constraint and decides the equipment rates to be loaded in each ring. We formulate the RRCP as a nonlinear integer programming, which is highly intractable to devise any polynomial-time algorithm, so that we propose a column-generation based solution approach. The whole algorithm has been implemented in C++ with linkage to the CPLEX solver and tested on various manageable networks with 10 to 30 nodes and 20 to 150 links. The objective values of the final solutions found from the column-generation method have shown, in average, at most 3% performance gap from the LP lower bound values.