Modeling and Optimization of Emergency Rescue Vehicle Routing Problem Considering Time Urgency
After unexpected disasters,it is of great theoretical and practical significance to deliver emergen-cy 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 satisfac-tion 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 deliv-ery time,lowest delivery deadline,and smallest penalty cost as the objective,but neglecting the cases of deliv-ery 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 ar-rival 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.Aim-ing at the minimum sum of the total cost(composed of penalty cost for early arrival+penalty cost for de-lay-reward cost for delivery within the time window),we divided the delivery time requirements of emer-gency materials at disaster sites into three situations(one being that where the earliest and latest required de-livery 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 Jiad-ing 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.
time urgencyearly arrival penalty costdelay penalty costvehicle routing optimizationexact algorithm
万方数据
维普
