A heuristic procedure for path location with multisource demand

In this paper, we present a lower bound for a path location problem with multisource demand based upon the Lagrangian relaxation of a binary integer formulation. Feasible solutions are obtained from the optima of the relaxed subproblems, the best being the heuristic solution. The correctness of the method is only guaranteed when the underlying graph is acyclic. Nevertheless, when the approach is tested by means of a computational study, near-optimum solutions for instances based on acyclic graphs with up to 200 nodes and 700 arcs and cyclic graphs with up to 100 nodes and 780 arcs are found in a few seconds.