Break planning with multi-label Dijkstra and time-dependent contraction hierarchies

Mandatory breaks for truck drivers are nowadays scheduled after the route has been decided. However, in some cases it is beneficial to plan these breaks during waiting time caused by truck driving bans. Optimally planning a single break considering driving bans can be done using Dijkstra's algorithm with multiple labels (Algorithm SBG in dataset). To improve the computation times, a single-label variant (SBG-SL) as well as a novel heuristic version of multi-label and single-label time-dependent contraction hierarchies (TCH) are introduced.The algorithms are tested using a generated dataset of 10,000 start-destination pairs based on the European ETIS database of freight flows through Europe.

当前，货运卡车司机的强制休息时段通常在行车路线确定后才进行规划。但在部分场景下，若在卡车通行禁令引发的等待时段内规划此类休息，反而能取得更优的方案。若要在兼顾通行禁令的前提下最优规划单次休息时段，可采用带多标签的迪杰斯特拉算法（Dijkstra's algorithm，本数据集中记为算法SBG）。为缩短计算耗时，本研究提出了单标签变体算法（SBG-SL），以及适用于多标签与单标签场景的新型启发式时间依赖收缩层级（time-dependent contraction hierarchies, TCH）算法。本次实验基于覆盖欧洲跨境货运流量的欧洲ETIS数据库，生成了包含10000个起讫点对的测试数据集，用以对上述算法开展性能验证。