Mixed integer programming formulations for the generalized traveling salesman problem with time windows
- PDF / 570,660 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 104 Downloads / 229 Views
Mixed integer programming formulations for the generalized traveling salesman problem with time windows Yuan Yuan1 · Diego Cattaruzza1 · Maxime Ogier1 · Cyriaque Rousselot1 · Frédéric Semet1 Received: 8 May 2020 / Revised: 8 May 2020 / Accepted: 8 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
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
B
Yuan Yuan [email protected] Diego Cattaruzza [email protected] Maxime Ogier [email protected] Cyriaque Rousselot [email protected] Frédéric Semet [email protected]
1
CNRS, Centrale Lille, Inria, UMR 9189 - CRIStAL Lille, Univ. Lille, Lille, France
123
Y. Yuan et al.
Mathematics Subject Classification 90-10
1 Introduction The problem addressed in this paper is the generalized traveling salesman problem with time windows (GTSPTW), where clusters represent possible delivery locations associated with a customer. In this paper, we propose and compare four mixed integer programming (MIP) formulations for this problem, based on different definitions of variables. The GTSPTW can be formally defined as follows: given a directed graph G = (V, A), the set of vertices V = {0, 1, ..., N } is partitioned into C0 = {0}, C1 , ..., C K clusters. K = {0, 1, ..., K } denotes the cluster index set. Cluster C0 contains only the depot. Ck , k > 0, k ∈ K represents the set of alternative locations on which customer k can be delivered. Each vertex is associated with a TW [E i , L i ], i ∈ {0, 1, ..., N } with [E 0 , L 0 ] = [0, T ] representing the optimization time horizon. If a vertex is visited, the visit occurs during its TW. An early arrival leads to waiting time while a late arrival causes infeasibility. Arcs are only defined between vertices belonging to different clusters, that is, A = {
Data Loading...
