Two-Echelon Routing Problem For Parcel Delivery By Cooperated Truck And Drones

With the digitalization and intelligentization in the battlefield,the induced fast pace,high mobility and large material consumption in current war necessitates higher requirements in logistics,especially the transportation of equipment and materials.However,due to the characteristics of high cost,poor mobility and easy casualties,the traditional distribution on the ground battlefield,such as vehicle delivery,cannot meet the requirements of the current war,which may result in poor connection or cannot provide support in a timely manner.In contrast,as an emerging transportation technology,drone has the advantages of low cost,high mobility,convenient operation and effective avoidance of casualties.Its application in battlefield distribution has become an inevitable development trend.However,with limited endurance and payload capacity of drone,the development of drone distribution is greatly inhibitive.Although vehicle delivery and drone delivery have their corresponding limitations,when they cooperate,the vehicle can be used as the mobile base station and mobile warehouse of drone to expand the effective transportation range of drones.On the other hand,drones can carry out "last mile" deliveries,decreasing the traveling distance of the vehicle,reducing the casualty risk as well as total costs.Based on the above considerations,this paper proposes the collaborative distribution mode of vehicle-mounted drone,and based on this mode,models and solves the doublelayer path planning problem of vehicle-mounted drone collaboration,mainly completing the following work:First,according to the background of parcel delivery Two-Echelon Routing Problem by Truck and Drones(2E-RP-T&D)is analyzed.During the delivery process of drone,it can complete the delivery of multiple target points on one flight.During the delivery,the load of drone decreases successively,which has a great influence on the energy consumption of drone.Considering the above characteristics,the two-stage model based on path is constructed,and the enumeration algorithm based on the idea of branch-andcut is constructed.Second,two heuristic algorithms are designed to solve this problem: the heuristic algorithm based on the idea of saving(H1)and the heuristic algorithm based on the idea of regression(H2).In order to compare the performance of two algorithms,random cases in three scales are constructed,and comparative experiments are carried out for both onetruck-one-drone delivery system and one-truck-multiple-drones delivery system.It was proved that the two algorithms have high adaptability and can construct feasible solutions quickly in a few seconds.However,the experiment proves that H1 is more suitable for the one-truck-one-drone delivery system,while H2 performs better in the one-truckmultiple-drones delivery system.Thirdly,a simulated annealing algorithm is designed to improve the search quality of solution provided by heuristic algorithms.According to the particularity of the problem,three operators are specifically designed,and the idea of Tabu Search is added to improve the search efficiency.Through random experiments and actual cases,it is proved that the search algorithm can optimize the feasible solution.Finally,through the sensitivity analysis of the key parameters in the actual cases,relevant suggestions are put forward for the development and application of the delivery system with cooperative truck and drones.