This paper deals with the ring star problem that consists in designing a ring that pass through a central depot, and then assigning each non visited customer to a node of the ring. The objective is to minimize the total routing and assignment costs. A new chain based formulation is proposed. Valid inequalities are proposed to strengthen the linear programming relaxation and are used as cutting planes in a branch-and-cut approach. A large set of instances are tested and show the effectiveness of the method that outperforms the results previously obtained on the problem.
Citation
submitted