Thumbnail - Request a copy

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érence
Titre du colloque
2019 6th International Conference on Control, Decision and Information Technologies (CoDIT)
Date du colloque
2019-04
Ville du colloque
Paris
Pays du colloque
France
Titre 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
2060
Pages
1462-1467
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Mahjoub, Ali Ridha
Laboratoire 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 algorithms