A machine learning-based approach to time-dependent shortest path queries
Road traffic is known to be time-dependent. The travel time of a road varies at different times of the day. Many algorithms have been proposed for finding a shortest path in a time-dependent road network. In this project, I explored an alternative approach that leveraged on GPS trajectories colle...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project |
| Language: | English |
| Published: |
2017
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/70473 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | Road traffic is known to be time-dependent. The travel time of a road varies at
different times of the day. Many algorithms have been proposed for finding a shortest
path in a time-dependent road network. In this project, I explored an alternative
approach that leveraged on GPS trajectories collected from thousands of taxis. Each
GPS trajectory was mapped to a set of real road segments. An abstract landmark
graph was built to represent the city’s road network and a machine learning-based
approach was proposed to estimate the travel time of each edge. The estimates
made by this approach were compared against real-time estimates made by existing
online mapping services to evaluate its accuracy. A modified Dijkstra’s algorithm was
presented to calculate a shortest path in a time-dependent landmark graph, based on
the travel time estimates. |
|---|