关键词: 智能交通, 配送点选址, 两阶段鲁棒优化, 无人机, 不确定性

Abstract: In recent years, frequent sudden-onset natural disasters and public health events have attracted widespread attention globally, and these disasters, including earthquakes, floods, epidemics, and mudslides, etc., not only pose a serious threat to the safety of people’s lives and property, but also have a serious impact on public infrastructure and transportation systems, which further aggravate the rescue and emergency response difficulties. In the aftermath of a disaster, the rapid distribution of relief materials is crucial to mitigating the situation and saving lives. As an emerging technology, an unmanned aerial vehicle (UAV) can avoid complex terrain and is not subject to the restrictions of ground transportation interruptions, which significantly improves the efficiency, safety and stability of the “last-mile” distribution, especially in the field of rescue material distribution, showing many unique advantages. However, the suddenness of disasters leads to uncertainty in the distribution of relief materials. Compared with traditional vehicle transportation, the energy consumption of UAV flights is easily affected by internal and external factors such as self-weight and weather. In addition, disaster-stricken areas are often accompanied by unpredictable factors such as population movement, infrastructure damage, and environmental changes, and the actual demand for materials may differ from the predicted results. Based on the humanitarian spirit, it is crucial to quickly meet the demand for relief materials in disaster-stricken areas. However, making decisions based only on forecast data and current weather conditions may lead to problems such as insufficient reserves at delivery points and limited range of drones during the subsequent material transportation phase. Therefore, under uncertain conditions, how to scientifically and reasonably plan the layout of temporary drone delivery points and the distribution of supplies in disaster-stricken areas has become an urgent problem. To improve the distribution efficiency and reliability and provide effective support for post-disaster relief, this paper investigates the site selection of UAV temporary delivery points, the reasonable allocation of UAV resources, and the distribution strategy of demand-splittable delivery, considering the uncertainty of power consumption of UAV and the uncertainty of demand at the disaster-affected sites, which is of important theoretical and practical significance.
In this paper, a two-stage robust optimization model is constructed to cope with the uncertainties of the demand and UAV power consumption at the post-disaster demand points, and the budget uncertainty set is used to characterize these two uncertainties. The model aims to minimize the total costs, including the delivery point siting cost, the drone configuration cost, the drone delivery cost, and the penalty cost incurred for unmet demand. In the first stage, the most suitable locations are selected from a set of known potential site locations to build temporary delivery points, which serve as both landing platforms for UAV and warehouses for storing relief materials. Based on the service radius constraints of drones, the demand points served by each temporary distribution point are determined, and an appropriate number of drones are allocated. In the second stage, when the uncertain information about demand and power consumption is clarified, specific distribution tasks are assigned. This phase fully considers the constraints of UAV’s load, energy consumption, and capacity. Given the limited carrying capacity of UAV, demand-splittable delivery is considered, i.e., when a single delivery cannot satisfy all the demands at the demand point, other UAVs are allowed to complete the subsequent deliveries. To accommodate this scenario, this paper approximates the UAV linear power consumption function. After transforming the model into its dual form and linearizing it, the C&CG algorithm is used to solve the problem.
This paper uses randomly generated data for experimental analysis, and the experimental results show that the two-stage robust optimization model proposed in this paper exhibits great effectiveness, robustness, and flexibility compared to the deterministic model, the two-stage model, and the single-stage robust model. On the basis of effectively controlling the slight increase in total cost, this model significantly improves the ability to withstand uncertainty risk. Especially in the scenario of demand-splittable delivery, the approximate UAV linear power consumption function proposed in this paper shows high practicality and effectiveness. To further verify the effectiveness and efficiency of the algorithm, the C&CG algorithm is compared with the Benders decomposition algorithm, and the experimental results show that the C&CG algorithm outperforms the Benders decomposition algorithm in terms of solving efficiency and handling of large-scale problems. The experiments also finds that the demand uncertainty has a greater impact on the model than the power consumption uncertainty. Decision makers can adjust the uncertainty level parameters and fluctuation coefficients in the model according to the actual situation to obtain solutions adapted to different uncertainty levels, thus enhancing the overall flexibility of the rescue plan. The research results in this paper provide flexible and practical decision support for actual post-disaster rescue operations, which can help to improve the response capability and efficiency of post-disaster rescue by the government and related rescue organizations, and better cope with disaster events.

Key words: intelligent transportation, delivery location, two-stage robust optimization, drone, uncertainty