隨著傳感和無線通信技術的進步，以遠端遙控的無人船隊（USV）可取代人力駕船方式，在特殊（譬如易擱淺、觸礁）的水域巡航以執行搜尋或科研任務。當USV的航線可進行標靶區域的任務時，該標靶區域即可視為被「覆蓋」，獲取其任務效果。假設水域中有多個標靶區域散佈四處，若能有效地規劃多台 USV 路線以同時巡航，將能在更短時間內完成更多的區域覆蓋任務以獲取最大的任務效果。然而， USV 體積小、續航力短，必須與其被搭載的母船(PB)會合才能進行充換電以重新出發。因此，母船的路線也應一併規劃才能發揮最大綜效。
本論文即探討在時限內能獲取最大任務效果的子母船聯合覆蓋路徑規劃問題，首先我們先針對母船之航線已知（但時程未知）的簡化版問題設定，建構一個以時空網路為基礎的整數規劃模型，由於該模型含有大量變數與限制式，僅能處理極小規模的情境，因此我們再以分進合擊的方式將分佈四處之標靶區域劃分成合適個數的分群任務區域，而各區域再以整數規劃模型(ICH)或局部搜尋演算法(ILS)分別處理，最後再串接母船航線。此簡化問題的測試結果顯示，ILS演算法效率極佳，但ICH模型僅適用於標靶必須較均勻分佈的情境。之後，我們再進一步將PB路線設成未定，亦建構整數規劃模型、修改ICH與ILS演算法，並設計「分段式啟發演算法」(SSH)，將規劃期間切成數個時段，再依序處理規模較小的整數規劃問題以串接成最後決策。測試結果顯示 SSH 與 ILS 皆有不錯之求解表現。

Due to improvements in sensing and wireless communication technology, a fleet of unmanned surface vehicles (USVs) can now be used to search water areas for the purpose of carrying out multiple targeted operations. Specifically, multiple USVs can conduct search tasks simultaneously. However, due to its limited battery or fuel capacity, a USV requires recharging (or refueling) or battery swapping to continue longer range missions. Thus, we propose a mechanism in which USVs can depart from and return to a parent boat (PB) for recharging and data collection.
Assuming each target has a value of importance, this thesis investigates how to calculate optimal routes for both PB and USVs so that USVs can cover all the target areas, with the total target values as the objective for operating in a limited amount of time. We propose an integer programming formulation on a time-space network for cases of a given PB path (C1) and the case where the PB path is not yet known (C2), based on techniques similar to the coverage path planning (CPP), the orienteering problem, and the two-echelon routing problem in the literature. Although mathematical formulations can be used to solve the problem, this is quite time-consuming.
We thus designed three methods to solve the problems related to calculating good routings in a shorter time. The first method is the Iterative Clustering Heuristic (ICH) based on the clustering technique, which was intended to limit the workspace for each USV. The second method is the Iterative Local Search (ILS) algorithm based on multiple local search procedures, which was intended to further shorten the computational results. The third method is the Sequential Segmentation Heuristic (SSH), which is based on the segmentation process and was intended to limit the time-bound in each segment. The results of our preliminary computational experiments for both cases and a real-world scenario problem setting indicate that the proposed solution methods can calculate good search plans faster than the proposed integer programming model.

Avellar, G., Pereira, G., Pimenta, L., & Iscold, P. (2015). Multi-UAV Routing for Area Coverage and Remote Sensing with Minimum Time. Sensors, 15(11), 27783-27803. doi:10.3390/s151127783
Campbell, S., Naeem, W., & Irwin,G. (2012). A review on improving the autonomy of unmanned surface vehicles through intelligent collision avoidance maneuvers. Annual Reviews in Control, vol. 36, No. 2, pp. 267-283.
Carlsson, J. G., & Song, S. (2017). Coordinated Logistics with a Truck and a Drone. Management Science, 64(9), 4052-4069. doi:10.1287/mnsc.2017.2824
Cuda, R., Guastaroba, G., & Speranza, M. G. (2015). A survey on two-echelon routing problems. Comput. Oper. Res., 55(C), 185-199. doi:10.1016/j.cor.2014.06.008
Cruz Chávez, M., Rodríguez-León, A., Rivera-Lopez, R., & Cruz-Rosales, M. (2019). A Grid-Based Genetic Approach to Solving the Vehicle Routing Problem with Time Windows. Applied Sciences, 9, 1. doi:10.3390/app9183656
Dallard, H., Lam, S. S., & Kulturel-Konak, S. (2007, 13-15 Aug. 2007). Solving the Orienteering Problem Using Attractive and Repulsive Particle Swarm Optimization. Paper presented at the 2007 IEEE International Conference on Information Reuse and Integration.
El-Hajj, R., Dang, D.-C., & Moukrim, A. (2016). Solving the Team Orienteering Problem with Cutting Planes. Computers & Operations Research, 74. doi:10.1016/j.cor.2016.04.008
Ferrandez, S. M., Harbison, T., Weber, T., Sturges, R., & Rich, R. (2016). Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. Journal of Industrial Engineering and Management, 9(2), 15. Retrieved from http://inis.iaea.org/search/search.aspx?orig_q=RN:48050833.
Fu, Z., Yu, J., Xie, G., Chen, Y., & Mao, Y. (2018). A Heuristic Evolutionary Algorithm of UAV Path Planning. Wireless Communications and Mobile Computing, 2018, 1-11. doi:10.1155/2018/2851964
Galceran, E., & Carreras, M. (2013). A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 61(12), 1258-1276. doi:10.1016/j.robot.2013.09.004
Garone, E., Naldi, R., Casavola, A., & Frazzoli, E. (2010). Cooperative mission planning for a class of carrier-vehicle systems. In 49th IEEE Conference on Decision and Control (CDC). Atlanta, Georgia, USA: IEEE
Gunawan A., Lau H.C., Lu K. (2015) An Iterated Local Search Algorithm for Solving the Orienteering Problem with Time Windows. In: Ochoa G., Chicano F. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2015. Lecture Notes in Computer Science, vol 9026. Springer, Cham
Gunawan, A., Ng, K.M., Yu, V. F., Adiprasetyo, G., and Lau, H. C. Iterated local search algorithm for the capacitated team orienteering problem. (2018). Proceedings of the 12th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2018), Vienna, Austria, August 28-31. 493-496. Research Collection School of Information Systems.
Kareem, M. M., Ismail, M., Altahrawi, M. A., Arsad, N., Mansor, M. F., & Ali, A. H. (2018, 26-28 Nov. 2018). Grid Based Clustering Technique in Wireless Sensor Network using Hierarchical Routing Protocol. Paper presented at the 2018 IEEE 4th International Symposium on Telecommunication Technologies (ISTT).
Khare, N., & Singh, P. (2011). Modeling and optimization of a hybrid power system for an unmanned surface vehicle. Journal of Power Sources, 198, 368–377. doi:10.1016/j.jpowsour.2011.09.080
Khan, A., Noreen, I., & Habib, Z. (2017). On Complete Coverage Path Planning Algorithms for Non-holonomic Mobile Robots: Survey and Challenges. Journal of Information Science and Engineering, 33(1), 101-121. doi: 10.6688/JISE.2017.33.1.7
Labadie, N., Mansini, R., Melechovský, J., & Wolfler Calvo, R. (2012). The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search. European Journal of Operational Research, 220(1), 15-27. doi:https://doi.org/10.1016/j.ejor.2012.01.030
Luo, Z., Liu, Z., & Shi, J. (2017). A Two-Echelon Cooperated Routing Problem for a Ground Vehicle and Its Carried Unmanned Aerial Vehicle. Sensors, 17(5), 1144. doi:10.3390/s17051144
Mukhina, K. D., Visheratin, A. A., & Nasonov, D. (2019). Orienteering Problem with Functional Profits for multi-source dynamic path construction. PLOS ONE, 14(4), e0213777. doi:10.1371/journal.pone.0213777
Matos, A., Cubber, G.D., Doroftei, D., Balta, H., Silva, E., Serrano, D., Govindaraj, S., Roda, R., Lobo, V., Marques, M., et al. (2017). Operational Validation of Search and Rescue Robots. In Search and Rescue Robotics; IntechOpen: doi: 10.5772/intechopen.69497
Mathew, N., Smith, S. L., & Waslander, S. L. (2015). Multirobot Rendezvous Planning for Recharging in Persistent Tasks. IEEE Transactions on Robotics, 31(1), 128-142. doi:10.1109/TRO.2014.2380593
Moravec, H., & Elfes, A. (1985). High resolution maps from wide angle sonar. Proceedings. 1985 IEEE International Conference on Robotics and Automation. doi:10.1109/robot.1985.1087316
Mirhedayatian, S. M., Crainic, T. G., Guajardo, M., & Wallace, S. W. (2019): A two-echelon location-routing problem with synchronization, Journal of the Operational Research Society, DOI: 10.1080/01605682.2019.1650625
Perez-Carabaza, S., Besada-Portas, E., Lopez-Orozco, J. A., & de la Cruz, J. M. (2018). Ant colony optimization for multi-UAV minimum time search in uncertain domains. Applied Soft Computing, 62, 789-806. doi:https://doi.org/10.1016/j.asoc.2017.09.009
Specht, C., Świtalski, E., & Specht, M. (2017). Application of an Autonomous/Unmanned Survey Vessel (ASV/USV) in Bathymetric Measurements. Polish Maritime Research, 24, 36-44. doi:10.1515/pomr-2017-0088
Vansteenwegen, P., Souffriau, W., Berghe, G. V., & Oudheusden, D. V. (2009). Iterated local search for the team orienteering problem with time windows. Computation Operation Research, 36(12), 3281-3290. doi:10.1016/j.cor.2009.03.008
Wang, X., & Wallace, S. (2016). Stochastic scheduled service network design in the presence of a spot market for excess capacity. EURO Journal on Transportation and Logistics, 5, 393–413. doi:10.1007/s13676-015-0089-1
Yahiaoui, A.-E., Moukrim, A., & Serairi, M. (2019). The clustered team orienteering problem. Computers & Operations Research, 111, 386-399. doi:https://doi.org/10.1016/j.cor.2019.07.008
Yuan, Y., & Tang, L. (2017). Novel time-space network flow formulation and approximate dynamic programming approach for the crane scheduling in a coil warehouse. European Journal of Operational Research. doi:10.1016/j.ejor.2017.03.007
Zhang, J., Jia, L.-m., Niu, S., Zhang, F., Tong, L., & Zhou, X. (2015). A Space-Time Network-Based Modeling Framework for Dynamic Unmanned Aerial Vehicle Routing in Traffic Incident Monitoring Applications. Sensors (Basel, Switzerland), 15, 13874-13898. doi:10.3390/s150613874
Zhang, J., Zhang, F., Liu, Z., & Li, Y. (2019). Efficient Path Planning Method of USV for Intelligent Target Search. Journal of Geovisualization and Spatial Analysis, 3(2), 13. doi:10.1007/s41651-019-0035-0