Jump to content

Ring star problem

Edit links
From Wikipedia, the free encyclopedia

Example of a Ring Star Problem network

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.

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

[edit]

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

[edit]

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

[edit]

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.

References

[edit]
  1. ^ a b c Labbé, Martine; Laporte, Gilbert; Martín, Inmaculada Rodríguez; González, Juan José Salazar (May 2004). "The Ring Star Problem: Polyhedral analysis and exact algorithm". Networks. 43 (3): 177–189. doi:10.1002/net.10114. ISSN 0028-3045.
  2. ^ a b Xu, Jiefeng; Chiu, Steve Y.; Glover, Fred (1999). "Optimizing a Ring-Based Private Line Telecommunication Network Using Tabu Search". Management Science. 45 (3): 330–345. doi:10.1287/mnsc.45.3.330. ISSN 0025-1909. JSTOR 2634881.
  3. ^ Simonetti, L.; Frota, Y.; de Souza, C.C. (September 2011). "The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm". Discrete Applied Mathematics. 159 (16): 1901–1914. doi:10.1016/j.dam.2011.01.015.
  4. ^ Kedad-Sidhoum, Safia; Nguyen, Viet Hung (January 2010). "An exact algorithm for solving the ring star problem". Optimization. 59 (1): 125–140. doi:10.1080/02331930903500332. ISSN 0233-1934.
  5. ^ Baldacci, R.; Dell'Amico, M.; González, J. Salazar (December 2007). "The Capacitated m -Ring Star Problem". Operations Research. 55 (6): 1147–1162. doi:10.1287/opre.1070.0432. ISSN 0030-364X.
  6. ^ Naji-Azimi, Zahra; Salari, Majid; Toth, Paolo (16 December 2010). "A heuristic procedure for the Capacitated m-Ring Star problem". European Journal of Operational Research. 207 (3): 1227–1234. doi:10.1016/j.ejor.2010.06.030. ISSN 0377-2217.
  7. ^ Baldacci, R.; Dell’Amico, M. (16 May 2010). "Heuristic algorithms for the multi-depot ring-star problem". European Journal of Operational Research. 203 (1): 270–281. doi:10.1016/j.ejor.2009.07.026. ISSN 0377-2217.
  8. ^ Sundar, Kaarthik; Rathinam, Sivakumar (1 March 2017). "Multiple depot ring star problem: a polyhedral study and an exact algorithm". Journal of Global Optimization. 67 (3): 527–551. doi:10.1007/s10898-016-0431-7. ISSN 1573-2916.
  9. ^ Fouilhoux, Pierre; Questel, Aurélien (April 2014). "A branch-and-cut for the Non-Disjoint m-Ring Star Problem". RAIRO - Operations Research. 48 (2): 167–188. doi:10.1051/ro/2014006. ISSN 0399-0559.
  10. ^ Khamphousone, Julien; Castaño, Fabian; Rossi, André; Toubaline, Sonia (March 2024). "A survivable variant of the ring star problem". Networks. 83 (2): 324–347. doi:10.1002/net.22193.
  11. ^ Truong, Anh Tan Mai; Toubaline, Sonia; Rossi, André (March 2024). "Survivable Ring Star Problem under the failure of two hubs". 25ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2024). Université Picardie Jules Vernes.
  12. ^ Dias, Thayse Christine S.; de Sousa Filho, Gilberto F.; Macambira, Elder M.; dos Anjos F. Cabral, Lucidio; Fampa, Marcia Helena C. (2006). "An Efficient Heuristic for the Ring Star Problem". Experimental Algorithms. Lecture Notes in Computer Science. Vol. 4007. Springer. pp. 24–35. doi:10.1007/11764298_3. ISBN 978-3-540-34597-8.
  13. ^ Zang, Xiaoning; Jiang, Li; Ding, Bin; Fang, Xiang (1 June 2021). "A hybrid ant colony system algorithm for solving the ring star problem". Applied Intelligence. 51 (6): 3789–3800. doi:10.1007/s10489-020-02072-w. ISSN 1573-7497.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ring_star_problem&oldid=1235871060"