Facing various uncertainties in real world traffic, navigation services are typically formulated as a certain stochastic shortest path problem (SSPP). In the past several years, many stochastic objectives in SSPP has been proposed, among which maximizing the probability of arrival on time draws certain attentions from researchers as it takes, besides absolute travel time, an extra dimension of information (user-specified deadlines) into consideration. This paper extends a recently proposed data-driven approach for SSPP in the following two aspects: (1) when deadline is loose enough, the original method may return more than one paths since all of them meet deadline with 100% probability. We propose to return a unique path with the least number of intersections by reformulating the objective function. (2) we extend the arrive-on-time problem to the case of visiting several fixed locations, which is a common scenario in real world application. Experimental results show the accuracy and effectiveness of the improved data-driven method.
Improving the performance of arrival on time in stochastic shortest path problem
01.11.2016
482684 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
Shortest path problem considering on-time arrival probability
Online Contents | 2009
|Shortest path problem considering on-time arrival probability
Online Contents | 2009
|Time-Constrained Shortest-Path Problem in Stochastic Dynamic Networks
British Library Conference Proceedings | 2005
|Research on Dynamic Stochastic Shortest Path Problem
ASCE | 2010
|