A branch-and-cut algorithm for the generalized ...
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
A branch-and-cut algorithm for the generalized traveling salesman problem with time windows
Auteur(s) :
Yuan, Yuan [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Cattaruzza, Diego [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Ogier, Maxime [Auteur]
Integrated Optimization with Complex Structure [INOCS]
SEMET, Frédéric [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Integrated Optimization with Complex Structure [INOCS]
Cattaruzza, Diego [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Ogier, Maxime [Auteur]
Integrated Optimization with Complex Structure [INOCS]
SEMET, Frédéric [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Titre de la revue :
European Journal of Operational Research
Éditeur :
Elsevier
Date de publication :
2020-11-01
ISSN :
0377-2217
Mot(s)-clé(s) en anglais :
generalized traveling salesman problem
time-windows
branch-and-cut
trunk delivery
time-windows
branch-and-cut
trunk delivery
Discipline(s) HAL :
Informatique [cs]
Informatique [cs]/Recherche opérationnelle [cs.RO]
Informatique [cs]/Recherche opérationnelle [cs.RO]
Résumé en anglais : [en]
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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-02947070/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01941090/file/Yuan_ROADEF2018.pdf
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02947070/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01941090/file/Yuan_ROADEF2018.pdf
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02947070/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01941090/file/Yuan_ROADEF2018.pdf
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- Paper_GTSPTW.pdf
- Accès libre
- Accéder au document
- Yuan_ROADEF2018.pdf
- Accès libre
- Accéder au document