Skip to Main content Skip to Navigation
Journal articles

A parallel variable neighborhood search for solving covering salesman problem

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.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03400355
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 8:41:33 AM
Last modification on : Wednesday, November 3, 2021 - 5:22:06 AM

Identifiers

Collections

Citation

Xiaoning Zang, Li Jiang, Mustapha Ratli, Bin Ding. A parallel variable neighborhood search for solving covering salesman problem. Optimization Letters, Springer Verlag, 2020, ⟨10.1007/s11590-020-01642-8⟩. ⟨hal-03400355⟩

Share

Metrics

Record views

5