The anchored network covering problem (Q2708103)

The authors introduce the Anchored Network Covering Problem (ANCP). A special case of this problem can be described as follows. Given a graph \(G=(V,E)\) having a source and a sink, there is a cost \(c_{ij}\) for each arc \(ij \in E\) and a profit \(a_j\) for each node \(j \in V\). The problem is to find a path from the source to the sink taking into account two criteria: minimizing the sum of the costs of the arcs in the path and maximizing the sum of the profits of the nodes visited by the path. The authors give two integer programming formulations for ANCP and compare them. They also discuss relations with other problems. No computational results are given.