查看文章

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 …