臺灣博碩士論文加值系統

由於路徑規劃對於大眾以及政府在決定路線的重要性逐年提高，本研究提出Patrolling Skyline Path Query，簡稱PSPQ來解決過去鮮少研究討論的巡訪與多條件路徑查詢問題。所謂的巡訪指的是在多次的查詢中行經各個路段。例如下雪中的城市，鏟雪車必須要能夠行經積雪量較多的路段，而這些路段又被稱為巡訪路段，這會導致每一次查詢的結果都不盡相同，且在每一次查詢時都要能有效率的找到積雪量最多的路段。除此之外還必須考慮到每個路段上的條件，例如距離、花費時間或安全性等等。而過往卻沒有一個有效的方法來解決這樣包含巡訪以及多條件路徑的問題。而這類問題會有以下難點(1)要如何快速得找出巡訪路段(2) 多條件路徑查詢上的效率以及產生不合理路徑的問題(3)巡訪路段若需要刻意繞路才能行經時該如何解決。
本研究提出基本近似巡訪天際線路徑查詢演算法與合理近似巡訪天際線路徑演算法，兩演算法來解決此類問題。在基本近似巡訪天際線路徑演算法中我們首先透過佇列的概念建立的一索引模型來快速取得巡訪路段，且避免了多次排序來取得積雪量較高的步驟。而在不同的應用與使用者皆對繞路有不同的容忍值，透過使用者所提供的容忍值，我們建立一子路網來改善傳統天際線路徑的不合理以及效率上的缺陷。在部分的案例中我們並不需要去巡訪過遠的路段，那麼基本近似巡訪天際線路徑查詢演算法所找出的巡訪路段可能會有不合理的情況，因此我們提出合理近似巡訪天際線路徑演算法基於基本近似巡訪天際線路徑查詢演算法之上，此演算法中額外提出挑選合適巡訪路段的方法，此方法基於空間天際線的概念所發展成，最後我們的模擬實驗也印證了合理近似巡訪天際線路徑演算法能在時間以及結果上更有利解決此類問題。

In this study, we formulated a novel route planning query referred to as the Patrolling Skyline Path Query. The term patrolling road refers to situations in which vehicles patrol a particular area and follow particular roads/routes according to a set schedule. For example, roads that require snowplow service are referred to as Patrolling roads. However, identifying these roads can be difficult, due to changes in the accumulation of snow over time and the need to take into account distance and time costs as well as issues related to safety. No existing search mechanism is able to deal with these kinds of variables. The following hard points must be addressed. (1) How can we identify patrolling roads efficiently? (2) How can we boost query speeds? (3) How can we minimize the number of detours?
In this study, we developed two methods to address these issues. The first method uses an index model to reduce the time required to identify roads that have not been serviced for a extended period. We also developed a sub-network of roads to reduce the number of nodes and edges and thereby enhance the efficiency of conventional skyline path queries while prioritizing roads of importance to the largest number of users and taking into account the tolerance of users for detours. We also developed a variation of the proposed method based on the concept of spatial skyline queries to enable the exclusion of some roads from the patrol schedule in order to reduce the overall workload. Simulation results demonstrate that the second method is more efficient with regard to time costs and the accuracy of results.

誌謝 i
摘要 ii
Abstract iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
第二章 相關研究 9
2.1 路徑規劃 9
2.2 多條件路徑 10
2.3 索引模型 11
第三章 定義 13
第四章 基本近似巡訪天際線路徑查詢演算法 15
4.1 取得信心指數低落路段 16
4.2 容忍子路網 18
4.3 改良傳統天際線路徑查詢演算法 22
4.4 APSPQ演算法的例子 25
第五章 合理近似巡訪天際線路徑查詢演算法 27
5.1 利用信心路網天際線找尋合適路段 27
5.2 基於文本相關空間天際線查詢的信心路網天際線 29
5.3 RAPSPQ演算法的例子 31
第六章 實驗模擬 33
6.1 起訖點路網最短距離變化的影響 34
6.2 巡訪路段數量的影響 40
6.3 資料維度的影響 43
6.4 連續APSPQ下的信心指數評估 46
6.5 各階段的花費時間 47
第七章 結論與未來研究 49
參考文獻 50

圖目錄
圖 1.1積雪與鏟雪後雪量示意圖 2
圖 1.2巡訪路徑查詢路網示意圖 2
圖 1.3 PSPQ例子示意圖 4
圖 2.1 片段天際線概念 10
圖 2.2傳統天際線與線性天際線示意圖 11
圖 4.1 APSPQ流程圖 16
圖 4.2路段索引示意圖 17
圖 4.3 MSRN建構中示意圖 19
圖 4.4容忍子路網建構流程圖 20
圖 4.5鄰居點case示意圖 21
圖 4.6片段支配示意圖 23
圖 4.7增加支配空間示意圖 25
圖 4.8 APSPQ例子示意圖 26
圖 5.1 RAPSPQ例子示意圖 28
圖 5.2 RAPSPQ流程圖 28
圖 5.3信心路網天際線概念 28
圖 5.4直線距離與路網距離示意圖 29
圖 6.1 德國奧登堡路網圖[24] 34
圖 6.2起訖點路網最短距離與天際線路徑數量的模擬圖 (a) APSPQ (b) RAPSPQ 35
圖 6.3起訖點最短距離與天際線路徑平均距離的模擬圖 (a)APSPQ (b)RAPSPQ 37
圖 6.4起訖點最短距離與耗費時間的模擬圖 (a)APSPQ (b)RAPSPQ 39
圖 6.5 巡訪路段數與天際線數量的模擬圖 40
圖 6.6 巡訪路段數與天際線路徑平均距離的模擬圖 41
圖 6.7 巡訪路段數與耗費時間的模擬圖 42
圖 6.8維度與天際線路徑數量的模擬圖 43
圖 6.9 維度與天際線路徑平均距離的模擬圖 44
圖 6.10 維度與耗費時間的模擬圖 45
圖 6.11 查詢頻率變化下的路網平均信心指數變化圖 46
圖 6.12 RAPSPQ 各階段花費時間 47

表目錄
表 1.1多屬性路徑示意圖 3
表 1.2 PSPQ例子示意表 4
表4.1更新前路段上的信心指數 17
表 4.2更新後路段上的信心指數 17
表 4.3改善片段支配儲存結構 24
表 5.1信心指數低下路段離起訖點距離與信心指數 31
表 5.2 CRNSQ示意圖 31
表 6.1 模擬實驗設定表 33

[1]Y. Tian, K.-C.-K. Lee, and W.-C. Lee, "Finding skyline paths in road networks," in Proc. ACM Int. Conf. Adv. Geograph. Inf. Syst. (SIGSPATIAL), 2009, pp. 444-447.
[2]H.-P. Kriegel, M. Renz, and M. Schubert, "Route skyline queries: A multipreference path planning approach," in Proc. IEEE Int. Conf. Data Eng. (ICDE), Mar. 2010, pp. 261-272.
[3]X. Chen, H. Cai, and T. Wolf, "Multi-criteria routing in networks with path choices," In Proc. IEEE Int. Conf Network Protocols (ICNP), 2015, pp. 334-344.
[4]Y.-C. Chen and C. Lee "Skyline path queries with aggregate attributes,” in Proc. IEEE Access, Aug. 2016, pp. 4690-4706.
[5]K. Jeddisaravi, R. J. Alitappeh, and F. G. Guimarães "Multi-objective mobile robot path planning based on A* search," in Proc. IEEE Int. Conf. Computer and Knowledge Engineering (ICCKE), 2016, pp. 7-12.
[6]P. Hansen, "Bicriterion Path Problems," Multiple criteria decision making theory and application. Springer, 1980, pp. 109-127.
[7]N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, "The R*-tree: An efficient and robust access method for points and rectangles,'' in Proc. ACM Special Interest Group Manage. Data (SIGMOD), 1990, pp. 322-331.
[8]T. M. Rao, S. Mitra, J. Zollweg, and F. Sahin, "Computing optimal snow plow route plans using genetic algorithms," in Proc. IEEE Int. Conf. Systems, Man and Cybernetics (SMC), Oct. 2011, pp. 2785-2790.
[9]T. M. Rao, S. Mitra, and J. Zollweg, "Route allocation for multiple snowplows using genetic algorithms," in Proc. IEEE Int. Conf. Systems, Man and Cybernetics (SMC), Oct. 2012, pp. 29-34.
[10] M. Sharifzadeh and C. Shahabi, “The spatial skyline queries,” in Proc. 32nd Int. Conf. Very Large Data Bases, 2006, pp. 751-762.
[11]Dijkstra, E. W., "A note on two problems in connexion with graphs," in Numerische Mathematik, 1959, pp. 1:269-271.
[12]Hart, P. E., Nilsson, N. J. and Raphael, B., "A formal basis for the heuristic determination of minimum cost Paths," in Proc. IEEE Transactions on Systems Science and Cybernetics SSC, 1968, pp. 100-107.
[13]S. Anthony, "Optimal and efficient path planning for partially-known environments," in Proc. IEEE Int. Conf. Robotics and Automation, 1994, pp. 3310-3317.
[14]Y. Xun, M. Liu, Y. Zhou, R. Wang and W. Zhang., "Ant colony based on cat swarm optimization and application in picking robot path planning," in Proc. IEEE Int. Conf. Software Engineering and Service Science (ICSESS) 2016, pp. 162-165.
[15]Y.-Z. Cong and S.-G. Ponnambalam, "Mobile robot path planning using ant colony optimization," in Proc. IEEE Int. Conf. Advanced Intelligent Mechatronics, July 2009, pp. 851-856.
[16]R. Rashid, N. Perumal, I. Elamvazuthi, M. K. Tageldeen, M.K.A. Ahamed Khan and S. Parasuraman, "Ant colony based on cat swarm optimization and application in picking robot path planning," in Proc. IEEE Int. Conf. Robotics and Manufacturing Automation (ROMA), 2016, pp. 1-6.
[17]K.Liu, and M. Zhang, "Path planning based on simulated annealing ant colony algorithm," in Proc. IEEE Int. Conf. Symposium on Computational Intelligence and Design (ISCID), 2016, pp. 461-466.
[18]S. Borzsony, D. Kossmann, and K. Stocker, "The skyline operator,'' in Proc. IEEE 17th Int. Conf. Data Eng. (ICDE), Apr. 2001, pp. 421-430.
[19]M. Shekelyan, G. Jossé and M. Schubert, "Linear path skylines in multicriteria networks," in Proc. IEEE Int. Conf. Data Eng. (ICDE), 2015, pp. 459-470.
[20]S. Saltenis, C.-S. Jensen, S.-T. Leutenegger, and M.-A. Lopez, "Indexing the Positions of Continuously Moving Objects," in Proc. ACM Special Interest Group Manage. Data (SIGMOD), 2000, pp. 331-342.
[21]H. Zhang, Y. Yan, G. Yang and X. Tan, "Multi-Approximation based Time-Parameterized moving objects R-tree," in Proc IEEE Int. Conf. on Communication Technology, 2013, pp. 733-737.
[22]R. Zhong, G. Li, K.-L. Tan, L. Zhou, and Z. Gong, "G-tree: An efficient index for knn search on road networks,” in Proc IEEE Trans. Knowl. Data Eng., Aug. 2015, pp. 2175-2189.
[23]Shi, J., Wu, D., Mamoulis, N.: "Textually relevant spatial skylines," in Proc IEEE Trans. Knowl. Data Eng., 2016, 224-237.
[24]Real Datasets for Spatial Databases: Road Networks and Points of Interest, "City of Oldenburg (OL) Road Network", URL: https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm