考虑紧急度的救灾车辆路径问题建模与优化

doi:10.11772/j.issn.1001-9081.2018122516

计算机应用 ›› 2019, Vol. 39 ›› Issue (8): 2444-2449.DOI: 10.11772/j.issn.1001-9081.2018122516

• 应用前沿、交叉与综合 • 上一篇下一篇

考虑紧急度的救灾车辆路径问题建模与优化

张玉州^1,2, 徐廷政^1,2, 郑军帅^1,2, 饶舜^1,2

1. 安庆师范大学计算机与信息学院, 安徽安庆 246133;
2. 安徽省高校智能感知与计算重点实验室, 安徽安庆 246011

收稿日期:2018-12-21 修回日期:2019-02-24 发布日期:2019-04-22 出版日期:2019-08-10
通讯作者: 徐廷政
作者简介:张玉州(1976-),男,安徽无为人,副教授,硕士,主要研究方向:智能交通、进化算法;徐廷政(1995-),男,安徽六安人,硕士研究生,主要研究方向:智能计算、车辆路径问题;郑军帅(1994-),男,安徽亳州人,硕士研究生,主要研究方向:智能计算;饶舜(1986-),男,安徽安庆人,硕士研究生,主要研究方向:智能交通、智能计算。
基金资助:
安徽省自然科学基金面上项目（1808085MF173）；安徽省高校省级自然科学研究重点项目（KJ2016A438）；安徽省高等学校省级质量工程重点项目（2017jyxm0302）。

Modeling and optimization of disaster relief vehicle routing problem considering urgency

ZHANG Yuzhou^1,2, XU Tingzheng^1,2, ZHENG Junshuai^1,2, RAO Shun^1,2

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

Received:2018-12-21 Revised:2019-02-24 Online:2019-04-22 Published:2019-08-10
Supported by:
This work is partially supported by the Anhui Provincial Natural Science Foundation (1808085MF173), the Natural ScienceKey Research Project for Higher Education Institutions of Anhui Province (KJ2016A438), the Key Projects of Provincial Quality Projects for Higher Education Institutions of Anhui Province (2017jyxm0302).

摘要/Abstract

摘要： 为了减少救灾物资配送的延误时间和救灾车辆的总运输时间，引入紧急度的概念，建立了基于紧急度的救灾物资车辆路径问题模型，并设计了一种改进遗传算法对该模型进行求解。首先，采用多种策略生成初始种群；然后，提出一种基于紧急度的任务再分配算法作为局部搜索算子，该算法依据紧急度为延误安置点重新安排配送车辆或调整配送顺序从而减少延误时间，对无延误的车辆优化其路线从而减少总运输时间，以达到延误时间和总运输时间两者最优。在17个数据集上与先来先服务（FCFS）算法、按紧急度排序（URGS）算法和遗传算法（GA）三种算法进行了对比。实验结果表明，具有基于紧急度的任务再分配策略的遗传算法（TRUD-GA）与GA相比，平均延误时间减少25.0%，平均运输时间减少1.9%，与FCFS、URGS算法相比改进则更加明显。

关键词: 紧急度, 优化, 车辆路径问题, 遗传算法, 局部搜索

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.

Key words: urgency, optimization, Vehicle Routing Problem (VRP), Genetic Algorithm (GA), local search

中图分类号:

TP301.6

张玉州, 徐廷政, 郑军帅, 饶舜. 考虑紧急度的救灾车辆路径问题建模与优化[J]. 计算机应用, 2019, 39(8): 2444-2449.

ZHANG Yuzhou, XU Tingzheng, ZHENG Junshuai, RAO Shun. Modeling and optimization of disaster relief vehicle routing problem considering urgency[J]. Journal of Computer Applications, 2019, 39(8): 2444-2449.

参考文献

[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.)

考虑紧急度的救灾车辆路径问题建模与优化

Modeling and optimization of disaster relief vehicle routing problem considering urgency

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	力尚龙, 刘建华, 贾鹤鸣. 融合多狩猎协调策略的爬行动物搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2818-2828.
[2]	刘栋, 李晨航, 吴长茂, 茹法鑫, 夏媛媛. 基于可校正强化搜索遗传算法的光学系统自动设计[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2838-2847.
[3]	赵秦壮, 谭红叶. 基于自适应阈值学习的时序因果推断方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2660-2666.
[4]	张睿, 张鹏云, 高美蓉. 自优化双模态多通路非深度前庭神经鞘瘤识别模型[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2975-2982.
[5]	周毅, 高华, 田永谌. 基于裁剪优化和策略指导的近端策略优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2334-2341.
[6]	杨乐, 张达敏, 何庆, 邓佳欣, 左锋琴. 改进猎人猎物优化算法在WSN覆盖中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2506-2513.
[7]	高培根, 锁斌. 基于加权犹豫模糊集的实验设计与分阶段PSO-Kriging建模[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2144-2150.
[8]	马天, 席润韬, 吕佳豪, 曾奕杰, 杨嘉怡, 张杰慧. 基于深度强化学习的移动机器人三维路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2055-2064.
[9]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[10]	袁子璇, 翁小清, 戈宁振. 基于正交局部保持映射和成本优化的多变量时间序列早期分类模型[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1832-1841.
[11]	赵楷文, 王鹏, 童向荣. 基于双阶段搜索的约束进化多任务优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1415-1422.
[12]	刘晓芳, 张军. 概率驱动的动态多目标多智能体协同调度进化优化[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1372-1377.
[13]	郑志强, 段海滨. 基于有限忍耐度鸽群优化的无人机近距空战机动决策[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1401-1407.
[14]	高麟, 周宇, 邝得互. 进化双层自适应局部特征选择[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1408-1414.
[15]	魏凤凤, 陈伟能. 分布式数据驱动的多约束进化优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1393-1400.