Two-Echelon Routing Problem for Parcel Delivery by Cooperated Truck and Drone

A new variant of the two-echelon routing problem is investigated, where the truck and the drone are used to cooperatively complete the deliveries of all parcels. The truck not only acts as a tool for parcel delivery but also serves as a moving depot for the drone. The drone can carry several parcels and take off from the truck, while returning to the truck after completing the delivery. The energy consumption model for the routing process of the drone is analyzed, when it is utilized to deliver multiple parcels. A two-stage route-based modeling approach is proposed to optimize both the truck’s main route and the drone’s adjoint flying routes. A hybrid heuristic integrating nearest neighbor and cost saving strategies is developed to quickly construct a feasible solution. The simulated annealing algorithm is integrated with Tabu search, to improve the quality of the solution as well as the search efficiency. Random instances at different scales are used to test the performance of the proposed algorithm. A case study based on the practical road network in Changsha, China, is presented, through which the sensitivity analysis is conducted with respect to some critical factors.