Global Routing Optimization in Road Networks

摘要

Route planning plays an increasingly important role in our society, and the routing results, which are the paths that vehicles actually travel in a road network, which influence the traffic condition naturally. However, the existing routing algorithms cannot consider the routing results and their influence simultaneously, so traffic congestion could be created when many vehicles are directed to follow similar routes. In this paper, we propose the Global Routing Optimization problem that aims to minimize traffic congestion by continuously evaluating traffic conditions for a set of routing tasks. It is non-trivial to achieve this global optimization goal, as routing and traffic condition evaluation is both time-consuming and interdependent. To break this dependency, we propose a global routing optimization paradigm that can evaluate the routing results’ influence on the traffic condition, and then plan the routes accordingly. To implement it, we first propose a serial model to optimize the next route, followed by a batch model to improve processing efficiency. After that, an iterative model is proposed to further optimize route qualities. Extensive experiments on large real-world networks with synthetic and real workloads validate the effectiveness and efficiency of our methods.