This paper aims at solving a stochasticshortestpath *** objective is to determine an optimal path which maximizes the probability of arriving on time given a time constraint(i.e.,a deadline).To solve this problem,we...
详细信息
This paper aims at solving a stochasticshortestpath *** objective is to determine an optimal path which maximizes the probability of arriving on time given a time constraint(i.e.,a deadline).To solve this problem,we propose a data-driven *** first reformulate the original finding optimal pathproblem as a cardinality minimization ***,we apply an L1 norm minimization technique to solve the cardinality *** problem is transformed into a mix integer linear programming problem,which can be solved using standard *** proposed approach has three advantages over the traditional methods:(1) the proposed approach can handle various or even unknown travel time distributions,while traditional stochastic routing algorithms can only work on specified distributions;(2) the proposed approach does not rely on the assumption that the travel time on different road segments is independent from each other;(3) unlike other existing approaches which require that the deadline must be larger than a certain value,the proposed approach can support more flexible deadline *** we test our approach respectively on artificial and real-world road networks,the experimental results show that the proposed approach can achieve a comparatively high accuracy when the sampling size of travel time is large ***,under some reasonable assumptions,the accuracy could be 100%.
暂无评论