İki aşamalı insansız hava aracı destekli topla-dağıt rotalama problemi

Öz

Son dönemlerde insansız hava araçları (İHA) teknolojisinin lojistik süreçlerde kullanılma potansiyeli ve bu alanda yaşanan hızlı gelişmeler, İHA destekli rotalama problemlerini akademik ve endüstriyel açıdan önemli bir araştırma konusu haline getirmiştir. Bu makalede, iki aşamalı İHA destekli rotalama problemi ele alınmıştır. Bu problemde, toplam çalışma süresini en küçükleyecek şekilde, kendisine yüklenen ürünler ve İHA’lar ile depodan hareket eden bir kara aracının hangi mobil depolara uğrayacağı ve bu mobil depolardan serbest bırakılan İHA'lar aracılığıyla hangi müşterilere hizmet verileceği belirlenmektedir. Bu çalışmada iki farklı durum ele alınmıştır. Birinci durumda, müşterilerin sadece dağıtım müşterisi olduğu ve İHA’ların mobil depolarda bir veya birkaç kez kullanılabildiği iki varyasyon ele alınmıştır. Bu problemler için karma tamsayılı doğrusal programlama modelleri geliştirilmiş ve geliştirilen modellerin literatürde var olan modellerden daha kısa sürede optimum çözüme ulaştığı deneysel olarak kanıtlanmıştır. İkinci durumda ise müşterilerin ya dağıtım ya da toplama müşterisi olabildiği İki Aşamalı İnsansız Hava Aracı Destekli Topla-Dağıt Rotalama Problemi (2A-İTDRP) isimli yeni bir problem tanıtılmıştır. 2A-İTDRP için bir İHA’nın bir mobil depodan bir veya birkaç kez kullanılabildiği iki varyasyon ele alınmış ve çözümü için karma tamsayılı doğrusal programlama modelleri önerilmiştir. Modeller, GAMS/CPLEX çözücüsü kullanılarak çözülmüş, önerilen matematiksel modellerin deneysel çalışmaları gerçekleştirilmiş ve elde edilen sonuçlar ayrıntılı olarak raporlanmıştır.

Anahtar Kelimeler

• İHA Rotalama
• araç rotalama
• matematiksel modelleme

Two-stage Unmanned Aerial Vehicle (UAV) assisted pickup and delivery routing problem

Öz

Recently, the potential of using unmanned aerial vehicles (UAVs) technology in logistics processes and the rapid developments in this field have made UAV-assisted routing problems an important focus. In this paper, a two-stage UAV-assisted routing problem is considered. In this problem, to minimize the completion time, a truck moving from a depot with loaded products and UAVs will determine which mobile depots to visit and which customers will be served by the UAV released from these mobile depots. In this study, two different cases are considered. In the first case, two variations are considered, where the customers are only delivery customers, and the UAVs can be used once or several times at the mobile depots. Mixed integer linear programming models are developed for these problems, and it is experimentally proven that the developed models reach the optimum solution in less time than the existing models in the literature. In the second case, a new problem called the “Two-Stage Unmanned Aerial Vehicle Assisted Pickup and Delivery Routing Problem" (2S-UAV-PDRP) is introduced where customers can be either pickup or delivery customers. For the 2A-ITDRP, two variations where a UAV can be used once or several times from a mobile depot are considered, and mixed integer linear programming models are proposed for its solution. The models are solved using the GAMS/CPLEX solver, experimental studies of the proposed mathematical models are performed, and the results are reported in detail.

Anahtar Kelimeler

• UAV Routing
• vehicle routing
• mathematical model

Kaynakça

1. [1] Moshref-Javadi M, Winkenbach M. "Applications and Research avenues for drone-based models in logistics: A classification and review". Expert Systems with Applications, 177, 114854, 2021.
2. [2] Macrina G, Pugliese LDP, Guerriero F, Laporte G. "Drone-aided routing: A literature review". Transportation Research Part C: Emerging Technologies, 120, 102762, 2020.
3. [3] Murray CC, Chu AG, "The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery". Transportation Research Part C: Emerging Technologies, 54, 86-109, 2015.
4. [4] Vu L, Vu DM, Hà MH, Nguyen VP. "The two‐echelon routing problem with truck and drones". International Transactions in Operational Research, 29(5), 2968-2994, 2022.
5. [5] Duan J, Luo H, Wang G. "Approaches to the truck-drone routing problem: A systematic review". Swarm and Evolutionary Computation, 92, 101825, 2025.
6. [6] Luo H, Duan J, Wang G. "Mathematical models for truck-drone routing problem: Literature review". Applied Mathematical Modelling, 144, 116074, 2025.
7. [7] Moradi N, Wang C, Mafakheri F. "Urban Air Mobility for Last-Mile Transportation: A Review". Vehicles, 6(3), 1383-1414, 2024.
8. [8] Rojas Viloria D, Solano‐Charris EL, Muñoz‐Villamizar A, Montoya‐Torres JR. "Unmanned aerial vehicles/drones in vehicle routing problems: a literature review". International Transactions in Operational Research, 28(4), 1626-1657, 2021.

9. [9] Carlsson JG, Song S. "Coordinated logistics with a truck and a drone". Management Science, 64(9), 4052-4069, 2018.
10. [10] Ha QM, Deville Y, Pham QD, Hà MH, "On the min-cost traveling salesman problem with drone". Transportation Research Part C: Emerging Technologies, 86, 597-621, 2018.
11. [11] Tu PA, Dat NT, Dung PQ. “Traveling Salesman Problem With Multiple Drones”. Proceedings of the 9th International Symposium on Information and Communication Technology, Da Nang City, Viet Na, 6-7 December 2018.
12. [12] Salama M, Srinivas S. "Joint optimization of customer location clustering and drone-based routing for last-mile deliveries". Transportation Research Part C: Emerging Technologies, 114, 620-642, 2020.
13. [13] Moshref-Javadi M, Hemmati A, Winkenbach M. "A truck and drones model for last-mile delivery: A mathematical model and heuristic approach". Applied Mathematical Modelling, 80, 290-318, 2020.
14. [14] Moshref-Javadi M, Lee S, Winkenbach M. "Design and evaluation of a multi-trip delivery model with truck and drones". Transportation Research Part E: Logistics and Transportation Review, 136, 101887, 2020.
15. [15] Nguyen MA, Dang GT-H, Hà MH, Pham M-T, "The min-cost parallel drone scheduling vehicle routing problem". European Journal of Operational Research, 299(3), 910-930, 2022.
16. [16] Poikonen S, Wang X, Golden B. "The vehicle routing problem with drones: Extended models and connections". Networks, 70(1), 34-43, 2017.
17. [17] Wang Z, Sheu JB. "Vehicle routing problem with drones". Transportation research part B: methodological, 122, 350-364, 2019.
18. [18] Gonzalez-R PL, Canca D, Andrade-Pineda JL, Calle M, Leon-Blanco JM. "Truck-drone team logistics: A heuristic approach to multi-drop route planning". Transportation Research Part C: Emerging Technologies, 114, 657-680, 2020.
19. [19] Dayarian I, Savelsbergh M, Clarke JP. "Same-day delivery with drone resupply". Transportation Science, 54(1), 229-249, 2020.
20. [20] Ha QM, Deville Y, Pham QD, Hà MH. "A hybrid genetic algorithm for the traveling salesman problem with drone". Journal of Heuristics, 26, 219-247, 2020.
21. [21] Kim S, Moon I. "Traveling salesman problem with a drone station". IEEE Transactions on Systems, Man, and Cybernetics: Systems, 49(1), 42-52, 2018.
22. [22] Murray CC, Raj R. "The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones". Transportation Research Part C: Emerging Technologies, 110, 368-398, 2020.
23. [23] Jeong HY, Song BD, Lee S, "Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones". International Journal of Production Economics, 214, 220-233, 2019.
24. [24] Mourelo Ferrandez S, Harbison T, Webwer T, Sturges R, Rich R. "Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm". Journal of Industrial Engineering and Management, 9(2), 374-388, 2016.
25. [25] Yin Y, Li D, Wang D, Yu Y, Cheng T. "Truck‐Drone Pickup and Delivery Service Optimization With Availability Profiles". Naval Research Logistics, 72(4), 534-565, 2024.
26. [26] Peng Y, Ren Z, Yu DZ, Zhang Y. "Transportation and carbon emissions costs minimization for time-dependent vehicle routing problem with drones". Computers & Operations Research, 176, 106963, 2025.
27. [27] Ozkan O, Kaya M. "UAV routing with genetic algorithm based matheuristic for border security missions". An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 11(2), 128-138, 2021.
28. [28] Dasdemir E, Köksalan M, Tezcaner Öztürk D. "Multi-objective route planning of an unmanned air vehicle in continuous terrain: An exact and an approximation algorithm". European Journal of Operational Research, 322(3), 960-977, 2025.
29. [29] Halat M, Özkan Ö. "The optimization of UAV routing problem with a genetic algorithm to observe the damages of possible Istanbul earthquake". Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 27(2), 187-198, 2021.