近年來，隨著科技發展的進步，無人機的應用範圍逐漸廣泛，其負載重量和飛行距離也逐漸增加。由於無人機的便利性和低成本，許多大型物流公司開始嘗試將無人機納入配送流程。此外，也有許多學者紛紛著手研究卡車與無人機間的協同物流，使其結果最佳化。再者，近期因COVID-19的盛行，無接觸的配送方式成為有效的防疫手段，且從公共衛生角度來看，這是一個優良的配送方式。
本研究探討具多台無人機的協同物流於具時間窗限制之旅行推銷員問題(TSPTW-mD)，其時間窗設定為早上、下午及傍晚。此外，並建立了數學模型來定義問題，目標最小化卡車行徑時間、等待時間、服務時間及違背時間窗帶來的懲罰的總和。本研究提出使用二分K均值演算法(Bisecting K-means algorithm)和基因演算法(Genetic algorithm；GA)來求解此問題。
本研究之實驗使用隨機產生的資料集，比較了不同無人機數量與電池容量的差異。並將其應用於三種情境中：城市、近郊、鄉下。從結果可以得知，在電池容量許可的飛行範圍內，無人機的數量越多，所帶來的效益也越高。最後，從成本方面進行分析，可知當無人機的使用率越高，成本的改善越明顯。

In recent years, the application of drones becomes popular since its load weight and flight distance have gradually been increased. Due to the convenience and low cost of drones, many logistics companies try to incorporate drones into the distribution. Many scholars also focus on the collaborative logistics between trucks and drones to optimize the results. Furthermore, due to the outbreak of COVID-19, contactless delivery has become an effective means of epidemic prevention. From the public health perspective, it will be an excellent delivery method.
In this study, multiple drones are considered to be used in travel salesman problem with time window (TSPTW-mD) for collaborative logistics. The time windows are set as morning, afternoon, and evening. A mathematical model is developed to define the problem, and the objective function is to minimize the sum of truck travel time, waiting time, service time and the penalty caused by violation of the time window. This problem is solved using the bisecting K-means algorithm and the genetic algorithm (GA).
The experiments in this study used randomly generated data sets to compare the differences among different numbers of drones and different battery endurances. Then, we apply it to three situations: urban, suburban, and countryside. From the results, it can be found if more drones are used (in the flight endurance), more saving will be produced. Finally, for transportation cost saving, the higher utilization rate of drones makes the cost improvement more obvious.

H. Allaoua, S. Borne, L. Létocart and R.W. Calvo, “A matheuristic approach for solving a home health care problem,” Electronic Notes in Discrete Mathematics, Vol. 41, pp.471-478, 2013
D. Applegate, R. Bixby, V. Chvatal and W. Cook, “On the solution of traveling salesman problems,” Documenta Mathematica, Extra Vol. ICM, pp. 645–656, 1998
S. Basu, “Tabu search implementation on traveling salesman problem and its variations: a literature survey,” American Journal of Operations Research, Vol.2, pp 163-173, 2012
V. Cerny, “Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm,” Journal of Optimization Theory and Applications, Vol. 45, No. l., 1985
P. C. Chang, W. H. Huang and C. J. Ting, “Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems,” Expert Systems with Applications, Vol. 37, pp.1863-1878, 2010
A.L. Chen, G.K. Yang, Z.M. Wu, “Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem,” Journal of Zhejiang University Science A, Vol. 7, pp.607-614, 2006
G. Dantzig, R. Fulkerson, and S. Johnson, "Solution of a large-scale traveling-salesman problem," Operations Research, Vol.2, pp. 393-410., 1954
Y. Deng, Y. Liu and D. Zhou, “An improved genetic algorithm with initial population strategy for symmetric TSP,” Mathematical Problems in Engineering, 2015
M. M. Flood, “The traveling-salesman problem,” Operations Research, Vol.4, pp.61-75, 1956
F. Focacci, A. Lodi and M. Milano, “A hybrid exact algorithm for the TSPTW,” INFORMS Journal on Computing, Vol. 14, No. 4, 2002
J.C. De Freitas and P.H. V. Penna, “A variable neighborhood search for flying sidekick traveling salesman problem,” International Transactions in Operational Research, Vol. 1, Issue 1, 2019
D. Gavalas, M. Kenteris, C. Konstantopoulos and G. Pantziou, “Web application for recommending personalized mobile tourist routes,” IET Software, Vol. 6, pp.313-322, 2012
X. Geng, Z. Chen, W.Yang, D. Shi and K. Zhao, “Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search”, Applied Soft Computing, Vol 11, pp.3680-3689, 2011
Q. M. Ha, Y. Deville, Q.D. Pham and M. H. Ha, “On the min-cost traveling salesman problem with drone,” Transportation Research Part C: Emerging Technologies, Vol.86, pp.597-621, 2018
K. Helsgaun, “An effective implementation of the Lin-Kernighan traveling salesman heuristic,” European Journal of Operational Research, Vol. 126, pp.106-130, 2000
M. Hoffmann, M. Mühlenthaler, S. Helwig and R. Wanka, “Discrete particle swarm optimization for TSP: theoretical results and experimental evaluations,” In: Bouchachia A. (eds) Adaptive and Intelligent Systems. ICAIS 2011. Lecture Notes in Computer Science, Vol. 6943, Springer, Berlin, Heidelberg.
J.H. Holland, “Adaptation in natural and artificial system,” The University of Michigan Press, Ann Arbor, Michigan (1975).
A. Hussain, Y. S. Muhammad, M. N. Sajid, I. Hussain, A. M. Shoukry and S. Gani, “Genetic algorithm for traveling salesman problem with modified cycle crossover operator,” Computational Intelligence and Neuroscience, 2017
I. Kaabachi, D. Jriji, F. Madany and S. Krichena, “A bi-criteria ant colony optimization for minimizing fuel consumption and cost of the traveling salesman problem with time windows,” Procedia Computer Science, Vol. 112, pp. 886-895, 2017
I. Kara and T. Derya, “Formulations for minimizing tour duration of the traveling salesman problem with time windows,” Procedia Economics and Finance, Vol. 26, pp.1026-1034, 2015.
G. Laporte and S.U. Palekar, “Some applications of the clustered travelling salesman problem,” Journal of the Operational Research Society, Vol. 53, pp. 972-976, 2002
F. Lin, C. Kao and C. Hsu, “Applying the genetic approach to simulated annealing in solving some NP-hard problems,” IEEE, Vol. 23, pp.1752-1767, 1993
M. Malek, M. Guruswamy, M. Pandya and H. Owens, “Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem,” Annals of Operations Research, Vol. 21, pp.59–84, 1989
G. Morton and A. H. Land, “A contribution to the ‘travelling-saleman’ Problem,” Journal of the Royal Statistical Society, Vol.17, pp. 185-203, 1955
C.C. Murray and A.G. Chu, “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery,” Transportation Research Part C: Emerging Technologies, Vol. 54, pp.86-109, 2015
G. Pataki, “Teaching integer programming formulations using the traveling salesman problem,” Siam Review, Vol. 45, No.1, pp.116-123, 2003
G. Pesant, M. Gendreau, J.Y. Potvin and J.M. Rousseau, “An exact constraint logic programming algorithm for the traveling salesman problem with time windows,” Transportation Science, Vol. 32, No. 1, 1998
Pragya, M. Dutta and Pratyush, “TSP solution using dimensional ant colony optimization,” 2015 Fifth International Conference on Advanced Computing & Communication Technologies, Haryana, pp. 506-512, 2015.
W.H. Press, B.P. Flannery, S.A. Teukolsky and W.T. Vetterling, Numerical recipes in C: the art of scientific computing, Second Edition, 1992.
N. M. Razali and J. Geraghty, “Genetic algorithm performance with different selection strategies in solving TSP,” Proceedings of the World Congress on Engineering, Vol. II, July 6 - 8, London, U.K., 2011.
M.W.P. Savelsberg, “Local search in routing problems with time windows,” Annals of Operations Research, Vol. 4, pp.285–305, 1985.
Y. Suzuki, “A new truck-routing approach for reducing fuel consumption and pollutants emission,” Transportation Research Part D, Vol. 16, pp 73-77, 2011
R. Tinós, K. Helsgaun, and D. Whitley, “Efficient recombination in the Lin-Kernighan-Helsgaun traveling salesman heuristic,” In: Auger A., Fonseca C., Lourenço N., Machado P., Paquete L., Whitley D. (eds) Parallel Problem Solving from Nature – PPSN XV. PPSN 2018. Lecture Notes in Computer Science, Vol. 11101, Springer, Cham.
Y. Tsujimura and M. Gen, “Entropy-based genetic algorithm for solving TSP,” IEEE, 2002.
K.P. Wang, L. Huang, C.G. Zhou, W. Pang, “Particle swarm optimization for traveling salesman problem,” Proceedings of the 2003 International Conference on Machine Learning and Cybernetics (IEEE Cat. No.03EX693), Xi'an, Vol. 3, pp. 1583-1585, 2003.
S. Zhan, J. Lin, Z. Zhang and Y. Zhong, “List-based simulated annealing algorithm for traveling salesman problem,” Computational Intelligence and Neuroscience, 2016
Y. Zhang, S. Wang and G. Ji, “A comprehensive survey on particle swarm optimization algorithm and its applications,” Mathematical Problems in Engineering, 2015