Abstract:

Efficient emergency supply distribution after sudden disasters stands as a critical factor in mitigating overall losses. The arrangement of emergency supply distribution encounters two challenges. First， it is difficult to mobilize sufficient emergency supply in a short time after the disaster， resulting in unmet needs of victims and subsequent losses. Second， there exists a pressing demand for timely supply arrivals， and any delays in emergency supply distribution cause further losses. Ensuing equitable access to disaster-stricken individuals necessitates vigilant monitoring of shortages of supply and impediments of distribution at each demand point. It is of great significance to formulate the routing strategy for scarce emergency supply distribution with time windows to reduce dual losses of storage and delay at each demand point as much as possible.In this paper， the problem of determining the optimal routes for emergency supply distribution is studied with the objective of minimizing the maximum dual losses of shortage and delay of each demand point. The premise acknowledges that the emergency supply is scarce and the available vehicles at the distribution center are potentially inadequate. The definition of shortage loss is given based on the shortage ratio， and the definition of delay loss is given based on piecewise penalty function.Further comprehensive consideration of supply shortage and distribution delay of each demand point servers as the foundation of developing a route selection model for emergency supply distribution. The objective of this proposed model is to minimize the maximum dual losses of shortage and delay of each demand point， aiming to avoid critical shortage at any single demand point and ensure adherence to stringent distribution time windows.An in-depth analysis of scenarios regarding supply shortage and distribution delay at each demand point is conducted. It delineates solutions in two distinct cases： sufficient vehicles and insufficient vehicles. In the case with sufficient vehicles， all amounts of supply in the distribution center can be sent to demand points. The routes for emergency supply distribution is initially determined based on the shortest paths from the distribution center to each demand point. Then， the quantities of supply distributed to each demand point is determined by equating the shortage ratio at each demand point， and an algorithm A^{\mathrm{*}} is developed accordingly. In the case with insufficient vehicles， it is not possible to send all amounts of supply in the distribution center， and an approximate algorithm G{A}^{\mathrm{*}} is developed to solve the problem in this case.By analyzing the performances of the proposed algorithms， the results demonstrate that algorithm A^{\mathrm{*}} is an exact algorithm in the case with sufficient vehicles. Its time complexity is O(n^{\mathrm{3}})， where n represents the number of demand points. The results also evaluate the time complexity of the approximate algorithm G{A}^{\mathrm{*}} in the case with insufficient vehicles. Its time complexity is O(L{n}^{\mathrm{2}})， where L denotes the number of vehicles and n represents the number of demand points. Additionally， the approximate ratio of algorithm G{A}^{\mathrm{*}} and the upper and lower bounds of the approximate ratio are also proved.A case study is conducted focusing on the rescue in Luding County， Sichuan Province in September 2022 with a magnitude 6.8 earthquake. The dataset utilized for analysis is based on actual road conditions and related reports from CHINANEWS.COM. The algorithms developed in this paper are used to solve the route selection model for emergency supply distribution with the objective of minimizing the maximum dual losses of shortage and delay of each single demand point. The routing strategy is obtained， and an approximation ratio of 1.32 is yielded when comparing the maximum dual losses of shortage and delay at each single demand point to the result of the optimal solution.By investigating the route selection for emergency supply distribution based on dual losses of shortage and delay， the model developed in this paper aims to prevent the simultaneous occurrence of maximum shortage and delay at a single demand point， thereby enhancing the effectiveness of emergency supply distribution after sudden disasters. The proposed algorithms also provide reference for similar research problems. Future research endeavor will likely focus on building a model that closely mirrors real-world scenarios or refining the algorithm to achieve improved efficacy.

Key words: scarcer emergency supply, distribution time windows, route selection problem, dual losses of shortage and delay, approximation algorithm