A layered compact formulation for the Multiple Steiner TSP with Order constraints
Mahjoub, Ali Ridha; Taktak, Raouia; Uchoa, Eduardo, A layered compact formulation for the Multiple Steiner TSP with Order constraints, 2019 6th International Conference on Control, Decision and Information Technologies (CoDIT), IEEE - Institute of Electrical and Electronics Engineers : Piscataway, NJ, p. 1462-1467. 10.1109/CoDIT.2019.8820661
Type
Communication / ConférenceConference title
2019 6th International Conference on Control, Decision and Information Technologies (CoDIT)Conference date
2019-04Conference city
ParisConference country
FranceBook title
2019 6th International Conference on Control, Decision and Information Technologies (CoDIT)Publisher
IEEE - Institute of Electrical and Electronics Engineers
Published in
Piscataway, NJ
ISBN
978-1-7281-0522-2
Number of pages
2060Pages
1462-1467
Publication identifier
Metadata
Show full item recordAuthor(s)
Mahjoub, Ali RidhaLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Taktak, Raouia
Institut Supérieur d'Informatique et de Multimédia de Sfax [ISIMS]
Uchoa, Eduardo
Universidade Federal Fluminense [UFF]
Abstract (EN)
In this paper we study a network design problem that consists in finding a minimum weight subgraph containing solutions for multiple Steiner Traveling Salesman Problems with Order constraints. We propose a layered compact ILP formulation for the problem. Experimental results show that it is reasonably effective and can solve to optimality medium-sized instances. Lage-scale instances are more difficult, and does not reach optimal solutions within a time limit of 3 hours. In order to improve our formulation, we investigate valid inequalities efficiency using a column-generation-based approach.Subjects / Keywords
Traveling salesman problems; Cybernetics; Information technology; Approximation algorithms; Heuristic algorithms; Moon; Genetic algorithmsRelated items
Showing items related by title and author.
-
Gabrel, Virginie; Mahjoub, Ali Ridha; Taktak, Raouia; Uchoa, Eduardo (2020) Article accepté pour publication ou publié
-
Borne, Sylvie; Mahjoub, Ali Ridha; Taktak, Raouia (2013) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Simonetti, Luidi; Uchoa, Eduardo (2013) Article accepté pour publication ou publié
-
Uchoa, Eduardo; Simonetti, Luidi; Mahjoub, Ali Ridha (2012) Communication / Conférence
-
Hanafi, Said; Mahjoub, Ali Ridha; Taktak, Raouia; Wilbaut, Christophe (2021) Communication / Conférence