A dynamic programming based local search approach for the double traveling salesman problem with multiple stacks

The double traveling salesman problem with multiple stacks consists in determining a pair of routes (pickup and delivery) for a unique vehicle in two different and disjoint networks. It models a realistic transportation problem with loading/unloading constraints imposed by having a set of last-in-first-out (LIFO) stacks used for storing the goods being transported. The arrangement of the items in the container determines the loading plan that in terms constrains both routes. In this paper, we propose a novel local search approach. The local search heuristic is applied to the loading plan instead of working directly on the routes. A dynamic programming algorithm is used to map the loading plan solution into corresponding optimal routes. Computational results show that the proposed approach is competitive with state-of-the-art heuristics for the problem.