Combining and projecting flow models for the (Precedence Constrained) Asymmetric Traveling Salesman Problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Networks Année : 2017

Combining and projecting flow models for the (Precedence Constrained) Asymmetric Traveling Salesman Problem

Résumé

There are many ways of modeling the Asymmetric Traveling Salesman Problem (ATSP) and the related Precedence Constrained ATSP (PCATSP). In this paper we present new formulations for the two problems that result from combining precedence variable based formulations with network flow based formulations. The motivation for this work is a property of the so-called GDDL inequalities (see Gouveia and Pesneau, 2006), the " disjoint sub-paths " property, that is explored to create formulations that combine two (or more) disjoint path network flow based formulations. Several sets of projected inequalities, in the space of the arc and precedence variables, and in the spirit of many inequalities presented in Gouveia and Pesneau (2006), are obtained by projecting these network flow based formulations. Computational results are given for the PCATSP and the ATSP to evaluate the quality of the new inequalities.
Fichier principal
Vignette du fichier
combining-projecting-flow.pdf (304.6 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01655793 , version 1 (05-12-2017)

Identifiants

Citer

Luís Gouveia, Pierre Pesneau, Mario Ruthmair, Daniel Santos. Combining and projecting flow models for the (Precedence Constrained) Asymmetric Traveling Salesman Problem. Networks, 2017, 71 (4), pp.451-465. ⟨10.1002/net.21765⟩. ⟨hal-01655793⟩
113 Consultations
670 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More