Abstract: In recent years, the outbreak of sudden disasters such as corona virus pneumonia, floods, earthquakes, and fires has occurred frequently, causing huge casualties and economic losses to our country. In this context, to save human life as much as possible and minimize the loss, it is particularly necessary to supply emergency materials quickly and in time. Therefore, the location-routing optimization problem of emergency logistics distribution center is worthy of in-depth study.
By sorting out the existing research literature, domestic and foreign scholars have carried out a lot of research on logistics distribution center location, distribution route optimization and joint location-routing optimization, but there are still two research gaps: Firstly, most of the existing literature is based on static deterministic network to carry out problem analysis and modeling. The speed of delivery vehicles is constant, but the traffic flow in the real urban road network has significant differences in time and space distribution, and traffic conditions have time-varying characteristics. The influence of the traffic network with real-time speed changes on the emergency facility location-routing optimization problem is ignored. Secondly, in the algorithms for solving the emergency facility location-routing optimization problem, such as the branch and bound method, Dijkstra algorithm, dynamic programming method, etc., the time and space complexity of the algorithm are large, and the calculation rate is low, such as ant colony algorithm, genetic algorithm, tabu search algorithm, simulated annealing algorithm, variable neighborhood search algorithm, quantum competitive decision-making, simulated plant growth and other intelligent optimization algorithms. The applied research on the location-routing optimization problem under the condition of time-varying road network is still insufficient, and the solution accuracy needs to be improved.
To sum up, the time-varying traffic network is rarely considered in the previous research on the location-routing optimization problem of emergency facilities, and the algorithm for solving it has shortcomings such as low calculation rate and poor solution accuracy. In emergency management, time is life. In the road traffic network, the time-varying characteristics of the path travel time caused by a change in the traffic flow throughout the day, and the different travel speeds in the road traffic network will affect the timeliness of emergency rescue. The location selection will also affect the travel time. Therefore, it is necessary to develop an accurate search algorithm that can effectively overcome the time-varying characteristics and uncertainties of dynamic traffic networks and provide technical support for the rapid solution and practical application of the model.
In view of this, this paper uses a multi-stage algorithm based on a time-varying traffic network to solve the location-routing optimization problem of emergency logistics centers, namely the ripple spreading algorithm, which evolves synchronously with the change in the time-coordinated environment of each unit. In each calculation process, the ripple relay race splits many ripples with the change in the node state, and the ripple spreading speed is consistent with the speed of the current road segment in unit time, reflecting the co-evolution of theoptimization steps and the road network traffic environment, generating a set of independent ripple relay race to explore the global optimal path. Taking the vehicle speed of different road conditions in different time periods into consideration, the co-evolution of the emergency vehicle distribution process and the time-varying speed is realized, and the site selection-path optimization that minimizes the total distribution time from the alternative emergency logistics center to all target nodes is constructed.
Taking an emergency material reserve center in Beijing as an example, the application of the above model is demonstrated, using the ripple spreading algorithm, the genetic algorithm, the dynamic Dijkstra algorithm and the branch-and-bound method to solve the optimal location-routing optimization scheme respectively. The calculation speed is much faster than the other three algorithms. In terms of the optimality of delivery time, the optimal solution can be obtained like the dynamic Dijkstra algorithm and the branch and bound method. Although the genetic algorithm is faster, the solution accuracy is very low. The speed change in the time-varying road network will lead to the change in the optimal emergency logistics center solution. The distribution path of the ripple spreading algorithm, and the real-time change of the traffic road network speed are more synergistically coupled and can be used in large-scale site selection. The optimal or better solution is achieved in a short time, and it exhibits excellent optimality and robustness in solving complex time-varying network location problems.

Key words: ripple spreading algorithm, emergency facilities, location-routing problem, time-varying road networks

摘要： 在应急管理中时间就是生命,应急运输车辆的时变速度特征会影响到应急设施选址-路径优化结果,从而影响救援及时性。鉴于此,本文考虑了交通路网的时变速度特征,实现了应急车辆运输过程与交通速度协同演变,构建了以备选应急设施到所有受灾节点的总配送时间最小化的选址-路径模型,设计了一种可以有效克服动态交通网络时变特性的涟漪扩散算法用于求解最佳应急设施选址-路径方案。以北京市石景山区应急物资储备中心为例,与其他算法相比,实验结果表明涟漪扩散算法在解决复杂时变路网下的选址-路径问题时优势明显,具有更强的鲁棒性、更好的求解精度和计算速率。

关键词: 涟漪扩散算法, 应急设施, 选址-路径优化, 时变路网