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érenceTitre du colloque
2019 6th International Conference on Control, Decision and Information Technologies (CoDIT)Date du colloque
2019-04Ville du colloque
ParisPays du colloque
FranceTitre de l'ouvrage
2019 6th International Conference on Control, Decision and Information Technologies (CoDIT)Éditeur
IEEE - Institute of Electrical and Electronics Engineers
Ville d’édition
Piscataway, NJ
Isbn
978-1-7281-0522-2
Nombre de pages
2060Pages
1462-1467
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(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]
Résumé (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.Mots-clés
Traveling salesman problems; Cybernetics; Information technology; Approximation algorithms; Heuristic algorithms; Moon; Genetic algorithmsPublications associées
Affichage des éléments liés par titre et auteur.
-
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