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

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

0.00 Avg rating0 Votes
Article ID: iaor201524378
Volume: 22
Issue: 1
Start Page Number: 61
End Page Number: 75
Publication Date: Jan 2015
Journal: International Transactions in Operational Research
Authors: , ,
Keywords: programming: travelling salesman, programming: dynamic, heuristics: local search, programming: multiple criteria, networks, simulation, queues: applications
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.