臺灣博碩士論文加值系統

近年來科技如火如荼的發展，智慧型手機、導航等技術也越來越成熟，許多產業也慢慢與科技結合。不管是旅遊、物流業者或是外送平台，路徑規劃的演算法在上述這些應用都扮演相當重要的角色。有許多相關的文獻也著重在拜訪點的路徑規劃，但大多是有指定起始點與終點以及沒有考慮到交通狀態的做法。本篇論文在獲得較短旅行距離與旅行時間方面分別提出不同的方法，距離方面提出兩種利用拜訪點配對與路段連接的演算法，時間方面建立交通狀態模型考量道路暢通、車多、壅塞三種情況，提出考量交通狀態的路徑規劃演算法。三種方法能夠有效降低因採用貪婪演算法而容易產生區域最佳化的問題。實驗結果顯示，距離方面，固定拓樸下與FCFS相比後本論文提出的方法能夠節省的距離約60~99%，隨機拓樸則能省下30%~45%。時間方面，固定拓樸並以拜訪點數量為變數時，與FCFS相比後本論文提出的方法能夠節省的時間約35~70%，隨機拓樸則能省下13%~20%。固定拓樸並以拜訪點停留時間為變數時，與FCFS相比能夠節省的時間約57%~71%，隨機拓則能省下13%~20%。在離峰與尖峰時段的比較中，離峰時段與FCFS相比能夠省下的時間約36%~70%，尖峰時段則能省下約46~98%。

Information technologies have rapidly developed on the smartphone. The navigation requirements for route planning have increased in traveling scheduling and the delivery platforms of the logistics companies. Many previous studies are proposed for route planning, but most of them focus on shortening the path between the start and end visit points without considering the traffic conditions.
This thesis proposes different approaches for shortening traveling distance and time. Two methods are proposed for reducing the length of distance. They utilized the pairing of visit points with road sections. This thesis gives a traffic model that considers the traffic congestion status to shorten the traveling time. One of the proposed methods is according to this model.
All proposed algorithms can effectively reduce the opportunity to find the local optimal routes which appear in the greedy algorithms. The experimental results show that the traveling distance saved by the proposed method is about 60% to 99% compared with the FCFS method in the fixed topology scenario and is about 30% to 45% in the random topology scenario. The traveling time in the fixed topology scenario can save 35-70% compared with the FCFS and 13%-20% in the random topology scenario. With different staying times on visit points, the time is saved 57%-71% and 13%-20%compared with the FCFS in these two topology cases. In the off-peak duration, the saved time is about 36%-70% compared to FCFS and in the rush hour is about 46%-98%.

中文摘要 .....i
英文摘要 .....ii
誌謝 .....iii
目錄 .....iv
表目錄 .....v
圖目錄 .....vii
符號說明 .....viii
第一章 簡介.....1
1.1 研究背景.....1
1.2 研究動機.....3
1.3 研究目的.....4
1.4 論文架構.....4
第二章 相關研究與文獻探討.....5
第三章 研究方法.....10
3.1 場景架設與假設.....10
3.2 問題描述.....11
3.3 給定拜訪點找出較短路徑.....12
3.3.1 獲得較短的旅行距離.....12
3.3.1.1 分段生成連接路徑規劃演算法.....12
3.3.1.2 離散式最小路段生成路徑規劃演算法.....15
3.3.2 獲得較少的旅行時間.....20
3.3.2.1 交通狀態路徑規劃演算法.....20
第四章 模擬與實驗結果.....26
4.1 模擬環境假設.....26
4.1.1 假設環境條件.....26
4.1.2 模擬環境參數.....26
4.2 實驗結果.....30
第五章 結論與未來展望.....62
參考文獻 .....63
Extended Abstract.....65

[1]交通部觀光局 (2021, March 24). 109年觀光統計年報 [Online].Available：https://admin.taiwan.net.tw/
[2]交通部觀光局 (2021, February 24).近三年觀光收支統計[Online]. Available：https://admin.taiwan.net.tw/
[3]Ettoday新聞雲 (2020 June 25) 史上最久連塞32小時！端午報復出遊 [Online].Available：https://www.ettoday.net/news/20200625/1746550.htm
[4]蘋果新聞網 (2020 October 10) 43萬人湧台南看國慶焰火散場大塞車！ [Online].Available：https://tw.appledaily.com/life/20201010/QCVTHO5HERESRMRZEBP2YI3LZA/
[5]聯合新聞網 (2021 January 29) 叫foodpanda嫌太久男吃免費餐點出手毆打外送員 [Online].Available：https://udn.com/news/story/7320/5214766
[6]聯合新聞網 (2021 January 5) 林口顧客和外送員起衝突 兩人刀槍相見釀一傷 [Online].Available：https://udn.com/news/story/7320/5148505
[7]星島日報(2017 November 11) 塞車造成心理壓力日積月累礙健康 [Online].Available：https://www.singtao.ca/1410990/2017-11-11/post-塞車造成心理壓力-日積月累礙健康/?variant=zh-hk
[8]A. Silberschatz, P. B. Galvin, G. Gagne, (2014), 作業系統概念, 9th edition, 東華書局。
[9]H. Azis, R. Mallongi, D. Lantara, and Y. Salim, “Comparison of Floyd-Warshall Algorithm and Greedy Algorithm in Determining the Shortest Route”, in proceeding of 2018 2nd East Indonesia Conference on Computer and Information Technology(EIConCIT), Makassar, Indonesia, 6-7 Nov. 2018, pp. 294-298.
[10]M. Zhao, T. W. S. Chow, K. F. Tsang, “Vehicle route planning for logistics network optimization via multiple spanning tree”, in proceeding of 2016 IEEE 14th International Conference on Industrial Informatics (INDIN), Poitiers, France, 19-21 July 2016, pp. 800-805.
[11]L. Cao, J. Tao and B. Chen, "Implementation of Personalized Scenic Spots Route Recommendation System," 2018 13th International Conference on Computer Science & Education (ICCSE), Colombo, Sri Lanka, 8-11 Aug. 2018, pp. 1-6.
[12]R. Xu, D. Miao, L. Liu, J. Panneerselva, “An Optimal Travel Route Plan for Yangzhou Based on the Improved Floyd Algorithm”, in proceeding of 2017 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), Exeter, UK, 21-23 June 2017, pp. 168-176.
[13]S. Liu and Y. Ma, "Research for Bidirectional Path Planning Based on An Improved A* Algorithm," 2020 IEEE International Conference on Advances in Electrical Engineering and Computer Applications( AEECA), Dalian, China , 25-27 Aug. 2020, pp. 1036-1039.
[14]E. H. Lu, H. Chen and V. S. Tseng, "An Efficient Framework for Multirequest Route Planning in Urban Environments," in IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 4, pp. 869-879, April 2017,
[15]I. M. Ari Santosa, N. Nyoman Utami Januhari, I. P. Ramayasa and I. Ketut Dedy Suryawan, "Comparison of Sweep and Tabu Search Methods in Searching for Item Delivery Routes based on Volume," 2019 1st International Conference on Cybernetics and Intelligent System (ICORIS), Denpasar, Indonesia, 22-23 Aug. 2019, pp. 257-262.
[16]K. Shi, H. Zhang, Z. Zhang and X. Zhou, "The Algorithm of Terminal Logistics Path Planning Based on TSP Problem," 2020 International Conference on Artificial Intelligence and Computer Engineering (ICAICE), Beijing, China, 23-25 Oct. 2020, pp. 130-133.
[17]Z. Song, H. Duan, S. Zhou, and X. Qiu, “Urban route planning considering traffic flows”, in proceeding of 2015 Chinese Automation Congress, Wuhan, China, 27-29 Nov. 2015, pp. 1940-1944.
[18]C. Agustina, Sardiarinto, D. A. Ambarsari, E. Rahmawati and A. Fauzi, "Optimization of Tourism Route “Balkondes Tour” in Borobudur using the Greedy Algorithm," 2019 7th International Conference on Cyber and IT Service Management (CITSM), Jakarta, Indonesia, 6-8 Nov. 2019, pp. 1-5, doi: 10.1109/CITSM47753.2019.8965397.
[19]W. Xu and J. Zhao, "Research on Traffic Flow Time Series Model and Shortest Path Algorithm of Urban Traffic Based on Travel Plans," 2019 International Conference on Intelligent Computing, Automation and Systems (ICICAS), Chongqing, China , 6-8 Dec. 2019, pp. 369-373.
[20]Z. Wu, X. Wan and R. Lin, "Multi-objective Route Planning Based on Improved K-means Algorithm," 2018 IEEE 18th International Conference on Communication Technology (ICCT), Chongqing, China, 8-11 Oct. 2018, pp. 1280-1285.
[21]A. Lobo, K. Hariharan, S. Sreekumar, M. N. Shetty, “Time Optimal Long Distance Trip Planning for Electric Vehicles”, in proceeding of 2019 5th International Conference On Computing, Communication, Control And Automation (ICCUBEA), Pune, India, 19-21 Sept. 2019, pp. 1-4, doi: 10.1109/ICCUBEA47591.2019.9129188.
[22]B. Huang, Y. Yu, J. Zheng, S. Su, Z. He and H. Zhou, "Delivery Route Optimization for Electric Logistics Vehicles based on Full Information Acquisition," 2020 IEEE 4th Conference on Energy Internet and Energy System Integration (EI2), Wuhan, China, 30 Oct.-1 Nov. 2020, pp. 3457-3462.
[23]Y. Ruotong, Y. Jiayi and L. Qian, "Research on Optimization of Car-hailing Driving Route based on Short-term Traffic Speed," 2021 6th International Conference on Inventive Computation Technologies (ICICT), Coimbatore, India , 20-22 Jan. 2021, pp. 1017-1024.
[24]C. Chen, D. Zhang, B. Guo, X. Ma, G. Pan, and Z. Wu, “TripPlanner：Personalized Trip Planning Leveraging Heterogeneous Crowdsourced Digital Footprints”, IEEE Transactions on Intelligent Transportation Systems, Vol. 16, Issue. 3, pp. 1259-1273, June 2015.
[25]Y. Xu, T. Hu, and Y. Li, “A travel route recommendation algorithm with personal preference”, in proceeding of 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), Changsha, China, 13-15 Aug. 2016, pp. 390-396.
[26]W. Zhou, L. Zheng, Y. Wu, Y. Wang and D. Cui, "Optimization Algorithm of Battlefield Medicinal Materials Distribution Route Planning," 2020 IEEE International Conference on Mechatronics and Automation (ICMA), Beijing, China, 13-16 Oct. 2020, pp. 1293-1298.