Efficient Route Planning in Road Networks with Applications to Demand Responsive Transport

Shortest path planning in road networks is an ubiquitous tool for vehicle navigation and logistics management. The efficiency of route planning algorithms is of utmost importance for real-time navigation and also for a high throughput of route planning queries in a client/server-architecture or when fleets of vehicles have to be handled. The talk provides an overview of recently developed acceleration algorithms. For example, when using contraction hierarchies or transit nodes, optimal paths in continental sized road networks can be computed in a few milli- or microseconds. On that basis, also more complex queries can be answered quickly as e.g. one-to-many queries, sequenced queries, personalized or multi-criteria queries, and queries with time windows. We discuss several of these complex query types in detail with a focus on their relevance and usefulness for ride-sharing and on-demand transport.