动态网络中多规则的最短路径查询算法

最佳排序路径查询,是智能交通中的热点问题.在实际的应用中,由于最佳排序路径查询有许多限制条件,现有的算法不能有效地解决动态网络中受限制的路径查询问题.为了解决动态网络中最佳排序路径查询问题,用规则表示每个限制条件,提出了一种新的最佳排序路径查询形式,即多规则的最短路径查询.提供了统一的框架,该框架包含了路径集合查询和最短路径查询.在路径集合查询部分,为了高效地查询出满足多规则的路径集合,在广义规则树的基础上,提出一种新的树的遍历方式,即树的继承全遍历;并基于树的继承全遍历思想,提出一种剪枝技术,对路径集合进行删减,最后求得候选路径集合.在最短路径查询部分,提出一种基于动态阈值的最短路径搜索方法.通过两个真实的动态道路网络的实验验证,所提出的算法能够高效地解决多规则的最短路径查询问题.

Multi-rule Shortest Path Query Algorithm in Time-dependent Networks

The optimal sequenced path query is a hot topic in the intelligent transportation. In practical applications, the existing approaches cannot effectively solve these constrained path query problems in the time-dependent network because of the constraints of the optimal sequenced path query. This study employs the rules to stand for the constraints. In order to solve the shortest travel time problem of the constrained path in the time-dependent network, a new query form of the optimal sequenced path, namely the multi-rule based shortest path query, is studied. This study provides a unified framework, which includes the path set query and the shortest path query. In order to efficiently retrieve the path set satisfying multiple rules, a new tree traversal method, inheritance and traversal of trees, is proposed on the basis of generalized rule tree. Based on the idea of tree inheritance and traversal, a pruning method is proposed to prune the path set, and finally, the candidate path set is obtained. In the shortest path query part, a dynamic threshold method is proposed. Extensive experiments with two real data offer evidence that the proposed solutions can solve the problem of multi-rule based shortest path query.