{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:18:42Z","timestamp":1775913522159,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"23","license":[{"start":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T00:00:00Z","timestamp":1591488000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T00:00:00Z","timestamp":1591488000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00500-020-05043-y","type":"journal-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T05:02:18Z","timestamp":1591506138000},"page":"17957-17968","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["The Multiple Steiner TSP with order constraints: complexity and optimization algorithms"],"prefix":"10.1007","volume":"24","author":[{"given":"Virginie","family":"Gabrel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. Ridha","family":"Mahjoub","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2377-5709","authenticated-orcid":false,"given":"Raouia","family":"Taktak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eduardo","family":"Uchoa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,7]]},"reference":[{"key":"5043_CR1","volume-title":"The traveling salesman problem: a computational study","author":"DL Applegate","year":"2011","unstructured":"Applegate DL, Bixby RE, Chvatal V, Cook WJ (2011) The traveling salesman problem: a computational study. Princeton University Press, Princeton"},{"key":"5043_CR2","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1023\/A:1008779125567","volume":"17","author":"N Ascheuer","year":"2000","unstructured":"Ascheuer N, J\u00fcnger M, Reinelt G (2000) A branch and cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Comput Optim Appl 17:61\u201384","journal-title":"Comput Optim Appl"},{"key":"5043_CR3","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0895480193259813","volume":"10","author":"M Ba\u00efou","year":"2002","unstructured":"Ba\u00efou M, Mahjoub AR (2002) Steiner 2-edge connected subgraph polytopes on series-parallel graphs. SIAM J Discrete Math 10:505\u2013514","journal-title":"SIAM J Discrete Math"},{"key":"5043_CR4","first-page":"241","volume":"68","author":"E Balas","year":"1995","unstructured":"Balas E, Fischetti M, Pulleyblank WR (1995) The precedence-constrained asymmetric traveling salesman polytope. Math Program 68:241\u2013265","journal-title":"Math Program"},{"key":"5043_CR5","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1287\/opre.48.2.318.12378","volume":"48","author":"C Barnhart","year":"2000","unstructured":"Barnhart C, Hane CA, Vance PH (2000) Using branch-and-price-and-cut to solve origin-destination integer multicommodity Flow problem. Oper Res 48:318\u2013326","journal-title":"Oper Res"},{"issue":"3","key":"5043_CR6","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","volume":"34","author":"T Bektas","year":"2006","unstructured":"Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3):209\u2013219","journal-title":"Omega"},{"issue":"1","key":"5043_CR7","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/s10479-011-1024-y","volume":"207","author":"E Benavent","year":"2013","unstructured":"Benavent E, Mart\u00ednez A (2013) Multi-depot multiple TSP: a polyhedral study and computational results. Ann Oper Res 207(1):7\u201325","journal-title":"Ann Oper Res"},{"key":"5043_CR8","doi-asserted-by":"crossref","unstructured":"Borne S, Virginie G, Mahjoub AR, Taktak R (2011) Multilayer survivable optical network design. In: International conference on network optimization. Springer, pp. 170\u2013175","DOI":"10.1007\/978-3-642-21527-8_22"},{"key":"5043_CR9","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/j.endm.2013.05.129","volume":"41","author":"S Borne","year":"2013","unstructured":"Borne S, Mahjoub AR, Taktak R (2013) A branch-and-cut algorithm for the multiple steiner TSP with order constraints. Electron Notes Discrete Math 41:487\u2013494","journal-title":"Electron Notes Discrete Math"},{"key":"5043_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01582008","volume":"33","author":"G Cornu\u00e9jols","year":"1985","unstructured":"Cornu\u00e9jols G, Fonlupt J, Naddef D (1985) The traveling salesman problem on a graph and some related integer polyhedra. Math Program 33:1\u201327","journal-title":"Math Program"},{"issue":"4","key":"5043_CR11","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2(4):393\u2013410","journal-title":"J Oper Res Soc Am"},{"key":"5043_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/b135457","volume-title":"Column generation","author":"G Desaulniers","year":"2005","unstructured":"Desaulniers G, Desrosiers J, Solomon MM (2005) Column generation, vol 5. Springer, Berlin"},{"key":"5043_CR13","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connection with graphs. Numer Math 1:269\u2013271","journal-title":"Numer Math"},{"key":"5043_CR14","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10288-010-0130-z","volume":"8","author":"D Feillet","year":"2010","unstructured":"Feillet D (2010) A tutorial on column generation and branch-and-price for vehicle routing problems. J Oper Res 8:407\u2013424","journal-title":"J Oper Res"},{"key":"5043_CR15","doi-asserted-by":"crossref","unstructured":"Geoffrion AM (1974) Lagrangean relaxation for integer programming. In: Approaches to integer programming. Springer, pp 82\u2013114","DOI":"10.1007\/BFb0120690"},{"issue":"2","key":"5043_CR16","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1002\/net.20122","volume":"48","author":"L Gouveia","year":"2006","unstructured":"Gouveia L, Pesneau P (2006) On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks 48(2):77\u201389","journal-title":"Networks"},{"issue":"1","key":"5043_CR17","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0377-2217(93)E0238-S","volume":"83","author":"L Gouveia","year":"1995","unstructured":"Gouveia L, Vo\u00df S (1995) A classification of formulations for the (time-dependent) traveling salesman problem. Eur J Oper Res 83(1):69\u201382","journal-title":"Eur J Oper Res"},{"issue":"4","key":"5043_CR18","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1002\/net.21765","volume":"71","author":"L Gouveia","year":"2018","unstructured":"Gouveia L, Pesneau P, Ruthmair M, Santos D (2018) Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem. Networks 71(4):451\u2013465","journal-title":"Networks"},{"issue":"1","key":"5043_CR19","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01582116","volume":"16","author":"M Gr\u00f6tschel","year":"1979","unstructured":"Gr\u00f6tschel M, Padberg MW (1979a) On the symmetric travelling salesman problem I: inequalities. Math Program 16(1):265\u2013280","journal-title":"Math Program"},{"issue":"1","key":"5043_CR20","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01582117","volume":"16","author":"M Gr\u00f6tschel","year":"1979","unstructured":"Gr\u00f6tschel M, Padberg MW (1979b) On the symmetric travelling salesman problem II: lifting theorems and facets. Math Program 16(1):281\u2013302","journal-title":"Math Program"},{"key":"5043_CR21","volume-title":"The traveling salesman problem and its variations","author":"G Gutin","year":"2006","unstructured":"Gutin G, Punnen AP (2006) The traveling salesman problem and its variations, vol 12. Springer, Berlin"},{"issue":"6","key":"5043_CR22","doi-asserted-by":"publisher","first-page":"1307","DOI":"10.1111\/itor.12419","volume":"24","author":"R Interian","year":"2017","unstructured":"Interian R, Ribeiro CC (2017) A grasp heuristic using path-relinking and restarts for the steiner traveling salesman problem. Int Trans Oper Res 24(6):1307\u20131323","journal-title":"Int Trans Oper Res"},{"issue":"4","key":"5043_CR23","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1016\/j.disopt.2010.05.002","volume":"7","author":"Y Kobayashi","year":"2010","unstructured":"Kobayashi Y, Sommer C (2010) On shortest disjoint paths in planar graphs. Discrete Optim 7(4):234\u2013245","journal-title":"Discrete Optim"},{"issue":"1","key":"5043_CR24","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.ejor.2013.01.044","volume":"228","author":"AN Letchford","year":"2013","unstructured":"Letchford AN, Nasiri SD, Theis DO (2013) Compact formulations of the steiner traveling salesman problem and related problems. Eur J Oper Res 228(1):83\u201392","journal-title":"Eur J Oper Res"},{"issue":"6","key":"5043_CR25","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1287\/opre.1050.0234","volume":"53","author":"ME L\u00fcbbecke","year":"2005","unstructured":"L\u00fcbbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper Res 53(6):1007\u20131023","journal-title":"Oper Res"},{"key":"5043_CR26","doi-asserted-by":"crossref","unstructured":"Mahjoub AR, Taktak R, Uchoa E (2019) A layered compact formulation for the multiple steiner TSP with order constraints. In: 2019 6th international conference on control, decision and information technologies (CoDIT). IEEE, pp 1462\u20131467","DOI":"10.1109\/CoDIT.2019.8820661"},{"issue":"3","key":"5043_CR27","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1016\/S0377-2217(01)00227-2","volume":"140","author":"C Moon","year":"2002","unstructured":"Moon C, Kim J, Choi G, Seo Y (2002) An efficient genetic algorithm for the traveling salesman problem with precedence constraints. Eur J Oper Res 140(3):606\u2013617","journal-title":"Eur J Oper Res"},{"key":"5043_CR28","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/0-306-48213-4_2","volume-title":"The traveling salesman problem and its variations","author":"D Naddef","year":"2007","unstructured":"Naddef D (2007) Polyhedral theory and branch-and-cut algorithms for the symmetric TSP. In: Gutin G, Punnen AP (eds) The traveling salesman problem and its variations. Springer, Boston, pp 29\u2013116"},{"issue":"3","key":"5043_CR29","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1016\/j.cor.2007.11.008","volume":"36","author":"T \u00d6ncan","year":"2009","unstructured":"\u00d6ncan T, Alt\u0131nel \u0130K, Laporte G (2009) A comparative analysis of several asymmetric traveling salesman problem formulations. Comput Oper Res 36(3):637\u2013654","journal-title":"Comput Oper Res"},{"key":"5043_CR30","first-page":"93","volume":"9","author":"AJ Orman","year":"2006","unstructured":"Orman AJ, Williams HP (2006) A survey of different integer programming formulations of the travelling salesman problem. Optim Econom Financ Anal 9:93\u2013108","journal-title":"Optim Econom Financ Anal"},{"issue":"1","key":"5043_CR31","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"MW Padberg","year":"1991","unstructured":"Padberg MW, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev 33(1):60\u2013100","journal-title":"SIAM Rev"},{"key":"5043_CR32","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0377-2217(02)00359-4","volume":"147","author":"JJ Salazar-Gonz\u00e1lez","year":"2003","unstructured":"Salazar-Gonz\u00e1lez JJ (2003) The steiner cycle polytope. Eur J Oper Res 147:671\u2013679","journal-title":"Eur J Oper Res"},{"key":"5043_CR33","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.cor.2014.05.014","volume":"51","author":"SC Sarin","year":"2014","unstructured":"Sarin SC, Sherali HD, Judd JD, Tsai P-FJ (2014) Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations. Comput Oper Res 51:64\u201389","journal-title":"Comput Oper Res"},{"issue":"6","key":"5043_CR34","first-page":"1349","volume":"29","author":"M Steinov\u00e1","year":"2012","unstructured":"Steinov\u00e1 M (2012) Approximability of the minimum steiner cycle problem. Comput Inform 29(6):1349\u20131357","journal-title":"Comput Inform"},{"key":"5043_CR35","volume-title":"Integer programming","author":"LA Wolsey","year":"1998","unstructured":"Wolsey LA (1998) Integer programming. Wiley, New York"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-020-05043-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00500-020-05043-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-020-05043-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,6]],"date-time":"2021-06-06T23:14:19Z","timestamp":1623021259000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00500-020-05043-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,7]]},"references-count":35,"journal-issue":{"issue":"23","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["5043"],"URL":"https:\/\/doi.org\/10.1007\/s00500-020-05043-y","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"value":"1432-7643","type":"print"},{"value":"1433-7479","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,7]]},"assertion":[{"value":"7 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"All authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Human and animal rights"}}]}}