期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 270, 期 3, 页码 1171-1181出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2018.04.028
关键词
Routing; Traveling salesman problem; Period TSP; Combinatorial optimization
We propose an indefinite period traveling salesman problem (TSP), in which customer nodes need to be visited an unknown multiple or infinite number of times but cannot be visited more than once in the same trip. The optimal solution seeks a visiting strategy for the long run including the routing and planning horizon decisions. We show that an optimal solution may be a set of routes in which a given customer is grouped with a number of different subsets of customers rather than simply repeated TSP or multiple TSP optimal routes. The problem is proven to be NP-hard, and important properties are explored theoretically. We propose exact as well as heuristic procedures for solving this problem. Our computational experiments show that the proposed heuristic produces high quality solutions for problems with certain sizes, and that the proposed exact algorithm can be implemented within a practical time tolerance. The numerical results demonstrate the importance of this problem for cost reduction in practice and the concerns about scheduling solution tours have been discussed for practical implementation. (C) 2018 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据