The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms

The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms

0.00 Avg rating0 Votes
Article ID: iaor20022491
Country: United States
Volume: 31
Issue: 4
Start Page Number: 259
End Page Number: 272
Publication Date: Jul 1998
Journal: Networks
Authors: , ,
Keywords: programming: integer
Abstract:

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issue of network vulnerability by prescribing alternate routes for traffic flows. Applications include the dispatching of duplicate packets of data to improve the reliability in communication networks and the diverting of traffic during congestion to reduce the chances of bottlenecks in transportation networks, in the presence of time-dependent variations in travel delays in the network. We prove that this problem, and many variations of it, are NP-hard and we develop a 0–1 linear programming model that can be used to solve this problem. This model can accommodate various degrees of disjointedness of the pair of paths, from complete to partial with respect to specific arcs. We also present some computational results obtained by solving the above models using CPLEX-MIP.

Reviews

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