Two multi-start heuristics for the k -traveling salesman problem
- PDF / 1,860,071 Bytes
- 41 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 190 Views
Two multi‑start heuristics for the k‑traveling salesman problem Venkatesh Pandiri1 · Alok Singh1 Accepted: 4 June 2020 © Operational Research Society of India 2020
Abstract This paper is concerned with the k-traveling salesman problem (k-TSP), which is a variation of widely studied traveling salesman problem (TSP). Given a set of n cities including a home city and a fixed value k such that 1 < k ≤ n , this problem seeks a tour of minimum length which starts and ends at the home city and visits k cities (including the home city) exactly out of these n cities. Finding a feasible solution to k-TSP involves finding a subset of k cities including the home city first, and then a circular permutation representing a tour of these k cities. In this paper, we have proposed two multi-start heuristic approaches for the k-TSP. The first approach is based on general variable neighborhood search algorithm (GVNS), whereas the latter approach is a hyper-heuristic (HH) approach. A variable neighborhood descent strategy operating over two neighborhood structures is utilized for doing the local search in the GVNS. As part of the hyper-heuristic, two low level heuristics are considered. To the best of our knowledge, these are the first metaheuristic and hyperheuristic approaches for the k-TSP. To evaluate the performance of our approaches, a set of benchmark instances is created utilizing instances from TSPLIB. Computational results on these benchmark instances show HH approach to be better than GVNS approach. Keywords k-traveling salesman problem · Traveling salesman problem · General variable neighborhood search · Hyper-heuristic · Heuristic
* Alok Singh [email protected] Venkatesh Pandiri [email protected] 1
School of Computer and Information Sciences, University of Hyderabad, Hyderabad, Telangana 500 046, India
13
Vol.:(0123456789)
OPSEARCH
1 Introduction The k-traveling salesman problem (k-TSP) is a variation of the well known traveling salesman problem (TSP). Given a set of n cities including a home city and a fixed value 1 < k ≤ n , the k-TSP consists in finding a subset of k cities including the home city and a tour visiting each city of this subset exactly once so that this tour has minimum length among all such tours over any subset of k cities that includes the home city. The TSP can be considered as a special case of kTSP with k = n . On the other hand, k-TSP in itself can be considered as a special case of prize collecting traveling salesman problem (PCTSP) [1] where each city is associated with a prize and a penalty. The salesman collects the prize associated with a city in case he visits that city, and incurs the penalty associated with a city in case he do not visit that city. The goal of the PCTSP is to minimize the sumtotal of distance traveled by the salesman and total penalties incurred while collecting a specified minimum aggregate of prize. The quota traveling salesman problem (QTSP) is a special case of the PCTSP, where there is no penalty for not visiting a city, i.e., penalties for all ci
Data Loading...
