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
Conference title
2019 6th International Conference on Control, Decision and Information Technologies (CoDIT)
Conference date
2019-04
Conference city
Paris
Conference country
France
Book 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
2060
Pages
1462-1467
Publication identifier
Metadata
Show full item record
Author(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]
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 algorithms