基于HSBSO算法的城市物流无人机指派

doi:10.3778/j.issn.1002-8331.2405-0233

摘要/Abstract

摘要： 针对头脑风暴优化算法求解带有时间窗同时寄取快递的城市物流无人机任务指派效果差、收敛速度慢等问题，提出了一种混合策略改进的头脑风暴优化算法（hybrid strategy-improved brain storm optimization，HSBSO）。通过Sobol序列初始化种群，增加种群多样性；引入改进的Sine混沌映射修正中间粒子，再用量子行为产生新粒子，提高算法全局搜索能力的同时加快收敛速度；二次函数动态调整局部搜索概率，控制全局搜索及局部搜索的精度；运用基于观测的变异学习策略跳出局部最优。实验结果表明，HSBSO算法与基本BSO算法、GA及SA相比，平均适应度值分别降低1.5%、21.4%及5.7%，程序运行时间分别下降4.5%、98.2%及70.2%，HSBSO算法运行时间增长率为每客户2.2 s，且HSBSO获得的90%解的适应度值优于BSO适应度值的平均值。同时，基于观测的变异学习策略在跳出局部最优的能力及稳定性方面也显著优于莱维飞行、动态透镜成像及透镜成像反向学习策略。

关键词: 城市物流无人机, 量子行为, Sine混沌映射, 基于观测的变异学习策略, 头脑风暴优化算法

Abstract: A hybrid strategy improved brainstorm optimization (BSO) algorithm, termed HSBSO, is proposed to address issues such as poor assignment efficiency and slow convergence in solving unmanned aerial vehicle (UAV) task assignments for city logistics involving simultaneous delivery and pickup with time windows. The HSBSO algorithm initializes the population using Sobol sequences to enhance population diversity. The algorithm introduces an improved Sine chaotic mapping to correct intermediate particles, then generates new particles using quantum behavior to enhance its global search capability while accelerating convergence speed. A quadratic function dynamically adjusts the probability of local search to control the precision of both global and local searches. Finally, an observation-based mutation learning strategy is used to escape local optima. Experimental results demonstrate that compared to BSO, genetic algorithms (GA), and simulated annealing (SA), HSBSO reduces average fitness values by 1.5%, 21.4%, and 5.7%, respectively. It also decreases program execution times by 4.5%, 98.2%, and 70.2%, respectively, and the growth rate of HSBSO’s running time is 2.2 seconds per customer. Moreover, HSBSO achieves fitness values for 90% of solutions that are superior to the average fitness values obtained by BSO. Furthermore, observation-based mutation learning strategy significantly outperforms strategies like Levy flight, dynamic lens imaging, and reverse lens imaging in terms of its ability to escape local optima and its stability.

Key words: urban logistics drones, quantum behavior, Sine chaotic mapping, observation-based mutation learning strategy, hybrid strategy-improved brain storm optimization algorithm (HSBSO)

张书琴, 夏洪山, 江炜, 杨文凯, 王莫凡. 基于HSBSO算法的城市物流无人机指派[J]. 计算机工程与应用, 2025, 61(17): 355-364.

ZHANG Shuqin, XIA Hongshan, JIANG Wei, YANG Wenkai, WANG Mofan. Urban Logistics Drones Task Allocation Based on Hybrid Strategy-Improved Brain Storm Optimization Algorithm[J]. Computer Engineering and Applications, 2025, 61(17): 355-364.

参考文献

[1] GUO X, LI Y, LIU X, et al. Research on vehicle routing optimization for company considering time window constraints[J]. Frontiers in Traffic and Transportation Engineering, 2023, 3(1): 8-17.
[2] WANG X F, YIN S, LUO L Y, et al. Research on multi-UAV task assignment based on a multi-objective, improved brainstorming optimization algorithm[J]. Applied Sciences, 2024, 14(6): 2365.
[3] MICHALOGLOU A, TSITSAS N L. A brain storm and chaotic accelerated particle swarm optimization hybridization[J]. Algorithms, 2023, 16(4): 208.
[4] BACANIN N, ZIVKOVIC M, BEZDAN T, et al. Dimensionality reduction using hybrid brainstorm optimization algorithm[C]//Proceedings of the International Conference on Data Science and Applications. Singapore: Springer Singapore, 2022: 679-692.
[5] HENDRAWAN R, BAIZAL Z K A, WULANDARI G S. Generating a multi-day travel itinerary recommendation using the hybrid ant colony system and brainstorm optimization algorithm[J]. International Journal of Intelligent Engineering and Systems, 2024, 17(2): 223-234.
[6] WANG Y M, SONG L N, ZENG L C, et al. Novel hybrid particle swarm and brainstorm optimization: electromagnetic applications with enhanced performance[J]. IEEE Antennas and Propagation Magazine, 2025, 67(1): 19-33.
[7] YANG Y, LIU B L, WANG J, et al. An improved multi-objective brainstorming algorithm with the application of rapeseed germination characteristics optimization[J]. Computers and Electronics in Agriculture, 2023, 209: 107865.
[8] ZHANG Y H, WEI W H, XIE S H, et al. Brain storm optimization algorithm with an adaptive parameter control strategy for finding multiple optimal solutions[J]. International Journal of Computational Intelligence Systems, 2023, 16(1): 160.
[9] ZHENG J L, LIN Z H, XIE X D. Improved multi-objective brain storm optimization algorithm for RFID network planning[J]. Wireless Networks, 2024, 30(2): 1055-1068.
[10] 曹泽轩, 王晓峰, 谢志新, 等. 融合多策略改进的哈里斯鹰优化算法[J]. 郑州大学学报(理学版), 2023, 55(6): 22-28.
CAO Z X, WANG X F, XIE Z X, et al. Improved Harris hawks optimization fused with multiple strategies[J]. Journal of Zhengzhou University (Natural Science Edition), 2023, 55(6): 22-28.
[11] ZHAO Z Y, XIAO P K, WANG J C, et al. Improved brain-storm optimizer for disassembly line balancing problems considering hazardous components and task switching time[J]. Mathematics, 2024, 12(1): 9.
[12] WU K, GUO X W, ZHOU M C, et al. Multi-objective discrete brainstorming optimizer for stochastic disassembly line balancing problem subject to disassembly failure[C]//Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. Piscataway: IEEE, 2020: 1224-1229.
[13] 胡春安, 熊昱然. 多策略改进的混沌哈里斯鹰优化算法[J]. 计算机工程与科学, 2023, 45(9): 1648-1660.
HU C A, XIONG Y R. A multi-strategy improved chaotic Harris hawk optimization algorithm[J]. Computer Engineering & Science, 2023, 45(9): 1648-1660.
[14] 黄建平, 陈谣, 邢文来, 等. 多策略融合的多目标萤火虫算法[J]. 江西科学, 2023, 41(6): 1039-1047.
HUANG J P, CHEN Y, XING W L, et al. Multi-objective firefly algorithm based on multi-strategy fusion[J]. Jiangxi Science, 2023, 41(6): 1039-1047.
[15] 卢颖, 庞黎晨, 陈雨思, 等. 一种面向城市战的无人机路径规划群智能算法[J]. 兵工学报, 2023, 44(S2): 146-156.
LU Y, PANG L C, CHEN Y S, et al. A swarm intelligence algorithm for UAV path planning in urban warfare[J]. Acta Armamentarii, 2023, 44(S2): 146-156.
[16] 陈功, 曾国辉, 黄勃, 等. 融合互利共生和透镜成像学习的HHO算法[J]. 计算机工程与应用, 2022, 58(10): 76-86.
CHEN G, ZENG G H, HUANG B, et al. HHO algorithm combining mutualism and lens imaging learning[J]. Computer Engineering and Applications, 2022, 58(10): 76-86.
[17] 展广涵, 王雨虹, 刘昊. 混合策略改进的哈里斯鹰优化算法及其应用[J]. 传感技术学报, 2022, 35(10): 1394-1403.
ZHAN G H, WANG Y H, LIU H. Improved Harris hawks optimization algorithm with hybrid strategy and its applic-ation[J]. Chinese Journal of Sensors and Actuators, 2022, 35(10): 1394-1403.
[18] 张海林, 陈泯融. 基于混合策略的改进哈里斯鹰优化算法[J]. 计算机系统应用, 2023, 32(1): 166-178.
ZHANG H L, CHEN M R. Improved Harris hawks optimization algorithm based on hybrid strategy[J]. Computer Systems and Applications, 2023, 32(1): 166-178.
[19] 曹旺. MATLAB智能优化算法: 从写代码到算法思想[M]. 北京: 北京大学出版社, 2021: 240-249.
CAO W. MATLAB intelligent optimization algorithm: from writing code to algorithm thought[M]. Beijing: Peking University Press, 2021: 240-249.
[20] 蒋东华, 刘立东, 陈颖频, 等. 基于分数阶Chen超混沌系统和压缩感知的可视化图像加密算法[J]. 小型微型计算机系统, 2022, 43(11): 2387-2393.
JIANG D H, LIU L D, CHEN Y P, et al. Visual image encry-ption algorithm based on fractional order chen hyperchaotic system and compressive sensing[J]. Journal of Chinese Computer Systems, 2022, 43(11): 2387-2393.