Clustered coverage orienteering problem of unmanned surface vehicles for water sampling

Wei Zhang, Kai Wang, Shuaian Wang, Gilbert Laporte

Research output: Journal article publicationJournal articleAcademic researchpeer-review

22 Citations (Scopus)


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 languageEnglish
Pages (from-to)353-367
Number of pages15
JournalNaval Research Logistics
Issue number5
Publication statusPublished - Aug 2020


  • 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


Dive into the research topics of 'Clustered coverage orienteering problem of unmanned surface vehicles for water sampling'. Together they form a unique fingerprint.

Cite this