A Survey on Constrained Shortest Path

PhD Qualifying Examination


Title: "A Survey on Constrained Shortest Path"

by

Mr. Libin WANG


Abstract:

Route planning is a fundamental operation in many spatial applications,
including navigation systems, taxi-hailing services, and food delivery
industry. More and more users query the fastest routes on the online mapping
platforms (such as Google Maps) to reach their destinations as soon as
possible. Existing mapping platforms often process these queries by modeling
the road network as a graph where edges are weighted and solving the classical
shortest path problem. However, the shortest path optimizing one single
objective can only be applied to limited scenarios. It would be more flexible
to impose additional constraints on the paths. Therefore, constrained shortest
path problems of different variants have been proposed and extensively studied.
In this survey, we review two classical variants where the constraint is
related to the numerical and categorical attributes of the edges along a path,
i.e., Resource Constrained Shortest Path (RCSP) and Label-Constrained Shortest
Path (LCSP), respectively. Furthermore, since RCSP is NP-hard, there is a line
of research on the approximation algorithms for the approximate RCSP problem.
We finally conclude this survey by showing some potential future directions
related to this research area.


Date:                   Wednesday, 1 November 2023

Time:                   4:00pm - 6:00pm

Venue:                  Room 5510
                        lifts 25/26

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


**** ALL are Welcome ****