近幾年，無人駕駛飛行器也被稱為無人機，是作為運輸商業領域中的一種新型物流方式，卡車不僅可以為客戶提供服務，且無人機可以在卡車路線上的節點進行發射與收回，無人機與卡車共同服務，各自向客戶交付貨物，提高服務質量，降低運輸時間成本。
　　本研究探討帶有無人機的車輛途程問題，考量客戶的時間窗限制。卡車與無人機都必須在客戶的服務時間窗內進行交付，並建立數學模型來定義此問題，目標是最小化每輛卡車回到倉庫的抵達時間，並使用最佳化求解軟體GUROBI來求解最佳解，由於大型實例題目難以在最佳化軟體上解決，因此應用了基因演算法來求解大型實例。
　　本研究之實驗使用隨機產生的資料集，並分析單純使用卡車進行交付之時間與卡車和無人機共同進行交付之時間，在不同客戶數量以及不同服務範圍進行運送所帶來之效益比較，節省時間之比率的多寡，也測試了無人機飛行之耐力時間。分析結果顯示，本研究所應用之基因演算法，在小型題目可找到最佳解證明其有效性，此外也可在不同大小之題目中找尋近似解，在越小的客戶數量以及越小的服務範圍內，無人機所帶來的效益較高。

　　In recent years, unmanned aerial vehicles (UAV) are also called drones. As a new logistics method in the transportation business field, trucks can not only provide services to customer but also drones can be launched and recovered at nodes on truck routes. Drones and trucks serve together, deliver goods to customers, improve service quality, and reduce transportation time costs.
　　This study explores the problem of vehicle routing problem with drones. Considering the time window constraints of customers. Trucks and drones must be delivered within the customer's service time window, and a mathematical model is established to define this problem. The goal is to minimize the arrival time of each truck return to the depot. It uses the optimization solution software GUROBI to solve the optimal solution. Because the problem of large examples is difficult to solve at the optimization software, the genetic algorithm is applied to solve the large examples.
　　The experiment in this study uses a randomly generated data set. Analyze the time of delivery comparison between only using trucks and using trucks and drones together. The improvement saving of delivery in different number of customers and different service areas. The endurance time of the drone flight was also tested. The analysis results show that the genetic algorithm applied in this study can find the optimal solution to prove its effectiveness in small-scale problems. In addition, it can also find approximate solutions in different larger size problems. The benefits brought by drones are higher at the smaller number of customers and the smaller service area.

REFERENCES

Ai, T.J., and Kachitvichyanukul, V., “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery,” Computers and Operations Research, 36 (5), pp. 1693-1702, 2009.
Alvarenga, G.B., Mateus, G.R., and de Tomi, G., “A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows,” Computers and Operations Research, 34 (6), pp. 1561-1584, 2007.
Berger, J., and Barkaoui, M., “A parallel hybrid genetic algorithm for the vehicle routing problem with time windows,” Computers and Operations Research, 31 (12), pp. 2037-2053, 2004.
Chang, Y.S., and Lee, H.J., “Optimal delivery routing with wider drone-delivery areas along a shorter truck-route,” Expert System Applications, 104, pp. 307-317, 2018.
Chen, A.L., Yang, G.K., and Wu, Z.M., “Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem,” Journal of Zhejiang University Science A, 7, pp. 607-614, 2006.
Cheng, C.B., and Wang, K.P., “Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm,” Expert Systems with Applications, 36 (4), pp. 7758-7763, 2009.
Chiang, W.C., and Russell, R.A., “Simulated annealing metaheuristics for the vehicle routing problem with time windows,” Annals of Operations Research, 63 (1), pp. 3-27, 1996.
Christofides, N., Mingozzi, A., and Toth, P., “The vehicle routing problem,” in Combinatorial Optimization, Christofides, N., Mingozzi, A., Toth, P. and Sandi, C. eds., John Wiley and Sons, London, 1979.
Chu, C.W., “A heuristic algorithm for the truckload and less-than-truckload problem,” European Journal of Operational Research, 165, pp. 657-667, 2005.
Dantzig, G., and Ramser, J., “The truck dispatching problem,” Management Science, 6(1), pp. 80-91, 1959.
Eberhart, R., and Kennedy, J., “A new optimizer using particle swarm theory,” MHS'95, Proceedings of the Sixth International Symposium on Micro Machine and Human Science, pp. 39-43, 1995.
French, S., “Drone delivery is already here– And it works,” Market Watch, 2015. https://www.marketwatch.com/story/drone-delivery-is-already-here-and-it-works-2015-11-30 (Accessed Dec. 30th, 2019)
Golden, B.L., Raghavan, S., and Wasil, E.A., “The Vehicle Routing Problem: Latest Advances and New Challenges,” Springer Science & Business Media, 43, 2008.
Ha, Q.M., Deville, Y., Pham, Q.D., and Hà, M. H., “On the min‐cost traveling salesman problem with drone”, Transportation Research Part C: Emerging Technologies, 86, pp. 597-621, 2018.
Herrera, F., Lozano, M., and Verdegay, J.L., “Tackling real-coded genetic algorithms: operators and tools for behavioural analysis,” Artificial Intelligence Review, 12 (4), pp. 265-319, 1998.
Ho, S.C., and Haugland, D., “A Tabu search heuristic for the vehicle routing problem with time windows and split deliveries,” Computers & Operations Research, 31 (12), pp. 1947-1964, 2004.
Ho, W., Ho, G.T.S., Ji, P., and Lau, H.C.W., “A hybrid genetic algorithm for the multi-depot vehicle routing problem,” Engineering Applications of Artificial Intelligence, 21, pp. 548-557, 2008.
Holland, J. H., Adaptation in Natural and Artificial System, The University of Michigan Press, Ann Arbor, Michigan, 1975.
Jiang, X., Zhou, Q., and Ye, Y., “Method of Task Assignment for UAV Based on Particle Swarm Optimization in logistics,” In Proceedings of the 2017 International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence, pp. 113-117, 2017.
Khoufi, I., Laouiti, A., and Adjih, C., “A Survey of Recent Extended Variants of the Traveling Salesman and Vehicle Routing Problems for Unmanned Aerial Vehicles,” Drones, 66, 3(3), 2019.
Kuo, Y., “Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem,” Computers and Industrial Engineering, 59 (1), pp. 157-165, 2010.
Koulamas, C., Antony, S., and Jaen, R., “A survey of simulated annealing applications to operations research problems,” Omega, 22 (1), pp. 41-56, 1994.
Laporte, G., Mercure, H., and Nobert, Y., “An exact algorithm for the asymmetrical capacitated vehicle routing problem,” Network, 16, pp. 33-46, 1986.
Lenstra, J.K., and Kan, A.H.G.R., “Complexity of vehicle routing and scheduling problems,” Networks, 11 (2), pp. 221-227, 1981.
Li, H., and Lim, A., “Local search with annealing-like restarts to solve the VRPTW,” European Journal of Operational Research, 150 (1), pp. 115-127, 2003.
Li, J.M., Li, A.H., Varbanov, P.S., and Liu, Z.Y., “Distance potential concept and its applications to the design of regional biomass supply chains and solving vehicle routing problems,” Journal of Cleaner Production, 144, pp. 426-436, 2017.
Liu, J., and He, Y., “A clustering-based multiple ant colony system for the waste collection vehicle routing problems,” 2012 Fifth International Symposium on Computational Intelligence and Design, Hangzhou, China, pp. 182-185, 2012.
Lourenço, H.R., Martin, O.C., and Stützle, T., “Iterated Local Search: Framework and Applications,” Handbook of Metaheuristics. International Series in Operations Research & Management Science, 146, pp.363-397, 2010.
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., and Teller, E., “Equation of state calculations by fast computing machines,” Journal of Chemical Physics, 21, pp. 1087-1092, 1953.
Mirjalili, S., “SCA: a sine cosine algorithm for solving optimization problems,” Knowledge - Based Systems, 96, pp. 120-133, 2016.
Miranda, D.M., and Conceição, S.V., “The vehicle routing problem with hard time windows and stochastic travel and service time,” Expert System with Applications, 64, pp. 104-116, 2016.
Murray, C.C., and Chu, A.G., “The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery,” Transportation Research Part C, 54, pp. 86-109, 2015.
Park, J., and Kim, B.I., “The school bus routing problem: a review,” European Journal of Operational Research, 202 (2), pp. 311-319, 2010.
Poikonen, S., Wang, X., and Golden, B., “The vehicle routing problem with drones: extended models and connections,” Networks, 70 (1), pp. 34-43, 2017.
Ren, Y., Dessouky, M., and Ordόñez, F., “The multi-shift vehicle routing problem with overtime,” Computers and Operations Research, 37, pp. 1987-1998, 2010.
Savelsbergh, M., “Local search in routing problems with time windows,” Annals of Operations Research, 4, pp. 285-305, 1985.
Sacramento, D., Pisinger, D., and Ropke, S., “An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones,” Transportation Research Part C, 102, pp. 289-315, 2019.
Solomon, M.M., “Vehicle routing and scheduling with time windows constraints: Models and algorithms.” Ph.D. Dissertation, Department of Decision Sciences, University of Pennsylvania, 1983.
Sun, Z.Y., Guan, Z.L., and Wang, Q., “An improved adaptive genetic algorithm for vehicle routing problem,” Logistics Systems and Intelligent Management, 2010 International Conference, pp. 116–120, 2010.
Tan, K.C., Lee, L.H., and Ou, K., “Artificial intelligence heuristics in solving vehicle routing problems with time window constraints,” Engineering Applications of Artificial Intelligence, 14, pp. 825-837, 2001.
Ursani, Z., Essam, D., Cornforth, D., and Stocker, R., “Localized genetic algorithm for vehicle routing problem with time windows,” Applied Soft Computing, 8, pp. 5375-5390, 2011.
Wang, K.P., Huang, L., Zhou, C.G., and Pang, W., “Particle swarm optimization for traveling salesman problem,” Machine Learning and Cybernetics, 2003
Wang, C., Mu, D., Zhao, F., and Sutherland, J., “A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows,” Computers and Industrial Engineering, 83, pp. 111-122, 2015.
Wang, X., Poikonen, S., and Golden, B., “The vehicle routing problem with drones: several worst-case results,” Optimization Letters 11, 4, pp. 679–697, 2016.
Wang, Z., and Sheu, J.B., “Vehicle routing problem with drones,” Transportation Research Part B: Methodological, 122, pp.350-364, 2019.
Wang, J., Yang, W., Du, P., and Niu, T., “A novel hybrid forecasting system of wind speed based on a newly developed multi-objective sine cosine algorithm,” Energy Conversion Management, 163, pp. 134-150, 2018.
Wei, L., Zhang, Z., Zhang, D., and Leung, S.C.H., “A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints,” European Journal Operation Research, 265 (3), pp. 843-859, 2018.
Wohlsen, M., “The next big thing you missed: Amazon's delivery drones could work–they just need trucks,” Wired: Business, 2014. https://www.wired.com/2014/06/the-next-big-thing-you-missed-delivery-drones-launched-from-trucks-are-the-future-of-shipping/. (Accessed Dec. 30th, 2019)
Yu, B., Yang, Z. Z., and Yao, B., “A hybrid algorithm for vehicle routing problem with time windows,” Expert Systems with Applications, 38(1), pp. 435-441, 2011.
Zirour, M., “Vehicle routing problem: models and solutions, Journal of Quality Measurement and Analysis,” Journal of Quality Measurement Analysis, 4 (1), pp. 205-218, 2008.