Time-Dependent Route Planning with Generalized Objective Functions
Time-Dependent Route Planning with Generalized Objective Functions
复制标题
DOI：
10.1007/978-3-642-33090-2_16
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
G. V. Batz;P. Sanders
中科院分区：
文献类型：
--
作者：
G. V. Batz;P. Sanders
我们考虑的问题，在道路网络中找到路线，优化旅行时间和额外的时不变成本的组合。这些可以是能耗、距离、通行费或其他处罚的近似值。由此产生的问题是NP难的，但是如果额外的成本与行驶距离成正比，我们可以使用多标签A* 搜索在2.3 s内在德国道路网络上最优地解决它。一个泛化的时间依赖的收缩层次的问题产生的近似值，可以忽略不计的错误，使用运行时间低于5毫秒，这使得该模型的高吞吐量的Web服务是可行的。通过引入收费，我们得到了相当困难的实例，但我们仍然有低于41毫秒的运行时间和非常小的错误。
We consider the problem of finding routes in road networks that optimize a combination of travel time and additional time-invariant costs. These could be an approximation of energy consumption, distance, tolls, or other penalties. The resulting problem is NP-hard, but if the additional cost is proportional to driving distance we can solve it optimally on the German road network within 2.3 s using a multi-label A* search. A generalization of time-dependent contraction hierarchies to the problem yields approximations with negligible errors using running times below 5 ms which makes the model feasible for high-throughput web services. By introducing tolls we get considerably harder instances, but still we have running times below 41 ms and very small errors.