A parallel variable neighborhood search for solving covering salesman problem
- PDF / 1,301,542 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 237 Views
A parallel variable neighborhood search for solving covering salesman problem Xiaoning Zang1 · Li Jiang2,3
· Mustapha Ratli4 · Bin Ding1
Received: 15 April 2020 / Accepted: 1 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Covering salesman problem (CSP) is to construct a minimum length Hamiltonian cycle over a subset of vertices, in which the vertices not visited on the cycle must be covered by at least one visited vertex. In this paper, the CSP is reformulated as a bilevel CSP (BCSP) with a leader and a follower sub-problem. Two parallel variable neighborhood search (PVNS) heuristics, namely, synchronous “master–slave” PVNS and asynchronous cooperative PVNS, are proposed to solve the BCSP. To test the proposed algorithms, extensive computational experiments on the benchmark instances are performed, and the results indicate the effectiveness of the proposed approaches. Keywords Covering salesman problem · Parallel variable neighborhood search · Bilevel programming
1 Introduction The Covering salesman problem (CSP) is a generalization of the traveling salesman problem (TSP), which has many applications in healthcare teams and logistics design problems. The problem can be defined as follows: Undirected graph is expressed as G (V , E), where V {v1 , v2 , . . . , vn } is the vertex set, and E {< vi , v j > |vi , v j ∈ V } is the edge set. Each vertex vi ∈ V must be visited or covered by the
B
Li Jiang jiangli@hfut.edu.cn
1
School of Management, University of Science and Technology of China, Hefei 230026, Anhui, People’s Republic of China
2
School of Management, Hefei University of Technology, Hefei 230009, Anhui, People’s Republic of China
3
Key Laboratory of Process Optimization and Intelligent Decision-Making, Ministry of Education, Hefei 230009, Anhui, People’s Republic of China
4
Université Polytechnique Hauts-De-France (UPHF)/LAMIH CNRS UMR 8201, Valenciennes Cedex 9, France
123
X. Zang et al.
tour, and an associated cost ci j is assigned for each edge < vi , v j >∈ E. The aim is to find a minimum length Hamiltonian cycle over a subset of vertices, in which the vertices not visited on the tour must be covered by at least one visited vertex. Current and Schilling [1] introduced CSP and proposed a two-phase heuristic called COVTOUR to solve the problem. In the first phase of the COVTOUR, a set covering problem (SCP) was solved to search for feasible solutions using a minimum number of vertices. In the second phase, a TSP was solved to determine a minimum length Hamiltonian cycle based on the feasible solutions found by the SCP. Golden et al. [2] defined the generalized CSP (GCSP) and proposed two local search algorithms (e.g., LS1 and LS2) to solve the problems. LS1 and LS2 exhibited good performance in solving GCSP and CSP by using improvement procedures to develop the current solution and by utilizing the perturbation procedure to escape the local optimum, respectively. LS1 referred to a large-scale neighborhood search algorithm, and LS2 was like to an
