Clustered coverage orienteering problem of unmanned surface vehicles for water sampling

Wei Zhang; Kai Wang; Shuaian Wang; Gilbert Laporte

doi:10.1002/nav.21906

Clustered coverage orienteering problem of unmanned surface vehicles for water sampling

Wei Zhang, Kai Wang, Shuaian Wang, Gilbert Laporte

Research output: Contribution to journal › Article › peer-review

22 Citations (SciVal)

87 Downloads (Pure)

Abstract

This study investigates a clustered coverage orienteering problem (CCOP), which is a generalization of the classical orienteering problem. The problem is widely motivated by the emerging unmanned techniques (eg, unmanned surface vehicles and drones) applied to environmental monitoring. Specifically, the unmanned surface vehicles (USVs) are used to monitor reservoir water quality by collecting samples. In the CCOP, the water sampling sites (ie, the nodes) are grouped into clusters, and a minimum number of nodes must be visited in each cluster. With each node representing a certain coverage area of the water, the objective of the CCOP is to monitor as much as possible the total coverage area in one tour of the USV, considering that overlapping areas provide no additional information. An integer programming model is first formulated through a linearization procedure that captures the overlapping feature. A two-stage exact algorithm is proposed to obtain an optimal solution to the problem. The efficiency and effectiveness of the two-stage exact algorithm are demonstrated through experiments on randomly generated instances. The algorithm can effectively solve instances with up to 60 sampling sites.

Original language	English
Pages (from-to)	353-367
Number of pages	15
Journal	Naval Research Logistics
Volume	67
Issue number	5
DOIs	https://doi.org/10.1002/nav.21906
Publication status	Published - 1 Aug 2020

Bibliographical note

Funding Information:
Canadian Natural Sciences and Engineering Research Council, 2015‐06189; National Key R&D Program of China, 2018YFE0102700; National Natural Science Foundation of China, 71701178; 71831008 Funding information

Funding Information:
This study is supported by the National Key R&D Program of China (Project No. 2018YFE0102700), the National Natural Science Foundation of China (grant numbers 71701178 and 71831008). G. L. was supported by the Canadian Natural Sciences and Engineering Research Council (grant number 2015‐06189). The authors would like to thank the Editor‐in‐Chief, the Associate Editor, and the anonymous referees for their constructive comments and suggestions.

Publisher Copyright:
© 2020 Wiley Periodicals, Inc.

Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

Keywords

clustered coverage orienteering problem
exact algorithm
unmanned surface vehicle
water sampling

ASJC Scopus subject areas

Modelling and Simulation
Ocean Engineering
Management Science and Operations Research

Access to Document

10.1002/nav.21906

Clustered coverage orienteering problem(1)
This is the peer reviewed version of the following article: Zhang, W, Wang, K, Wang, S, Laporte, G. Clustered coverage orienteering problem of unmanned surface vehicles for water sampling. Naval Research Logistics. 2020; 67: 353– 367, which has been published in final form at https://doi.org/10.1002/nav.21906 . This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving.
Accepted author manuscript, 2.72 MB

Cite this

@article{4c725fc2d7644380a32fa2163d318bd1,

title = "Clustered coverage orienteering problem of unmanned surface vehicles for water sampling",

abstract = "This study investigates a clustered coverage orienteering problem (CCOP), which is a generalization of the classical orienteering problem. The problem is widely motivated by the emerging unmanned techniques (eg, unmanned surface vehicles and drones) applied to environmental monitoring. Specifically, the unmanned surface vehicles (USVs) are used to monitor reservoir water quality by collecting samples. In the CCOP, the water sampling sites (ie, the nodes) are grouped into clusters, and a minimum number of nodes must be visited in each cluster. With each node representing a certain coverage area of the water, the objective of the CCOP is to monitor as much as possible the total coverage area in one tour of the USV, considering that overlapping areas provide no additional information. An integer programming model is first formulated through a linearization procedure that captures the overlapping feature. A two-stage exact algorithm is proposed to obtain an optimal solution to the problem. The efficiency and effectiveness of the two-stage exact algorithm are demonstrated through experiments on randomly generated instances. The algorithm can effectively solve instances with up to 60 sampling sites.",

keywords = "clustered coverage orienteering problem, exact algorithm, unmanned surface vehicle, water sampling",

author = "Wei Zhang and Kai Wang and Shuaian Wang and Gilbert Laporte",

note = "Funding Information: Canadian Natural Sciences and Engineering Research Council, 2015‐06189; National Key R&D Program of China, 2018YFE0102700; National Natural Science Foundation of China, 71701178; 71831008 Funding information Funding Information: This study is supported by the National Key R&D Program of China (Project No. 2018YFE0102700), the National Natural Science Foundation of China (grant numbers 71701178 and 71831008). G. L. was supported by the Canadian Natural Sciences and Engineering Research Council (grant number 2015‐06189). The authors would like to thank the Editor‐in‐Chief, the Associate Editor, and the anonymous referees for their constructive comments and suggestions. Publisher Copyright: {\textcopyright} 2020 Wiley Periodicals, Inc. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

year = "2020",

month = aug,

day = "1",

doi = "10.1002/nav.21906",

language = "English",

volume = "67",

pages = "353--367",

journal = "Naval Research Logistics",

issn = "0894-069X",

publisher = "John Wiley and Sons Inc.",

number = "5",

}

TY - JOUR

T1 - Clustered coverage orienteering problem of unmanned surface vehicles for water sampling

AU - Zhang, Wei

AU - Wang, Kai

AU - Wang, Shuaian

AU - Laporte, Gilbert

N1 - Funding Information: Canadian Natural Sciences and Engineering Research Council, 2015‐06189; National Key R&D Program of China, 2018YFE0102700; National Natural Science Foundation of China, 71701178; 71831008 Funding information Funding Information: This study is supported by the National Key R&D Program of China (Project No. 2018YFE0102700), the National Natural Science Foundation of China (grant numbers 71701178 and 71831008). G. L. was supported by the Canadian Natural Sciences and Engineering Research Council (grant number 2015‐06189). The authors would like to thank the Editor‐in‐Chief, the Associate Editor, and the anonymous referees for their constructive comments and suggestions. Publisher Copyright: © 2020 Wiley Periodicals, Inc. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/8/1

Y1 - 2020/8/1

N2 - This study investigates a clustered coverage orienteering problem (CCOP), which is a generalization of the classical orienteering problem. The problem is widely motivated by the emerging unmanned techniques (eg, unmanned surface vehicles and drones) applied to environmental monitoring. Specifically, the unmanned surface vehicles (USVs) are used to monitor reservoir water quality by collecting samples. In the CCOP, the water sampling sites (ie, the nodes) are grouped into clusters, and a minimum number of nodes must be visited in each cluster. With each node representing a certain coverage area of the water, the objective of the CCOP is to monitor as much as possible the total coverage area in one tour of the USV, considering that overlapping areas provide no additional information. An integer programming model is first formulated through a linearization procedure that captures the overlapping feature. A two-stage exact algorithm is proposed to obtain an optimal solution to the problem. The efficiency and effectiveness of the two-stage exact algorithm are demonstrated through experiments on randomly generated instances. The algorithm can effectively solve instances with up to 60 sampling sites.

AB - This study investigates a clustered coverage orienteering problem (CCOP), which is a generalization of the classical orienteering problem. The problem is widely motivated by the emerging unmanned techniques (eg, unmanned surface vehicles and drones) applied to environmental monitoring. Specifically, the unmanned surface vehicles (USVs) are used to monitor reservoir water quality by collecting samples. In the CCOP, the water sampling sites (ie, the nodes) are grouped into clusters, and a minimum number of nodes must be visited in each cluster. With each node representing a certain coverage area of the water, the objective of the CCOP is to monitor as much as possible the total coverage area in one tour of the USV, considering that overlapping areas provide no additional information. An integer programming model is first formulated through a linearization procedure that captures the overlapping feature. A two-stage exact algorithm is proposed to obtain an optimal solution to the problem. The efficiency and effectiveness of the two-stage exact algorithm are demonstrated through experiments on randomly generated instances. The algorithm can effectively solve instances with up to 60 sampling sites.

KW - clustered coverage orienteering problem

KW - exact algorithm

KW - unmanned surface vehicle

KW - water sampling

UR - http://www.scopus.com/inward/record.url?scp=85084990876&partnerID=8YFLogxK

U2 - 10.1002/nav.21906

DO - 10.1002/nav.21906

M3 - Article

AN - SCOPUS:85084990876

SN - 0894-069X

VL - 67

SP - 353

EP - 367

JO - Naval Research Logistics

JF - Naval Research Logistics

IS - 5

ER -

Clustered coverage orienteering problem of unmanned surface vehicles for water sampling

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this