Vehicle Routing Problem With Time Windows Considering Emergency Supply Shortage

The research on vehicle route selection of emergency supplies distribution after the occurrence of sudden disasters is of great theoretical significance and practical value.Previous research either only consider a single objective such as shortage of emergency supplies and time requirement,or consider both out-of-stock and delay,aiming at minimizing the total out of stock or total delay.In practice,if only the total stock-out is taken into account,all emergency supplies may be distributed to a certain disaster site,and other disaster sites may not be distributed.If only the total delay is taken into account,priority will be given to the distribution of emergency supplies to the time window is very small disaster sites,resulting in some of the disaster sites were delivered late or not even delivered.This paper comprehensively considers the amount of out-of-stock and delivery delay of emergency supplies at a single point of demand,and aims to minimize the comprehensive penalty cost of maximum out-of-stock delay at a single point of demand.The problem of route selection of emergency supplies distribution vehicles with time window under emergency supplies shortage at a single distribution center and m distribution centers is studied.The main work and innovative productions of the paper are as follows.Vehicle routing model and solution of single distribution center with time window under emergency supplies shortage.Considering that the emergency supplies are in short and the demand point has a time requirement for the delivery of emergency supplies,with the goal of minimizing the comprehensive penalty cost for maximum out-of-stock delay at a single demand point,a vehicle route selection model was established for a single distribution center,the model is solved in two types of out-of-stock and delay situations.In the case of emergency supplies shortage,soft time window and sufficient distribution vehicles,an accurate algorithm A^*is designed,algorithm A^*can calculate the result withinO（ln~2）.In the case of emergency supplies shortage,soft time window and insufficient distribution vehicles,an approximate algorithmGA^*is designed,algorithmGA^*can calculate the result withinO（n~2）,and the approximate ratio ofGA^*is analyzed.Finally,a case study of Wenchuan earthquake in Mianyang was carried out to verify the validity of the model and algorithm.Vehicles rout selection model and solution of m distribution centers with time window under emergency supplies shortage.Considering that the emergency supplies are in short supply and the demand points have time requirements for the delivery of emergency supplies,with the goal of minimizing the comprehensive penalty cost for maximum out-of-stock delay at a single demand point,a vehicle route selection model was established for m single distribution centers,and the model is solved in two types of out-of stock and delay situations.In the case of emergency supplies shortage,soft time window and sufficient vehicles in each distribution center,an accurate algorithm MDA^*is designed,algorithmMDA^*can calculate the result withinO（l（7）m（10）n（8）~2）.In the case of emergency supplies shortage,soft time window and insufficient vehicles in some distributions centers,an approximate algorithmMDGA^*is designed,algorithmMDGA^*can calculate the result within O（7）m（7）m（10）n（8）~2（8）,and the approximate ratio ofMDGA^*is analyzed.Finally,a case study of Wenchuan earthquake in Mianyang was carried out to verify the validity of the model and algorithm.