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

Journal Article

  • Author(s): Hanif D. Sherali, Kaan Ozbay, Shivaram Subramanian
  • Article first published online: 07 Dec 1998
  • DOI: 10.1002/(SICI)1097-0037(199807)31:4<259::AID-NET6>3.0.CO;2-C
  • Read on Online Library
  • Subscribe to Journal


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. © 1998 John Wiley & Sons, Inc. Networks 31: 259–272, 1998

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.