Vehicle Routing Problem With Drone Station

In recent years,drone scheduling has become a highly active research area both in industry and academia.In particular,drones can promise greater delivery efficiency in the field of logistics.In the meanwhile,many scholars consider drones in the distribution system and are committed to research into the vehicle routing problem with drone.Nevertheless,few studies have considered economic-benefits producing drone stations.Against this background,this paper introduces drone stations that can provide basic drone services such as takeoff,landing,charging,loading and unloading of packages,and proposes the vehicle routing problem with drone station(VRP-DS).In addition,this paper constructs an arc-based model for VRP-DS,regarding the latest arrival time for packages,the number of drones and the maximum flying duration,combining the lowest total cost as the objective function.Trucks departing from warehouses can visit customers,or drone stations,and a drone can visit customers from a drone station.The VRP-DS involve both truck scheduling and drone scheduling,thus contains numerous variables and complex constraints,and presents an angular structure.Hence,this paper decomposes the original problem model into a path-based main problem model and two sub-problem models which are truck sub-problem and drone sub-problem,by Dantzig-Wolfe decomposition.And this paper designs a branch and price algorithm to get the global optimal solution.This paper also provides multiple instances and numerical experiments to verify the correctness of the model and the effectiveness of the algorithm.The numerical results reveal the following findings: 1)The depth-first search strategy is superior to the breadth-first search strategy in VRP-DS.2)The branch and price algorithm is superior to the commercial solver Gurobi in terms of solving time and quality.3)The proportion of customers within drone’s service area has a more significant impact on the total cost,rather than the speed and number ratios of drones to trucks.4)The travelling cost of the trucks occupies a higher proportion of the total cost.5)Expanding the use of drones can yield sizable cost savings.