Additive Bounds for the Double Traveling Salesman Problem with Multiple Stacks

The Double TSP with Multiple Stacks is a challenging combinatorial optimization problem, asking for two Hamiltonian cycles on two weighted graphs, a pick-up graph and a delivery graph; the two cycles originate from two given depots, one for each graph, and they visit the vertices in an order that allows a single vehicle to collect the pick-up items in a given number of stacks and to deliver them according to a Last-In-First-Out policy for each stack. We investigate the use of the additive bounding procedure, starting from the Held-Karp lower bound, within a branch-and-bound algorithm. Computational results show that this method often provides tighter bounds than the Double TSP relaxation.