论文标题
建模和工程限制了电池电动汽车的最短路径算法
Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles
论文作者
论文摘要
我们研究了电池电动汽车的计算限制最短路径的问题。由于电池容量有限，因此最快的路线通常是不可行的。相反，用户对能源消耗不超过电池容量的快速路线感兴趣。为此，驾驶员可以故意降低速度以节省能源。因此，路线规划应提供路径和速度建议。为了解决由此产生的NP-HARD优化问题，先前的工作交易了基础模型的正确性或实际运行时间的准确性。我们提出了一个新颖的框架，用于计算使用更现实的物理模型的电动汽车的最佳约束最短路径（无需充电停止），同时考虑了速度适应。仔细的算法工程即使在大型，现实的道路网络上也可以实用：我们在不到一秒钟的典型电池容量下计算最佳解决方案，与以前的不精确方法的性能相匹配。对于更快的查询时间，可以通过启发式方法轻松扩展该方法，从而在毫秒内提供高质量的解决方案。
We study the problem of computing constrained shortest paths for battery electric vehicles. Since battery capacities are limited, fastest routes are often infeasible. Instead, users are interested in fast routes on which the energy consumption does not exceed the battery capacity. For that, drivers can deliberately reduce speed to save energy. Hence, route planning should provide both path and speed recommendations. To tackle the resulting NP-hard optimization problem, previous work trades correctness or accuracy of the underlying model for practical running times. We present a novel framework to compute optimal constrained shortest paths (without charging stops) for electric vehicles that uses more realistic physical models, while taking speed adaptation into account. Careful algorithm engineering makes the approach practical even on large, realistic road networks: We compute optimal solutions in less than a second for typical battery capacities, matching the performance of previous inexact methods. For even faster query times, the approach can easily be extended with heuristics that provide high quality solutions within milliseconds.
