無人機展演的過程由轉場及展演交錯而成，展演時，根據腳本中的圖形設計可得 知需要無人機亮燈的座標位置，而除了在各個展演畫面變換的過程中避免無人機互相 撞擊之外，由於無人機的電池續航力的限制，需要在電池耗盡前返回地面充換電。因 此，如何經由適妥的路徑規劃，讓表演順暢進行、降低整個表演的總消耗電量，並有 效地減少成本支出，將會是無人機展演所面臨的重要議題。然而傳統上，無人機展演 的路徑規劃主要是以程式輔助逐一檢驗各架無人機之飛行路徑，檢驗其與它架無人機 飛行路徑是否全程保持安全距離，若有需要只能以人工手動方式調整，也因此容易顧 此失彼，難以兼顧全局，其規劃與調整過程十分費時耗力，又無法保證求解品質。
本研究將無人機的電池續航力限制、展演座標上可進行移動的路徑、以及腳本中 預計亮燈之時刻與座標位置等設定視為已知，以層空網路為架構，將燈光秀過程分為 「展演」與「轉場」等兩類互相交錯的時間區段，建立整數規劃模式以規劃無人機在 展演時段的位置及轉場時段的飛行路線，期望在考量無人機行進間安全距離的前提下， 用最少的能量耗費以及無人機架數來完成演出。
相較於現行無人機群飛展演所採用的人工編排路徑規劃方式，本研究提出的整 數規劃模式可根據展演腳本計算出理論上耗能最少且具安全距離保證的無人機群路 線規劃方式，然而此精確解法求解十分耗時，因此我們針對現實較大規模的展演再設 計滾動式求解機制與貪婪演算法等兩種啟發式演算法機制以加速求解。由多組不同情 境的數值模擬測試結果中，我們觀察到貪婪演算法求解極快但可能啟用較多架無人機， 而滾動式求解機制則以整數規劃模式為基礎，兼顧求解效率與品質，是具學理根據的 系統性創新作法，特別推薦給相關展演業者及學術研究，用於規劃考量安全距離的無 人機展演群飛路線。

This research investigates a path planning problem for a fleet of drones making a light show. In particular, assuming that the figures in the light show are known beforehand, we need to deploy at least a drone in specific locations in the sky at a particular time. To the best of our knowledge, this problem is solved manually in practice. We propose an integer program (IP) based on a time-space network to calculate the movements for each drone with the minimum costs, including the fixed equipment costs and the total flying distance. We divide the entire show period into two types: the show period and the transition period, where the former displays the figures, and the latter is used for drones to transit to new positions in the sky. However, our IP model is too time-consuming. We, consequently, introduce a greedy heuristics algorithm that can calculate a good solution in a much shorter time. In addition, we propose a rolling horizon mechanism, which divides the entire planning horizon into smaller ones and then consecutively solves each IP model of a shorter planning horizon. The proposed mechanism is efficient and effective in our computational experiments.

中文
工研院無人機講座 揭示台灣產業發展路向 (民 107 年 9 月 27 日)。民 108 年 8 月 5 日，取自 https://dronesplayer.com/drone-use/工研院無人機講 座-揭示台灣產業發展路向
馬哈曼(2019)。執行區域覆蓋任務之可充換電無人機及其載具之最佳聯合 路線規劃問題研究。國立成功大學工業與資訊管理碩士論文。取自 http://etds.lib.ncku.edu.tw/html/
陳冠㞶(2016)。基於多目標演化式演算法的視角可調之無人機路徑規劃。 中華大學資訊工程碩士論文。取自 https://hdl.handle.net/11296/qvcnrg
陳彥瑋(2020)。考量靜態標靶節線偵測機率之搜救隊與無人機群最佳協同搜救路線規劃研究。國立成功大學工業與資訊管理碩士論文。取自 http://etds.lib.ncku.edu.tw/html/
無人機送貨趨勢全球市場規模展望 (DIGITIMES 整理) ，取自 https://digitimes.com.tw/tech/showimg.asp?source=&filename=548634-1- K92NX.jpg&Sourcetype=1&newskey=548634
黃慧雯 (民 108 年 2 月 20 日)。屏東燈會 Intel 神助攻 無人機排出 TAIWAN 閃耀天空。中時電子報。民 108 年 8 月 5 日，取自 https://www.chinatimes.com/realtimenews/20190220001470-260412
蔡成鴻(2020)。考慮電量耗損之無人機群飛展演最佳群飛路徑規劃研究。 國立成功大學工業與資訊管理在職專班碩士論文。取自 http://etds.lib.ncku.edu.tw/html/
劉禹慶 (民 108 年 4 月 10 日)。澎湖花火節 22 場次主打無人機表演。自由 時 報 。 民 108 年 8 月 5 日 ， 取 自 https://news.ltn.com.tw/news/local/paper/1280418

英文
Chen, Y.K., Wang, Y.C., Chen, X.Y., Han, J.X.(2018).Research on the Flight Path of the Drones Based on the 0-1 Linear Programming Model for the Light Show. International Conference on Mechanical, Electronic and Information Technology, 172-175. doi: 10.12783/dtetr/icmeit2018/23404
He, L., Bai, P., Liang, X., Zhang, J., Wang, W.(2018).Feedback formation control of UAV swarm with multiple implicit leaders. Aerospace Science and technology, 72, 327-334.doi: 10.1016/j.ast.2017.11.020
Huang, C. X., Lan, Y. S., Liu, Y. C., Zhou, W., Pei, H. B., Yang, L. Z., & Peng, Y. H. (2018). A New Dynamic Path Planning Approach for Unmanned Aerial Vehicles. Complexity, 17,doi:10.1155/2020/6549572.
Luo, Z., Liu, Z., & Shi, J. (2017). A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle, Sensors, vol. 17, no. 5, pp. 1-17.
Majd, A., Loni, M., Sahebi, G., & Daneshtalab, M. (2020). Improving motion safety and efficiency of intelligent autonomous swarm of drones. Drones, 4(3), 48, doi: 10.3390/drones4030048
Mor, A., & Speranza, M. G. (2020). Vehicle routing problems over time: a survey. 4OR. doi:10.1007/s10288-020-00433-2.
Oz, I., Topcuoglu, H. R., & Ermis, M. (2013). A meta-heuristic based three- dimensional path planning environment for unmanned aerial vehicles. Simulation-Transactions of the Society for Modeling and Simulation International, 89(8), 903-920.
Prats, X., Delgado, L., Ramirez, J., Royo, P., & Pastor, E. (2012). Requirements, issues, and challenges for sense and avoid in unmanned aircraft systems. Journal of aircraft, 49(3), 677-687, doi: 10.2514/1.C031606
Ropero, F., Muñoz, P., & R-Moreno, M. D. (2019). Terra: A path planning algorithm for cooperative ugv-uav exploration. Engineering Applications of Artificial Intelligence, 78, 260–272.
Schneider, M., & Drexl, M. (2017). A survey of the standard location-routing problem. Annals of Operations Research, 259(1-2), 389– 414. doi:10.1007/s10479-017-2509-0
Sun, H., Qi, J., Wu, C., Wang, M.(2020).Path Planning for Dense Drone Formation Based on Modified Artificial Potential Field.Proceeding of the 39th Chinese Control Conference. 4658-4664. doi:10.23919/CCC50068.2020.9189345
Wang, X., Yadav, V., & Balakrishnan, S. N. (2007). Cooperative UAV formation flying with obstacle/collision avoidance. IEEE Transactions on control systems technology, 15(4), 672-679, doi: 10.1109/TCST.2007.899191
Yilmaz, O., Yakici, E., & Karatas, M. (2019). A UAV location and routing problem with spatio-temporal synchronization constraints solved by ant colony optimization. Journal of Heuristics, 25(4-5), 673-701.
Yu, K., Budhiraja, A. K., Buebel, S., & Tokekar, P. (2019). Algorithms and experiments on routing of unmanned aerial vehicles with mobile recharging stations. Journal of Field Robotics, 36(3), 602-616.