基于改进鲸鱼算法的汽车材料运输应急调度及平台研究

王 爽,梁 娜,刘庆军,安绘春

(1.铜川职业技术学院,陕西 铜川 727031;2.陕西科技大学,陕西 西安 710016)

在汽车材料中,存在部分危险化学品,一旦运输时间过长,容易在空气中暴露,进而造成严重的环境污染[1-2]。因此,建立科学的调度平台,对提高汽车材料运输的应急调度起得到积极的作用。而针对应急调度问题,文家燕等提出灰狼优化算法(GWO)和非支配排序遗传算法(NSGA-Ⅱ)应用到矿车的运输调度中,验证了算法寻优的效果,但没有考虑路况变化因素[3];王思涵等采用鲸鱼群算法对车间的调度工作进行了测试,验证了算法的可行性和有效性[4];蒋华伟等针对鲸鱼群算法求解多配送中心带时间窗的物资应急调度问题时存在的易陷入局部极值等缺点,提出一种改进离散鲸鱼群算法[5]。基于此,研究则结合汽车材料应急运输中存在的暴露易导致环境污染的问题,考虑路况变化因素对运输调度方案的影响,提出采用鲸鱼群算法,并运用到汽车材料运输的调度方案中,从而保证汽车危险材料的应急调度安全。

1 汽车材料运输应急调度平台总体框架

参考主流的运输调度算法思维导图(见图1)总结目前主流的运输调度方法,研究提出基于分组移动的鲸鱼群算法的运输应急调度平台,其采用多层次技术结构,将路况、运输距离、时间等因素加入决策方案中;具体平台设计框图如图2所示。

图1 主流的运输调度算法

图2 平台整体框架

由图2可知,整个框架分为4层结构,其中应用服务层是配送中心调度管理的系统平台;系统支持层是为应用服务层提供相应的算法和基本应用的支持,包括用户管理和数据的管理;基础数据层是提供地理及路线等基础数据,存储系统应用用户等重要数据;底层硬件是放置在运输车辆中的,目的是让运输车辆和平台建立联系,并接收调度方案,安排运输车辆行驶路线。

2 平台硬件与软件设计

2.1 硬件部分设计

本应急调度平台的需求:①对运输车辆进行GPS定位;②对运输车辆发送调度命令。因此,考虑到上述需求,讲运输车辆基础硬件设计为如图3所示。在硬件部分中,主要包括PIC单片机、GPS模块和GSM模块等。平台通过GPS精确定位运输工具,通过GSM数据接口完成应急调度。

图3 硬件结构图

2.2 平台界面设计

汽车材料运输的Web页面是面向应急调度系统的二次开发,其中页面模块中对应的关系如图4所示。

图4 软件设计框架

3 基于分组移动的鲸鱼群算法平台应急调度策略设计

对汽车材料运输的调度主要是通过应急调度决策模块实现,调度决策过程需要综合考虑已发出的车辆、路况动态变化、运输距离等因素,通过算法选择较优的运输路径,再由平台发送调度方案到需要进行移动的运输车辆基础设备中,从而高效完成材料运输的工作。综合目前的应急调度优化算法,采用鲸鱼群算法(WSA)进行改进和求解[6-8]。具体从以下几点改进:

3.1 初始化方式

在传统鲸鱼群算法中,引导个体在求解较优路径时具有较好效果,但在求解大规模车辆路径问题时,求解速度下降。当道路路况变化时,会导致种群更新或多个种群求解速度不达标,所以提出的基于分组移动的鲸鱼群算法进行路线更新。其中,采用基于最短路径变异的混合算子对种群进行初始化;然后进行分组,并对剩余未接收到材料的接收点进行配送。算法优先使用当前已发出的车辆,若不满足条件,再从配送中心派出新的车辆进行汽车危险化学品材料的运输。考虑到路况信息更新时需要重新规划未被访问的接收点,此时开始节点不一定是配送中心(可能是道路交叉点或接收点),且此时的车辆不一定处于满载状态。因此,采用最短路径算法生成的子问题初始解,并对初始解进行扩充,从而得到初始种群。

3.2 种群个体分组

对当前种群的个体根据其差异性进行等量划分,进行层次聚类分组,具体算式:

(2)

式中:μi、Si分别表示第i类样本的均值向量和样本集合。

衡量种群中个体的质量,具体衡量公式:

(3)

式中:di表示个体i完成配送行驶的总距离。

计算个体间的差异,具体计算公式:

(4)

式中:n代表总接收点数;m表示个体使用的车辆数。

3.3 个体移动方式

在上述基础上,引入长期记忆单元(LTMU)来记录种群中最优个体。当路况发生变化时,若当前种群不是初始种群,则将新种群最优个体与初始种群中的最优个体进行比较,若新种群的个体优于初始种群个体,则用新种群替换初始种群;反之不变。替换后更新LTMU的其他个体,具体过程如图5所示[9-15]。

图5 改进算法图示

3.4 扩展搜搜空间策略

随着节点个数增加,鲸鱼个体的移动是以原有个体为基础,引导个体为导向进行的局部小范围搜索;而种群个体的更新趋于空间解,在移动时,计算量呈爆炸式增长,若种群中个体都进行移动会导致种群多样性降低,不能获取在全局范围内的最优解。因此使用种群多样性来反映种群个体移动时总搜索空间的大小和个体间差异表示,因此在式(4)基础上构建式(5)来衡量种群多样性。

(5)

式中:s代表种群大小;dij为式4计算所得的个体间的差异性。

另外,由式(3)可知,个体质量与个体所表示的车辆总行驶距离成反比,即个体所表示的车辆总行驶距离越长,其质量越差。而在同一个体中,由于每辆车所配送的接收点不同,导致车辆行驶的距离具有一定差异,因而个体中每辆车的行驶距离对其质量产生的影响程度也不同。在同一车辆段(车辆段表示一个车辆的完整行驶路径,包括车辆所访问的接收点及其配送顺序)中,车辆访问某一接收点所行驶的距离与该接收点在车辆段中的相对位置有关,所以需要考虑个体中不同车辆段或接收点访问顺序对搜索空间产生的影响。因此对于种群中的个体,分别计算个体中每辆车的行驶距离在总行驶距离中的占比,从而得到每个车辆段权重:

w=di/Di

(6)

式中:Di表示所有车辆总的行驶距离。

根据式(6)可得到每个节点在该车辆段中的权重,删除权重最大的节点,计算当前车辆段中车辆的可用载重。依次对其余节点进行遍历,随机选择其中一个节点插入一个新节点后总距离最小,且满足所选节点的需求量不超过可用载重,则交:2个节点的位置,从而产生新个体。

4 实验结果与分析

4.1 实验准备

为验证算法及平台生成初始路径的有效性,利用不同算法对采集到的汽车材料应急运输数据集进行对比实验。其中设置数据集的节点数分别为10、20、50和100,节点位置和节点需求量为随机选取,种群大小为30、LTMU大小为6,分组数为2,多样性阈值为0.4。

4.2 算法横向对比

为验证分组移动的鲸鱼群(WSA-PM)算法求解的性能,与目前常使用的蚁群系统(ACS)、自适应混沌遗传算法(ACGA)对相同问题进行求解,计算结果如表1所示。

表1 不同节点数下2组数据在3种算法的计算结果

由表1可知,随着种群的迭代更新,节点数的增加,传统算法的偏差逐渐增大,最优解在改进的算法下计算出的距离最小,对运输成本和运输时间上更有优势。同时,在解算相同问题时,分组进行的鲸鱼群算法的计算结果远远高于ACS和ACGA算法,对节点数多的时候更加有优势。同时,在解算相同问题时,分组进行的鲸鱼群算法的计算结果远远高于ACS和ACGA算法,对节点数多的时候更加有优势。

5 结语

综上,基于汽车材料运输中路况这一动态因素,结合鲸鱼群算法的原理进行改进,用于制定初始车辆的行驶路径,并能经过路况这一因素进行及时的调整调度方案,从个体移动和种群搜索空间两个方面对算法进行了优化,实现了在动态路况变化下汽车危险化学材料运输的实时更新调度,且平均距离得到了较大的改善,对运输成本的控制有着实际作用,保证了调度方案的可行性和高效性。