Unmanned aerial vehicle supported vehicle routing problem

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.