论文标题
有效的路线规划，临时驾驶禁令，封路和评级停车区
Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas
论文作者
论文摘要
当某些街道或区域在某些时候关闭时，我们研究道路网络中规划路线的问题。对于重型车辆，此类地区可能非常大，因为许多欧洲国家在夜间或周末都施加临时驾驶禁令。在这种情况下，可行的路线可能需要在停车场等待，并且在封闭区域周围等待和驾驶绕道之间的几条可行路线可能存在不同的折衷。我们提出了一个新颖的模型，其中驾驶和等待是分配抽象成本，等待成本依赖于位置，以反映停车区的不同质量。我们的目标是在目的地和总成本上找到帕累托最佳路线。我们研究了模型的复杂性，并确定对成本参数的必要限制，以便在多项式时间内解决问题。我们介绍了彻底设计的实施，并在生产级现实世界数据集上执行实验。实验表明，我们的实施可以在大约一秒钟或更少的时间内回答现实的查询，这使其对于实际应用而言是可行的。
We study the problem of planning routes in road networks when certain streets or areas are closed at certain times. For heavy vehicles, such areas may be very large since many European countries impose temporary driving bans during the night or on weekends. In this setting, feasible routes may require waiting at parking areas, and several feasible routes with different trade-offs between waiting and driving detours around closed areas may exist. We propose a novel model in which driving and waiting are assigned abstract costs, and waiting costs are location-dependent to reflect the different quality of the parking areas. Our goal is to find Pareto-optimal routes with regards to arrival time at the destination and total cost. We investigate the complexity of the model and determine a necessary constraint on the cost parameters such that the problem is solvable in polynomial time. We present a thoroughly engineered implementation and perform experiments on a production-grade real world data set. The experiments show that our implementation can answer realistic queries in around a second or less which makes it feasible for practical application.
