Finding the $$\mathrm{K}$$ 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.