计算机应用

作者：张玉州, 徐廷政, 郑军帅, 饶舜

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

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

基金：安徽省自然科学基金面上项目（1808085MF173）；安徽省高校省级自然科学研究重点项目（KJ2016A438）；安徽省高等学校省级质量工程重点项目（2017jyxm0302）。

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

来源：2019年第8期

《计算机应用》期刊编辑部

查看计算机应用杂志2019年第8期