基于改进遗传算法的动态路径规划研究

doi:10.3778/j.issn.1002-8331.1708-0248

计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (19): 49-55.DOI: 10.3778/j.issn.1002-8331.1708-0248

基于改进遗传算法的动态路径规划研究

董小帅1，2，3，毛政元1，2，3

1.福州大学福建省空间信息工程研究中心，福州 350002
2.福州大学空间数据挖掘与信息共享教育部重点实验室，福州 350002
3.福州大学地理空间信息技术国家地方联合工程研究中心，福州 350002

出版日期:2018-10-01 发布日期:2018-10-19

Research on solution of dynamic Vehicle Routing Problem based on improved genetic algorithm

DONG Xiaoshuai1，2，3, MAO Zhengyuan1，2，3

1.Provincial Spatial Information Engineering Research Center, Fuzhou University, Fuzhou 350002, China
2.Key Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education, Fuzhou University, Fuzhou 350002, China
3.National Engineering Research Centre of Geospatial Space Information Technology, Fuzhou University, Fuzhou 350002, China

Online:2018-10-01 Published:2018-10-19

摘要/Abstract

摘要： 在静态路网模型的基础上构建时间依赖的动态路网模型数据库，进行动态路径规划问题研究。针对传统遗传算法在解决此问题中存在的“早熟收敛”、局部搜索能力差等问题，对其进行下列改进：结合随机选择和趋于终点方向的种群初始化策略，在保持初始种群多样性的同时提高其个体质量；根据空间邻近关系选择交叉位置点，有效保留父代优良基因，同时避免“早熟收敛”；采用节点适应度的局部搜索策略，根据路段所属道路等级、转弯类型、实时路况以及与局部路段终点的夹角四个影响因子，构建当前节点邻接节点的适应度，提高局部搜索能力。研究结果表明，改进后的遗传算法具有更好的收敛效果和收敛稳定性，满足行进中的动态最优路径规划对求解精度和效率的要求。

关键词: 动态路径规划, 改进遗传算法, 邻近交叉策略, 局部搜索

Abstract: A time-dependent dynamic database of road network model is established based on the static road network model and the research on dynamic VRP is carried out. Considering the barriers caused by the traditional genetic algorithm in solving this problem, such as “premature convergences”, poor local search abilities and so forth, the following improvements have been made：The quality of initial population is improved while the diversity of the initial population is maintained by combining population initialization strategy of random selection with that of direction tending to end. In order to preserve excellent genes of the parent generation effectively and avoid “premature convergence”, the cross point is selected according to proximity. Based on the local search strategy of node fitness, the fitness of adjacent nodes of the current one is constructed according to four influence factors which are grade, turning type, real-time traffic condition of the road containing the section and the angle between the road and the end of the local section, and the local search capabilities are improved by doing so. The results show that the improved genetic algorithm has a better convergence effect and convergence stability, and meets the requirements for precision and efficiency in planning the dynamic optimal path during marching.

Key words: dynamic VRP（Vehicle Routing Problem）, improved genetic algorithm, adjacent cross strategy, local search

董小帅1，2，3，毛政元1，2，3. 基于改进遗传算法的动态路径规划研究[J]. 计算机工程与应用, 2018, 54(19): 49-55.

DONG Xiaoshuai1，2，3, MAO Zhengyuan1，2，3. Research on solution of dynamic Vehicle Routing Problem based on improved genetic algorithm[J]. Computer Engineering and Applications, 2018, 54(19): 49-55.

[1]	槐创锋，郭龙，贾雪艳，张子昊. 改进A*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(8): 244-248.
[2]	徐辰华，骆珠光，吴冠宏，刘斌. 基于正弦因子和量子局部搜索的灰狼优化算法[J]. 计算机工程与应用, 2021, 57(24): 83-89.
[3]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[4]	姜良重，雷航，李贞昊，钱伟中，施甘图. 采用自适应优化权重的出库货位优化方法研究[J]. 计算机工程与应用, 2021, 57(15): 271-278.
[5]	闫苗苗，刘三阳. 多班级交互式教学优化算法[J]. 计算机工程与应用, 2019, 55(9): 10-16.
[6]	王瑞安，魏文军. 基于stackelberg多步博弈的无人机协同搜索路径规划[J]. 计算机工程与应用, 2019, 55(8): 34-39.
[7]	孙波，姜平，周根荣，卢易天. 改进遗传算法在移动机器人路径规划中的应用[J]. 计算机工程与应用, 2019, 55(17): 162-168.
[8]	刘春苗，张惠珍. 求解无容量设施选址问题的混合蝙蝠算法[J]. 计算机工程与应用, 2018, 54(22): 28-34.
[9]	赵峰1，杨春曦1，陈飞1，黄凌云2，谈诚2. 自适应搜索半径蚁群动态路径规划算法[J]. 计算机工程与应用, 2018, 54(19): 56-61.
[10]	吴聪聪1，赵建立1，2，刘雪静1，陈嶷瑛1. 改进的差分演化算法求解多维背包问题[J]. 计算机工程与应用, 2018, 54(11): 153-160.
[11]	胡炜1，2，曾斌1，姚路1. 事件驱动下的重点海域监测站部署算法研究[J]. 计算机工程与应用, 2017, 53(7): 136-140.
[12]	梁承姬，吴宇. 不确定环境下集装箱码头泊位与岸桥联合调度[J]. 计算机工程与应用, 2017, 53(7): 212-219.
[13]	宋强. 改进迭代局部搜索算法在MMTVRP中的应用[J]. 计算机工程与应用, 2017, 53(7): 248-255.
[14]	康文锋，汤光明，孙怡峰. 装备联合配送路径优化及算法分析[J]. 计算机工程与应用, 2017, 53(24): 147-153.
[15]	孙梦娜，杨如民，余成波. 导航系统中多目标路径平滑化规划的研究[J]. 计算机工程与应用, 2017, 53(18): 17-23.

基于改进遗传算法的动态路径规划研究

Research on solution of dynamic Vehicle Routing Problem based on improved genetic algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics