多充电桩下考虑运载机械释放时间的充电调度

裴 植，万明重，杜 蕊，李英德，陈 勇

(浙江工业大学 机械工程学院工业工程研究所，浙江 杭州 310032)

0 引言

近年来，自动引导小车(Automated Guided Vehicle, AGV)凭借其低能耗、低碳环保、高安全系数和环境适应性强等优势[1]，在自动化工厂和现代物流仓库得到了广泛应用。亚马逊公司于2012年收购了Kiva System公司开发的柔性仓库运载机器人Kiva，并陆续在其运营的多家仓库内投放了15 000台Kiva，以期降低货物交付时间，提高顾客满意度。此外，相关研究也表明AGV的应用能大幅度地提升工厂及仓储的产能和效能[2]。

在现代仓库运营管理中，基于射频识别、导航定位和物联网等技术，AGV已实现在大型工厂和物流仓库中的应用[3]。但如何让生产系统与物流系统自动、高效地完成AGV的路径规划和车辆调度，仍然是备受关注的问题。陈冠中等[4]通过排队网络模型对AGV的调度问题进行了分析;李军军等[5]、刘二辉等[6]、肖海宁等[7]利用启发式算法对AGV的路径规划问题进行了求解。与本研究密切相关的AGV的充电调度问题也得到了学者的广泛关注，张亚琦等[8]针对自动化码头AGV的充电与作业中的AGV充电利用率、最末任务完成时间以及AGV空载时间优化目标，设计了基于遗传算法的集成调度方案，该研究并未就AGV的具体充电过程建立模型。由于AGV充电调度属于电动车辆充电调度问题，张书玮等[9]基于实时信息交互系统，采用改进的Dijkstra方法求解多目标规划模型，得到了大规模电动汽车充电路径规划方案，针对充电过程主要考量电网负荷与电动汽车可达里程约束;李军等[10]通过修改公交车发车策略最小化车队运营成本，该研究假设电动公交车充电需求可被充分满足，无需排队等待充电桩;Boysen等[11]探讨了电动汽车在单一充电桩条件下的充电调度问题;郭戈等[12]从充电优化、路径优化和车队配置等不同的角度研究了汽车的充电调度问题;曾鸣等[13]和陆坚毅等[14]研究了公路交通系统下充电桩与电动汽车的匹配问题。

由于不同类型的AGV具有不同的重要性，根据作业进程具有不同的释放时间，且不同的充电桩与AGV的配对方式将产生不同的充电效能，传统的电动车辆充电调度策略所采用的先到充电桩先充电的策略将不能保证物流系统中的AGV得到高效利用。本文以亚马逊的Kiva为例，研究AGV在包含多个充电桩条件下的柔性自动化仓库作业中的充电调度策略，以期提高Kiva的使用效能。Kiva现有的充电方式大致可分为更换电池、插电式充电和无线充电3种。更换电池的方式虽然能快速地为Kiva补充电量，却需要人力干预或额外设立更换电池的平台，并且备用电池的储存、运输也会增加额外的成本;无线充电的充电效率低、设备成本较高、充电距离有限，但能更好地实现工厂的自动化。因此，在工厂、仓库等场所更多地选择插电式充电或无线充电的方式为Kiva补充电量。插电式充电和无线充电均会占用Kiva的作业时间，因而如何缩短充电时间对于提高AGV工作效能具有重要意义。

本文根据Kiva充电的调度问题，建立了对应的混合整数二次优化模型。由于Kiva具有不同的释放时间，使得该类问题变得十分复杂，且模型中同时存在二次约束和整数约束，使得该模型不能直接通过求解器进行求解。在已有的文献中，Lin等[15]对该类问题进行了研究，并通过设计的调度规则得到该问题的调度方案。与调度规则不同的，本文提出了根据Kiva的释放时间将原调度模型拆分成若干子问题的近似逼近算法，通过半定松弛对子问题进行处理，利用局部搜索寻找子问题的可行解，并组合得到原问题的调度方案。

1 Kiva智能充电模型描述

1.1 Kiva充电调度的问题描述

在Kiva实际工作中，即便Kiva初始是满电状态，根据不同的工况和作业负荷，这部分电量通常不足以支持Kiva完成一天的作业任务，因此在作业期间仍然需要为Kiva充电。Kabir等[16]的研究指出，可以通过降低AGV充电的目标电量来提高工厂作业的柔性，这意味着Kiva每次充电无需充满。本文认为，每台Kiva所需充电时间各不相同。又由于不同充电桩的充电效率存在差异，不失一般性，本文假定每台Kiva在每个充电桩上所需的充电时间不同。

每台Kiva的活动过程如图1所示，Kiva从满电状态开始作业直到Kiva的电量低于给定的电量阈值，这时认为这台Kiva被释放，即可以开始充电。同时，根据系统的调度方案，决定该Kiva的实际开始充电时间。当Kiva电量达到充电的目标，Kiva停止充电并返回仓库专业，该时刻被认为是Kiva充电完工时间。

在柔性物流仓库作业中，为了保证所有的Kiva都能在电量耗尽前行驶到充电区域，可以通过传感器技术和无线通讯技术实时监测Kiva的剩余电量，并为Kiva的剩余电量设定一个阈值。当Kiva的剩余电量低于阈值且完成当前调度任务后，要求该Kiva前往指定充电区域，Kiva到达充电等待区的时刻，认为是Kiva的释放时间。

Kiva调度流程如图2所示，当进行柔性物流仓库作业的Kiva电量低于阈值时，低电量的Kiva会自动行驶到充电等待区域等待充电。为便于模型讨论，假设Kiva充电区域容量不会对问题求解产生影响。对于充电等待区域的Kiva，可通过笔者团队的调度算法来确定下一个进行充电的Kiva及其对应的充电桩。在Kiva按照要求完成其充电操作后，自动返回仓库继续作业。

此外，由于每台Kiva作业类型和强度不同，其电量消耗至需要充电的阈值的时间也不尽相同，即认为每台Kiva的可安排充电状态具有不同的起始时间(release date)。因为每台Kiva的路径调度和工作任务是事先决定的，所以容易得到其充电操作的可排程时刻。本文中，假定所有Kiva的释放时间均为已知，即所研究的柔性物流系统中的Kiva充电调度问题是一个静态调度问题。

在柔性物流仓库的Kiva充电调度问题中，本文希望最大化Kiva的有效工作时间，即最小化每台Kiva在充电调度问题中的累计充电完成时间。由于不同的Kiva在物流系统中具有不同的重要程度，其承担的配送作业紧急程度也不尽相同，考虑为每台Kiva的充电完成时间设定不同的权重。综上所述，本文所研究问题的目标为最小化每台Kiva在充电调度结果中的累计加权充电完成时间。

1.2 Kiva充电调度的数学模型

通过第1.1节中对Kiva充电调度问题的分析，本节将尝试构建相应数学模型进行求解。在这之前，本文将给出数学模型中所使用的符号定义，如表1所示。

表1 数学模型中符号说明

通过建立相应数学模型，得到该问题的混合二次整数规划模型(Mixed Quadratic Integer Programming, MQIP)如下：

(1)

s.t.

(2)

(3)

Sj≥Rj,j∈N;

(4)

(5)

xij∈{0,1},i∈M,j∈N;

(6)

ykj∈{0,1},i∈M,j∈N。

(7)

其中:目标函数(1)是最小化所有Kiva的加权完工时间的加和，即最大化Kiva的工作时间。约束(2)要求每台Kiva在且仅在一个充电桩上充电；式(3)定义了Kiva开始充电的时间，并要求每个充电桩在同一时刻最多只能给一台Kiva充电；式(4)确保Kiva只能在被释放后才开始充电；式(5)定义了Kiva完成充电的时间，即Kiva的充电完成时间为Kiva开始充电的时间加上它充电所需的时间，式(2)和式(5)的共同作用使得Kiva的充电过程不可被打断；式(6)和式(7)要求决策变量均为0-1变量。

上述数学模型可以看作是目标函数为最小化总加权完工时间的带释放时间的单阶段无关机调度问题，其中单阶段表示一个工件只需要在任意一个机器上进行加工即可，无关机则指工件在不同机器上的加工时间是相互独立的。但该类问题是NP-hard问题，即无法在多项式时间内求得最优解。近年来Tang等[17]和Lin等[15]对该类问题进行了研究。

定理1目标函数是最小化总加权完工时间的带释放时间的单阶段无关机调度问题是NP-hard问题。

证明Lenstra等[18]证明了目标函数是总加权完工时间的带释放时间的单机调度问题，是NP-hard问题。单机调度是无关机调度的一种特殊情况，即只有一台机器的情况。因此，作为更复杂的调度情形，以上模型所研究的问题同样也是NP-hard问题。

此外，由于式(3)中含有0-1二次约束，以上模型不能直接求解。第2章将提出一种算法,将原调度问题分解成若干较易分析求解的子问题来处理。

2 Kiva智能充电系统调度算法

在第1章中，本文建立了考虑Kiva释放时间的充电调度模型。由于该模型中含有0-1二次约束，当问题规模较大时，求解时间将显著增长。为此，本文提出一种新的近似算法，将原问题分割为若干易于求解的子问题，并将子问题的解组合得到原Kiva充电调度问题的近优解。

2.1 划分子问题

根据Kiva释放时间不同，原问题可被分割为若干子问题，且每个子问题中的Kiva均具有相同的释放时间。为了更方便地描述算法，下面首先给出相关符号说明：

Gj为第j个Kiva的释放时间;

Subk为第k个子问题中，Kiva的释放时间;

K为具有不同释放时间的Kiva总数。

由此可进一步给出原问题的具体分割规则。首先将所有Kiva按其释放时间由小到大的顺序排列，令第一个子问题中Kiva的释放时间Sub1=R1，假设第j-1台Kiva包含于第k个子问题，则Subk=Rj-1，此时若第j台Kiva的释放时间满足Rj=Rj-1，可知Subk=Rj；否则Subk+1=Rj成立，其中j∈{2,3,…,N},k∈{1,2,…,K-1}。基于该分割规则可将原问题划分为K个子问题，在每个子问题中与释放时间相关的约束可以被忽略，并得到如下的混合整数规划模型。

(8)

(9)

xij∈{0,1},i∈M,j∈Nk。

(10)

尽管上述不含释放时间约束的子问题易于求解，但在实际分析子问题时可以发现，第k个子问题中的Kiva并不总是在第k+1个子问题开始前完成充电。针对该现象可以分如下两种情况讨论：

情形1第k个子问题中的Kiva，直到第k+1个子问题开始时仍未开始进行充电。

情形2第k个子问题中的Kiva，在第k+1个子问题开始前已开始充电，但尚未完成充电。

2.2 求解子问题及原问题

针对2.1节给出的子问题MIPk，可通过如下混合整数规划模型求解。

(11)

s.t.

(12)

xij∈{0,1},i∈M,j∈Nk。

(13)

其中：x∈Rmn是将xij重新排列后得到的向量，在任意充电桩i上，xij根据Wj/Pij从小到大的顺序进行排列;向量c∈Rmn由cij=WjPij组成;矩阵D=(d(ij)(i′j′))是一个mn×mn的半正定矩阵，其构成规则如下：

通过对MQIPk中的0-1变量进行半定松弛，得到如下模型：

(14)

s.t.

Ax=1;

(15)

X-xxT≻0;

(16)

diag(X)=x;

(17)

X∈Smn×mn,x∈Rmn。

(18)

其中：A为mn×mn的全1矩阵；x为由xij构成的向量。模型MQIPk中的0-1约束(13)在模型SDPk中被式(15)和式(16)代替，其中diag(X)表示矩阵X的主对角元元素组成的向量。

以上SDPk模型为标准半正定规划(Semi-definite Programming, SDP)模型，因此可通过SeDuMi等求解器直接求解。为了得到原问题的可行解，本文设计如下算法处理子问题的松弛解，并组合为原充电问题的调度方案。算法流程如下：

(1)将所有Kiva按释放时间从小到大顺序排序，找到Kiva所需的最长充电时间Pmax=max{Pij}，定义集合SP用以储存最终的调度方案，定义集合LSDP用以储存已求解的SDPk问题。

(2)当k=1时，Sub1=G1；Subk=Gj-1，若Gj=Gj-1，j∈{2,3,…,n}，则将第j个Kiva加入第k个子问题，否则将其加入第k+1个子问题。

(3)搜索集合LSDP，若已存在相同的SDPk问题，则直接读取该问题的松弛解；否则求解第k个子问题SDPk，调用SeDuMi求得其松弛解。

(4)利用局部搜索算法，根据SDPk的松弛解找到第k个子问题的可行调度方案。若该调度方案中存在Kiva开始充电的时间Sj大于k+1个子问题的开始时间Subk，则将该Kiva放入下一个子问题中求解，并令Gj=Subk+1。

(5)若上述调度方案中存在第k个子问题已经开始充电的Kiva，且在k+1个子问题开始前未完成充电，则此Kiva的充电分为两部分进行。假设Kiva编号为j在第t个充电桩上进行充电，设其在k+1个子问题中在第t个充电桩上所需的充电时间Ptj=Cj-Subk+1，在其余充电桩上所需的充电时间为Q1，并令其权重Wj=Q2。

(6)将所有能在第k+1个子问题前开始充电的Kiva调度方案储存在集合SP中。

(7)重复步骤(3)～步骤(6)，直到k=K，这时SP中存储的调度方案即为原问题的调度方案。

综上所述，主算法模块伪代码如下：

算法1主程序。

1 初始化pmax=max{pij},∀i∈M,j∈N,令Sub1=G1,k=1,并令SP,LSDP为空;

2 for j=2:N do

3 if Gj=Gj-1then

4 将第j个Kiva加入第k个子问题;

5 else

6 将第j个Kiva加入第k个子问题;

7 K=k,k=k+1;

8 for k=1:K do

9 if LSDP中存在相同的SDPk问题then

10 直接读取该SDPk的松驰解;

11 else

12 求解子问题模型SDPk,得到其松弛解，并存入LSDP集合;

13 利用局布搜索算法，找到第k个问题的可行解;

14 for j=1:Nkdo

15 if Cj>Subkthen

16 if Sj>Subkthen

17 Ptj=Cj-Subk+1,Pj=Q1，Wj=Q2

18 else

19 将第j个Kiva放入第k+1个子问题，Gj=Subk+1;

20 将所有能在下个阶子问题前开始充电的Kiva的调度方案储存在集合SP中;

21 计算结束，输出集合SP中的调度方案。

其中第13行中的局部搜索算法流程如下：

(1)对第k个子问题中的任意Kivaj，找到使xij最大的充电桩i′，令xi′j=1；对其余的i≠i′,i∈M，令xij=0，得到可行调度方案。

(2)对调任意两台Kiva的充电顺序，如果新的充电调度方案的总加权等待时间更小，则保留新方案；否则保留原方案。

由此可知，局部搜索子算法部分的伪代码如下所示：

算法2局部搜索程序。

1 for j=1:Nkdo

2 for i=1:M do

3 找到令xij最大的i,记作i′

4 令xi′j=1,对其余的i≠i′,i∈M,令xij=0

5 计算当前调度方案的目标函数值，记作Opt0,令Optmax=Opt0

6 for j=1:Nkdo

7 调换任意两台Kiva的充电顺序，计算新的调度方案的目标函数值，记作Optjif Optj>Optmaxthen

8 令Optmax=Optj,并保留新的调度方案

9 返回主程序

3 算例分析

MQIP模型描述了一个以最小化总加权完工时间为目标的不相干平行机调度问题，其中每个工件的释放时间不完全相同。前文中已经说明这类问题是NP-hard问题，这意味着本文所研究的问题无法在多项式时间内得到最优解。在第2章中，本文提出一种新的算法，将原问题分解为若干个子问题并进行求解，再由子问题的调度方案组合出原问题的调度方案。本章将通过与其他算法的对比来验证本文所提算法的性能。

本文所有的计算都在CPU频率为2.3 GHz、内存为8 GB的电脑上进行。所有的算法均基于MATLAB R2016a 软件进行编程求解，其中半定规划问题通过SeDuMi求解。根据柔性物流仓库的应用实例，本文考虑包含有5台充电桩、60台Kiva的充电调度情境。对应每台Kiva所需的充电时间和权重，将在本文的附录表1中给出。

使用本文所提算法求解该充电调度问题，得到了如图3所示的调度方案。其中M1～M5分别表示第1到第5台充电桩，编号1～60为Kiva的编号。方块长度表示Kiva所需充电时长，方块颜色由深至浅分别表示Kiva剩余电量较少、剩余电量中等、剩余电量较多。图中还给出了每段充电桩连续给Kiva充电的开始时间。从图3的调度结果可以看出，系统通常会优先为剩余电量较多的Kiva进行充电，以此最小化所有Kiva总的等待时间。

如图4所示为初次使用本文所提算法的计算时间分布，其中黑色部分为使用该算法求解的总时间；浅灰色部分的每一格为求解10次SDP问题所消耗的时间；深灰色部分为算法中其余部分的计算时间，这一部分计算时间在算法总计算时间中占比较小，且总是小于5 s。可以看出，在初次使用该算法求解调度问题时，计算时间的主要花费是求解SDP子问题。为减少计算时间，算法中设计了LSDP库用于储存已求解的SDP问题。当需要求解SDP问题时，算法会首先搜索LSDP集合，若LSDP集合中存在相似的SDP问题，则可以直接调用LSDP库中的求解结果。通过调用LSDP集合，可以明显降低求解SDP问题的次数，从而使算法的计算时间得到明显的降低。

Lin等[15]对目标函数是总加权完工时间的带释放时间的单阶段无关机调度问题提出了NEH加权完工时间(Weighted Completion Time Nawaz-Ens-

core-Ham, WCT-NEH)算法，因此本文将主要与该算法进行比较。此外，本文还会与Kiva先到充电桩先开始充电这种最直观的方法进行比较。为验证本文所提算法的性能，算例部分还将考虑仓库分别安装有3、5和7台充电桩，为40、60和80台Kiva执行充电调度的问题，每组算例的计算结果和时间均为20次重复实验的平均值，其充电参数在附录表2中给出。在非7台充电桩和80台Kiva时，充电参数的取值如附录表2所示。

充电调度问题求解算法性能比较如表2所示，表中：FIFO表示Kiva先到充电桩先开始充电这一调度策略；WCT-NEH是利用Lin[15]提出的方法求解的结果；OUR表示本文所提出的算法；CPLEX 12.6是由IBM公司推出的一种具备可靠、快速、灵活等特性的商业软件，可以解决线性规划问题、二次规划问题、二次约束规划问题及混合整数规划问题，CPLEX表示由该求解软件在3 600 s内能得到的最优解。为了更直观地比较计算结果，本文比较了前3类算法与CPLEX在3 600 s内的最优解的比例差(GAP)。GAP的计算公式为

GAP=(v(当前算法)-v(CPLEX))/

v(当前算法)，

其中v(算法)表示使用该算法求解的计算结果。

如表2所示，本文所提算法与最优解间的GAP小于3%；当CPLEX不能在3 600 s内求得最优解时，本文提出的算法可能得到比CPLEX更好的解，此时本文提出的算法与最优解间的GAP为负数，例如M=5，N=80；M=7，N=80时。通过FIFO算法得到的解与最优解间的GAP最大为35%，通过FIFO算法得到的解与最优解间的GAP最大为19%。相比以上两种方法，尽管本文提出的算法需要较多的计算时间，但能明显提高解的质量。

表2 充电调度问题求解算法性能比较

由图5可以观察到，在9种不同的情境中，本文提出的算法能得到比其他两种算法更好的解。随着问题中需要充电的Kiva数量增加，本文算法得到的调度结果较其他两种算法在解的质量方面均有较大幅度提升，这说明本文提出的算法能显著降低Kiva的充电等待时间，提高Kiva整体的利用效率。

4 结束语

本文针对现代化物流仓库中Kiva的充电调度问题，建立了混合整数规划模型，并提出一种新的基于半定规划的近似算法。通过将复杂的原调度问题分解为若干子问题求解，可有效降低问题的求解难度。同时，本文证明了此类子问题的划分方式将不会打断已经开始充电作业的Kiva，并且组合子问题的解之后可得到原调度问题的近似最优解。基于实际自动化仓库Kiva充电作业案例的计算结果可以发现，本文提出的算法较传统的FIFO方法、WCT-NEH方法可明显缩短Kiva的充电等待时间，提高Kiva在仓库作业的利用率。此外，由本文的算例结果可知，在Kiva充电调度问题中，应优先为权重较大的Kiva执行充电；当有多台Kiva等待充电时，应优先为所需充电时间较短的Kiva执行充电，从而可有效缩短所有Kiva的累积等待时间。

由于实际工业现场中影响AGV运行的因素较多，Kiva的充电调度也相应更为复杂。下一步研究需要同时考虑Kiva运行时的协同联动与交通规划、等待充电Kiva的队列结构、不同Kiva工作负荷下电池的充放电曲线及其使用寿命等。此外，为维持正常的车间内物流运作，进行Kiva充电调度时也需同时确保正常执行搬运的Kiva数量，以达到生产过程的动态均衡。

附录

表1 Kiva充电参数(M=5,N=60)

续表1

表2 Kiva充电参数(M=7,N=80)