Premium
A Minimax Method for Finding the k Best “Differentiated” Paths
Author(s) -
Kuby Michael,
Zhongyi Xu,
Xiaodong Xie
Publication year - 1997
Publication title -
geographical analysis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.773
H-Index - 65
eISSN - 1538-4632
pISSN - 0016-7363
DOI - 10.1111/j.1538-4632.1997.tb00966.x
Subject(s) - minimax , shortest path problem , disjoint sets , path (computing) , computer science , routing (electronic design automation) , mathematical optimization , k shortest path routing , fraction (chemistry) , yen's algorithm , path length , combinatorics , algorithm , mathematics , dijkstra's algorithm , graph , computer network , chemistry , organic chemistry
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.