A branch-and-cut algorithm for the generalized ...
Document type :
Compte-rendu et recension critique d'ouvrage
Title :
A branch-and-cut algorithm for the generalized traveling salesman problem with time windows
Author(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]
Journal title :
European Journal of Operational Research
Publisher :
Elsevier
Publication date :
2020-11-01
ISSN :
0377-2217
English keyword(s) :
generalized traveling salesman problem
time-windows
branch-and-cut
trunk delivery
time-windows
branch-and-cut
trunk delivery
HAL domain(s) :
Informatique [cs]
Informatique [cs]/Recherche opérationnelle [cs.RO]
Informatique [cs]/Recherche opérationnelle [cs.RO]
English abstract : [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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- https://hal.archives-ouvertes.fr/hal-02947070/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-01941090/file/Yuan_ROADEF2018.pdf
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-02947070/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-01941090/file/Yuan_ROADEF2018.pdf
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-02947070/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-01941090/file/Yuan_ROADEF2018.pdf
- Open access
- Access the document
- document
- Open access
- Access the document
- Paper_GTSPTW.pdf
- Open access
- Access the document
- Yuan_ROADEF2018.pdf
- Open access
- Access the document