基于混合算法的电力物料车辆排队服务优化

王伟丽，张明伟

（天津仁爱学院，天津 301636）

0 引言

随着经济加速发展，企业经营规模迅速扩大，供应链中各节点的物流运输负担加重，在企业仓储园区中，经常出现运输车辆排队等待服务的现象，由于出入库订单扰动大，无法预估仓库装卸时间，排队等待服务时间不确定，较长的车辆排队造成了巨大的人员与成本浪费。这种现象在电力物料类的运输存储过程中尤为明显，因为电力物料种类繁多，体积重量大小不一，各类型的物料搬运装卸工具差异较大，不同物料还需要适配车辆类型，所以车辆的排队等待时间具有很大的不确定性。

借鉴经典排队理论，将仓库看作服务台，将车辆看作顾客，仓储装卸排队服务属于M/M/C排队模型。此时很多管理人员需要利用排队理论找到一种最佳资源配置方案[1]，因此有许多对排队经典理论M/M/C模型的深入研究和场景应用，如医疗系统排队模型[2-3]、停车场排队模型[4]、道路交通排队模型[5]等。对于模型的求解算法，较多学者建立状态转移图和方程进行数值分析[6-7]，或者使用仿真软件建立模型[8-9]。目前针对仓储装卸的排队模型鲜有研究，但以上研究为本文关于电力物料车辆排队服务优化研究提供了理论参考和借鉴。

1 问题描述与假设条件

1.1 问题描述

企业一般将多个自有仓库规划在一个园区，仓库存储各种种类、型号、体积、重量等不一的物料，部分类型的产品在多个仓库均有库存，各种类型的物料装载卸载方式不同，装卸搬运的时间也有较大差异。将车辆分为入库和出库两部分，对于入库车辆，根据订单和定位系统，可以对到达时间做出较为准确的预测，并且可以根据订单获取车辆运输物料的相关信息。对于出库车辆，需要根据需求订单由第三方物流派遣车辆，车辆类型须满足物料装载要求，车辆的到达时间需要根据仓库园区内车辆排队等待情况进行优化。由于车辆装载多种类型物料，物料存放仓库不同，因此同一车辆需要在多个仓库进行转换，来装卸与仓库存储匹配的物料。

当货运需求较大时，随着订单和车辆单位时间内集中到达，车辆排队等待装卸服务的现象较为突出，随着订单的不断到达，对既定排队服务调度方案也将产生较大扰动。在此情境下，如何减少车辆的排队等待时间，减少排队造成的成本浪费，提高作业效率，从而提高服务满意度，是本文研究的目标问题。

本文将一定时间内动态到达园区的入库车辆和出库订单统一进行优化，以确定出库车辆的到达时间和次序，减少车辆排队服务时间和成本。设定调度点对新加入订单进行重新调度，以减少新到订单对调度优化结果的扰动。模型的优化目标为所有车辆平均空闲时间最小和所有车辆最大空闲时间最小。

1.2 符号说明

k:货运车辆，k ∈K；

p:不同种类或不同型号的产品，p ∈P；

m:不同的仓库，m ∈M；

r：重调度的次数，r ∈{1,2,...,R}；

1.3 条件假设

（1）根据订单和定位系统，入库车辆到达时刻能够确定；

（2）仓库的装载或卸载作业开始后不会中断；

（3）出库作业由第三方物流安排各种类型适配车辆且数量足够；

（4）仓库中有足够物料满足出库订单需求；

（5）仓库在同一时间只能容纳一辆货车进行装载或者卸载作业；

（6）入库车辆只执行卸载任务，出库车辆只执行装载任务。

2 模型构建

2.1 装载卸载时间

这里，车辆k的装载时间Lk为：

车辆k的卸载时间Uk为：

2.2 模型建立

模型的目标函数为：

优化目标式（3）表示车辆平均空闲时间最小；优化目标式（4）表示车辆最大空闲时间最小。

目标函数约束条件S.T.：

式（5）和式（6）表示h产品和l产品不能同时在仓库m装载和卸载；式（7）表示车辆同一时间只能在一个仓库装载或者卸载一种物料；式（8）表示车辆k在一次运输过程只执行出库或者入库其中一种任务；式（9）表示车辆在装载或卸载过程中不中断任务；式（10）表示卸载决策变量；式（11）表示装载决策变量；式（12）表示重调度决策变量。

3 算法设计

由于车辆需要在仓库间转移，此类排队服务问题为NP难度问题[10]，使用数学解析的方法求得最优解。智能优化算法对此类问题的求解具有良好的效果[11]。遗传算法（Genetic Algorithm，GA）具有较强的优良基因传递能力和良好的收敛性，粒子群算法（Particle Swarm optimization，PSO）具有较好的搜索方向性。本文将遗传算法与粒子群算法结合，利用GA的染色体遗传特性保留优良解，利用粒子群算法的方向性，使得染色体能够快速获取局部最优和全局最优基因。并利用模拟退火算法中的Metropolis准则来防止陷入局部最优和过早停滞现象。混合算法流程如图1所示。

图1 GA-PSO混合算法流程图

借助GA算法的优良基因遗传特性，利用PSO算法的搜索方向性，将PSO中本代最优Pbest和全局最优Gbest分别与其他粒子进行交叉操作，以保留良好的基因。为避免陷于局部最优，本文提出采用模拟退火算法中的Metropolis抽样准则来判断是否接受Pbest或者Gbest，以避免算法的早熟，接受概率ψ按照式（13）计算。

其中，Γ为接受概率系数，与迭代次数成反比，与ψ成正比，即接受概率ψ随着迭代次数增加逐渐减小。

3.1 算法编码

为方便表达模型的实际信息含义，减少不可行解的产生，GA-PSO混合算法采用分层实数编码。共分为4层代表不同信息变量，如图2所示。

图2 粒子编码示意图

图2中，第一层为车辆信息，不同的数字对应不同的运输车辆，数字出现的顺序表示运输车辆装卸不同类型物料的次序，如[1,2,1,3,2,1,3]中第一个“1”表示车辆1装卸第一种物料，第一个“2”表示车辆2装卸第一种物料，第二个“1”则表示车辆1装卸第二种物料，以此类推；第二层表示运输车辆对应的装卸物料信息；第三层表示运输车辆装卸物料选择的仓库。

3.2 个体更新

3.2.1 交叉算子：由于在智能优化算法中，实数编码在更新或者交叉等算子操作中经常会产生大量不可行解，本文提出动态交叉算子的方法来避免在粒子交叉过程中产生不可行解，如图3所示。

图3 交叉算子操作示意图

图3 为交叉算子操作过程，首先在Pbesti(t)中随机产生2个交叉点x1和x2，然后在Si(t)中自粒子起始位置，依次搜索与交叉点x1和x2之间含有相同数字（次序可以不同）的连续基因片段y1和y2，然后将x1、x2之间的基因片段与y1、y2之间的基因片段进行交换，完成交叉过程，产生新的粒子Pbest’i(t)和S’i(t)。如果交叉操作过程中，在Si(t)没有找到与x1、x2之间基因片段对应的y1、y2，则减小x1、x2之间的一位数字，继续搜索，直到x1、x2之间基因片段减小到一位数字，则重新产生x1、x2交叉点，继续重复上述过程，直到能够执行交叉操作为止。粒子的第二层和第三层编码跟随第一层交叉操作同时移动。

3.2.2 变异算子。GA-PSO中的变异算子操作采用多对变异、多层变异的方式，即在粒子中随机生成两点，两点的车辆信息、物料信息、仓库信息之间互相交换。在交换完毕后，针对第三层仓库信息，重新随机生成一个装卸物料仓库，以保证变异操作能够充满解空间。

3.3 适应度计算

GA-PSO混合算法中适应度值取越大越优，双优化目标为所有车辆平均空闲时间Tw最小和车辆最大空闲时间Tv最小。两个优化目标的权重系数根据企业偏好确定。适应度函数为：

式（14）中的λ1和λ2为双目标的权重系数，即为企业对车辆平均空闲时间和车辆最大空闲时间的偏好系数。

4 仿真算例

4.1 算例数据

以国家电网天津市电力物资公司智慧物流园区的实际物料出入库记录作为算例数据。物流园区经常运输配送的电力物料主要有19种，各种物料存放在园区的7个仓库中。园区5号库、6号库为智能立体仓库，1号库和7号库为露天堆场，其他仓库为平库。受仓库大门和通道限制，立体库和平库同时只能允许一辆运输车辆进行装卸作业。堆场主要存放电力电缆等大型物料，受装卸搬运工具限制，同时只能为一辆运输车辆进行装卸作业服务。物流园区中的仓库类型、序号及存储的常见电力物料见表1。

表1 仓库及物料信息表

表1中，同一个物料装载和卸载时间可能不同。有的电力物料体积、重量较大，一般没有外包装，如物料1、8、9等，一般在露天仓库存放，装卸需要借助吊车或者门式起重机，装载后需要固定和检查，需要耗费较长时间。有些物料包装规格为多个物料装纸箱或者木箱，如2、3、12等，企业一般使用叉车进行装卸，装载、卸载时间近似相等。

实际生成过程中，同一辆车辆有时装载或者卸载多个种类的电力物料，由于不同物料存储仓库不同，所以车辆需要在各个仓库之间转移。

表2为装卸运输车辆在智慧物流园区的7个仓库之间转移的时间，主要包括行驶时间、调整到装卸位置时间、手续交接时间等。任两个仓库之间往返时间相等。

表2 转移仓库时间(min)

由于区域电力物料公司物流园区经常有采购收货、退货，成本中心发货、项目发货、工单发货，工厂间和工厂内转移，甚至拍卖销售等，各种车辆每日进出仓库装卸货物频繁，若到达时间集中则会造成大量等待和成本浪费。以天津电力物料公司某一天实际物料出入库记录为数值算例，见表3。表3中，入库车辆到达时间可以由发车时间、在途时间和卫星定位等做出较为准确的预估，并且入库车辆装载的电力物料信息可以由订单获取。出库物料由第三方物流公司派遣车辆，现公司已经拥有三维装箱优化系统，可以根据出库订单中物料的种类、数量、体积和质量等约束，优化派遣车辆的类型与数量。因此，物流公司根据与智慧物流园区的距离和道路拥堵情况，可以安排装箱优化后的出库车辆准时到达。为减少车辆空闲等待时间，本文根据以上算例的信息和数值，对车辆排队等待服务进行优化，并给出出库车辆最优到达时间，使出库和入库的所有车辆的平均空闲时间与最大空闲时间最小。

表3 运输车辆到达及物料出库信息

4.2 仿真结果

针对4.1节算例数据，使用GA-PSO混合算法进行仿真优化。以Matlab2022a为运算工具，多目标模型的帕累托解与目标的权重系数相关，模型中两个优化目标为一定时间内所有车辆平均空闲时间最小和车辆最大空闲时间最小，其值与企业对两者的重视程度相关，由于两个目标性质相近，故两者的权重系数采用λ1=λ2=1。

采用均匀设计试验[12]的方法来确定GA-PSO 中参数取值，初始种群规模设置为1 000，交叉率为0.35，变异率为0.08，变异对数为3。算法的终止条件为：当进行200次迭代运算后，若算法的适应度函数值不再变化，则算法终止。

将表1、表2中的电力物料公司物料、仓储和仓库信息，以及表3中公司某一日的物料出入库数据，输入电力物料装卸排队服务优化模型，并对模型仿真30次，对优化结果取平均值，即“模型优化”的值，并且与“当日实际”发生的值进行对比分析，得到优化结果见表4。

表4 模型优化结果

由表4可知，模型优化后比当时实际的车辆平均空闲时间、最大空闲时间和总空闲时间都有大幅度减少。

取其中的一个优化结果进行分析，其优化调度甘特图如图4所示。

图4 车辆排队服务优化调度甘特图

最优粒子的三层信息编码为：

根据公司历史资料数据，当日实际车辆出入库排队服务调度甘特图如图5所示。

图5 当日实际车辆排队服务调度甘特图

表5给出了图4中优化解的具体数值，并与当日车辆的实际到达排队次序和空闲时间进行对比。

表5 当日实际数据与模型优化结果

由表5可知，优化后的平均空闲时间和最大空闲时间相比实际数据分别减少了55.2%和41.1%，可以看出模型对电力物资出入库车辆的排队服务时间优化效果明显。

5 结语

针对电力物料类产品的出库入库排队服务调度有其固有属性和特征，如产品种类繁多、重量体积不一，装卸时间差异大，且装卸方式、工具各不相同，极易造成集中排队，等待服务，浪费大量时间和成本。本文建立了电力物料出库入库排队服务模型，考虑了车辆仓库转换时间对排队服务时间的影响。提出了将遗传算法与粒子群算法结合的GA-PSO混合算法，并引入了Metropolis抽样准则以提高算法跳出局部最优的能力。最后对国家电网天津市电力物资公司智慧物流园区实际数据算例进行仿真优化分析，结果表明了算法的高效性和模型的可行性，相关研究模型已在企业物流智慧园区供应链多环节协同关键技术研究项目中进行分析与验证，并应用于企业实际仓储服务信息系统，极大地减小了企业运输车辆排队等待服务现象，减少了时间与成本浪费，具有较强实际意义与应用价值。

后续研究拟根据企业实际需求，通过企业运营大数据，对电力物料出入库历史数据进行统计分析预测，科学合理分派物料存储仓库及库位，并减小调度点间隔时间，建立智能动态电力物料仓储运输排队服务模型。