Pricing strategies for capacitated ring-star problems based on dynamic programming algorithms

The Capacitated m-Ring-Star Problem (crsp) is the problem of designing a set of rings that pass through a central depot and through some transition points and/or customers, and then assigning each nonvisited customer to a visited point or customer. The number of customers visited and connected to a ring is bounded by an upper limit: the capacity of the ring. The objective is to minimize the total routing cost plus assignment costs. The problem has several applications in telecommunication network design and transportation planning. In addition, closely related versions to the crsp involving different graph topologies and objective functions have been recently studied by several authors. The recent literature shows that effective methods for solving these class of difficult optimization problems are based on the combination of column-and-cut generation techniques. In particular, the effectiveness of these methods strongly depend on the qualities and complexities of the associated pricing problems.