Efficient solution algorithm for finding spatially dependent reliable shortest path in road networks
Efficient solution algorithm for finding spatially dependent reliable shortest path in road networks
复制标题
DOI：
10.1002/atr.1408
复制
发表时间：
2016-11
影响因子：
2.3
通讯作者：
B. Chen;W. Lam;Qingquan Li
中科院分区：
文献类型：
--
作者：
B. Chen;W. Lam;Qingquan Li
摘要在拥挤的道路网络中，行程时间通常是随机的和空间相关的。然而，很少有现有的路径诱导系统（RGS）可以提供可靠的指导服务，以帮助旅行者规划他们的行程，考虑明确的旅行时间的可靠性约束。本研究的目的是开发这样一个RGS特别考虑到旅客的行程时间可靠性在拥挤的道路网络的不确定性的关注。在这项研究中，空间相关的可靠最短路径问题（SD-RSPP）制定为一个多准则的最短路径搜索问题的道路网络相关的路段行程时间。三个有效的优势条件，建立了不同水平的行程时间相关性的链接。提出了一种有效的算法求解SD-RSPP自适应使用三个优势条件。还明确考虑了现实中道路网络的复杂性。为了证明所提出的算法的适用性，在香港进行了全面的案例研究。算例结果表明，该算法能有效地考虑出行者的多种路径选择标准。计算结果表明，所提出的求解算法可以确定可靠的最短路径的大规模道路网络的实时基础上。版权所有© 2016约翰威利父子有限公司.
Summary Travel times are generally stochastic and spatially correlated in congested road networks. However, very few existing route guidance systems (RGS) can provide reliable guidance services to aid travellers planning their trips with taking account explicitly travel time reliability constraint. This study aims to develop such a RGS with particular consideration of travellers' concern on travel time reliability in congested road networks with uncertainty. In this study, the spatially dependent reliable shortest path problem (SD-RSPP) is formulated as a multi-criteria shortest path-finding problem in road networks with correlated link travel times. Three effective dominance conditions are established for links with different levels of travel time correlations. An efficient algorithm is proposed to solve SD-RSPP by adaptively using three established dominance conditions. The complexities of road networks in reality are also explicitly considered. To demonstrate the applicability of proposed algorithm, a comprehensive case study is carried out in Hong Kong. The results of case study show that the proposed solution algorithm is robust to take account of travellers' multiple routing criteria. Computational results demonstrate that the proposed solution algorithm can determine the reliable shortest path on real-time basis for large-scale road networks. Copyright © 2016 John Wiley & Sons, Ltd.