Online Preference Weight Estimation Algorithm with Vanishing Regret for Car-Hailing in Road Network

摘要

Car-hailing services play an important role in the modern transportation system, and the utilities of the service providers highly depend on the efficiency of route planning algorithms. A widely adopted route planning framework is to assign weights to roads and compute the routes with the shortest path algorithms. Existing techniques of weight-assigning often focus on the traveling time and length of the roads, but cannot incorporate with the preferences of the passengers (users). In this paper, a set of preference weight estimation models is employed to capture the users' preferences over paths in car-hailing with their historical choices. Since the user preferences may vary dynamically over time, it is a challenging task to make real-time decisions over the models. The main technical contribution of this paper is to propose an online learning-based preference weight chasing (PWC) algorithm to solve this problem. The worst-case performance of PWC is analyzed with the metric regret, and it is proved that PWC has a vanishing regret, which means that the time-averaged loss concerning the fixed in-hindsight best model tends to zero. Experiments based on real-world datasets are conducted to verify the effectiveness and efficiency of our algorithm. The code is available at https://github.com/GaoYucen/PWC.