Constrained energy-efficient routing in time-aware road networks

详细信息    查看全文

• 作者：Yaqiong Liu ; Hock Soon Seah ; Guochu Shou
• 关键词：Time ; aware road network ; Time constraint ; Route query ; Approximation algorithm ; Greedy algorithm
• 刊名：GeoInformatica
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：21
• 期：1
• 页码：89-117
• 全文大小：
• 刊物类别：Earth and Environmental Science
• 刊物主题：Geographical Information Systems/Cartography; Data Structures, Cryptology and Information Theory; Computer Science, general; Information Storage and Retrieval; Multimedia Information Systems;
• 出版者：Springer US
• ISSN：1573-7624
• 卷排序：21

文摘

Routing problems find applications in many location-based services. Existing works which answer route queries mainly focus on static road networks rather than time-aware road networks. Observe the fact that (i) the same road segment may be driven with different speeds during different time intervals, and (ii) users usually prefer driving on a route that consumes minimum energy within a travel time budget. Motivated by this, this paper proposes the Constrained Energy-Efficient Time-Aware Routing problem, denoted as CEETAR. We take time factor into consideration and utilize a time-aware speed model and a time-aware polynomial energy cost model. To solve CEETAR, we propose a dynamic programming solution, and then propose an approximation algorithm which uses the branch and bound, and scaling strategy with provable approximation bounds to answer the query of CEETAR in real-world dense road networks. In addition, we also propose a greedy route planning algorithm. Experimental results demonstrate that our approximation algorithms can efficiently answer CEETAR queries with high accuracy.