Show simple item record

dc.contributor.authorGabrel, Virginie
dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorTaktak, Raouia
dc.contributor.authorUchoa, Eduardo
dc.date.accessioned2020-07-01T11:18:44Z
dc.date.available2020-07-01T11:18:44Z
dc.date.issued2020
dc.identifier.issn1432-7643
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20901
dc.language.isoenen
dc.subjectSteiner TSP
dc.subjectOrder constraints
dc.subjectInteger linear programming
dc.subjectBranch-and-Price algorithm
dc.subjectBranch-and-Cut algorithm
dc.subject.ddc005en
dc.titleThe Multiple Steiner TSP with order constraints: complexity and optimization algorithms
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe consider a variant of the Travelling Salesman Problem (TSP), the Multiple Steiner TSP with Order constraints (MSTSPO). Consider a weighted undirected graph and a set of salesmen, and each salesman is associated with a set of compulsory vertices to visit, called terminals. The MSTSPO consists in finding a minimum-cost subgraph containing for each salesman a tour going in a specified order through its terminals. Along with its importance from a theoretical point of view, the problem is also challenging in practice since it has applications in telecommunication networks. We show that the problem is NP-hard even for a single salesman and propose integer programming formulations. We then devise both Branch-and-Cut and Branch-and-Price algorithms to solve the problem. The extensive computational results are presented, showing the efficiency of our algorithms.
dc.relation.isversionofjnlnameSoft Computing
dc.relation.isversionofjnldate2020
dc.relation.isversionofdoi10.1007/s00500-020-05043-y
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2020-12-17T19:02:46Z
hal.person.labIds989
hal.person.labIds989
hal.person.labIds989
hal.person.labIds


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record