TY - GEN
T1 - Preprocessing Parallelization for the ALT-Algorithm
AU - Peque, Genaro
AU - Urata, Junji
AU - Iryo, Takamasa
N1 - Publisher Copyright:
© 2018, Springer International Publishing AG, part of Springer Nature.
PY - 2018
Y1 - 2018
N2 - In this paper, we improve the preprocessing phase of the ALT algorithm through parallelization. ALT is a preprocessing-based, goal-directed speed-up technique that uses A* (A star), Landmarks and Triangle inequality which allows fast computations of shortest paths (SP) in large-scale networks. Although faster techniques such as arc-flags, SHARC, Contraction Hierarchies and Highway Hierarchies already exist, ALT is usually combined with these faster algorithms to take advantage of its goal-directed search to further reduce the SP search computation time and its search space. However, ALT relies on landmarks and optimally choosing these landmarks is NP-hard, hence, no effective solution exists. Since landmark selection relies on constructive heuristics and the current SP search speed-up is inversely proportional to landmark generation time, we propose a parallelization technique which reduces the landmark generation time significantly while increasing its effectiveness.
AB - In this paper, we improve the preprocessing phase of the ALT algorithm through parallelization. ALT is a preprocessing-based, goal-directed speed-up technique that uses A* (A star), Landmarks and Triangle inequality which allows fast computations of shortest paths (SP) in large-scale networks. Although faster techniques such as arc-flags, SHARC, Contraction Hierarchies and Highway Hierarchies already exist, ALT is usually combined with these faster algorithms to take advantage of its goal-directed search to further reduce the SP search computation time and its search space. However, ALT relies on landmarks and optimally choosing these landmarks is NP-hard, hence, no effective solution exists. Since landmark selection relies on constructive heuristics and the current SP search speed-up is inversely proportional to landmark generation time, we propose a parallelization technique which reduces the landmark generation time significantly while increasing its effectiveness.
KW - ALT algorithm
KW - Large-scale traffic simulation
KW - Shortest path search
UR - http://www.scopus.com/inward/record.url?scp=85049002172&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049002172&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-93713-7_7
DO - 10.1007/978-3-319-93713-7_7
M3 - Conference contribution
AN - SCOPUS:85049002172
SN - 9783319937120
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 89
EP - 101
BT - Computational Science – ICCS 2018 - 18th International Conference, Proceedings
A2 - Dongarra, Jack
A2 - Fu, Haohuan
A2 - Krzhizhanovskaya, Valeria V.
A2 - Lees, Michael Harold
A2 - Sloot, Peter M.
A2 - Shi, Yong
A2 - Tian, Yingjie
PB - Springer Verlag
T2 - 18th International Conference on Computational Science, ICCS 2018
Y2 - 11 June 2018 through 13 June 2018
ER -