東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Design of a data model and algorithm...

Indriasari, Vini.

FindBook

Google Book

Amazon

博客來

Design of a data model and algorithm for time-dependent shortest paths.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Design of a data model and algorithm for time-dependent shortest paths./
作者:	Indriasari, Vini.
面頁冊數:	110 p.
附註:	Source: Dissertation Abstracts International, Volume: 76-10(E), Section: B.
Contained By:	Dissertation Abstracts International76-10B(E).
標題:	Geographic information science and geodesy. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3706611
ISBN:	9781321806410

Design of a data model and algorithm for time-dependent shortest paths.
Indriasari, Vini.

Design of a data model and algorithm for time-dependent shortest paths. - 110 p.

Source: Dissertation Abstracts International, Volume: 76-10(E), Section: B.

Thesis (Ph.D.)--The University of Texas at Dallas, 2015.

This item is not available from ProQuest Dissertations & Theses.

This study focuses on the design of a data model and algorithm for time-dependent shortest paths (TDSPs). The shortest paths were defined in terms of travel times. Various speed-up techniques have been introduced for static shortest paths (SSPs). Unfortunately, many of these techniques are not applicable for TDSP, especially techniques that require various types of pre-computation. Therefore, this study introduced a new TDSP technique that is able to produce solutions on large networks in a reasonable time without requiring pre-computation, namely the Minimum Step Linkage (MSL) algorithm. This algorithm works with a data model called Cumulative Cost Model (CCM). This model merges continuous edges with common attribute values into links to reduce the network size. Then, network impedances are modeled by simulating a movement of a vehicle along the road. This model accumulates impedances of edges associated with the links to speed up the cost computation. The MSL estimates TDSPs by evaluating a delay function in the SSPs. It considers the minimum steps between links and links' levels to find a path. When a long delay is encountered in a link along the path, the algorithm will alter the path iteratively by avoiding the delayed link. The MSL was tested through a simulation. Its solution quality and performances were compared against TD-A* and TD-Dijkstra. After the edges were merged into links, the network size was reduced by 68.96%. Results showed that the more edges in a path, the smaller percent of links relative to edges. Solutions of TD-A* in general were better than those of the MSL. Within 99% of cases, TD-A* had errors close to zero, while errors of the MSL ranged from 0 to 0.5. In terms of runtime, the MSL was relatively constant for any given distance between the origin and destination, while TD-A* and TD-Dijkstra tended to run longer when the distance increased. Runtime of TD-Dijkstra increased more rapidly than TD-A* did. Results on time complexity showed similar trends to results on runtime. Judging from these trends, the MSL will likely run faster than TD-A* and TD-Dijkstra for larger networks.

ISBN: 9781321806410Subjects--Topical Terms:

2122917
Geographic information science and geodesy.

Design of a data model and algorithm for time-dependent shortest paths.
LDR:03116nmm a2200301 4500 001 2069006
005 20160507120459.5
008 170521s2015 ||||||||||||||||| ||eng d
020 $a 9781321806410
035 $a (MiAaPQ)AAI3706611
035 $a AAI3706611
040 $a MiAaPQ $c MiAaPQ
100 1 $a Indriasari, Vini. $3 3183986
245 1 0 $a Design of a data model and algorithm for time-dependent shortest paths.
300 $a 110 p.
500 $a Source: Dissertation Abstracts International, Volume: 76-10(E), Section: B.
500 $a Adviser: Denis Dean.
502 $a Thesis (Ph.D.)--The University of Texas at Dallas, 2015.
506 $a This item is not available from ProQuest Dissertations & Theses.
520 $a This study focuses on the design of a data model and algorithm for time-dependent shortest paths (TDSPs). The shortest paths were defined in terms of travel times. Various speed-up techniques have been introduced for static shortest paths (SSPs). Unfortunately, many of these techniques are not applicable for TDSP, especially techniques that require various types of pre-computation. Therefore, this study introduced a new TDSP technique that is able to produce solutions on large networks in a reasonable time without requiring pre-computation, namely the Minimum Step Linkage (MSL) algorithm. This algorithm works with a data model called Cumulative Cost Model (CCM). This model merges continuous edges with common attribute values into links to reduce the network size. Then, network impedances are modeled by simulating a movement of a vehicle along the road. This model accumulates impedances of edges associated with the links to speed up the cost computation. The MSL estimates TDSPs by evaluating a delay function in the SSPs. It considers the minimum steps between links and links' levels to find a path. When a long delay is encountered in a link along the path, the algorithm will alter the path iteratively by avoiding the delayed link. The MSL was tested through a simulation. Its solution quality and performances were compared against TD-A* and TD-Dijkstra. After the edges were merged into links, the network size was reduced by 68.96%. Results showed that the more edges in a path, the smaller percent of links relative to edges. Solutions of TD-A* in general were better than those of the MSL. Within 99% of cases, TD-A* had errors close to zero, while errors of the MSL ranged from 0 to 0.5. In terms of runtime, the MSL was relatively constant for any given distance between the origin and destination, while TD-A* and TD-Dijkstra tended to run longer when the distance increased. Runtime of TD-Dijkstra increased more rapidly than TD-A* did. Results on time complexity showed similar trends to results on runtime. Judging from these trends, the MSL will likely run faster than TD-A* and TD-Dijkstra for larger networks.
590 $a School code: 0382.
650 4 $a Geographic information science and geodesy. $3 2122917
650 4 $a Computer science. $3 523869
650 4 $a Operations research. $3 547123
690 $a 0370
690 $a 0984
690 $a 0796
710 2 $a The University of Texas at Dallas. $b Geospatial Information Sciences. $3 3183987
773 0 $t Dissertation Abstracts International $g 76-10B(E).
790 $a 0382
791 $a Ph.D.
792 $a 2015
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3706611