Pairs of disjoint paths between two nodes in a network provide a primary path as well as a backup path, such that the latter can be used in case one of the arcs of the first is not available. The problem of finding the shortest pair of disjoint paths can be formulated as a minimum cost flow model. It finds applications in areas like telecommunications or transportation.
We will address the shortest pair of disjoint paths problem with two objective functions and related problems dealing with different types of path disjointness. Exact algorithms to find efficient solutions for these problems will be discussed.
|