To improve the reliability of the increasing network two disjoint paths should be found between a given source and a given destination. The problem of finding two minimum cost node-disjoint/edge-disjoint paths with different costs in a directed network can be formulated as a linear integer programming problem minimizing the sum of the costs on the edges in two paths, which is strongly NP-complete problem. Linear relaxation programming which relaxes the integer variables in the original programming is often applied to solve this NP problem. Comparing with linear relaxation programming, Lagrangean relaxation affords a lower bound of the objective value of original programming. Based on this a Lagrangean relaxation method for solving two disjoint paths is presented after a mathematical programming model of the problem is established. By using a modified subgradient optimization technology a new algorithm to solve the Lagrangean relaxation is put forward. The complexity of the proposed algorithm is as same as the Dijkstra’s algorithm (O(n2)). The efficiency of this algorithm is demonstrated by test examples.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.