Scalable Routing Optimization in Road Networks

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Scalable Routing Optimization in Road Networks"

By

Miss Yehong XU


Abstract:

Traffic congestion causes large economic, environmental, and public-health 
costs. Recent studies show that modern navigation services (e.g., Google Maps 
and GaoDe Maps) can further worsen congestion: a small number of centralized 
platforms compute routes for many users, often independently under the same 
predicted traffic, and may therefore send many drivers to the same currently 
fastest road segments. Yet, this centralization also creates the basis for 
coordinated optimization. This thesis thus studies the problem of scalable 
global routing optimization in road networks. Given a road network and a 
large set of travel queries, it aims to plan these queries jointly so that 
their total travel time is minimized after accounting for the traffic caused 
by the planned routes themselves.

The first part of the thesis formulates Global Routing Optimization (GRO) for 
fixed-departure queries. The core difficulty is the circular dependency 
between routing and traffic: routes require edge travel-time weights, but 
those weights depend on the traffic flows created by the chosen routes. To 
handle this feedback loop, the thesis develops a Routing--TE--WT cycle, where 
Routing computes routes under the current edge weights, Traffic Evaluation 
(TE) evaluates the traffic induced by the planned routes, and Weight Tuning 
(WT) updates the edge weights for later routing. The cycle is instantiated 
with serial, batch, and iterative optimization models. The thesis then moves 
beyond route-only coordination through Global Optimal Travel Planning (GOTP). 
For queries with flexible departure intervals, GOTP adds a Timing operation 
before routing, allowing demand to be distributed across both time and roads. 
Impact-aware GRO further improves global routing optimization by efficiently 
estimating how a local route change may propagate through the network and 
affect other queries, improving both solution quality and efficiency.

The global routing methods above depend on a time-dependent routing engine 
that repeatedly finds fastest paths for individual queries under evolving 
traffic states. The final part of the thesis studies how to support efficient 
routing in dynamic and time-dependent road networks. It proposes the Sliding 
Window Time-Dependent (SWTD) index for maintaining exact near-future routing 
information with high query availability.

Together, our works form a two-layer framework for scalable global routing. 
The upper layer coordinates queries' travels by evaluating their induced 
traffic effects, while the lower layer supports the upper layer with fast and 
accurate time-dependent routing.


Date:                   Thursday, 30 July 2026

Time:                   4:00pm - 6:00pm

Venue:                  Room 4475
                        Lifts 25/26

Chairman:               Prof. Shuhuai YAO (MAE)

Committee Members:      Prof. Xiaofang ZHOU (Supervisor)
                        Prof. Raymond WONG
                        Dr. Zihan ZHANG
                        Prof. Hai YANG (CIVL)
                        Dr. Jianzhong QI (University of Melbourne)