The ring star problem (RSP) is a

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

problem in

combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...

. In a

complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...

weighted

mixed graph In graph theory, a mixed graph is a graph consisting of a set of vertices , a set of (undirected) edges , and a set of directed edges (or arcs) . Definitions and notation Consider adjacent vertices u,v \in V. A directed edge, called an arc, ...

, 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. RSP is a generalization of the

traveling salesman problem In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exac ...

. 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 Telecommunication, often used in its plural form or abbreviated as telecom, is the transmission of information over a distance using electronic means, typically through cables, radio waves, or other communication technologies. These means of ...

, transports or

logistics Logistics is the part of supply chain management that deals with the efficient forward and reverse flow of goods, services, and related information from the point of origin to the Consumption (economics), point of consumption according to the ...

Exact formulations

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

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) * The multi-depot ring star problem (2010) * The non-disjoint m-ring star problem (2014) * The survivable ring star problem (2024)

Heuristics

The first

heuristic A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...

for RSP, a general

variable neighborhood search Variable neighborhood search (VNS), proposed by Mladenović & Hansen in 1997, is a metaheuristic method for solving a set of combinatorial optimization and global optimization problems. It explores distant neighborhoods of the current incumbent so ...

has been introduced in order to obtain approximate solutions more quickly. In 2013, an

evolutionary algorithm Evolutionary algorithms (EA) reproduce essential elements of the biological evolution in a computer algorithm in order to solve "difficult" problems, at least Approximation, approximately, for which no exact or satisfactory solution methods are k ...

also approximates RSP. In 2020, an ant colony optimization heuristic outperforms the evolutionary algorithm heuristic.

References

{{reflist NP-hard problems Complexity classes