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

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-08-10 发布日期:2019-04-22
通讯作者: 徐廷政
作者简介:张玉州(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-08-10 Published:2019-04-22
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]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	陈俊, 何庆. 基于余弦相似度的改进蝴蝶优化算法[J]. 计算机应用, 2021, 41(9): 2668-2677.
[3]	牛瑞华, 杨俊, 邢斓馨, 吴仁彪. 基于卷积注意力模块和双通道网络的微表情识别算法[J]. 计算机应用, 2021, 41(9): 2552-2559.
[4]	罗明宇, 骆晓萌, 朱文敏, 张磊, 范秀敏. 船舶狭小空间虚拟人维修姿态建模技术[J]. 计算机应用, 2021, 41(8): 2466-2472.
[5]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[6]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[7]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[8]	汤安迪, 韩统, 徐登武, 谢磊. 基于混沌麻雀搜索算法的无人机航迹规划方法[J]. 计算机应用, 2021, 41(7): 2128-2136.
[9]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[10]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[11]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[12]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[13]	蔡瑞光, 张德生, 肖燕婷. 参数独立的加权局部均值伪近邻分类算法[J]. 计算机应用, 2021, 41(6): 1694-1700.
[14]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[15]	程美英, 钱乾, 倪志伟, 朱旭辉. 信息筛选多任务优化自组织迁移算法[J]. 计算机应用, 2021, 41(6): 1748-1755.