On scenario construction for stochastic shortest path problems in real road networks

Dongqing Zhang, Stein Wallace, Zhaoxia Guo, Yucheng Dong and Michal Kaut

Transportation Research Part E: Logistics and Transportation Review, 2021, vol. 152, issue C

Abstract: Stochastic shortest path (SSP) computations are often performed under very strict time constraints, so computational efficiency is critical. A major determinant for the CPU time is the number of scenarios used. We demonstrate that by carefully picking the right scenario generation method for finding scenarios, the quality of the computations can be improved substantially over random sampling for a given number of scenarios. We study extensive SSP instances from a freeway network and an urban road network, which involve 10,512 and 37,500 spatially and temporally correlated speed variables, respectively. On the basis of experimental results from a total of 42 origin–destination pairs and 6 typical objective functions for SSP problems, we find that (1) the scenario generation method generates unbiased scenarios and strongly outperforms random sampling in terms of stability (i.e., relative difference and variance) whichever origin–destination pair and objective function is used; (2) to achieve a certain accuracy, the number of scenarios required for scenario generation is much lower than that for random sampling, typically about 6–10 times lower for a stability level of 1% in the freeway network; and (3) different origin–destination pairs and different objective functions could require different numbers of scenarios to achieve a specified stability.

Keywords: Stochastic shortest path; Spatial and temporal correlation; Scenario generation; Random sampling; Number of scenarios; Stability (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554521001770
Full text for ScienceDirect subscribers only

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:eee:transe:v:152:y:2021:i:c:s1366554521001770

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2021.102410

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().