Ring star problem

The ring star problem (RSP) is a NP-hard problem^[1] in combinatorial optimization. In a complete weighted mixed graph, the ring star problem aims to find a minimum cost ring star subgraph formed by a cycle (ring part) and a set of arcs (star part) such that each arc's child node belongs to the cycle and each arc's parent node does not. The costs for the arcs are usually different than the cycle's costs. The cycle must contains at least one node which is called the depot or the root.

Example of a Ring Star Problem network

RSP is a generalization of the traveling salesman problem.^[1] When the costs of the arcs are infinite and the ring contains all nodes, the RSP reduces to TSP. Some applications of RSP arise in the context of telecommunications,^[2] transports or logistics.

Exact formulations

RSP was first formulated in 1998.^[2] The first MILP for solving RSP was introduced in 2004 alongside valid inequalities that improve the formulation.^[1] Several exact formulations have since been introduced in order to solve the Ring star problem such as a graph-layers based ILP^[3] and a st-chains formulation.^[4]

Variants of the ring star problem

Many variants of the ring star problem have been studied since 2006.

• The capacitated m-ring star problem (2006)^[5][6]
• The multi-depot ring star problem (2010)^[7][8]
• The non-disjoint m-ring star problem (2014)^[9]
• The survivable ring star problem (2024)^[10][11]

Heuristics

The first heuristic for RSP, a general variable neighborhood search has been introduced in order to obtain approximate solutions more quickly.^[12] In 2013, an evolutionary algorithm also approximates RSP. In 2020, an ant colony optimization^[13] heuristic outperforms the evolutionary algorithm heuristic.