The Unmanned Aerial Vehicle Routing Problem with Recharging

摘要: The application of Unmanned aerial vehicles (UAVs) in both civilian and military domains is drawing increasing attention recently. This paper investigates a new routing problem of small UAVs for information collection, where UAVs can be recharged at platforms (ground vehicles or stations) distributed in the area. Different from the previous works on UAV routing, the UAVs are allowed to partially recharge their batteries according to the requirement in the following route. A mixed integer nonlinear programming model is developed to formulate the problem, where both the overall time for completing all targets’ observation and the number of UAVs are minimized. An improved adaptive large neighborhood search (ALNS) algorithm with simulated annealing criterion is designed, and a recharging platform insertion heuristic is developed to determine the recharging strategy and construct feasible solutions. To verify the effectiveness of the proposed ALNS algorithm, a set of new benchmark instances are designed based on the well-known Solomon dataset and solved. The computational results are compared with those obtained by the ant colony optimization and variable neighborhood search, which shows that ALNS performs significantly better and stable. Furthermore, analysis of the experimental results indicates that many advantages can be obtained through introducing the recharging strategy for small UAVs.