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

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

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

Cite this