Integrating Dijkstra’s algorithm into deep inverse reinforcement learning for food delivery route planning

Abstract

In China, rapid development of online food delivery brings massive orders, which relies heavily on deliverymen riding e-bikes. In practice, actual delivery routes of most orders are not the same as the system recommended routes, and the road network information for some areas is outdated or incomplete. In this research, we develop a deep inverse reinforcement learning (IRL) algorithm to capture deliverymen’s preferences from historical GPS trajectories and recommend their preferred routes. Considering the characteristics of food delivery routes, we employ Dijkstra’s algorithm instead of value iteration, to determine the current policy and compute the gradient of IRL. Moreover, we plan routes at the presence and absence of road network information, providing accurate navigation when road network information is unknown. Numerical experiments on real delivery trajectories provided by Meituan-Dianping Group show that our approach improves F1-scoredistance by 8.0% and 6.1% at the presence and absence of road network information, respectively.