考虑时间紧迫度的应急救援车辆路径问题建模与优化

Modeling and Optimization of Emergency Rescue Vehicle Routing Problem Considering Time Urgency

考虑时间紧迫度的应急救援车辆路径优化,具有重要的理论价值与实际意义。以总费用(早到惩罚费用+延时惩罚费用-时间窗内送达奖励费用)最小为目标构建模型,并针对车辆在时间窗内送达以及早到、晚到的三种不同情形,定义时间紧迫度,设计精确算法A求解,证明了算法A的时间复杂度为O(ln^(3)),其中l、n分别为配送车辆和受灾点的个数,以决策应急救援车辆的行驶路径。最后以上海嘉定区疫情防控应急物资配送为例,对模型和算法的有效性进行了证明,可为政府部门应急救援路径选择提供有效理论依据。

After unexpected disasters,it is of great theoretical and practical significance to deliver emergency materials to disaster sites as soon as possible or at least to the satisfaction of the time requirement.There are two research directions in the existing studies;one is to optimize the routing of emergency rescue vehicles while considering demand requirements and with minimum stock shortage and maximum demand satisfaction ratio as the objective,but neglecting the time window requirements.The second is to optimize routing of emergency rescue vehicles while considering the time window requirements and with shortest total delivery time,lowest delivery deadline,and smallest penalty cost as the objective,but neglecting the cases of delivery outside of time window;moreover,the penalty cost mentioned above only includes delay penalty to the exclusion of those relating to the extra resource occupation caused by early arrival of the delivery vehicles.However,in practice,the early arrival of emergency rescue vehicles will take up limited unloading space or human resources,and reduce the dispatching efficiency of emergency rescue vehicles.By setting the early arrival penalty cost,we can prevent excessive resources(such as emergency rescue vehicles)from reaching the disaster sites ahead of schedule,ensuring that the emergency materials arrive within a predetermined time window to reduce unnecessary waiting time.In view of the shortcomings of previous studies,we proposed a method that comprehensively considered the three different situations of the delivery vehicles,namely arriving within the time window,early arrival,and late arrival,and established the route optimization model of emergency rescue vehicles with the goal of minimizing the sum of total costs at all disaster sites.First,we set up an undirected network G=(V,E),and defined the concept of time urgency.On such basis,we constructed the route optimization model of emergency rescue vehicles considering time urgency.Aiming at the minimum sum of the total cost(composed of penalty cost for early arrival+penalty cost for delay-reward cost for delivery within the time window),we divided the delivery time requirements of emergency materials at disaster sites into three situations(one being that where the earliest and latest required delivery time of emergency materials is different in all disaster sites;two being that where some disaster sites have the same earliest required delivery time of emergency materials but different latest required delivery time;and three being that where some disaster sites have the same latest required delivery time of emergency materials but different earliest required delivery time).Then,we designed an exact algorithm A to solve the problem,and obtained the time complexity function to determine the driving path of the emergency rescue vehicles.Finally,taking the distribution of emergency materials for epidemic prevention and control in Jiading District of Shanghai as an example,we proved the effectiveness of the model and algorithm.The research results can provide effective theoretical basis for government departments to choose emergency rescue routes.