NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times

Dreyfus, 1969, An appraisal of some shortest-path algorithms, Oper. Res., 17, 395, 10.1287/opre.17.3.395 Gendreau, 2015, Time-dependent routing problems: a review, Comput. Oper. Res., 64, 189, 10.1016/j.cor.2015.06.001 Batz, 2014 Delling, 2009, Time-dependent route planning, vol. 5868, 207 Nannicini, 2012, Bidirectional A* search on time-dependent road networks, Networks, 59, 240, 10.1002/net.20438 Strasser, 2021, Space-efficient, fast and exact routing in time-dependent road networks, Algorithms, 14, 10.3390/a14030090 Kleff, 2020, Efficient route planning with temporary driving bans, road closures, and rated parking areas, vol. 160 Orda, 1990, Shortest-path and minimum delay algorithms in networks with time-dependent edge-length, J. ACM, 37, 607, 10.1145/79147.214078 Orda, 1991, Minimum weight paths in time-dependent networks, Networks, 21, 295, 10.1002/net.3230210304 Foschini, 2014, On the complexity of time-dependent shortest paths, Algorithmica, 68, 1075, 10.1007/s00453-012-9714-7 Orda, 1989 Garey, 1979 Bellman, 1958, On a routing problem, Q. Appl. Math., 16, 87, 10.1090/qam/102435 Wojtczak, 2018, On strong NP-completeness of rational problems, 308 Johnson, 1981, The NP-completeness column: an ongoing guide, J. Algorithms, 2, 393, 10.1016/0196-6774(81)90037-7