Publication Type
Journal Article
Version
publishedVersion
Publication Date
6-2016
Abstract
This paper aims at solving the stochastic shortest path problem in vehicle routing, the objective of which is to determine an optimal path that maximizes the probability of arriving at the destination before a given deadline. To solve this problem, we propose a data-driven approach, which directly explores the big data generated in traffic. Specifically, we first reformulate the original shortest path problem as a cardinality minimization problem directly based on samples of travel time on each road link, which can be obtained from the GPS trajectory of vehicles. Then, we apply an l(1)-norm minimization technique and its variants to solve the cardinality problem. Finally, we transform this problem into a mixed-integer linear programming problem, which can be solved using standard solvers. The proposed approach has three advantages over traditional methods. First, it can handle various or even unknown travel time probability distributions, while traditional stochastic routing methods can only work on specified probability distributions. Second, it does not rely on the assumption that travel time on different road segments is independent of each other, which is usually the case in traditional stochastic routing methods. Third, unlike other existing methods which require that deadlines must be larger than certain values, the proposed approach supports more flexible deadlines. We further analyze the influence of important parameters to the performances, i. e., accuracy and time complexity. Finally, we implement the proposed approach and evaluate its performance based on a real road network of Munich city. With real traffic data, the results show that it outperforms traditional methods.
Keywords
Stochastic shortest path, cardinality minimization, l(1)-norm minimization, mixed integer linear programming
Discipline
Databases and Information Systems
Publication
IEEE Transactions on Intelligent Transportation Systems
Volume
17
Issue
6
First Page
1688
Last Page
1702
ISSN
1524-9050
Identifier
10.1109/TITS.2015.2498160
Publisher
Institute of Electrical and Electronics Engineers
Citation
CAO, Zhiguang; GUO, Hongliang; ZHANG, Jie; NIYATO, Dusit; and FASTENRATH, Ulrich Fastenrath.
Finding the shortest path in stochastic vehicle routing: A cardinality minimization approach. (2016). IEEE Transactions on Intelligent Transportation Systems. 17, (6), 1688-1702.
Available at: https://ink.library.smu.edu.sg/sis_research/8194
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://doi.org/10.1109/TITS.2015.2498160