基于深度卷积神经网络的电力物资运输车辆调度优化算法研究

宫寅林,王民涛

(1.国网内蒙古东部电力有限公司物资分公司,内蒙古 呼和浩特 010090) (2.国网内蒙古东部电力有限公司,内蒙古 呼和浩特 010090)

深度卷积神经网络是基于人工神经网络逐渐演变而来的[1],其通过神经元处理输入信号来判断是否进行下一步响应[2-3]。以此为基础构建神经网络数学模型,通过不断卷积运算保证深度卷积神经网络的处理结果更加完善,且拟合能力更强。

电力物资的配送根据不同客户的需求特点,通过高效有序方式实现[4]。随着社会的高速发展,电网企业项目类型不断增多,各电力公司所需的物资也逐渐增多,而当前许多物资配送调度方法无法满足物资的整合与配送要求,在配送过程中通常难以选择经济合理的配送方式与配送路线[5],导致电力企业在物资配送方面的开销逐渐加大,因此研究一种合理有效的配送车辆调度方法就显得极为重要。许多学者对此进行了研究,如卢锦川[6]进行了基于扰动收缩粒子群算法的物联网配送车辆调度研究,但在进行车辆调度时仅考虑了运输路径,未能有效节约配送时间;贺体龙等[7]采用改进飞蛾扑火算法获得车辆调度方案,但在进行配送时所需油耗更大,并不能合理节约开销。

本文提出基于深度卷积神经网络的电力物资运输车辆调度优化算法,通过Hopfield神经网络处理电力物资运输车辆调度问题,并利用禁忌搜索算法对调度模型进行优化。

1 电力物资运输车辆调度优化算法

1.1 Hopfield神经网络基本原理

选用Hopfield神经网络实现深度卷积,该网络是一种反馈型网络[8-9]。神经网络能量函数为:

(1)

式中:E为能量函数,Tij为神经元i与j之间的连接权值,Ii为神经元i的输入阈值,Vi、Vj分别为神经元i与j的输出值。

在一定条件下,只要能量函数沿着网络的解递减,能量函数的导数为零时网络达到平衡状态。通过Hopfield神经网络,可有效实现神经网络的深度卷积。

1.2 电力物资运输车辆调度

为研究电力物资运输车辆调度优化问题,假设某个电力物资配送点在T时刻存在多个客户需求,此时存在已知的送货时间、地点、客户需求量以及道路情况,且运输车容量为已知。基于这种情况,为使运输车辆利用率得到提高,需要合理安排行驶路线,以使车辆运行距离最短。为此,构建电力物资运输车辆调度问题数学模型,优化电力运输车辆调度过程。

1.2.1电力物资运输车辆调度问题数学模型

(2)

式中:1表示车辆从点i行驶至点j,0表示车辆未从点i行驶至点j。由此,可得到运输车调度数学模型如下:

(3)

(4)

(5)

(6)

(7)

(8)

(9)

1)当i为电力物资配送点时,运输的固定开销与运行开销如式(10)所示:

cij=c0+c1dij,j=1,…,n

(10)

2)当i同时为需求点时,仅包含运行开销,如式(11)所示:

cij=c1dij,i≠0,j=1,…,n

(11)

式中:c1为运输距离的开销系数,c0为已有运输车固定开销,dij为添加新车辆的边际开销。通常情况下,若c1=0,c0>0,则表示达到目标配送点所使用的车辆数最少。

在构建的运输车辆调度优化问题模型中,式(3)为目标函数,式(4)～式(9)均为约束条件。其中,式(4)为每辆车的载货量限制,式(5)表示每个需求点仅能进行单次访问,式(6)～式(8)为每辆车从配送点出发到需求点后再次返回配送点的限制,式(9)为路径选择约束。通过参数差异化分析,可将调度优化问题调整为组合优化问题。假设某辆运输车已经被使用,则该问题可转变为旅行商问题(TSP),以此构建调度优化模型。

1.2.2基于改进Hopfield神经网络的车辆调度问题数学模型求解

利用改进Hopfield神经网络对VRPRW进行求解。Hopfield神经网络属于连续的单层反馈网络,变量具有连续性[11-13],方程为微分形式。

运用改进Hopfield神经网络求解车辆调度问题时,分为以下4个步骤。

1)构造邻接矩阵。

用网络节点表示起始点、交汇点以及停车点,并用抽象的边连接每个点形成有向路径,绘制出一个有向图G,G=(N,L,D),L为边数,N为节点数,D为N×N矩阵。由1.2.1节调度问题数学模型可知,需进行优化的目标为边(i,j)对应的长度、开销与时间,因此可构建距离、开销与时间的邻接矩阵。若两个节点之间存在路径,那么对应的矩阵元素为路径长度、开销与运输时长;若两个节点之间不存在路径,那么对应矩阵元素值为∞。

用行与列表示车辆路径,列描述运输车配送顺序,行描述配送点与需求点。将需求点排序,从“0”开始编号,其中“0”表示起始位置。

2)约束的处理。

将多个附加约束条件描述为神经网络的能量项,在每个能量方程中引入惩罚项,通过这种形式,使约束条件的能量随着神经网络的不断收敛而变得更加稳定。

设需求点所需物资质量为qx,设配送点序号为x,y。

①假设每行每列仅存在一个1,此时车辆集合为Vyi,若运输车仅路过一次需求点,则车辆集合为Vxi,若必须配送一次,则车辆集合为Vxj,返回配送点的约束条件如式(12)、式(13)所示:

(12)

(13)

②若全部列的值之和为J,即配送的路径数量为J,车辆集合为V0t,则存在约束如式(14)所示:

(14)

③若整个矩阵内每个单元之和为(n+J),则存在约束如式(15)所示:

(15)

④若配送车的配送起始点必须为物资配送点,则车辆集合为V0t,存在约束如式(16)所示:

V01=1

(16)

⑤配送车存在负载量限制,且每辆车存在容量限制Q,若达到限制标准则返回起始位置。

⑥构建目标函数,如式(19)所示:

(17)

式中:f为目标函数,Vxi(Vy,i+1+Vy,i-1)为车辆集合反演结果,dxy为需求点访问阈值。

3)神经网络计算。

假设邻接矩阵中各元素均与一个神经元对应,并设定Vxi为位置(x,i)的神经元输出函数,对应不同车辆集合反演结果。在计算之前,需确定网络的能量函数,通过能量函数的计算,可获取神经元的传递函数与状态转移方程,之后通过网络的持续迭代,实现网络收敛。网络的能量函数E′为:

(18)

式中:A、B、C、D、E分别为状态转移阶段对应的各神经元收敛系数,gx为当前值,Z为收敛域。

②在初始输出状态中引入一个小的随机偏置,使每个初始单元的值分布不均匀。

④分析神经元生成路径,获取再次循环后的输入状态值,并进行循环计算。

⑤将状态值设置为不同收敛期的动态值。

⑥若E′在循环10次内变化低于10-4且满足全部循环计算条件,或循环达到4 000次后,终止循环。

4)形成调度方案。

当神经网络收敛后,可汇集成一个换位阵,该阵由0和1构成,在阵中车辆经过的节点由1表示,将节点间的距离、运输时间与开销相加,即可得到最短距离、时间以及最低的开销,结合附加约束条件,可获得运输车辆调度方案。

1.3 禁忌搜索算法优化车辆调度

利用禁忌搜索算法对上述求解过程进行优化,使配送车调度过程更加完善。通过该算法,可以使神经网络在深度卷积过程中避免出现局部最优解现象[14-15],具体算法实现步骤如下:

1)对解进行评价。利用禁忌搜索算法优化车辆调度问题时,需对求解的内容进行评价,保证经过迭代后可以获取最优解。针对某个约束条件下的解,假设其相应的配送路径方案的路径条数与初始配送路径之差为M,其目标函数的值为W,并设每条不可运输路径的惩罚权重为Pw,由此可计算该解的评价值β′:

β′=W+M×Pw

(19)

2)对邻域进行操作。选取两交换法处理邻域,即随机挑选解中的两个元素,将两个元素的值进行交换,即完成邻域处理。

3)获取禁忌对象。在每次进行迭代时获得最优解,将其作为禁忌对象放置在禁忌表内。

4)获取禁忌长度。每个被禁对象不能选择相同数量的迭代步骤,根据求解规模选择禁忌长度。

5)获取候选集合。从当前解邻域内随机挑选若干个邻域,并将这些邻域设为候选集合。

6)确定终止条件。将迭代的指定步数作为该算法的终止条件。

通过上述步骤,可以实现电力物资运输车辆调度的优化,提升算法的迭代速度,使计算效率提高。

2 实验分析

对某企业电力物资配送过程中的电力物资运输车辆调度进行优化,并选取文献[6]基于扰动收缩粒子群算法的物联网配送车辆调度算法、文献[7]基于改进飞蛾扑火算法求解多需求点的应急物资调度算法进行对比。

分析不同算法从电力物资配送点到达物资需求点的规划路线,结果如图1所示。

图1 不同算法的规划路线

由图1可知,不同算法到达3个需求点所规划的路径不同,文献[7]算法规划后的路径距离最长,该路径呈曲线,车辆依次到达各需求点后依然按照曲线路径返回物资配送点;文献[6]算法规划后的路径明显短于文献[7]算法规划的路径,但要明显长于本文算法规划的路径。本文算法规划的路径为直线,将物资配送至各个需求点后仍沿直线路线返回至物资配送点。由此可知,本文算法可有效优化物资配送路径。

选取10个电力物资需求点进行配送服务,从需求点1起步运输直至需求点10,分析不同算法路径规划后达到各个需求点的路线长度,结果如图2所示。

图2 不同算法规划路线长度分析

由图2可知,随着需求点逐渐增多,3种算法的配送路线长度也逐渐增加,其中文献[7]算法在进行配送时路线总长度最长,文献[6]算法的配送总长度略低于文献[7]算法,但两种算法到达需求点10时的配送总长度均已超过180 km。本文算法的配送总长度仅为165 km,低于另外两种算法,由此可知,利用本文算法进行车辆调度,可有效缩短总的配送路径长度。

分析向每个需求点运送不同物资时所需的运输时间,结果如图3所示。

图3 不同物资运输所需时间

由图3可知,随着配送需求点的增加,每种物资配送的所需时间也有所增加,其中在配送电力绝缘物资时所需时间最长,这是由于绝缘物资在运输时需要专用车辆,而应急物资配送所需时间最短,报废物资配送所需时间略高于应急物资,说明应用本文算法进行配送车辆调度可加快应急电力物资的配送。同时,配送3种物资的所需时间均未超过7.5 h,处于合理的时间范围内,因此利用本文算法调度电力物资运输车辆可有效节约配送时间。

向10个需求点分别配送1 000箱物资,并要求在10 h内完成所有配送,且3种算法在规划路径后均使用两辆车进行配送,分析不同算法在配送时的消耗情况,即不同算法调度后所需油耗,分析结果见表1。

表1 不同算法车辆调度后的消耗情况 单位:L/100 km

由表1可知,文献[6]算法规划的路径油耗最高,文献[7]算法规划的路径在到达需求点1时的油耗最高,本文算法规划路径的油耗始终低于其他两种算法,说明本文算法规划的车辆配送路径可以节约开销,降低运输成本。

3 结束语

本文完成了电力物资运输车辆调度优化算法的研究。基于深度卷积神经网络,构建了电力物资运输车辆调度问题数学模型,并通过禁忌搜索算法实现调度过程优化。在未来的研究中,可对现有算法继续优化,以实现多种类型物资运输车辆的调度,并通过路径规划避免车辆运输时出现意外情况。