Article ID: | iaor2001756 |
Country: | United States |
Volume: | 47 |
Issue: | 1 |
Start Page Number: | 81 |
End Page Number: | 92 |
Publication Date: | Jan 1999 |
Journal: | Operations Research |
Authors: | Labb Martine, Gendreau Michel, Jongh Anne De |
Keywords: | networks |
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.