Yuan Yuan
email: yuan.yuan@inria.fr

Diego Cattaruzza

Maxime Ogier

Frédéric Semet

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

Keywords: generalized traveling salesman problem, time windows, branch-and-cut

Problem description

The generalized traveling salesman problem with time windows (GTSPTW) can be defined as follows. Let G = (V, A) be a directed graph, where the set of vertices V = {0, 1, ..., N } is partitioned to C 0 = {0}, C 1 , ..., C K clusters. K = {0, 1, ..., K} denotes the cluster index set. Cluster C 0 contains only the depot. Arcs are only defined between vertices belonging to different clusters, that is,

A = {(i, j) : i ∈ C k , j ∈ C l , k = l}. Each arc (i, j) ∈ A is associated with a traveling cost C ij and time T ij . Each vertex is associated with a time window (TW) [E i , L i ] with [E 0 , L 0 ] = [0, T ].
A visit can only be made to a vertex during its TW. The objective of the GTSPTW 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. Three variables are introduced: binaries y i and x ij represent if vertex i and arc (i, j) are chosen or not in the tour; real variable t i is the arrival time at vertex i. The GTSPTW can be modeled as follows. min

(i,j)∈A C ij x ij (1) s.t. i∈C k y i = 1 k ∈ {0, 1, ..., K}, (2)
(i,j)∈δ + (i)

x ij = (j,i)∈δ -(i) x ji = y i ∀i ∈ V, (3)
E i y i ≤ t i ≤ L i y i ∀i ∈ V, (4) t i -t j + T ij x ij ≤ L i y i -E j y j -(L i -E j )x ij ∀(i, j) ∈ A, j = 0, ( 5
) t i + T i0 x i0 ≤ L 0 ∀i ∈ V \ {0}, (6) y i ∈ {0, 1} ∀i ∈ V, (7) x ij ∈ {0, 1} ∀(i, j) ∈ A. (8)
The objective function (1) minimizes the overall costs. Constraints (2) ensure that exactly one vertex from each cluster is visited. Constraints (3) are flow conservation constraints. Constraints (4) ensure that a vertex is visited during its TW. Constraints (5) ensure that the arrival and traveling time are consistent, meanwhile eliminating subtours. Constraints (7) and ( 8) are variable definitions.

The GTSPTW reduces to the well-known Generalized Traveling Salesman Problem [START_REF] Fischetti | A branch-and-cut algorithm for the symmetric generalized traveling salesman problem[END_REF] when TWs are not considered. For the multi-vehicle case, the problem is named Generalized Vehicle Routing Problem with TWs [START_REF] Luigi | An incremental tabu search heuristic for the generalized vehicle routing problem with time windows[END_REF].

• Arc orientation inequality.

x ij + x ji ≤ y i i, j ∈ V, i = j.
In any feasible solution either (i, j) or (j, i) is used, but not both.

• Arc-or-vertex inequality.

x ij + h∈C ij k y h ≤ 1 i, j ∈ V, i = j, k ∈ K \ {0},
where

C ij k = {h ∈ C k |E h + SP hi + T ij > L j or E h + SP hi > L i , E i + T ij + SP jh > L h or E j + SP jh > L h }.
SP ij represents the shortest traveling time from vertex i to vertex j. When the triangle inequality is not satisfied, the shortest path to go from i to j can include the visit of other vertices. These constraints detect if a vertex and an arc can not be simultaneously selected in a feasible solution due to TWs.

Exponential families of valid inequalities for the GTSPTW

• Generalized subtour elimination inequality (GSEC).

(i,j)∈δ + (S) x ij ≥ 1 ∀S = ∪ h∈H C h , H ⊂ K, 2 ≤ |H| ≤ K -1.
GSEC avoids tours visiting a subset of clusters.

• Clique inequality. i∈S y i ≤ |S| -1, S ⊂ V.
If no feasible path passing through all the vertices of set S ⊂ V exists (due to TWs), then the vertices of S that can be visited in any feasible solution are less than its size .

A branch-and-cut scheme

We develop a branch-and-cut algorithm for the GTSPTW. We include at the root node of the branch and bound tree all the inequalities defined in Section 2.1. On the other side, due to their exponential cardinality, we separate the GSEC inequalities using a classical approach based on the resolution of a max-flow problem using Gomory-Hu algorithm. Clique inequalities on subsets S of V with cardinality up to 3 are directly introduced at the root node of the branch and bound tree. In addition, clique inequalities on subsets S of V with cardinality of 4 are dynamically added whenever a fractional solution violates one of them.

Please note that GSECs and clique inequality are satisfied for any feasible integer solution of the GTSPTW and they are not problem defining. However, they are helpful to improve the linear relaxation lower bound during the branch and bound algorithm.

Conclusions and perspectives

The branch-and-cut algorithm is tested on the instances we propose for the GTSPTW created from instances for the GTSP. Instances with up to 16 clusters with 76 nodes can be solved to optimality. Undergoing work is on the development of heuristic algorithms to obtain initial feasible solutions. Meanwhile new families of cuts based on infeasibility detection are under development.


Yuan Yuan

Diego Cattaruzza

Maxime Ogier

Frédéric Semet

A branch-and-cut algorithm for the generalized

come   L'archive ouverte pluridisciplinaire

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

Yuan Yuan, Diego Cattaruzza, Maxime Ogier, Frédéric Semet

Univ. Lille, CNRS, Centrale Lille, Inria, UMR 9189 -CRIStAL, F-59000 Lille, France yuan.yuan@inria.fr Keywords : generalized traveling salesman problem, time windows, branch-and-cut.

The generalized traveling salesman problem with time windows (GTSPTW) can be defined as follows. Given a directed graph, the vertex set is partitioned into clusters with one cluster including only the depot. Arcs are only defined between vertices belonging to different clusters. Each vertex is associated with a time window (TW) and each arc has a traveling cost and a traveling time. The objective of the GTSPTW 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. It reduces to the well-known Generalized Traveling Salesman Problem when TWs are not considered.

Several valid inequalities are proposed for the GTSPTW, dividing into two types, i.e., polynomial families and exponential families. Polynomial families : (1) Arc orientation inequalities. An arc can only be oriented in one way, it either enters or leaves a vertex. This family of inequalities can be generalized considering clusters instead of vertices. (2) Arc-or-vertex inequalities. If a vertex cannot be visited either before or after an arc due to TWs, then only one of them can be chosen in any feasible solution. Exponential families : (1) Generalized subtour elimination constraints (GSEC). (2) Sequential ordering polytope constraints (SOP). SOP inequalities are based on the precedence relationships between pairs of vertices which are inferred by TWs. (3) Clique inequalities. If there is no feasible path passing through all the vertices in a certain set, then the number of vertices in this set that can be visited in all feasible solutions is strictly less than the size of the set.

We develop a branch-and-cut algorithm for the GTSPTW. Here we describe some important procedures included in this algorithm : (1) Preprocessing. The size of the problem can be reduced by eliminating arcs and vertices that cannot be a part of any feasible solution. ( 2) Initial heuristic to calculate upper bound. Given a fixed cluster sequence, a feasible solution can be obtained by solving a shortest path problem with TWs. (3) Separation algorithms to tighten lower bound. Heuristic separation for SOP inequalities and exact separation for GSEC inequalities are developed to iteratively improve the lower bound. Besides, other valid inequalities are stored in a cut pool and they are taken into account only when violation is found. (4) Branching priorities. To enhance the perfermance of the branch-and-cut algorithm, we branch on priority on variables that fix the visiting sequence of the clusters.

The algorithm is implemented in C++ using CPLEX 12.6 and Concert framework. For testing our algorithm, we propose new instances for the GTSPTW derived from GTSP instances. Results show that the proposed valid inequalities are effective to improve the lower bound. Instances with up to 24 clusters and 120 vertices can be solved to optimality within one hour.