求解带时间窗车辆路径问题的改进FPA  

Improved flower pollination algorithm for vehicle routing problem with time windows

作　　者：丛扬潇 袁志高 李素[1] 姜缘平 王祖荣 CONG Yang-xiao;YUAN Zhi-gao;LI Su;JIANG Yuan-ping;WANG Zu-rong(Computer College,Beijing Technology and Business University,Beijing 100048,China)

机构地区：[1]北京工商大学计算机学院,北京100048

出　　处：《计算机工程与设计》2024年第3期793-798,共6页Computer Engineering and Design

基　　金：国家自然科学基金青年基金项目(42101470)。

摘　　要：车辆路径规划问题广泛应用于物流行业,为解决这一NP难的组合优化问题,提出一种求解带时间窗车辆路径问题的改进花授粉算法。针对FPA存在寻优精度低和过早陷入局部最优等缺陷,在原始FPA中引入遗传算法的交叉和变异因子,设计基于精英父代的多点交叉算子和单亲多点基因变异换位算子;对FPA中的转换概率p进行自适应调整并重新定义全局授粉和局部授粉操作;采用国际通用标准测试集Solomon对算法进行测试,将求得结果与已知多个算法求得的结果进行对比分析。其结果表明,改进FPA求解带时间窗车辆路径问题是可行有效的。Vehicle path planning problem is widely used in logistics industry.To solve this NP difficult combinatorial optimization problem,an improved pollination algorithm for solving vehicle routing problem with time windows was proposed.For the pollination of flowers,there are some shortcomings such as low precision of optimization and premature of falling into local optimum.The crossover and mutation factors of genetic algorithm were introduced into the pollination algorithm of flower,and the multi-point crossover operator and single parent multipoint gene mutation transposition operator based on elite fathers were designed.The transformation probability p in the pollination algorithm of the flower was adaptively adjusted and the global pollination and the local pollination operations were redefined.The algorithm was tested using an international standard test set Solomon,and results obtained were compared with those obtained using known algorithms.The results show that the improved pollination algorithm is feasible and effective in solving the vehicle routing problem with time windows.

关 键 词：花授粉算法 遗传算法 路径优化 时间窗 自适应 算法改进 物流配送 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]