Constrained energy-efficient routing in time-aware road networks

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 C E E T A R. We take time factor into consideration and utilize a time-aware speed model and a time-aware polynomial energy cost model. To solve C E E T A R, 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 C E E T A R 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 C E E T A R queries with high accuracy.