A MINIMAX METHOD FOR FINDING THE K-BEST DIFFERENTIATED PATHS

In real-world applications, the k-shortest-paths between a pair of nod es on a network will often be slight variations of one another. This c ould be a problem for many path-based models, particularly those on a capacitated networks where different routing alternatives are needed t hat are less likely to encounter the same capacity constraints. This p aper develops a method to solve for k differentiated paths that are re latively 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 min imax algorithm is used to select the path whose largest sum of length, plus shared length vis-a-vis each previously selected path, is as sim ple as possible. We present computational results for the Chinese rail way system, comparing the paths generated by a standard k-shortest-pat h algorithm with those from our new model.