Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem

Abstract : In this paper we present a new formulation for the Time-Dependent Travelling Salesman Problem (TDTSP). We start by reviewing well known natural formulations with some emphasis on the formulation by Picard and Queyranne (1978). The main feature of this formulation is that it uses, as a subproblem, an exact description of the n-circuit problem. Then, we present a new formulation that uses more variables and is based on using, for each node, a stronger subproblem, namely a n-circuit subproblem with the additional constraint that the corresponding node is not repeated in the circuit. Although the new model has more variables and constraints than the original PQ model, the results given from our computational experiments show that the linear programming relaxation of the new model gives, for many of the instances tested, gaps that are close to zero. Thus, the new model is worth investigating for solving TDTSP instances. We have also provided a complete characterization of the feasible set of the corresponding linear programming relaxation in the space of the variables of the PQ model. This characterization permits us to suggest alternative methods of using the proposed formulations.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2014, Combinatorial Optimization, 164, pp.138-153. 〈10.1016/j.dam.2011.11.019〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00648451
Contributeur : Pierre Pesneau <>
Soumis le : mardi 5 décembre 2017 - 11:16:26
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Fichier

NEFTDTSP_Revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Maria Teresa Godinho, Luis Gouveia, Pierre Pesneau. Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem. Discrete Applied Mathematics, Elsevier, 2014, Combinatorial Optimization, 164, pp.138-153. 〈10.1016/j.dam.2011.11.019〉. 〈hal-00648451〉

Partager

Métriques

Consultations de la notice

510

Téléchargements de fichiers

38