Program > By author > Barbato Michele

The Double TSP with Stack Constraints is a variant of the classical TSP where the traveling salesman must complete a pickup tour in a weighted graph G(P) and afterwards perform a delivery tour in another weighted graph G(D) having the same number of vertices. Both tours begin and end in a special node (i.e., the depot) of their respective graph. Each time a new item is picked up, the traveling salesman puts it on a stack, hence covering the other items already present in that stack. During the delivery tour, stacks must be unloaded by following a LIFO policy. A pair of Pickup and Delivery tours are compatible if there is a feasible loading configuration for the stacks. The goal is to minimize the sum of the cost of the pickup and delivery tours. The cost is defined as the sum of the weight associated to each arc. In this work we present a new MILP model for the case in which only 2 stacks are available and no capacity constraints are assumed on stacks. The model is based on two families of variables: the x(i,j), useful for describing the pickup and delivery tours, and the y(i,j), useful for capturing, in a given tour, the precedence relationship between nodes i and j. The variables y(i,j) allow to easily describe the compatibility of any pair of tours in G(P) and G(D). The advantages of this model is that it focuses only on the routing aspect of the problem without explicitly constructing a configuration of stacks. Both theoretical and computational results are presented. We analyze the polyhedral structure of this model, by introducing several new families of cuts which have been tested to be facets for small instances. Moreover, we prove that they are useful for solving the problem by implementing them in a Branch-and-Cut algorithm. In the Branch-and-Cut we also exploit cuts which have already been studied for the classical TSP and the Precedence Constrained TSP. Computational tests on the istance used in the literature give good results, comparing with the best known in literature.