A branch-and-cut algorithm for the generalized traveling salesman problem with time windows - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue European Journal of Operational Research Année : 2020

A branch-and-cut algorithm for the generalized traveling salesman problem with time windows

Résumé

The generalized traveling salesman problem with time windows (GTSPTW) is defined on a directed graph where the vertex set is partitioned into clusters. One cluster contains only the depot. Each vertex is associated with a time interval, the time window, during which the visit must take place if the vertex is visited. The objective is to find a minimum cost tour starting and ending at the depot such that each cluster is visited exactly once and time constraints are respected, i.e., for each cluster, one vertex is visited during its time window. In this paper, two integer linear programming formulations for GTSPTW are provided as well as several problem-specific valid inequalities. A branch-and-cut algorithm is developed in which the inequalities are separated dynamically. To reduce the computation times, an initial upper bound is provided by a simple and fast heuristic. We propose different sets of instances characterized by their time window structures. Experimental results show that our algorithm is effective and instances including up to 30 clusters can be solved to optimality within one hour.
Fichier principal
Vignette du fichier
Paper_GTSPTW.pdf (403.36 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02947070 , version 1 (23-09-2020)

Identifiants

Citer

Yuan Yuan, Diego Cattaruzza, Maxime Ogier, Frédéric Semet. A branch-and-cut algorithm for the generalized traveling salesman problem with time windows. European Journal of Operational Research, 2020, 286 (3), ⟨10.1016/j.ejor.2020.04.024⟩. ⟨hal-02947070⟩
103 Consultations
1003 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More