Solving the asymmetric travelling salesman problem with time windows by branch-and-cut (Q5943078)

Motivated by an application concerning the control of a stacker crane in a warehouse the paper presents a computational study of asymmetric TSPs with time windows. Let a directed graph be given. For every node \(i\) a processing time \(p_i\), a release date and a due date is given. Moreover, an arc duration \(c_{ij}\) is associated with every arc \((i,j)\). The problem is to find a sequence of nodes with minimum total duration, starting and ending in a specified depot node, where each node has to be processed within its time window. It is allowed that the travelling person arrives at a node and waits until it is released. Moreover, it is assumed that the amounts \(\vartheta_{ij}:=p_i + c_{ij}\) fulfill a triangle inequality. The authors wrote branch \& cut codes for three models, namely a model with binary arc and node variables, a model involving only binary arc variables (Model 2) and a model involving binary as well as integer arc variables. Model 2 is based on modelling time windows by infeasible path constraints [see \textit{N. Ascheuer, M. Fischetti} and \textit{M. Grötschel}, Networks 36, 69--79 (2000; Zbl 0972.90085)]. The computational experiments showed clearly that for the actual application Model 2 was suited best. The following classes of cutting planes were used in the implementation of the branch and cut algorithm for model 2: infeasible path elimination constraints, TSP inequalities, cutting planes arising from the sequential ordering problem and inequalities which generalize Balas' cutting planes for the precedence constrained ATSP. During the preprocessing steps the time windows were tightened, the due dates adjusted, precedences were constructed and certain arcs were eliminated. Moreover, an extensive use of various construction and improvement heuristics was made within the code. The reported computational results on data from the underlying control problem of a stacker crane show that the ATSP with time windows with up to 70-90 nodes can be solved optimally in this way.