Optimization approach for multiple trucks and drones flexible collaboration routing problem

Abstract:

To improve transportation efficiency and reduce total costs, an optimization approach is adopted to address truck-drone flexible collaboration routing problem. Firstly, a mixed integer linear programming model with the goal of minimizing the operation cost and customer waiting cost is formulated, combining the characteristics of multiple-truck-drone flexible collaboration and drone continuous delivery. Secondly, a two-stage heuristic solution framework is designed to optimize the routes of drones and trucks respectively in two stages. Finally, a tailored adaptive hybrid neighborhood search algorithm based on destroy operator, repair operator and k-opt operator is proposed for routing in each stage. The Solomon dataset is selected for numerical experiments, and the results show that: compared with CPLEX solver, the proposed method can obtain satisfactory solutions with higher quality in a short time. Compared with iterative local search, variable neighborhood search and ant colony optimization algorithm, the solution quality of the proposed method is improved by 5.49%, 6.88% and 27.82% in small-, medium- and large-scale instances, respectively. Compared to pure truck transportation mode, the truck-drone collaborative transportation mode is more suitable for small- and medium-scale operations, achieving a 4.70% to 8.56% reduction in overall costs. The research results can provide theoretical basis for the practice of truck-drone collaborative transportation.