基于蚁群优化算法的物流配送路径研究

邓必年
摘 要: 针对区间重构方法进行物流配送路径寻优收敛性不好的问题,提出一种基于蚁群优化算法的物流配送路径优化选择方法。采用重极标差法进行物流配送路径的邻域网格分割,进行路径的动态实时统计特性分析,设计物流配送路径选择流程。采用蚁群优化算法进行物流配送路径的自适应寻优,实现路径优化选择规划。仿真结果表明,采用该算法进行物流配送路径规划,缩短了配送行程距离,节省了物流时间。
关键词: 蚁群算法; 物流; 配送; 路径规划; 重极标差法
中图分类号: TN99?34; TP242 文献标识码: A 文章编号: 1004?373X(2017)15?0167?04
Abstract: Aiming at the poor optimization convergence of the interval reconstruction method for logistics distribution route, an ant colony optimization algorithm based optimal selection method of logistics distribution route is proposed. The rescaled range analysis method is used to carry out the neighborhood mesh segmentation of the logistics distribution route, analyze the dynamic real?time statistical property of the route, and design the selection process of the logistics distribution route. The ant colony optimization algorithm is used to perform the adaptive optimization of the logistics distribution path to realize the path optimization selection and planning. The simulation results show that the algorithm used to plan the logistics distribution path can shorten the distribution distance, and save the logistics time.
Keywords: ant colony algorithm; logistics; distribution; path planning; rescaled range analysis method
随着电子商务和电子物流产业的快速发展,物流的配送路径优化是提高物流配送速度和效率的关键因素。传统方法中,对物流配送路径规划主要采用的是最短路径法和网格分割法等[1?2],该类方法以最短路径和区域网格为路径选择准则,但是随着物流规模的扩大,上述方法不能实现最优路径选择。随着智能仿生算法的发展,利用动物觅食的路径寻优策略,采用智能仿生算法进行物流配送路径寻优受到人们的重视[3],本文利用蚂蚁种群的觅食寻优策略进行物流配送路径规划,提出一种基于蚁群优化算法的物流配送路径优化选择方法。
1 邻域网格分割及物流配送路径选择
1.1 重极标差法的物流配送路径邻域网格分割
为了实现对物流配送路径的规划,采用蚁群算法进行路径寻优,首先需要进行配送路径和邻域网格的分割设计。把物流配送路徑的链接线路分为公路、铁路、水运、航空等路径。采用重极标差法(Rescaled Range Analysis)对物流供应链中的区域覆盖进行至小尺度分割[4],将一个物流配送路径的邻域网格分割为一个长度为的个子序列,在小尺度时间范围内满足;将每一个物流配送路径覆盖的网格子序列采用表示,,在中的物流供应链的动力学演化行为序列属于布朗运动。采用表示物流运输承载量,其中,对于每一个子序列,根据重极标差法,得到物流路径分形的边向量:
1.2 物流配送路径选择流程
在采用重极标差法进行物流配送路径的邻域网格分割的基础上,进行路径的动态实时统计特性分析,构建基于蚁群优化的路径规划模型,在物流配送的路径分布空间中,随机值初始化个蚂蚁个体,蚂蚁个体在时刻在物流配送出发点的位置可表示为,采用路径状态特征融合方法[5]对个体在时刻的物流配送速度表示为,该速度能有效描述物流配送路径的传输效率。求解蚂蚁个体在全局解向量空间中的最优路线,得到最优解为。
在进行路径优选过程中,设时刻蚁群个体在物流中转节点的信息素强度最小,以此为约束条件,求得邻域网格中下一个移动点为。在蚁群觅食过程中,通过更新全局蚁群信息得到路径中转节点的信息素强度为:
式中:为物流配送路线网格上的蚁群个体节点之间的等效距离,称为物流配送邻域网格分割的前端等效距离;为物流配送路径中转节点到目标位置之间的等效距离,称为后端等效距离。
通过邻域网格分割寻优计算,动态实时统计分析路径,求解蚂蚁的最优线路作为最优配送路径。根据上述设计思想,得到基于蚁群优化算法的物流配送路径选择流程,如图1所示。
2 物流配送路径选择实现
2.1 物流配送路径的选择方法
蚁群优化算法的物流配送路径优化选择方法首先进行路径的动态实时统计特性分析,在大规模群体行为下,蚁群在维搜索空间的集合为为蚁群的个数,蚂蚁在进行配送路径寻优过程中经历过的最好位置为为物流配送路径的线路个数。每个蚁群个体的自身速度和位置计算公式描述为:
式中:为迭代次数;和为学习因子。初始化个蚁群为。
采用惯性权重的对角寻优方法进行均匀遍历[7],得到物流配送路径的线路对角元素为:
为了改善蚁群在物流配送路径规划中的全局寻优能力,采用个体之间的差异度作为调节因子,即:
蚁群在时刻的惯性权重取值描述为:
式中和分别是惯性权重上下限。
采用蚁群优化算法进行物流配送路径的自适应寻优,采用重采样测量方法对物流配送路径规划中的路径和效益进行均衡匹配,设种群中蚁群个体数为蚁群信息素浓度特征为群体的适应度方差为:
在蚁群解向量的区间中,对全局极值位置进行自适应寻优,蚁群寻优的检测阈值为当时,保存最优结果,均衡权重为下,利用物流配送路径中的蚂蚁个体信息对初值的敏感特点,统计每个蚁群的动态实时特性,得到蚁群的变异特征集合将物流配送路径的规划过程转换成决策变量的优化求解过程:
定义为路径的动态实时统计特性,得到时刻物流路径节点分布的状态估计式为:
在位置更新阶段,根据列表入口进行物流配送路径的动态决策,第只蚂蚁在时刻的位置为:
式中:表示的先验概率分布特征向量。从初始信息素概率密度函数中调整当前蚂蚁个体的位置函数。
以蚂蚁移动轨迹确定物流路径规划方向,得到蚁群个体中蚂蚁到蚂蚁的物流配送路径规划为:
由此实现配送路径的选择计算。
2.2 物流配送路径的自适应寻优
由于物流配送过程中受到交通拥堵等因素的干扰,需要进行干扰滤波和邻域变化调整,滤波系统函数描述为:
根据列表入口进行物流配送路径的动态决策,在最优移动概率选择下,物流配送路径规划的全概率覆盖模型为:
在通过次数为的迭代处理后,构建物流配送全概率覆盖模型,解决约束冲突问题[8],设定蚁群的适应度值为,得到物流配送路径规划的自适应路径选择表达式为:
在物流配送区域的动态决策范围内,每个个体避开交通拥堵等障碍的目标函数及最优路径选择函数为:
式中:表示两个物流配送目标点的物流配送的中转节点之间的直线路径间的距离。
3 结果与分析
实验测试中,具体实验参数与环境设置如下:物流配送的环境区域覆盖规模取3 000 m×4 000 m,在配送区域坐标系内,配送起点和配送终端的坐标设定分别为[0,0],[260,380],起始点到目标点的直线长度为2 031.98 m, 蚁群的学习速率,初始化惯性权重为0.3,蚁群个体位置变换概率=0.45,最大迭代次数为30次。进行物流配送规划仿真,优化前后的物流配送路径规划图如图2和图3所示。
分析图2和图3的结果得知,采用本文方法進行物流配送路径规划能明显缩短配送路径,提高物流配送效率。表1给出了不同的物流配送路径规划方法进行配送的时间开销和距离定量分析结果,从表1中的结果得知,本文方法能降低物流配送的时间开销,缩短总体配送距离,提高物流配送效率。
4 结 语
本文研究了物流配送的路径优化问题,提出基于蚁群优化算法的物流配送路径优化选择方法,采用重极标差法进行物流配送路径的邻域网格分割,进行路径的动态实时统计特性分析,采用蚁群优化算法进行物流配送路径的自适应寻优,以蚁群个体的信息素强度作为导引参量,实现路径优化选择规划。仿真结果表明,采用该算法进行物流配送路径规划缩短了配送行程距离,节省了物流时间,具有较好的应用价值。
参考文献
[1] CHARLES P, BILODEAU G, BERGEVIN R. SuBSENSE: a universal change detection method with local adaptive sensitivity [J]. IEEE transactions on image processing, 2015, 24(1): 359?373.
[2] LI Shutao, YANG Bin. A new pan?sharpening method using a compressed sensing technique [J]. IEEE transactions on geo?sciences and remote sensing, 2011, 49(2): 738?746.
[3] YANG Shuyuan, WANG Min, JIAO Licheng. Fusion of multispectral and panchromatic images based on support value transform and adaptive principal component analysis [J]. Information fusion, 2012, 13(3): 177?184.
[4] 任志刚,赵松云,黄姗姗,等.求解多维背包问题的蚁群?拉格朗日松弛混合优化算法[J].控制与决策,2016,31(7):1178?1184.
[5] 史恒亮,白光一,唐振民,等.基于蚁群优化算法的云数据库动态路径规划[J].计算机科学,2010,37(5):143?145.
[6] 熊杰,冯春,张怡.基于复杂网络的灾难救援物流网络鲁棒性分析[J].系统仿真学报,2013,25(7):1639?1645.
[7] 贾安超,周刚.基于粗糙集和BP神经网络的供应商选择研究[J].物流技术,2012,31(12):229?232.
[8] 吴建军,段淑敏.交通拥堵状态下的智能调度平台的设计与仿真[J].现代电子技术,2016,39(16):40?43.