Clustered coverage orienteering problem of unmanned surface vehicles for water sampling
Wei Zhang,
Kai Wang,
Shuaian Wang and
Gilbert Laporte
Naval Research Logistics (NRL), 2020, vol. 67, issue 5, 353-367
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.
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)
Downloads: (external link)
https://doi.org/10.1002/nav.21906
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:67:y:2020:i:5:p:353-367
Access Statistics for this article
More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().