Premium
A dynamic programming based local search approach for the double traveling salesman problem with multiple stacks
Author(s) -
Urrutia Sebastián,
Milanés Anolan,
Løkketangen Arne
Publication year - 2015
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12053
Subject(s) - travelling salesman problem , heuristics , mathematical optimization , traveling purchaser problem , computer science , 2 opt , container (type theory) , pickup , set (abstract data type) , heuristic , disjoint sets , bottleneck traveling salesman problem , local search (optimization) , plan (archaeology) , dynamic programming , integer programming , fifo and lifo accounting , packing problems , mathematics , engineering , artificial intelligence , fifo (computing and electronics) , mechanical engineering , archaeology , combinatorics , computer hardware , image (mathematics) , history , programming language
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.