汤雪松，邓 勇，刘 鑫，龚仁兰，廖 勇

（1.国网重庆市电力公司铜梁供电分公司，重庆 402560；2.重庆大学 微电子与通信工程学院，重庆 400044）

随着物联网技术的不断发展，我国电网规模不断扩大，电力系统的物资需求量正在不断增加。为保障电力系统安稳运行，面对紧急事故能够快速解决物资供应任务，最为理想状态是物资供应商不经中转直接向物资需求点进行物资运输，但在实际应用中，电力物资需先送至物资预置点，随后运输至物资需求点，往往会出现前线电力物资紧缺，物资预置点中物资储存量却不足，无法满足物资的及时供应。因此，物资预置与调度问题亟待解决［1－3］。

Chai［4］设计了一个基于多救点、多物资的应急调度算法和最短路径求解算法，能够在满足时间与出救点数量的同时，解决灾害地多种物资调度问题。但是在物资调度过程中，并没有结合时间效益和经济效益。Han等［5］基于优化思想，以运输时间和需要物资数量安全到达目的地为对象，建立了调度模型解决紧急任务，并研究了运输时间和安全性，但是并没有考虑物资预置问题。Dawei等［6］建立了基于物资运输最早时间、成本最低的双层优化数学模型，用于解决紧急物资调度连续消耗问题，但是在实践中存在很多不连续消耗问题。陈勤等［7］考虑了复杂道路环境中车速和安全性因素，将非支配排序遗传算法（non-dominated sorting genetic algorithm-Ⅱ，NSGA-Ⅱ）应用于解决军事应急物流路径优化问题，结合了时效性、安全性、经济性，却没有考虑应急物资存储量不足的情况，造成军事应急物资无法送达问题。

灰色模型（grey model，GM）能够对原始数据做出高精度的预测，已在电力物资需求领域得到较好地应用。史德明等［8］指出，GM近年来已被引入电力系统的预测中，获得效果较好，并且具有建模信息少、运算方便、建模精度高的优势。刘宇等［9］提出了一种基于改进灰色理论的电力系统中长期负荷预测方法，该方法将经典灰色预测模型和三点平滑法相结合，首先对历史数据进行预处理，然后再构建基于等维信息矩阵的灰色预测模型，最后利用残差处理方法对预测结果进行修正。仿真结果表明：改进灰色预测方法在预测精度和适用性方面都具有显著优势。

为了解决电力物资供应不足、不及时的问题，设计了一个三级网络模型，分层次设置大量的物资预置点（转运点），进行电力物资预置，分级快速供应电力物资。首先根据区域中的历史电力物资需求总量数据利用GM预测出未来的物资需求总量，供应商提前将该区域内所需电力物资运输至物资预置点（转运点）预置充足电力物资；在出现供应不足时，可以从其他区域或供应商处进行物资调度。在模型方面，结合实际情况，在考虑时间、随机风险的基础上，基于泊松过程建立了多目标物资调度模型。基于此模型，提出了一种基于随机游走算法改进的遗传物资调度算法（random walk-genetic algorithm，RW-GA），首先通过RW算法进行全局随机搜索，确定最优解候选集，再利用GA进行局部寻优，快速规划得到全局最优的电力物资配送路线。最后，通过仿真验证了本文所提算法的可行性和有效性。

1 物资预置及调度模型

1.1 问题描述与说明

电力物资需求点分布广泛，物资供应商通过对电力物资预置点（转运点）进行物资储备，预置点可进行区域性的物资输送，保证负责区域内所有物资需求点的物资及时送达；为了避免出现区域物资储备不足的问题，可从其他区域进行物资调度，供应商也可对电力物资直接输送。本文求解电力物资预置及配送问题，物资供应商可以按照预测的物资需求量提前向物资预置点进行物资配送并贮存，当该区域多处发生电力故障时，急需大量电力物资对这些地区进行电力抢修，这时由预置点向需求点按照优化路径进行输送，同时也可从其他区域或供应商处进行物资调度。

1.2 三级网络GM物资预置模型

为保证电力物资的及时供应，通过建立三级网络模型进行物资预置、物资需求分解，保障物资的快速、及时供应，如图1所示，假设每个物资供应商SI对应M个物资预置点（转运点），物资预置点用Hm（m＝1，2，…，M）表示，每个物资预置点对该区域的物资需求点Dmn进行物资输送，其中m表示为物资预置点的标号，n表示物资需求点的序号，在物资供应商、物质预置点以及物资需求点之间采用运输工具ki（i＝1，…，K）进行资源运输。

基于建立的三级网络模型，物资供应商可向物资预置点提前进行电力物资的配送及贮存，为了避免资源浪费或资源贮存不足，采用GM对每个区域所需要的电力物资总量进行预测。

已知x（0）＝x（0）（i），i＝1，2，…，n为参考数据列，1次累加生成序列：

式中：x（1）（k），k＝1，2，…，n中各数据表示对应前几项数据的累加，x（1）（k）的均值生成序列：

建立灰微分方程：

1.3 多目标物资调度模型

运输时间分为直达路线时间分量与转运路线时间分量［10］。当物资需要转运时，每一段转运路程采用不同的运输工具，但为了方便起见，要求每一段路程只能使用一种运输工具。电力物资通过预置点转运带来不同的转运时间，转运时间与物资运输量有关。总运输时间如式（7）所示：

式中：T表示电力物资总的运输时间；xid表示供应商i向需求点d直达的物资量；disid表示供应商i和需求点d的直达距离；disih表示供应商i和转运点h的距离；dishd表示转运点h和需求点d的距离；vk表示交通工具k的速度；tzz表示转运速率；λid表示供应商i到需求点d的各直达路段泊松强度；λih表示供应商i到转运点h的各路段泊松强度；λhd表示转运点h到需求点d的路线上的泊松强度；“？”表示选择下标，即对“？”后的离散变量进行选择；λi？d为布尔变量，供应商i选择任意需求点d且不经过任意转运点情况下为1，否则为0；λi？k为布尔变量，在λi？d＝1前提下，选择运输工具k为1，否则为0；λi？h为布尔变量，如果供应商i选择转运点h为1，否则为0；λih？k为布尔变量，在λi？h＝1前提下，如果选择运输工具k为1，否则为0；λhd？k为布尔变量，在λi？h＝1前提下，从转运点h到需求点d，选择运输工具k为1，否则为0；I表示供应商集合，∀i∈I；H表示物资转运点（物资预置点），集合∀h∈H；D表示物资需求点集合，∀d∈D；K表示运输工具集合，∀k∈K。

E0是运输工具在行驶过程中发生突发状况的概率。对电力物资运输过程中的随机风险进行考量，即针对该过程的某个特征函数进行考察。本文选取泊松过程的均值函数为考量对象，即在一段路线中，发生突发状况的期望值越低，则安全到达的概率越大，随机风险则会越小，得到电力物资前随机风险如式（8）所示：

1.4 目标函数

目标函数是由时间消耗量与随机风险2个要素加权得到，因为2个指标具有不同的量纲，故本文对其进行标准化。为样本的均值，σ为样本的标准差。本文对多目标函数进行处理，通过加权求和得到综合适应度Z*。得到的目标函数如式（9）所示：

在满足上述约束条件的同时，要求每个物资需求点有且只有一次被配送物资，增加的约束条件为

2 RW-GA物资调度算法

结合1.3节提出的多目标调度模型，进一步提出了一种基于随机游走算法改进的遗传物资调度算法（RW-GA）。RW算法针对全局进行大范围的随机搜索［11］，确定最优解候选集，结合GA寻优的特点［12－14］，解决GA寻优抖振问题，能够保证在电力故障发生的紧急情况下，快速规划出全局最优的电力物资配送路线，将电力物资及时送达所有电力故障点。该算法流程如图2所示。

图2 RW-GA算法流程框图

1）生成初始序列

假设有若干运输车辆，N个物资需求点，物资运送车辆从物资预置点Hi出发，按照｛Dip，…，Diq｝的顺序进行物资配送，将物资配送给所有物资需求点后回到物资预置点，初始化序列表示为｛Hi，Dip，…，Diq，Hi｝，其中，Hi表示物资预置点，Dij，j＝1，…，N表示物资需求单位。

2）随机游走确定解候选集

随机游走算法是一种全局搜索算法。通过设置步长和阈值，在迭代过程中计算函数值，得到更优初始值。若在迭代次数内仍找不到更优值，则认为最优解在以当前最优解为中心，步长为半径的球内。

3）适应度函数

选取式（9）中构建的多目标函数作为适应度函数。适应度高的染色体在进化过程中往往被保留下来，更有可能接近最优解。

4）交叉与变异

交叉与变异促使生成新的个体，保证群体多样性。父代的基本特征通过交叉操作使子代继承保留，从而使种群的优良特性延续下去。变异操作是指群体中的个体基因根据设定的变异率发生突变，从而保证全局优化。

RW-GA算法的具体步骤如下：

?

3 仿真实验与分析

为了验证模型的准确性和算法的实用性，根据所建立的三级网络模型，由历史需求量的数据利用灰色模型预测出区域物资预置点（转运点）未来所需的电力物资总量，然后模拟在该区域中某些地区发生电力故障，需要尽快将电力物资送达所有物资需求点，通过RW-GA算法确定物资输送的最优路径，以期保证电力物资在短时间内送达物资需求点，快速修复电力故障。假设时间、随机风险权重分别为α＝0.8、β＝0.2，转运速率tzz＝0.3 h／t。其他相关参数见表1和表2。

表1 物资预置点（转运点）H1物资储存量

表2 物资需求点的模拟位置坐标 km

3.1 物资预置与输送路线

通过所建立的GM模型，利用表1数据运用Matlab求出预测结果曲线，如图3所示，从而通过该曲线图预测出未来几个月物资预置点所需的物资量，电力物资供应商能够提前将电力物资运输到该物资预置点进行储存。

图3 物资预测曲线

根据多目标物资调度模型，结合RW-GA算法，利用Matlab编程求解得出物资输送路径，如图4所示。物资预置点即转运点（图中圆圈处）与物资供应商位置（图中矩形框处）的坐标分别为（30，20）、（20，25），其中蓝线为经过转运点的输送路线，红线为由供应商直达运输的路线，分别按箭头指示方向出发，经过每个物资需求点，进行物资输送，最后回到各自出发点，从而完成电力物资调度任务。

图4 物资输送路径优化曲线

3.2 结果分析

电力物资预置的精确度检测误差指标为残差和级比偏差，对比了指数平滑法与GM方法的预测精度与效果。指数平滑法［15］是数据预测模型中的重要方法之一，在经济方面应用广泛。表3给出了2种方法的计算误差结果，经过分析验证，相比指数平滑法，GM方法的预测误差较低、精度较高，能够对第一层网络中的电力物资预置做出较好地预测与预报。

表3 模型预测精度

图5是30次随机产生初始群体适应度累积分布曲线，以此观察所提RW-GA算法的收敛情况。从图中可以看出：加入随机游走算法改进交叉的遗传算法主要密集分布在0附近。在20次迭代之前，种群进化速度较快，RW-GA算法进入快速收敛阶段；在40次迭代之后，开始出现逐渐收敛的状态；迭代次数到80次后，RW-GA算法基本进入了收敛稳定期。在20次迭代之前，由于RW算法的作用，算法能够快速进入收敛期。从图中也可以看出：通过随机游走算法改进的遗传算法有着较好的稳定性和收敛性，可以确保算法的收敛精度与速度。

图5 运行30次收敛分布曲线

为了验证算法的有效性，在不同运行时间下比较了RW-GA算法与GA算法适应度的均值和方差，结果如表4所示。

表4 RW-GA与GA算法性能对比

从表4中可以看出：在不同运行次数下，RWGA算法的均值和方差的结果均优于GA算法。从方差可以看出：RW-GA算法的稳定性比GA算法表现更好，RW-GA算法程序运行时长相比GA算法更短。针对上述结果，一方面说明了本文所提RW-GA算法的稳定性；另一方面说明运用随机游动改进的遗传算法收敛性好，能够在短时间内得到稳定、满意的电力物资配送路线。

4 结论

提出了一种基于RW-GA的电力物资配送多目标路径优化方案。建立三级网络GM物资预置模型，通过求解该模型得到物资转运点的最优预置方案；建立以时间短、风险小为目标的多目标资源调度模型；提出了一种RW-GA电力物资调度算法，从而快速规划得到全局最优的电力物资配送路线。通过搭建仿真实验，验证了提出的三级网络GM在电力物资预置中有更高的精度，更适合于电力物资的预置；所提的RW-GA算法收敛速度快，能够在多目标约束条件下规划电力物资输送路径，从而有效保障及时修复电力故障与提升电网的整体安全性。