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

Hanif D. Sherali, Kaan Ozbay, Shivaram Subramanian

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)259-272
Number of pages14
JournalNetworks
Volume31
Issue number4
DOIs
StatePublished - Jul 1998

Keywords

  • Complexity
  • Disjoint paths
  • Integer programming
  • Shortest paths
  • Time-dependent delays

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms'. Together they form a unique fingerprint.

  • Cite this