Research Project

Global Routing Optimization in Road Networks

Abstract

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.

Project members

Lei LI

Assistant Professor

Xiaofang ZHOU

Chair Professor

Publications

1. Global Routing Optimization In Road Networks. Yehong Xu, Lei Li, Mengxuan Zhang, Zizhuo Xu, and Xiaofang Zhou. ICDE 2023.
2. Global Optimal Travel Planning for Massive Travel Queries in Road Network

Project Period

2023 - Present

Research Area

Graph, Transportation

Keywords

Graph, Index, Road Network, Route Planning, Shortest Path, Transportation