Towards Effective Use of Constrained Shortest Paths in Road Networks

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


PhD Thesis Defence


Title: "Towards Effective Use of 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, we study how to effectively use the CSP from local and global 
views. From a local view, given a query with a constraint and two points, we 
aim to improve the efficiency of processing each query. First, we consider 
Resource Constrained Shortest Path (RCSP) under the numerical constraint (also 
called the resource constraint). It sets an upper bound on one metric value of 
the path, also called the path cost (e.g., the budget value for the toll fee in 
the previous example). We aim to find the RCSP that minimizes an objective, 
represented by the other metric value of the path (e.g., the distance and 
travel time), under the numerical constraint. We design by far the fastest 
solution called QHL, which runs faster than previous solutions by orders of 
magnitude. Its query time complexity has one fewer multiplier than that of the 
best-known algorithm. Second, we consider the Label Constrained Shortest Path 
(LCSP) under the categorical constraint (also called the label constraint). 
Specifically, in the context of regular languages, each edge is associated with 
a label (or symbol) from an alphabet, and the path label concatenated by the 
edge labels along the path can be seen as a "word" and should satisfy the given 
regular language constraint. For example, the categorical constraint can 
prohibit the use of toll roads when edges are associated with labels that 
indicate whether the corresponding roads have toll charges or not. We propose 
the fastest known solution called PCSP, which answers each query in around 100 
microseconds and outperforms the best-known solution by orders of magnitude. 
Finally, 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 congestion-driven constrained shortest paths, which are 
sometimes slightly slower routes with acceptable detours processed by CSP 
algorithms. 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:                   Wednesday, 7 August 2024

Time:                   10:00am - 12:00noon

Venue:                  Room 5501
                        Lifts 25/26

Chairman:               Dr. Maosheng XIONG (MATH)

Committee Members:      Prof. Raymond WONG (Supervisor)
                        Prof. Gary CHAN
                        Dr. Dongdong SHE
                        Prof. Xueqing ZHANG (CIVL)
                        Prof. Zhifeng BAO (RMIT)