Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/35194
Title: Historical traffic-tolerant paths in road networks
Authors: Li, Pui Hang
Keywords: Choice of transportation -- Mathematical models.
Urban transportation.
Issue Date: 2015
Publisher: The Hong Kong Polytechnic University
Abstract: Nowadays, with the extensive installation of roadside sensors and the advance-ment of mobile technology, historic traffic information is widely collected. It is valuable in transportation analysis and planning, e.g., evaluating the reliability of routes for representative source-destination pairs. Also, it can be utilized to provide efficient and effective route-search services. In view of these applications, this thesis proposes the traffic-tolerant path (TTP) problem in road networks. The problem takes an integer k, a source-destination (SD) pair, and historic traffic information as input, and returns k paths that minimize the aggregate historic travel time. Unlike the shortest path problem, the TTP problem has a combinatorial search space that renders the optimal solution expensive to com-pute. First, we prove the NP-hardness of the TTP problem. Second, we propose an exact algorithm with effective pruning rules to reduce the search time. Third, we develop an anytime heuristic algorithm that makes 'best-effort' to find a low-cost solution within a given time limit. Extensive experiments on real and synthetic traffic data demonstrate the effectiveness of TTPs and the efficiency of our proposed algorithms.
Description: PolyU Library Call No.: [THS] LG51 .H577M COMP 2015 LiP
xvi, 69 pages :illustrations (some color) ;30 cm
URI: http://hdl.handle.net/10397/35194
Rights: All rights reserved.
Appears in Collections:Thesis

Files in This Item:
File Description SizeFormat 
b28163631_link.htmFor PolyU Users203 BHTMLView/Open
b28163631_ir.pdfFor All Users (Non-printable)1.69 MBAdobe PDFView/Open
Show full item record

Page view(s)

45
Last Week
2
Last month
Checked on May 21, 2017

Download(s)

24
Checked on May 21, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.