本研究探討一個「船載無人機旅行推銷員問題」，旨在指揮一艘船從給定的起點出發，沿途拜訪開放水域中的 n 個目的地後，再抵達給定的訖點。船可以在各目的地附近施放其所承載的單或雙架無人機，由速度較快但續航力較短的無人機去目的地執行探勘或收送件任務。依不同的任務需要，無人機或可在續航力足夠的情況下，一次拜訪多個目的地，再與船會合，而無人機與船的每次起飛與降落之會合點不見得要相同。本研究重點在於規劃船與無人機的最佳協同任務時程與路線，以使整個任務能在最短的時間內完成。

為了尋找最佳之目的地拜訪順序以及無人機各趟的起降點座標，本研究設計了一個具旅行推銷員問題限制的混整數二階錐規劃模式(SOCP)，並使用最佳化軟體 GUROBI 求解之。依任務類別需要，本研究考慮了單（SV）或雙架無人機（TV），及其每趟飛行僅拜訪單一(ST)或多個(MT)目的地等，總共四類問題設定。然而，使用數學規劃模式求解十分耗時，僅能處理小規模的問題。倘若給定各架無人機應造訪的目的地指派與其順序組合，本研究之混整數二階錐規劃模式即可較快計算出其對應的最佳無人機起降點座標。因此，針對ST類別問題，本研究提出一個二階段啟發式演算法：在第一階段用模擬退火法(ALG-SA) 猜測目的地造訪順序；而第二階段求解SOCP以算出其對應的最佳無人機起降座標。針對MT類別問題，本研究提出一個四階段啟發式演算法：第一階段先以ST模式直接使用ALG-SA與SOCP計算ST模式之各目的地起降座標；第二階段再使用一個分群演算法(CA)以指派單架無人機在MT設定下，可造訪的目的地集合；第三階段針對每架無人機負責的個別目的地分群，以一個基於最短路徑而設計的演算法 (ALG-SP)進一步決定其各趟航程需造訪的目的地集合與其順序；最後，於第四階段求解SOCP以得到精確的各趟無人機起降點座標。

針對單趟航程多目的地(MT)以及雙架無人機(TV)的路線規劃問題，本研究所設計的數學模式與演算法皆為相關領域首創。在數值測試實驗中，本研究實作並測試了五種不同的SOCP模式，以得出未來研究的數學規劃模式選用建議。而本研究所設計的二階段與四階段啟發式演算法，皆能在數秒內針對中大規模(n=70)問題計算出品質不錯的解。

This research investigates a carrier vehicle traveling salesman problem (CVTSP) to visit n targets. Each target will be visited by a smaller vehicle (e.g., unmanned aerial vehicle, UAV) launched from a carrier (e.g., ship). The vehicle will land at the carrier after visiting one or a few targets. The smaller vehicles and the carrier have to synchronize in takeoff and landing. To seek the best target visiting sequence and the associated takeoff and landing coordinates, this research presents a mixed integer second order cone programming model with TSP-like constraints and solves the problem by GUROBI, the state-of-the-art optimization software.

This research considers two settings on the number of targets that a vehicle can visit within one flight: (1) the single-target-per-flight setting (ST), and (2) the multiple-target-per-flight setting (MT), which requires a target composition that records which target to be visited for a specific flight by a specific vehicle. This research also considers two settings on the number of vehicles: (1) single vehicle (SV) and (2) two vehicles (TV). Given a sequence of targets to be visited and the corresponding target-vehicle assignment, our mathematical programming model can calculate optimal coordinates to take off and land each vehicle on a carrier. To speed up the solution process, this research proposes a Simulated Annealing algorithm (ALG-SA) to determine the target visiting sequence for all cases and a Shortest-Path-based algorithm (ALG-SP) to determine the target composition for the MT cases. The results from the computational experiments indicate that our proposed solution methods can calculate a good solution faster than the proposed mixed integer second order cone programming model by GUROBI.

Agatz, N., Bouman, P., & Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4), 965-981. doi:10.1287/trsc.2017.0791
Chowdhury, S., Emelogu, A., Marufuzzaman, M., Nurre, S. G., & Bian, L. (2017). Drones for disaster response and relief operations: A continuous approximation model. International Journal of Production Economics, 188, 167-184. doi:10.1016/j.ijpe.2017.03.024
de Andrade, R. C. (2016). New formulations for the elementary shortest-path problem visiting a given set of nodes. European Journal of Operational Research, 254(3), 755-768. https://doi.org/10.1016/j.ejor.2016.05.008
Dorling, K., Heinrichs, J., Messier, G. G., & Magierowski, S. (2017). Vehicle routing problems for drone delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(1), 70-85. doi:10.1109/tsmc.2016.2582745
Duhamel, C., Lacomme, P., & Prodhon, C. (2011). Efficient frameworks for greedy split and new depth first search split procedurs for routing problems. Computers & Operations Research, 38(4), 723-739. doi:10.1016/j.cor.2010.09.010
Erdoğan, G., & Yıldırım, E. A. (2020). Exact and heuristic algorithms for the carrier–vehicle traveling salesman problem. Transportation Science. doi:10.1287/trsc.2020.0999
Fahradyan, T., Bono Rossello, N., & Garone, E. (2020). Multiple carrier-vehicle travelling salesman problem. In Modelling and Simulation for Autonomous Systems (pp. 180-189).
Gambella, C., Lodi, A., & Vigo, D. (2018). Exact solutions for the carrier–vehicle traveling salesman problem. Transportation Science, 52(2), 320-330. doi:10.1287/trsc.2017.0771
Garone, E., Determe, J.-F., & Naldi, R. (2012). A travelling salesman problem for a class of heterogeneous multi-vehicle systems. Paper presented at the IEEE 51st IEEE Conference on Decision and Control (CDC). https://ieeexplore.ieee.org/document/6426488/
Garone, E., Naldi, R., Casavola, A., & Frazzoli, E. (2008). Cooperative path planning for a class of carrier-vehicle systems. Paper presented at the 2008 47th IEEE Conference on Decision and Control.
Garone, E., Naldi, R., Casavola, A., & Frazzoli, E. (2010). Cooperative mission planning for a class of carrier-vehicle systems. Paper presented at the 49th IEEE Conference on Decision and Control (CDC).
Ha, Q. M., Deville, Y., Pham, Q. D., & Hà, M. H. (2018). On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 86, 597-621. doi:10.1016/j.trc.2017.11.015
Klaučo, M., Blažek, S., Kvasnica, M., & Fikrar, M. (2014). Mixed-integer SOCP formulation of the path planning problem for heterogeneous Multi-Vehicle Systems. Paper presented at the 2014 European Control Conference (ECC).
Li, Z., & Garcia-Luna-Aceves, J. J. (2006). Finding multi-constrained feasible paths by using depth-first search. Wireless Networks, 13(3), 323-334. doi:10.1007/s11276-006-7528-8
Luo, Z., Liu, Z., & Shi, J. (2017). A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle. Sensors (Basel), 17(5). doi:10.3390/s17051144
Manyam, S. G., Rasmussen, S., Casbeer, D. W., Kalyanam, K., & Manickam, S. (2017). Multi-uav routing for persistent intelligence surveillance & reconnaisance mission. Paper presented at the 2017 International Conference on Unmanned Aircraft Systems (ICUAS)
Otto, A., Agatz, N., Campbell, J., Golden, B., & Pesch, E. (2018). Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks, 72(4), 411-458. doi:10.1002/net.21818
Poikonen, S., & Golden, B. (2020). The mothership and drone routing problem. INFORMS Journal on Computing, 32(2), 249-262. doi:10.1287/ijoc.2018.0879
Poikonen, S., Golden, B., & Wasil, E. A. (2019). A branch-and-bound approach to the traveling salesman problem with a drone. INFORMS Journal on Computing, 31(2), 335-346. doi:10.1287/ijoc.2018.0826
Tokekar, P., Hook, J. V., Mulla, D., & Isler, V. (2016). Sensor planning for a symbiotic uav and ugv system for precision agriculture. IEEE Transactions on Robotics, 32(6), 1498-1511. doi:10.1109/tro.2016.2603528
Wang, X., Poikonen, S., & Golden, B. (2016). The vehicle routing problem with drones: several worst-case results. Optimization Letters, 11(4), 679-697. doi:10.1007/s11590-016-1035-3
Yakıcı, E. (2016). Solving location and routing problem for UAVs. Computers & Industrial Engineering, 102, 294-301. doi:10.1016/j.cie.2016.10.029
Yu, K., Budhiraja, A. K., & Tokekar, P. (2018). Algorithms for routing of unmanned aerial vehicles with mobile recharging stations. Paper presented at the 2018 IEEE International Conference on Robotics and Automation (ICRA).