期刊
COMPUTERS & OPERATIONS RESEARCH
卷 39, 期 5, 页码 1074-1086出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2011.07.013
关键词
Traveling salesman problem; Handling cost; Pickup and delivery; Metaheuristics
类别
资金
- Canadian Natural Science and Engineering Research Council [39682-10]
- Ministero dell'Istruzione, dell'Universita e della Ricerca, Italy
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. (C) 2011 Published by Elsevier Ltd.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据