İnsansız hava aracı destekli araç rotalama problemi

Abstract

Araç rotalama problemi, literatürde ve gerçek hayatta en sık çalışılan problemlerden biridir. Bu problemin yeni ortaya çıkan ve insansız hava araçlarını (İHA) dağıtım faaliyetlerine entegre eden yeni bir türevi, kamyon ve İHA'ların, zaman ve konum olarak koordinasyonunu sağlayarak eşzamanlı dağıtım yapmalarını amaçlamaktadır. Bu tez çalışması kapsamında, ilk olarak, tek kamyon ve tek İHA'nın eşzamanlı dağıtım yaptığı problemin (ARP-İHA) çözümü için, 2-aşamalı, yinelemeli bir kesin çözüm yaklaşımı geliştirilmiştir. Bu yaklaşımda, kamyon rotası ilk aşamada belirlenmektedir. İHA rotası ise ikinci aşamada, geliştirilen karışık tamsayılı doğrusal programlama modeli çözülerek eniyilenmektedir. Çözüme en kısa kamyon rotası ile başlanarak, atama ve rotalama kararları yinelemeli olarak iyileştirilmektedir. Yapılan sayısal çalışma ile, çözüm yaklaşımının performansı değerlendirilmiştir. Sonrasında, orta ve büyük ölçekli ARP-İHA'ların çözümü için, makine öğrenmesi ile fonksiyon kestirimine dayanan melez bir genetik algoritma geliştirilmiştir. Literatürdeki mevcut çalışma ile karşılaştırılan sonuçlar, küçük ve orta ölçekli problemlerde melez genetik algoritmanın daha başarılı olduğunu göstermiştir. Önerilen kesin çözüm yaklaşımı ve melez genetik algoritma, kamyon ve birden fazla İHA'nın eşzamanlı dağıtım yaptığı (ARP-mİHA) probleme uyarlanmıştır. Bilindiği kadarıyla, tez kapsamında kabul edilen varsayımları dikkate alarak, ARP-mİHA için geliştirilmiş kesin ve sezgisel çözüm yaklaşımları, ilk kez bu tez çalışması tarafından önerilmektedir. Yapılan sayısal çalışma ile, geliştirilen yöntemlerin performansı ve İHA sayısındaki artışın dağıtım sürelerine etkisi analiz edilmiştir.

Vehicle routing problem is one of the most studied problems in the literature and real life. An emerging variant of this problem, which integrates unmanned aerial vehicles (UAVs) into the last-mile delivery operations, aims the coordinated delivery of truck and UAVs while synchronizing them in terms of both time and location. In this thesis, initially, a 2-stage, iterative exact solution approach is developed for the solution of the coordinated delivery problem of a truck and a UAV (TSP-D). In this approach, the truck route is determined at the first stage. The UAV route is optimized at the second stage by the mixed integer linear programming model. Beginning with the shortest truck route, the assignment and routing decisions are iteratively improved. A computational study is conducted to evaluate the performance of the solution approach. Next, a hybrid genetic algorithm which is based on function approximation by machine learning is developed to solve medium and large-scale problems. The results are compared with the state-of-the-art study and it is concluded that the proposed algorithm gives better results for the small and medium-scale problems. The proposed exact solution approach and hybrid genetic algorithm are extended to the delivery problem in which a truck and multi-UAV deliver parcels in conjunction (TSP-mD). To the best of our knowledge, this is the first study proposing exact and heuristic solution approaches for the TSP-mD under the assumptions existing in this study. A computational study is conducted to analyze the performance of the proposed algorithms and the impact of the increase in the number of UAVs on the delivery times.