Finding the \(\mathrm{K}\) Mean-Standard Deviation Shortest Paths Under Travel Time Uncertainty

The mean-standard deviation shortest path problem (MSDSPP) incorporates the travel time variability into the routing optimization. The idea is that the decision-maker wants to minimize the travel time not only on average, but also to keep their variability as small as possible. Its objective is a linear combination of mean and standard deviation of travel times. This study focuses on the problem of finding the best- \(K\) $K$ optimal paths for the MSDSPP. We denote this problem as the KMSDSPP. When the travel time variability is neglected, the KMSDSPP reduces to a \(K\) $K$ -shortest path problem with expected routing costs. This paper develops two methods to solve the KMSDSPP, including a basic method and a deviation path-based method. To find the \(k+1\) $k+1$ th optimal path, the basic method adds \(k\) $k$ constraints to exclude the first- \(k\) $k$ optimal paths. Additionally, we introduce the deviation path concept and propose a deviation path-based method. To find the \(k+1\) $k+1$ th optimal path, the solution space that contains the \(k\) $k$ th optimal path is decomposed into several subspaces. We just need to search these subspaces to generate additional candidate paths and find the \(k+1\) $k+1$ th optimal path in the set of candidate paths. Numerical experiments are implemented in several transportation networks, showing that the deviation path-based method has superior performance than the basic method, especially for a large value of \(K\) $K$ . Compared with the basic method, the deviation path-based method can save 90.1% CPU running time to find the best \(1000\) $1000$ optimal paths in the Anaheim network.