An exact algorithm for solving the ring star problem

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

Article

Download

View An exact algorithm for solving the ring star problem