Lagrangean relaxation heuristics for thep-cable-trench problem

Abstract

We address thep-cable-trench problem. In this problem,pfacilities are located, a trench network is dugand cables are laid in the trenches, so that every customer – or demand – in the region is connected to afacility through a cable. The digging cost of the trenches, as well as the sum of the cable lengthsbetween the customers and their assigned facilities, are minimized. We formulate an integerprogramming model of the problem using multicommodity flows that allows finding the solution forinstances of up to 200 nodes. We also propose two Lagrangean Relaxation-based heuristics to solvelarger instances of the problem. Computational experience is provided for instances of up to 300 nodes.