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

Maocan Song (), Lin Cheng (), Huimin Ge (), Chao Sun () and Ruochen Wang ()
Additional contact information
Maocan Song: Jiangsu University
Lin Cheng: Southeast University
Huimin Ge: Jiangsu University
Chao Sun: Jiangsu University
Ruochen Wang: Jiangsu University

Networks and Spatial Economics, 2024, vol. 24, issue 2, No 5, 395-423

Abstract: Abstract 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.

Keywords: K Shortest path problem; Mean-standard deviation object; Solution space decomposition; Deviation path; Travel time uncertainty (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11067-024-09618-2 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netspa:v:24:y:2024:i:2:d:10.1007_s11067-024-09618-2

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-024-09618-2

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().