The indefinite period traveling salesman problem

Lei Sun, Mark H. Karwan and Moustapha Diaby

European Journal of Operational Research, 2018, vol. 270, issue 3, 1171-1181

Abstract: 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.

Keywords: Routing; Traveling salesman problem; Period TSP; Combinatorial optimization (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171830331X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:270:y:2018:i:3:p:1171-1181

DOI: 10.1016/j.ejor.2018.04.028

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().