Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/86511
Title: | Historical traffic-tolerant paths in road networks | Authors: | Li, Pui Hang | Degree: | M.Phil. | Issue Date: | 2015 | 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. | Subjects: | Choice of transportation -- Mathematical models. Urban transportation. Hong Kong Polytechnic University -- Dissertations |
Pages: | xvi, 69 pages : illustrations (some color) ; 30 cm |
Appears in Collections: | Thesis |
Access
View full-text via https://theses.lib.polyu.edu.hk/handle/200/8085
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.