Deep learning improves customizable route planning for diverse users
Customizable and Jointly Optimized Route Planning: A Deep Architecture Enabling Differentiable Shortest-Path Search
Artificial Intelligence
Summary
Finding the best route on maps is tricky because different users want different things, like shortest time or scenic paths. The authors designed a deep learning system that learns how to pick the best routes based on many criteria all at once. They first find all the best possible routes offline and then train a neural network that can quickly choose the best one according to user preferences. Their experiments show this method works better than older approaches at customizing routes. This may help apps give better directions tailored to what each user cares about.
What this means in practice
- •For navigation software developers: Provide routing engines that flexibly adapt to individual user preferences using learned cost functions and route selections.
- •For ride-hailing platform engineers: Optimize route recommendations that balance multiple user needs like time, distance, and comfort in real time.
Authors
Rui Zhao, Chao Chen, Longfei Xu, Chenguang Ji, Hengbin Cui, Kaikui Liu, Xiaolong Li
Abstract
With the widespread use of online navigation and ride-hailing services, achieving optimal route planning for diverse user preferences has recently attracted increasing attention. Classic graph algorithms for pathfinding use heuristic cost functions to define edge weight, thus providing no optimality guarantee of route quality. Prior data-driven approaches equating ground truth of the optimal route with user trajectory, which is however moderately influenced by the navigation service, suffers from the feedback loop problem. To address these issues, we propose a deep architecture that is able to jointly optimize cost functions and route-ranking model towards any route preference. First, we run a multi-objective Dijkstra algorithm offline to collect the set of Pareto optimal routes, deeming it as the complete candidate set. Exploiting the property of such a set, we design a neural network structure that emulates shortest-path search and route ranking in an end-to-end differentiable manner. Second, we define route preference as a task of constrained optimization of route attributes, and propose a novel loss function that optimizes a single-objective variable, with other variables strictly under constraints. We conduct extensive experiments on real-world datasets. The results show that our architecture significantly outperforms state-of-the-art methods in route quality and customizability.