Algorithm for time-dependent shortest safe path on transportation networks | |
Jigang, Wu ; Jin, Song ; Ji, Haikun ; Srikanthan, Thambipillai | |
2011 | |
英文摘要 | The shortest path problem in network has been studied widely and intensively over years. Many speed-up techniques for Dijkstra's algorithm have been developed. However, only few of those techniques work in time-dependent networks. This paper studies how to answer the shortest safe path between a pair of nodes over a large time-dependent transportation network, for typical applications, such as a heavy truck carrying inflammable materials, poison gas or explosive cargo, and traveling in a city. In this type of applications, a path is safe if the danger factor on each edge of the path is no more than a given upper bound. An efficient algorithm is proposed for finding the shortest safe path from source node to destination node when the starting time (departure time from the source) can be selected in a user-given starting-time interval. The proposed algorithm can provide optimal solution and the best starting time when a safe path exists in the given network. Also, it can find an approximate solution when the safe path does not exist. Moveover, our algorithm can handle both undirected and directed time-dependent network. ? 2011 Published by Elsevier Ltd.; EI; 0 |
语种 | 英语 |
DOI标识 | 10.1016/j.procs.2011.04.101 |
内容类型 | 其他 |
源URL | [http://ir.pku.edu.cn/handle/20.500.11897/263658] |
专题 | 软件与微电子学院 |
推荐引用方式 GB/T 7714 | Jigang, Wu,Jin, Song,Ji, Haikun,et al. Algorithm for time-dependent shortest safe path on transportation networks. 2011-01-01. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论