Finding disjoint routes in telecommunications networks with two technologies

Finding disjoint routes in telecommunications networks with two technologies

0.00 Avg rating0 Votes
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: , ,
Keywords: networks
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.