On the Covering tour problem with resource consumption limitation

We address a variant of the well-known covering tour problem [1] in which the resource con- sumption is considered. The problem is characterized by a set of nodes N that can be visited and a set of nodes V that must be covered. The set N contains two particular nodes, i.e., 0 and its copy, namely n+ 1, representing the nodes at which the tour starts and ends, respectively. For each node i ∈N \{0,n+ 1}, it is possible to define a subset W(i) which contains all the nodes belonging to V that can be covered by visiting i. A resource consumption tu is associated with each node u∈N ∪V \{0,n+ 1}. A set of edges E= {(i,j) : i,j ∈N}is also defined. Each edge (i,j) ∈E is characterized by a distance dij and a resource consumption tij . The problem consists of 1) selecting the nodes i∈N to be visited; 2) deciding the order in which such nodes are visited; and 3) the nodes v ∈W(i) to be covered when node i∈N is visited such that the total traveled distance is minimized, all nodes belonging to V are covered, and the overall resource consumption is below a given threshold T. We analyze the impact of resource limitation on the optimal solution, exploiting the bi-objective nature of the problem. We also investigate the possibility of defining new optimality cuts derived from a Lagrangean relaxation based on the resource consumption lim- itation. An extensive computational phase is carried out on instances derived from benchmarks for the covering tour problem.