Finding optimal routes between two points in a road network is a crucial challenge for navigation platforms used by millions of users daily. Users typically seek routes that minimize travel distance or time, which aligns this problem with the classical shortest path problem in graph theory. However, real-world scenarios complicate this task with factors such as individual driving preferences, the need to balance travel time with environmental concerns like carbon emissions, and adapting to changing road conditions such as closures. Consequently, navigation systems often generate a set of candidate routes rather than a single “best” one, a process known as alternative route computation. This process has garnered significant attention in the literature, where it is typically treated as a graph optimization problem that balances the diversity of routes—ensuring alternatives are distinct—and the quality of each route—ensuring efficiency. However, finding exact optimal solutions for these problems can be impractical for general graphs, leading to the reliance on heuristic methods.
This project aims to develop a novel approach that leverages deep learning to learn representations of road networks. Rather than manually crafting and fine-tuning heuristic algorithms, the project will utilize existing route planning algorithms, such as A* or Dijkstra’s search, to create a succinct representation that inherently captures multiple high-quality routes between any pair of nodes. This approach seeks to enhance the efficiency and adaptability of navigation systems in providing diverse and optimal route options.
References:
Peter E Hart, Nils J Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4, 2 (1968), 100–107.
Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable route planning in road networks. Transp. Sci., 51(2):566–591, 2017.
Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Alternative routes in road networks. ACM J. Exp. Algorithmics, 18, 2013.
A Zhai, D Guo, S Gollapudi, K Kollias, D Delling. Deep Learning-Based Alternative Route Computation. International Conference on Artificial Intelligence and Statistics, 2024.