A Minimax Method for Finding the k Best “Differentiated” Paths

Abstract

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.