Scalability of Customizable Route Planning
Summary
Current state-of-the-art shortest path algorithms can compute shortest paths on continental-sized graphs within a couple of milliseconds. Customizable Route Planning (CRP) is one such algorithm and distinguishes itself from other algorithms by being robust to metric changes and by being able to incorporate new metrics quickly. CRP uses three stages: two separate preprocessing stages and a query stage. In this research project, we focus on the query stage, in which shortest paths are computed using a multilevel Dijkstra search. Our goal is to find a distributed memory approach to this stage of CRP, such that scalability is improved. We treat three different approaches and investigate their implications for scalability, performance and total amount of used resources.