Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs

Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs

0.00 Avg rating0 Votes
Article ID: iaor20118771
Volume: 39
Issue: 5
Start Page Number: 1074
End Page Number: 1086
Publication Date: May 2012
Journal: Computers and Operations Research
Authors: , , ,
Keywords: combinatorial optimization, programming: dynamic, heuristics: tabu search
Abstract:

This paper studies the Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs. The subproblem of minimizing the handling cost for a fixed route is analyzed in detail. It is solved by means of an exact dynamic programming algorithm with quadratic complexity and by an approximate linear time algorithm. Three metaheuristics integrating these solution methods are developed. These are based on tabu search, iterated local search and iterated tabu search. The three heuristics are tested and compared on instances adapted from the related literature. The results show that the combination of tabu search and exact dynamic programming performs the best, but using the approximate linear time algorithm considerably decreases the CPU time at the cost of slightly worse solutions.

Reviews

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