  Vehicle-based mobile sensing is an emerging data collection paradigm that
leverages vehicle mobilities to scan a city at low costs. Certain urban sensing
scenarios require dedicated vehicles for highly targeted monitoring, such as
volatile organic compounds (VOCs, a type of air pollutant) sensing, road
surface monitoring, and accident site investigation. A hallmark of these
scenarios is that the points of interest (POIs) need to be repeatedly visited
by a set of agents, whose routes should provide sufficient sensing coverage
with coordinated overlap at certain important POIs. For these applications,
this paper presents the open team orienteering problem with repeatable visits
(OTOP-RV). The adaptive large neighborhood search (ALNS) algorithm is tailored
to solve the OTOP-RV considering specific features of the problem. Test results
on randomly generated datasets show that: (1) For small cases, the ALNS matches
Gurobi in terms of optimality but with shorter computational times; (2) For
large cases, the ALNS significantly outperforms the greedy algorithm (by 9.7%
to 25.4%), and a heuristic based on sequential orienteering problems (by 6%).
Finally, a real-world case study of VOCs sensing is presented, which highlights
the unique applicability of the OTOP-RV to such specific sensing tasks, as well
as the effectiveness of the proposed algorithms in optimizing the sensing
utilities.
