Mixed integer programming formulations for the generalized traveling salesman problem with time windows

Yuan Yuan (), Diego Cattaruzza (), Maxime Ogier (), Cyriaque Rousselot () and Frédéric Semet ()
Additional contact information
Yuan Yuan: Univ. Lille
Diego Cattaruzza: Univ. Lille
Maxime Ogier: Univ. Lille
Cyriaque Rousselot: Univ. Lille
Frédéric Semet: Univ. Lille

4OR, 2021, vol. 19, issue 4, No 5, 592 pages

Abstract: Abstract 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 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, a single vertex is visited during its time window. In this paper, four mixed integer linear programming formulations for the GTSPTW are proposed and compared. They are based on different definitions of variables. All the formulations are compact, which means the number of decision variables and constraints is polynomial with respect to the size of the instance. Dominance relations between their linear relaxations are established theoretically. Computational experiments are conducted to compare the linear relaxations and branch-and-bound performances of the four formulations. The results show that two formulations are better than the other ones.

Keywords: Generalized traveling salesman problem; Time windows; Mixed integer programming formulations; Last mile delivery; 90-10 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-020-00461-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:19:y:2021:i:4:d:10.1007_s10288-020-00461-y

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-020-00461-y

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().