1. School of Computer and Information, Anqing Normal University, Anqing Anhui 246133, China; 2. Key Laboratory of Intelligent Perception and Computing in Anhui Province, Anqing Anhui 246011, China
Abstract：In order to reduce the delay time of disaster relief materials distribution and the total transportation time of disaster relief vehicles, the concept of urgency was introduced to establish a vehicle routing problem model of disaster relief vehicles based on urgency, and an improved Genetic Algorithm (GA) was designed to solve the model. Firstly, multiple strategies were used to generate the initial population. Then, an urgency-based task redistribution algorithm was proposed as local search operator. The proposed algorithm achieved the optimal delay time and total transportation time based on urgency. The delay time was reduced by rescheduling the vehicle or adjusting the delivery sequence for delay placements. The routes of the vehicles without delay were optimized to reduce the total transportation time. In the experiments, the proposed algorithm was compared with First-Come-First-Served (FCFS) algorithm, Sort by URGency (URGS) and GA on 17 datasets. Results show that the Genetic Algorithm with Task Redistribution strategy based on Urgency Degree (TRUD-GA) reduces the average delay time by 25.0% and decreases the average transportation time by 1.9% compared with GA, and has more obvious improvement compared with FCFS and URGS algorithms.
[1] LI Q, TU W, ZHUO L. Reliable rescue routing optimization for urban emergency logistics under travel time uncertainty[J]. International Journal of Geo-Information, 2018, 77(7):1-21. [2] 徐浩,李佳川,韩传峰.震后运速受限条件下的多目标定位:路径问题研究[J].管理工程学报,2017,31(4):147-155. (XU H, LI J C, HAN C F. Multi-target localization under the condition of limited speed after earthquake:research on path problem[J].Journal of Industrial Engineering/Engineering Management,2017,31(4):147-155.) [3] 张国富,王永奇,苏兆品,等.应急救援物资多目标分配与调度问题建模与求解[J].控制与决策,2017,32(1):86-92. (ZHANG G F, WANG Y Q, SU Z P, et al. Modeling and solving multi-objective allocations-cheduling problem for emergency relief materials[J]. Control and Decision, 2017, 32(1):86-92.) [4] SHAHPARVARI S, ABBASI B, CHHETRI P, et al. Vehicle routing and scheduling for bushfire emergency evacuation[C]//Proceedings of the 2015 IEEE International Conference on Industrial Engineering and Engineering Management. Piscataway, NJ:IEEE, 2015:696-700. [5] HE Y, WEN J, HUANG M. Study on emergency relief VRP based on clustering and PSO[C]//Proceedings of the 11th International Conference on Computational Intelligence and Security. Washington, DC:IEEE Computer Society, 2015:43-47. [6] 石建力,张锦.需求点随机的分批配送VRP模型与算法研究[J].控制与决策,2017,32(2):213-222. (SHI J L,ZHANG J.Model and algorithm for split delivery vehicle routing problem with stochastic customers[J].Control and Decision,2017,32(2):213-222.) [7] ZHAO J, GUO Y, DUAN X. Dynamic path planning of emergency vehicles based on travel time prediction[J]. International Journal of Communications, Network and System Sciences, 2018, 11(2):Article ID:9184891. [8] LIU J, XIE K. Emergency materials transportation model in disasters based on dynamic programming and ant colony optimization[J]. Kybernetes, 2017, 46(4):656-671. [9] QIN J, YE Y, CHENG B, et al. The emergency vehicle routing problem with uncertain demand under sustainability environments[J]. Sustainability, 2017, 9(3):1-24. [10] ZHENG Y, LING H. Emergency transportation planning in disaster relief supply chain management:a cooperative fuzzy optimization approach[J]. Soft Computing, 2013, 17(7):1301-1314. [11] 易云飞,蔡永乐,董文永,等.求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J].电子学报,2015,43(10):2053-2061. (YI Y F, CAI Y L, DONG W Y, et al. Improved ITO algorithm for multiobjective real-time vehicle routing problem with customers' satisfaction[J].Acta Electronica Sinica,2015,43(10):2053-2061.) [12] 任锡德,朱建明,王晶,等.考虑均衡性的不确定时间车辆调度问题研究[J].运筹与管理,2013,22(2):86-91. (REN X D, ZHU J M, WANG J, et al. Research on load-balancing vehicle routing problem with uncertain travel time[J]. Operations Research and Management Science, 2013, 22(02):86-91.) [13] 文仁强,钟少波,袁宏永,等.应急资源多目标优化调度模型与多蚁群优化算法研究[J].计算机研究与发展,2013,50(7):1464-1472. (WEN R Q, ZHONG S B, YUAN H Y, et al. Emergency resource multi-objective optimization scheduling model and multic-olony ant optimization algorithm for emergency resources[J].Journal of Computer Research and Development,2013,50(7):1464-1472.) [14] 徐志宇,张杰,彭嘉臻,等.应急物流的分批配送模型及亚启发式算法求解[J].系统仿真学报,2012,24(12):2500-2505, 2510. (XU Z Y, ZHANG J, PENG J Z, et al. Split delivery model and metaheuristic approach for emergency logistics[J]. Journal of System Simulation, 2012, 24(12):2500-2505, 2510.) [15] 朱建明,黄钧,刘德刚,等.突发事件应急医疗物资调度的随机算法[J].运筹与管理,2010,19(1):9-14. (ZHU J M, HUANG J, LIU D G, et al. Randomized algorithm for vehicle routing model for medical supplies in large-scale emergencies[J]. Operations Research and Management Science, 2010, 19(1):9-14.)
2019, Vol. 39 
