Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/86511
| DC Field | Value | Language |
|---|---|---|
| dc.contributor | Department of Computing | - |
| dc.creator | Li, Pui Hang | - |
| dc.identifier.uri | https://theses.lib.polyu.edu.hk/handle/200/8085 | - |
| dc.language.iso | English | - |
| dc.title | Historical traffic-tolerant paths in road networks | - |
| dc.type | Thesis | - |
| dcterms.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. | - |
| dcterms.accessRights | open access | - |
| dcterms.educationLevel | M.Phil. | - |
| dcterms.extent | xvi, 69 pages : illustrations (some color) ; 30 cm | - |
| dcterms.issued | 2015 | - |
| dcterms.LCSH | Choice of transportation -- Mathematical models. | - |
| dcterms.LCSH | Urban transportation. | - |
| dcterms.LCSH | Hong Kong Polytechnic University -- Dissertations | - |
| 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.