A heuristic algorithm for the Resource Constrained Covering Tour Problem

The Resource Constrained Covering Tour Problem (RCCTP) [1] is a network optimization problem arising in wireless communications. It is defined on an undirected graph, where nodes represent sensors deployed within a geographic area, to monitor environmental parameters like air and noise pollution, traffic congestion, and others. Some nodes (ground nodes) are directly accessible by an unmanned vehicle (agent) that can physically recharge sensor batteries. By con- trast, other nodes (air nodes) are not directly accessible. In the latter case, battery recharging is performed via wireless power transmission technologies. Specifically, while the agent recharges the batteries of the ground nodes directly, it can also recharge the batteries of the air nodes lying within a predefined covering radius. Travelling between ground nodes and performing recharg- ing tasks consume limited resources. The RCCTP aims to find a minimum distance Hamiltonian tour visiting possibly a subset of ground nodes, while ensuring that all air nodes are covered and the resource consumed does not exceed a given threshold. We propose a heuristic decomposition scheme and discuss some preliminary computational results, carried out on instances adapted from standard benchmarks for the Covering Tour Problem.