Parisa Torabi

Computers & Operations Research 183 Doi: https://doi.org/10.1016/j.cor.2025.107188

In offshore environmental monitoring projects, ocean currents enable the detection of chemical signals from a distance, with longer observation times at each point increasing the area that can be monitored. Leveraging this principle, the covering tour problem with varying coverage was recently introduced for environmental monitoring. In this paper, we introduce a generalization of this problem, where we utilize a main vessel and a fleet of autonomous underwater vehicles (AUVs), and the properties of time-varying coverage, which refers to the dynamic changes in the area that can be monitored based on the duration spent at each location, to minimize the required time to visit or cover a set of pre-specified locations in an area of interest. This problem can be presented as a rich covering salesperson problem, namely the multi-visit multi-drone covering salesperson problem with varying coverage (mCSP-VC). We present a mixed integer linear programming (MILP) model of mCSP-VC, and considering the complexity of the problem, design and implement an adaptive matheuristic algorithm and showcase its effectiveness. Moreover, we investigate the effects of altering different parameters on the solutions and provide managerial insights into optimizing monitoring operations and resource allocation.

Computers & Operations Research 174 Doi: https://doi.org/10.1016/j.cor.2024.106881

Covering Tour Problem (CTP) is a combinatorial optimization problem in which the objective is to identify a minimum-cost tour that satisfies the coverage of a certain subset of nodes in a graph. The Covering Tour Problem with Varying Coverage (CTP-VC) is an extension of this problem in which the coverage radius is dependent on the amount of time spent at each node. In this paper, we propose a novel approach to address the CTP-VC using a Deep Reinforcement Learning Hyperheuristic (DRLH). This study includes experiments on the existing Adaptive Metaheuristic to solve CTP-VC, to enhance its solution quality. Further, new heuristics and three selection methods, namely Uniform Random Selection (URS), adaptive Metaheuristic (AMH), and the proposed DRLH are introduced. We detail the computational setup, including the instance sets utilized, the training process for the DRLH agent, and the validation procedures for model selection. Through extensive experimentation and analysis, we evaluate the performance of different selection methods, assess the solution quality of the DRLH approach, investigate the robustness of selection methods, examine heuristic selection frequency, and analyze solution convergence. Our results demonstrate the efficacy of the DRLH approach in tackling the CTP-VC, offering promising insights for future research in the interface of combinatorial optimization and reinforcement learning methodologies.

Applied Mathematical Modelling 124 p. 279-299 Doi: https://doi.org/10.1016/j.apm.2023.07.024

In this paper, we present a novel variant of the Covering Tour Problem (CTP), called the Covering Tour Problem with Varying Coverage (CTP-VC). We consider a simple graph 𝐺 = (𝑉 ,𝐸), with a measure of importance assigned to each node in 𝑉 . A vehicle with limited battery capacity visits the nodes of the graph and has the ability to stay in each node for a certain period of time, which determines the coverage radius at the node. We refer to this feature as stay-dependent varying coverage or, in short, varying coverage. The objective is to maximize a scalarization of the weighted coverage of the nodes and the negation of the cost of moving and staying at the nodes. This problem arises in the monitoring of marine environments, where pollutants can be measured at locations far from the source due to ocean currents. To solve the CTP-VC, we propose a mathematical formulation and a heuristic approach, given that the problem is NP-hard. Depending on the availability of solutions yielded by an exact solver, we evaluate our heuristic approach against the exact solver or a constructive heuristic on various instance sets and show how varying coverage improves performance. Additionally, we use an offshore CO2 storage site in the Gulf of Mexico as a case study to demonstrate the problem’s applicability. Our results demonstrate that the proposed heuristic approach is an efficient and practical solution to the problem of stay-dependent varying coverage. We conduct numerous experiments and provide managerial insights.

ghgt online scientific paper