Budget-Driven and Congestion-Driven Constrained Shortest Paths in Road Networks

PhD Thesis Proposal Defence


Title: "Budget-Driven and Congestion-Driven Constrained Shortest Paths in Road 
Networks"

by

Mr. Libin WANG


Abstract:

Route planning has been an integral part of many spatial applications, such as 
online navigation systems, ride-hailing platforms, and food delivery services. 
One of the fundamental operations in route planning is the point-to-point 
shortest path query due to its ubiquitous and simple usage. However, finding 
the "shortest" path that minimizes a single objective (such as the shortest 
distance and travel time) cannot satisfy various routing demands in practice. 
For example, a traveler may have a limited budget for the toll fee, and the 
shortest path can be infeasible when it traverses several highways and bridges 
with high toll charges. It is more flexible to consider the constrained 
shortest path (CSP) that minimizes an objective under a constraint imposed on 
the path.

In this thesis proposal, we study the CSP from two perspectives, namely 
budget-driven CSP and congestion-driven CSP. From a local view, given a query 
with a budget constraint and two points, we first study how to efficiently 
process each CSP query. Though the budget constraint increases the 
computational difficulty, compared with finding the unconstrained shortest 
path, it also brings many pruning and speedup opportunities. We design by far 
the fastest CSP solution that attaches importance to the pruning power of the 
budget. From a global view of processing millions of routing queries daily in a 
navigation system (such as Google Maps), it can be observed that routing 
queries with similar sources and destinations are answered by similar shortest 
paths, which aggravates traffic congestion. To mitigate it, we study how to 
properly define different CSP queries to return sometimes slightly slower 
routes with acceptable detours. We propose solutions that aim to enable instant 
responses to online routing queries while achieving congestion minimization 
with theoretical guarantees in a long term.


Date:                   Tuesday, 30 April 2024

Time:                   4:00pm - 6:00pm

Venue:                  Room 4472
                        Lifts 25/26

Committee Members:      Prof. Raymond Wong (Supervisor)
                        Prof. Xiaofang Zhou (Chairperson)
                        Prof. Gary Chan
                        Dr. Binhang Yuan