Ring star problem

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 from the cycle's costs. The cycle must contain at least one node designated as 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

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.

References

  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. hdl:11380/610536. 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. hdl:11380/659439. 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. arXiv:1407.5080. 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, Tran Mai Anh; 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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.