Two hybrid metaheuristic approaches for the covering salesman problem
- PDF / 957,779 Bytes
- 21 Pages / 595.276 x 790.866 pts Page_size
- 23 Downloads / 188 Views
(0123456789().,-volV)(0123456789(). ,- volV)
ORIGINAL ARTICLE
Two hybrid metaheuristic approaches for the covering salesman problem Venkatesh Pandiri1 • Alok Singh1
•
Andre´ Rossi2,3
Received: 3 October 2019 / Accepted: 26 March 2020 Ó Springer-Verlag London Ltd., part of Springer Nature 2020
Abstract This paper addresses the covering salesman problem (CSP), which is an extension of the classical traveling salesman problem (TSP). Given a set of cities and a coverage radius associated with each one of them, the CSP seeks a Hamiltonian cycle over a subset of cities such that each city not in the subset is within the coverage radius of at least one city in the subset and that has minimum length among all Hamiltonian cycles over such subsets. To solve this problem, one has to deal with the aspects of subset selection and permutation. The CSP finds application in emergency and disaster management and rural healthcare. This paper presents two hybrid metaheuristic approaches for the CSP. The first approach is based on the artificial bee colony algorithm, whereas the latter approach is based on the genetic algorithm. Both the approaches make use of several new first improvement or best improvement based local search strategies defined over various neighborhood structures. Computational results on a wide range of benchmark instances demonstrate the effectiveness of the proposed approaches. We are able to improve the best known solution values on majority of the large instances. Keywords Covering salesman problem Traveling salesman problem Heuristic Genetic algorithm Artificial bee colony algorithm
1 Introduction The traveling salesman problem (TSP) is regarded as one of the classical problems in the fields of combinatorial optimization and operations research owing to its wide applicability in diverse practical scenarios. The TSP seeks a minimum length Hamiltonian cycle over a given set of cities. In the TSP, every city needs to be visited exactly & Alok Singh [email protected] Venkatesh Pandiri [email protected] Andre´ Rossi [email protected]; [email protected] 1
School of Computer and Information Sciences, University of Hyderabad, Hyderabad 500 046, India
2
Universite´ Paris-Dauphine, PSL, LAMSADE UMR CNRS 7243, Place du Mare´chal de Lattre de Tassigny, 75775 Paris Cedex 16, France
3
Universite´ d’Angers, LERIA EA CNRS 2645, 49000 Angers, France
once. However, it may not be possible in some practical scenarios particularly when there are limitations on resources like fuel, manpower etc. Keeping in mind these scenarios, Current and Schilling [4] formulated the covering salesman problem (CSP) that can be considered as a variant of the TSP. Unlike TSP, all the cities need not be visited in CSP. However, every city has to be either visited or has to be within a pre-specified distance from at least one visited city in the tour. If a city is within a pre-specified distance from a visited city in the tour then it is is considered to be covered. Hence, in CSP, every city has to be
Data Loading...
