Finding Disjoint Routes in Telecommunications Networks with Two Technologies

We consider networks in which a cost is associated with each arc or edge and a transition cost is associated with each node. This last cost is related to the presence of two technologies on the network and is incurred only when a flow enters and leaves the corresponding node on arcs of different types. The problem we consider consists in finding two node disjoint paths with minimum total cost. We show that it is strongly NP-complete. Then we propose two heuristics, study their worst case behavior, provide a lower bounding procedure based on Lagrangean relaxation, and finally embed those elements in a branch and bound procedure.