Multi-Cost Optimal Route Planning Under Time-Varying Uncertainty
Multi-Cost Optimal Route Planning Under Time-Varying Uncertainty
复制标题
时变不确定性下的多成本最优路径规划
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Shuo Shang
中科院分区：
文献类型：
--
作者：
Bin Yang;Chenjuan Guo;Christian S. Jensen;Manohar Kaul;Shuo Shang
道路网络的不同用途需要考虑不同的出行成本：在路线规划中，通常会考虑出行时间和距离，并且越来越多地考虑温室气体（GHG）排放。此外，旅行时间和温室气体排放等成本取决于时间且不确定。为了支持此类用途，我们提出了一些技术，可以根据穿过道路网络的车辆的 GPS 数据构建道路网络的多成本、时间相关、不确定图 (MTUG) 模型。基于 MTUG，我们定义考虑多种成本和时间相关不确定性的最佳路线，并提出有效的算法来检索给定源-目的地对和开始时间的最佳路线。对丹麦三个道路网络和大量 GPS 数据集的实证研究可深入了解 MTUG 的设计特性和最佳路线算法的效率。
Different uses of a road network call for the consideration of different travel costs: in route planning, travel time and distance are typically considered, and green house gas (GHG) emissions are increasingly being considered. Further, costs such as travel time and GHG emissions are time-dependent and uncertain. To support such uses, we propose techniques that enable the construction of a multi-cost, time-dependent, uncertain graph (MTUG) model of a road network based on GPS data from vehicles that traversed the road network. Based on the MTUG, we define optimal routes that consider multiple costs and timedependent uncertainty, and we propose efficient algorithms to retrieve optimal routes for a given source-destination pair and a start time. Empirical studies with three road networks in Denmark and a substantial GPS data set offer insight into the design properties of the MTUG and the efficiency of the optimal route algorithms.