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 |
id |
sg-ntu-dr.10356-70473 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-704732023-03-03T20:25:09Z A machine learning-based approach to time-dependent shortest path queries Wei, Yumou Xiao Xiaokui School of Computer Science and Engineering DRNTU::Engineering::Computer science and engineering 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. Bachelor of Engineering (Computer Science) 2017-04-25T01:35:51Z 2017-04-25T01:35:51Z 2017 Final Year Project (FYP) http://hdl.handle.net/10356/70473 en Nanyang Technological University 76 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
DRNTU::Engineering::Computer science and engineering |
spellingShingle |
DRNTU::Engineering::Computer science and engineering Wei, Yumou A machine learning-based approach to time-dependent shortest path queries |
description |
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. |
author2 |
Xiao Xiaokui |
author_facet |
Xiao Xiaokui Wei, Yumou |
format |
Final Year Project |
author |
Wei, Yumou |
author_sort |
Wei, Yumou |
title |
A machine learning-based approach to time-dependent shortest path queries |
title_short |
A machine learning-based approach to time-dependent shortest path queries |
title_full |
A machine learning-based approach to time-dependent shortest path queries |
title_fullStr |
A machine learning-based approach to time-dependent shortest path queries |
title_full_unstemmed |
A machine learning-based approach to time-dependent shortest path queries |
title_sort |
machine learning-based approach to time-dependent shortest path queries |
publishDate |
2017 |
url |
http://hdl.handle.net/10356/70473 |
_version_ |
1759856535998038016 |