Finding disjoint routes in telecommunications networks with two technologies
成果类型：
Article
署名作者：
De Jongh, A; Gendreau, M; Labbé, M
署名单位：
Universite Libre de Bruxelles; Universite de Montreal
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.47.1.81
发表日期：
1999
页码：
81-92
关键词：
摘要：
We consider networks in which a cost is associated with each are 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 Lagrangan relaxation, and finally embed those elements in a branch and bound procedure.