Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/86511
DC FieldValueLanguage
dc.contributorDepartment of Computing-
dc.creatorLi, Pui Hang-
dc.identifier.urihttps://theses.lib.polyu.edu.hk/handle/200/8085-
dc.language.isoEnglish-
dc.titleHistorical traffic-tolerant paths in road networks-
dc.typeThesis-
dcterms.abstractNowadays, 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.accessRightsopen access-
dcterms.educationLevelM.Phil.-
dcterms.extentxvi, 69 pages : illustrations (some color) ; 30 cm-
dcterms.issued2015-
dcterms.LCSHChoice of transportation -- Mathematical models.-
dcterms.LCSHUrban transportation.-
dcterms.LCSHHong Kong Polytechnic University -- Dissertations-
Appears in Collections:Thesis
Show simple item record

Page views

10
Last Week
0
Last month
Citations as of Sep 24, 2023

Google ScholarTM

Check


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