臺灣博碩士論文加值系統

本研究專注於利用無人飛行載具（Unmanned Aerial Vehicle, UAV）在城市街道上收集各種數據，其中包括空氣品質、噪音和電錶等數據。在城市發展和管理中，即時且準確的資料收集非常重要，但在偏遠地區或網路基礎設施薄弱的地方，資料收集面臨著巨大挑戰。相較於過往透過無人地面載具（Unmanned Ground Vehicle, UGV）收集街道數據的方式，利用無人飛行載具進行數據收集將更具靈活性和機動性，因為無人飛行載具能夠飛越建築物來進行街道拜訪。在本研究中，我們將專注於優化無人飛行載具之飛行路徑，最大程度地利用有限的電池容量，在更短的移動路徑下完成數據收集。通過實驗模擬，可以驗證本研究所提出的方法，相較於過往的做法，可以在更短的移動距離下，完成街道數據的收集。

This study focuses on utilizing unmanned aerial vehicles (UAVs) to collect various data on urban streets, including air quality, noise, and electric meter readings. In urban development and management, timely and accurate data acquisition is crucial. However, data collection in remote areas or regions with weak network infrastructure faces significant challenges. Compared to the traditional method of using unmanned ground vehicles (UGVs) to collect street data, UAVs offer greater flexibility and mobility as they can fly over buildings to visit streets. This research aims to optimize the flight paths of UAVs to maximize the use of limited battery capacity and complete data collection with shorter travel distances. Through experimental simulations, the proposed method in this study can be validated to collect street data in a shorter travel distance compared to traditional methods.

摘要 I
Abstract II
誌謝 III
目次 IV
圖目錄 VI
表目錄 VII
第一章　簡介 1
第二章　文獻探討 3
第三章　問題定義及環境假設 5
第四章　方法描述 7
4.1確認奇數度頂點 8
4.2 添加虛擬邊 9
4.3 考慮飛行高度 10
4.4 路徑規劃 13
4.5 時間複雜度分析 15
第五章　演算法與流程 16
第六章　實驗模擬 18
6.1 直角飛行與斜角飛行之比較 19
6.2 城市街道總長度不同之比較 19
6.3 不同分支度數上限之比較 21
6.4 不同街道數量之比較 22
6.5 演算法執行時間之比較 22
第七章　結論 24
參考文獻 25

[1]G. A. Sampedro, F. Dañas, M. Abisado, D. -S. Kim and J. -M. Lee, "Strategic Unmanned Aerial Vehicle (UAV) Routing: An Energy-Efficient Approach," IEEE INFOCOM 2023 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Hoboken, NJ, USA, 2023, pp. 1-5, doi: 10.1109/INFOCOMWKSHPS57453.2023.10225866.
[2]M. Elloumi, R. Dhaou, B. Escrig, H. Idoudi and L. A. Saidane, "Monitoring road traffic with a UAV-based system," 2018 IEEE Wireless Communications and Networking Conference (WCNC), Barcelona, Spain, 2018, pp. 1-6, doi: 10.1109/WCNC.2018.8377077.
[3]A. Goyal, N. Kumar, A. Dua, N. Kumar, J. J. P. C. Rodrigues and D. N. K. Jayakody, "An Efficient Scheme for Path Planning in Internet of Drones,"2019 IEEE Global Communications Conference (GLOBECOM), Waikoloa, HI, USA, 2019, pp. 1-7, doi: 10.1109/GLOBECOM38437.2019.9014305.pp. 1-7, doi: 10.1109/GLOBECOM38437.2019.9014305.
[4]C. -Y. Tsai, J. -P. Sheu and P. -Y. Yi, "UAV-Assisted Routing Algorithm for Truck Parcel Delivery," 2024 IEEE Wireless Communications and Networking Conference (WCNC), Dubai, United Arab Emirates, 2024, pp. 1-6, doi: 10.1109/WCNC57260.2024.10571229.
[5]J. Li, G. Deng, C. Luo, Q. Lin, Q. Yan and Z. Ming, "A Hybrid Path Planning Method in Unmanned Air/Ground Ve-hicle (UAV/UGV) Cooperative Systems," in IEEE Transactions on Vehicular Technology, vol. 65, no. 12, pp. 9585-9596, Dec. 2016, doi: 10.1109/TVT.2016.2623666.
[6]H. Shakhatreh et al., "Unmanned Aerial Vehicles (UAVs): A Survey on Civil Applications and Key Research Challenges," in IEEE Access, vol. 7, pp. 48572-48634,2019,doi:10.1109/ACCESS.2019.2909530.
[7]A. G. Korchenko and O. S. Illyash, "The generalized classification of unmanned air vehicles", Proc. IEEE 2nd Int. Conf. Actual Problems Unmanned Air Vehicles Develop. (APUAVD), pp. 28-34, Oct. 2013.
[8]R. J. Szczerba, P. Galkowski, I. S. Glicktein and N. Ternullo, "Robust algorithm for real-time route planning," in IEEE Transactions on Aerospace and Electronic Systems, vol. 36, no. 3, pp. 869-878, July 2000, doi: 10.1109/7.869506.
[9]K. Mei-ko, Chinese Postman Problem, 1962.
[10]H. Eiselt, M. Gendreau, and G. Larporte, Arc routing problems, part I: the Chinese postman problem, Operations Research 43, 231-242 (1995).
[11]C. Hierholzer and C. Wiener, "Über die möglichkeit einen linienzug ohne wiederholung und ohne unterbrechung zu umfahren", Mathematische Annalen, vol. 6, no. 1, pp. 30-32.
[12]F. H. Tseng, T. T. Liang, C. H. Lee, L. D. Chou and H. C. Chao, "A Star Search Algorithm for Civil UAV Path Planning with 3G Communication," 2014 Tenth International Conference on Intelligent Information Hiding and Multimedia Signal Processing, Kitakyushu, Japan, 2014, pp. 942-945, doi: 10.1109/IIH-MSP.2014.236.
[13]Y. Han and W. Gao, "Research on UAV Multi-Objective Path Planning Problem Based on Optimization Algorithm," 2023 3rd International Conference on Computer Science, Electronic Information Engineering and Intelligent Control Technology (CEI), Wuhan, China, 2023, pp. 861-865, doi: 10.1109/CEI60616.2023.10527848.
[14]U. B. Sayata and N. P. Desai, "An algorithm for Hierarchical Chinese postman problem using minimum spanning tree approach based on Kruskal's algorithm," 2015 IEEE International Advance Computing Conference (IACC), Banglore, India, 2015, pp. 222-227, doi: 10.1109/IADCC.2015.7154702.
[15]H. Kocabas, C. Allred and M. Harper, "Divide and Survey: Observability Through Multi-Drone City Roadway Coverage," 2022 IEEE International Smart Cities Conference (ISC2), Pafos, Cyprus, 2022, pp. 1-7, doi: 10.1109/ISC255366.2022.9922207.
[16]Z. Wang, X. Zhao, Z. Wang and X. Qian, "Carrier-based sensor deployment by a mobile robot for wireless sensor networks," 2012 12th International Conference on Control Automation Robotics & Vision (ICARCV), Guangzhou, China, 2012, pp. 1663-1668, doi: 10.1109/ICARCV.2012.6485429.
[17]V. Roberge, M. Tarbouchi and G. Labonte, "Comparison of Parallel Genetic Algorithm and Particle Swarm Optimization for Real-Time UAV Path Planning," in IEEE Transactions on Industrial Informatics, vol. 9, no. 1, pp. 132-141, Feb. 2013, doi: 10.1109/TII.2012.2198665.
[18]S. Jimbo, "The NP-completeness of Eulerian Recurrent Length for 4-regular Eulerian Graphs," 2014 4th International Conference on Artificial Intelligence with Applications in Engineering and Technology, Kota Kinabalu, Malaysia, 2014, pp. 155-159, doi: 10.1109/ICAIET.2014.34.
[19]L. Eulero, "Solutio problematis ad geometriam situs pertinentis", Com-mentarii Academiae scientiarum imperialis Petropolitanae, vol. 8, pp. 128-140.
[20]H. Barnett, “Early Writings on Graph Theory: Euler Circuits and The Königsberg Bridge Problem,” in Resources for Teaching Discrete Mathematics: Classroom Projects, History Modules, and Articles, B. Hopkins, Ed. Mathematical Association of America, 2009, pp. 197–208