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

In this paper, we investigate different pricing strategies based on dynamic programming algorithms for the crsp that can also be adapted to deal with different graph topologies. We describe a general bounding procedure based on column-and-cut generation that is used to test the effectiveness of the different pricing strategies. We report an extensive computational analysis on crsp benchmark instances from the literature and on newly generated instances for its generalization to the multi-depot case, the Multi-Depot Ring-Star Problem (mdrsp). The results obtained show the effectiveness of the pricing strategies proposed and that tight lower bounds can be computed for instances involving up to 431 nodes.