TY - JOUR
T1 - A minimax method for finding the k best "differentiated" paths
AU - Kuby, Michael
AU - Zhongyi, Xu
AU - Xiaodong, Xie
PY - 1997/10
Y1 - 1997/10
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0031430841&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031430841&partnerID=8YFLogxK
U2 - 10.1111/j.1538-4632.1997.tb00966.x
DO - 10.1111/j.1538-4632.1997.tb00966.x
M3 - Article
AN - SCOPUS:0031430841
SN - 0016-7363
VL - 29
SP - 298
EP - 313
JO - Geographical Analysis
JF - Geographical Analysis
IS - 4
ER -