A minimax method for finding the k best "differentiated" paths

Michael Kuby, Xu Zhongyi, Xie Xiaodong

Research output: Contribution to journalArticlepeer-review

47 Scopus citations


In real-world applications, the k-shortest-paths between a pair of nodes on a network will often be slight variations of one another. This could be a problem for many path-based models, particularly those on capacitated networks where different routing alternatives are needed that are less likely to encounter the same capacity constraints. This paper develops a method to solve for k differentiated paths that are relatively short and yet relatively different from one another but not necessarily disjoint. Our method utilizes the sum of a path's distance plus some fraction of its shared distance with each other path. A minimax algorithm is used to select the path whose largest sum of length, plus shared length vis-à-vis each previously selected path, is as small as possible. We present computational results for the Chinese railway system, comparing the paths generated by a standard k-shortest-path algorithm with those from our new model.

Original languageEnglish (US)
Pages (from-to)298-313
Number of pages16
JournalGeographical Analysis
Issue number4
StatePublished - Oct 1997

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Earth-Surface Processes


Dive into the research topics of 'A minimax method for finding the k best "differentiated" paths'. Together they form a unique fingerprint.

Cite this