多充電樁下考慮運(yùn)載機(jī)械釋放時間的充電調(diào)度

裴 植，萬明重，杜 蕊，李英德，陳 勇

(浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院工業(yè)工程研究所，浙江 杭州 310032)

0 引言

近年來，自動引導(dǎo)小車(Automated Guided Vehicle, AGV)憑借其低能耗、低碳環(huán)保、高安全系數(shù)和環(huán)境適應(yīng)性強(qiáng)等優(yōu)勢[1]，在自動化工廠和現(xiàn)代物流倉庫得到了廣泛應(yīng)用。亞馬遜公司于2012年收購了Kiva System公司開發(fā)的柔性倉庫運(yùn)載機(jī)器人Kiva，并陸續(xù)在其運(yùn)營的多家倉庫內(nèi)投放了15 000臺Kiva，以期降低貨物交付時間，提高顧客滿意度。此外，相關(guān)研究也表明AGV的應(yīng)用能大幅度地提升工廠及倉儲的產(chǎn)能和效能[2]。

在現(xiàn)代倉庫運(yùn)營管理中，基于射頻識別、導(dǎo)航定位和物聯(lián)網(wǎng)等技術(shù)，AGV已實現(xiàn)在大型工廠和物流倉庫中的應(yīng)用[3]。但如何讓生產(chǎn)系統(tǒng)與物流系統(tǒng)自動、高效地完成AGV的路徑規(guī)劃和車輛調(diào)度，仍然是備受關(guān)注的問題。陳冠中等[4]通過排隊網(wǎng)絡(luò)模型對AGV的調(diào)度問題進(jìn)行了分析;李軍軍等[5]、劉二輝等[6]、肖海寧等[7]利用啟發(fā)式算法對AGV的路徑規(guī)劃問題進(jìn)行了求解。與本研究密切相關(guān)的AGV的充電調(diào)度問題也得到了學(xué)者的廣泛關(guān)注，張亞琦等[8]針對自動化碼頭AGV的充電與作業(yè)中的AGV充電利用率、最末任務(wù)完成時間以及AGV空載時間優(yōu)化目標(biāo)，設(shè)計了基于遺傳算法的集成調(diào)度方案，該研究并未就AGV的具體充電過程建立模型。由于AGV充電調(diào)度屬于電動車輛充電調(diào)度問題，張書瑋等[9]基于實時信息交互系統(tǒng)，采用改進(jìn)的Dijkstra方法求解多目標(biāo)規(guī)劃模型，得到了大規(guī)模電動汽車充電路徑規(guī)劃方案，針對充電過程主要考量電網(wǎng)負(fù)荷與電動汽車可達(dá)里程約束;李軍等[10]通過修改公交車發(fā)車策略最小化車隊運(yùn)營成本，該研究假設(shè)電動公交車充電需求可被充分滿足，無需排隊等待充電樁;Boysen等[11]探討了電動汽車在單一充電樁條件下的充電調(diào)度問題;郭戈等[12]從充電優(yōu)化、路徑優(yōu)化和車隊配置等不同的角度研究了汽車的充電調(diào)度問題;曾鳴等[13]和陸堅毅等[14]研究了公路交通系統(tǒng)下充電樁與電動汽車的匹配問題。

由于不同類型的AGV具有不同的重要性，根據(jù)作業(yè)進(jìn)程具有不同的釋放時間，且不同的充電樁與AGV的配對方式將產(chǎn)生不同的充電效能，傳統(tǒng)的電動車輛充電調(diào)度策略所采用的先到充電樁先充電的策略將不能保證物流系統(tǒng)中的AGV得到高效利用。本文以亞馬遜的Kiva為例，研究AGV在包含多個充電樁條件下的柔性自動化倉庫作業(yè)中的充電調(diào)度策略，以期提高Kiva的使用效能。Kiva現(xiàn)有的充電方式大致可分為更換電池、插電式充電和無線充電3種。更換電池的方式雖然能快速地為Kiva補(bǔ)充電量，卻需要人力干預(yù)或額外設(shè)立更換電池的平臺，并且備用電池的儲存、運(yùn)輸也會增加額外的成本;無線充電的充電效率低、設(shè)備成本較高、充電距離有限，但能更好地實現(xiàn)工廠的自動化。因此，在工廠、倉庫等場所更多地選擇插電式充電或無線充電的方式為Kiva補(bǔ)充電量。插電式充電和無線充電均會占用Kiva的作業(yè)時間，因而如何縮短充電時間對于提高AGV工作效能具有重要意義。

本文根據(jù)Kiva充電的調(diào)度問題，建立了對應(yīng)的混合整數(shù)二次優(yōu)化模型。由于Kiva具有不同的釋放時間，使得該類問題變得十分復(fù)雜，且模型中同時存在二次約束和整數(shù)約束，使得該模型不能直接通過求解器進(jìn)行求解。在已有的文獻(xiàn)中，Lin等[15]對該類問題進(jìn)行了研究，并通過設(shè)計的調(diào)度規(guī)則得到該問題的調(diào)度方案。與調(diào)度規(guī)則不同的，本文提出了根據(jù)Kiva的釋放時間將原調(diào)度模型拆分成若干子問題的近似逼近算法，通過半定松弛對子問題進(jìn)行處理，利用局部搜索尋找子問題的可行解，并組合得到原問題的調(diào)度方案。

1 Kiva智能充電模型描述

1.1 Kiva充電調(diào)度的問題描述

在Kiva實際工作中，即便Kiva初始是滿電狀態(tài)，根據(jù)不同的工況和作業(yè)負(fù)荷，這部分電量通常不足以支持Kiva完成一天的作業(yè)任務(wù)，因此在作業(yè)期間仍然需要為Kiva充電。Kabir等[16]的研究指出，可以通過降低AGV充電的目標(biāo)電量來提高工廠作業(yè)的柔性，這意味著Kiva每次充電無需充滿。本文認(rèn)為，每臺Kiva所需充電時間各不相同。又由于不同充電樁的充電效率存在差異，不失一般性，本文假定每臺Kiva在每個充電樁上所需的充電時間不同。

每臺Kiva的活動過程如圖1所示，Kiva從滿電狀態(tài)開始作業(yè)直到Kiva的電量低于給定的電量閾值，這時認(rèn)為這臺Kiva被釋放，即可以開始充電。同時，根據(jù)系統(tǒng)的調(diào)度方案，決定該Kiva的實際開始充電時間。當(dāng)Kiva電量達(dá)到充電的目標(biāo)，Kiva停止充電并返回倉庫專業(yè)，該時刻被認(rèn)為是Kiva充電完工時間。

在柔性物流倉庫作業(yè)中，為了保證所有的Kiva都能在電量耗盡前行駛到充電區(qū)域，可以通過傳感器技術(shù)和無線通訊技術(shù)實時監(jiān)測Kiva的剩余電量，并為Kiva的剩余電量設(shè)定一個閾值。當(dāng)Kiva的剩余電量低于閾值且完成當(dāng)前調(diào)度任務(wù)后，要求該Kiva前往指定充電區(qū)域，Kiva到達(dá)充電等待區(qū)的時刻，認(rèn)為是Kiva的釋放時間。

Kiva調(diào)度流程如圖2所示，當(dāng)進(jìn)行柔性物流倉庫作業(yè)的Kiva電量低于閾值時，低電量的Kiva會自動行駛到充電等待區(qū)域等待充電。為便于模型討論，假設(shè)Kiva充電區(qū)域容量不會對問題求解產(chǎn)生影響。對于充電等待區(qū)域的Kiva，可通過筆者團(tuán)隊的調(diào)度算法來確定下一個進(jìn)行充電的Kiva及其對應(yīng)的充電樁。在Kiva按照要求完成其充電操作后，自動返回倉庫繼續(xù)作業(yè)。

此外，由于每臺Kiva作業(yè)類型和強(qiáng)度不同，其電量消耗至需要充電的閾值的時間也不盡相同，即認(rèn)為每臺Kiva的可安排充電狀態(tài)具有不同的起始時間(release date)。因為每臺Kiva的路徑調(diào)度和工作任務(wù)是事先決定的，所以容易得到其充電操作的可排程時刻。本文中，假定所有Kiva的釋放時間均為已知，即所研究的柔性物流系統(tǒng)中的Kiva充電調(diào)度問題是一個靜態(tài)調(diào)度問題。

在柔性物流倉庫的Kiva充電調(diào)度問題中，本文希望最大化Kiva的有效工作時間，即最小化每臺Kiva在充電調(diào)度問題中的累計充電完成時間。由于不同的Kiva在物流系統(tǒng)中具有不同的重要程度，其承擔(dān)的配送作業(yè)緊急程度也不盡相同，考慮為每臺Kiva的充電完成時間設(shè)定不同的權(quán)重。綜上所述，本文所研究問題的目標(biāo)為最小化每臺Kiva在充電調(diào)度結(jié)果中的累計加權(quán)充電完成時間。

1.2 Kiva充電調(diào)度的數(shù)學(xué)模型

通過第1.1節(jié)中對Kiva充電調(diào)度問題的分析，本節(jié)將嘗試構(gòu)建相應(yīng)數(shù)學(xué)模型進(jìn)行求解。在這之前，本文將給出數(shù)學(xué)模型中所使用的符號定義，如表1所示。

表1 數(shù)學(xué)模型中符號說明

通過建立相應(yīng)數(shù)學(xué)模型，得到該問題的混合二次整數(shù)規(guī)劃模型(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)

其中:目標(biāo)函數(shù)(1)是最小化所有Kiva的加權(quán)完工時間的加和，即最大化Kiva的工作時間。約束(2)要求每臺Kiva在且僅在一個充電樁上充電；式(3)定義了Kiva開始充電的時間，并要求每個充電樁在同一時刻最多只能給一臺Kiva充電；式(4)確保Kiva只能在被釋放后才開始充電；式(5)定義了Kiva完成充電的時間，即Kiva的充電完成時間為Kiva開始充電的時間加上它充電所需的時間，式(2)和式(5)的共同作用使得Kiva的充電過程不可被打斷；式(6)和式(7)要求決策變量均為0-1變量。

上述數(shù)學(xué)模型可以看作是目標(biāo)函數(shù)為最小化總加權(quán)完工時間的帶釋放時間的單階段無關(guān)機(jī)調(diào)度問題，其中單階段表示一個工件只需要在任意一個機(jī)器上進(jìn)行加工即可，無關(guān)機(jī)則指工件在不同機(jī)器上的加工時間是相互獨(dú)立的。但該類問題是NP-hard問題，即無法在多項式時間內(nèi)求得最優(yōu)解。近年來Tang等[17]和Lin等[15]對該類問題進(jìn)行了研究。

定理1目標(biāo)函數(shù)是最小化總加權(quán)完工時間的帶釋放時間的單階段無關(guān)機(jī)調(diào)度問題是NP-hard問題。

證明Lenstra等[18]證明了目標(biāo)函數(shù)是總加權(quán)完工時間的帶釋放時間的單機(jī)調(diào)度問題，是NP-hard問題。單機(jī)調(diào)度是無關(guān)機(jī)調(diào)度的一種特殊情況，即只有一臺機(jī)器的情況。因此，作為更復(fù)雜的調(diào)度情形，以上模型所研究的問題同樣也是NP-hard問題。

此外，由于式(3)中含有0-1二次約束，以上模型不能直接求解。第2章將提出一種算法,將原調(diào)度問題分解成若干較易分析求解的子問題來處理。

2 Kiva智能充電系統(tǒng)調(diào)度算法

在第1章中，本文建立了考慮Kiva釋放時間的充電調(diào)度模型。由于該模型中含有0-1二次約束，當(dāng)問題規(guī)模較大時，求解時間將顯著增長。為此，本文提出一種新的近似算法，將原問題分割為若干易于求解的子問題，并將子問題的解組合得到原Kiva充電調(diào)度問題的近優(yōu)解。

2.1 劃分子問題

根據(jù)Kiva釋放時間不同，原問題可被分割為若干子問題，且每個子問題中的Kiva均具有相同的釋放時間。為了更方便地描述算法，下面首先給出相關(guān)符號說明：

Gj為第j個Kiva的釋放時間;

Subk為第k個子問題中，Kiva的釋放時間;

K為具有不同釋放時間的Kiva總數(shù)。

由此可進(jìn)一步給出原問題的具體分割規(guī)則。首先將所有Kiva按其釋放時間由小到大的順序排列，令第一個子問題中Kiva的釋放時間Sub1=R1，假設(shè)第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}。基于該分割規(guī)則可將原問題劃分為K個子問題，在每個子問題中與釋放時間相關(guān)的約束可以被忽略，并得到如下的混合整數(shù)規(guī)劃模型。

(8)

(9)

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

(10)

盡管上述不含釋放時間約束的子問題易于求解，但在實際分析子問題時可以發(fā)現(xiàn)，第k個子問題中的Kiva并不總是在第k+1個子問題開始前完成充電。針對該現(xiàn)象可以分如下兩種情況討論：

情形1第k個子問題中的Kiva，直到第k+1個子問題開始時仍未開始進(jìn)行充電。

情形2第k個子問題中的Kiva，在第k+1個子問題開始前已開始充電，但尚未完成充電。

2.2 求解子問題及原問題

針對2.1節(jié)給出的子問題MIPk，可通過如下混合整數(shù)規(guī)劃模型求解。

(11)

s.t.

(12)

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

(13)

其中：x∈Rmn是將xij重新排列后得到的向量，在任意充電樁i上，xij根據(jù)Wj/Pij從小到大的順序進(jìn)行排列;向量c∈Rmn由cij=WjPij組成;矩陣D=(d(ij)(i′j′))是一個mn×mn的半正定矩陣，其構(gòu)成規(guī)則如下：

通過對MQIPk中的0-1變量進(jìn)行半定松弛，得到如下模型：

(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構(gòu)成的向量。模型MQIPk中的0-1約束(13)在模型SDPk中被式(15)和式(16)代替，其中diag(X)表示矩陣X的主對角元元素組成的向量。

以上SDPk模型為標(biāo)準(zhǔn)半正定規(guī)劃(Semi-definite Programming, SDP)模型，因此可通過SeDuMi等求解器直接求解。為了得到原問題的可行解，本文設(shè)計如下算法處理子問題的松弛解，并組合為原充電問題的調(diào)度方案。算法流程如下：

(1)將所有Kiva按釋放時間從小到大順序排序，找到Kiva所需的最長充電時間Pmax=max{Pij}，定義集合SP用以儲存最終的調(diào)度方案，定義集合LSDP用以儲存已求解的SDPk問題。

(2)當(dāng)k=1時，Sub1=G1；Subk=Gj-1，若Gj=Gj-1，j∈{2,3,…,n}，則將第j個Kiva加入第k個子問題，否則將其加入第k+1個子問題。

(3)搜索集合LSDP，若已存在相同的SDPk問題，則直接讀取該問題的松弛解；否則求解第k個子問題SDPk，調(diào)用SeDuMi求得其松弛解。

(4)利用局部搜索算法，根據(jù)SDPk的松弛解找到第k個子問題的可行調(diào)度方案。若該調(diào)度方案中存在Kiva開始充電的時間Sj大于k+1個子問題的開始時間Subk，則將該Kiva放入下一個子問題中求解，并令Gj=Subk+1。

(5)若上述調(diào)度方案中存在第k個子問題已經(jīng)開始充電的Kiva，且在k+1個子問題開始前未完成充電，則此Kiva的充電分為兩部分進(jìn)行。假設(shè)Kiva編號為j在第t個充電樁上進(jìn)行充電，設(shè)其在k+1個子問題中在第t個充電樁上所需的充電時間Ptj=Cj-Subk+1，在其余充電樁上所需的充電時間為Q1，并令其權(quán)重Wj=Q2。

(6)將所有能在第k+1個子問題前開始充電的Kiva調(diào)度方案儲存在集合SP中。

(7)重復(fù)步驟(3)～步驟(6)，直到k=K，這時SP中存儲的調(diào)度方案即為原問題的調(diào)度方案。

綜上所述，主算法模塊偽代碼如下：

算法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的調(diào)度方案儲存在集合SP中;

21 計算結(jié)束，輸出集合SP中的調(diào)度方案。

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

(1)對第k個子問題中的任意Kivaj，找到使xij最大的充電樁i′，令xi′j=1；對其余的i≠i′,i∈M，令xij=0，得到可行調(diào)度方案。

(2)對調(diào)任意兩臺Kiva的充電順序，如果新的充電調(diào)度方案的總加權(quán)等待時間更小，則保留新方案；否則保留原方案。

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

算法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 計算當(dāng)前調(diào)度方案的目標(biāo)函數(shù)值，記作Opt0,令Optmax=Opt0

6 for j=1:Nkdo

7 調(diào)換任意兩臺Kiva的充電順序，計算新的調(diào)度方案的目標(biāo)函數(shù)值，記作Optjif Optj>Optmaxthen

8 令Optmax=Optj,并保留新的調(diào)度方案

9 返回主程序

3 算例分析

MQIP模型描述了一個以最小化總加權(quán)完工時間為目標(biāo)的不相干平行機(jī)調(diào)度問題，其中每個工件的釋放時間不完全相同。前文中已經(jīng)說明這類問題是NP-hard問題，這意味著本文所研究的問題無法在多項式時間內(nèi)得到最優(yōu)解。在第2章中，本文提出一種新的算法，將原問題分解為若干個子問題并進(jìn)行求解，再由子問題的調(diào)度方案組合出原問題的調(diào)度方案。本章將通過與其他算法的對比來驗證本文所提算法的性能。

本文所有的計算都在CPU頻率為2.3 GHz、內(nèi)存為8 GB的電腦上進(jìn)行。所有的算法均基于MATLAB R2016a 軟件進(jìn)行編程求解，其中半定規(guī)劃問題通過SeDuMi求解。根據(jù)柔性物流倉庫的應(yīng)用實例，本文考慮包含有5臺充電樁、60臺Kiva的充電調(diào)度情境。對應(yīng)每臺Kiva所需的充電時間和權(quán)重，將在本文的附錄表1中給出。

使用本文所提算法求解該充電調(diào)度問題，得到了如圖3所示的調(diào)度方案。其中M1～M5分別表示第1到第5臺充電樁，編號1～60為Kiva的編號。方塊長度表示Kiva所需充電時長，方塊顏色由深至淺分別表示Kiva剩余電量較少、剩余電量中等、剩余電量較多。圖中還給出了每段充電樁連續(xù)給Kiva充電的開始時間。從圖3的調(diào)度結(jié)果可以看出，系統(tǒng)通常會優(yōu)先為剩余電量較多的Kiva進(jìn)行充電，以此最小化所有Kiva總的等待時間。

如圖4所示為初次使用本文所提算法的計算時間分布，其中黑色部分為使用該算法求解的總時間；淺灰色部分的每一格為求解10次SDP問題所消耗的時間；深灰色部分為算法中其余部分的計算時間，這一部分計算時間在算法總計算時間中占比較小，且總是小于5 s。可以看出，在初次使用該算法求解調(diào)度問題時，計算時間的主要花費(fèi)是求解SDP子問題。為減少計算時間，算法中設(shè)計了LSDP庫用于儲存已求解的SDP問題。當(dāng)需要求解SDP問題時，算法會首先搜索LSDP集合，若LSDP集合中存在相似的SDP問題，則可以直接調(diào)用LSDP庫中的求解結(jié)果。通過調(diào)用LSDP集合，可以明顯降低求解SDP問題的次數(shù)，從而使算法的計算時間得到明顯的降低。

Lin等[15]對目標(biāo)函數(shù)是總加權(quán)完工時間的帶釋放時間的單階段無關(guān)機(jī)調(diào)度問題提出了NEH加權(quán)完工時間(Weighted Completion Time Nawaz-Ens-

core-Ham, WCT-NEH)算法，因此本文將主要與該算法進(jìn)行比較。此外，本文還會與Kiva先到充電樁先開始充電這種最直觀的方法進(jìn)行比較。為驗證本文所提算法的性能，算例部分還將考慮倉庫分別安裝有3、5和7臺充電樁，為40、60和80臺Kiva執(zhí)行充電調(diào)度的問題，每組算例的計算結(jié)果和時間均為20次重復(fù)實驗的平均值，其充電參數(shù)在附錄表2中給出。在非7臺充電樁和80臺Kiva時，充電參數(shù)的取值如附錄表2所示。

充電調(diào)度問題求解算法性能比較如表2所示，表中：FIFO表示Kiva先到充電樁先開始充電這一調(diào)度策略；WCT-NEH是利用Lin[15]提出的方法求解的結(jié)果；OUR表示本文所提出的算法；CPLEX 12.6是由IBM公司推出的一種具備可靠、快速、靈活等特性的商業(yè)軟件，可以解決線性規(guī)劃問題、二次規(guī)劃問題、二次約束規(guī)劃問題及混合整數(shù)規(guī)劃問題，CPLEX表示由該求解軟件在3 600 s內(nèi)能得到的最優(yōu)解。為了更直觀地比較計算結(jié)果，本文比較了前3類算法與CPLEX在3 600 s內(nèi)的最優(yōu)解的比例差(GAP)。GAP的計算公式為

GAP=(v(當(dāng)前算法)-v(CPLEX))/

v(當(dāng)前算法)，

其中v(算法)表示使用該算法求解的計算結(jié)果。

如表2所示，本文所提算法與最優(yōu)解間的GAP小于3%；當(dāng)CPLEX不能在3 600 s內(nèi)求得最優(yōu)解時，本文提出的算法可能得到比CPLEX更好的解，此時本文提出的算法與最優(yōu)解間的GAP為負(fù)數(shù)，例如M=5，N=80；M=7，N=80時。通過FIFO算法得到的解與最優(yōu)解間的GAP最大為35%，通過FIFO算法得到的解與最優(yōu)解間的GAP最大為19%。相比以上兩種方法，盡管本文提出的算法需要較多的計算時間，但能明顯提高解的質(zhì)量。

表2 充電調(diào)度問題求解算法性能比較

由圖5可以觀察到，在9種不同的情境中，本文提出的算法能得到比其他兩種算法更好的解。隨著問題中需要充電的Kiva數(shù)量增加，本文算法得到的調(diào)度結(jié)果較其他兩種算法在解的質(zhì)量方面均有較大幅度提升，這說明本文提出的算法能顯著降低Kiva的充電等待時間，提高Kiva整體的利用效率。

4 結(jié)束語

本文針對現(xiàn)代化物流倉庫中Kiva的充電調(diào)度問題，建立了混合整數(shù)規(guī)劃模型，并提出一種新的基于半定規(guī)劃的近似算法。通過將復(fù)雜的原調(diào)度問題分解為若干子問題求解，可有效降低問題的求解難度。同時，本文證明了此類子問題的劃分方式將不會打斷已經(jīng)開始充電作業(yè)的Kiva，并且組合子問題的解之后可得到原調(diào)度問題的近似最優(yōu)解?；趯嶋H自動化倉庫Kiva充電作業(yè)案例的計算結(jié)果可以發(fā)現(xiàn)，本文提出的算法較傳統(tǒng)的FIFO方法、WCT-NEH方法可明顯縮短Kiva的充電等待時間，提高Kiva在倉庫作業(yè)的利用率。此外，由本文的算例結(jié)果可知，在Kiva充電調(diào)度問題中，應(yīng)優(yōu)先為權(quán)重較大的Kiva執(zhí)行充電；當(dāng)有多臺Kiva等待充電時，應(yīng)優(yōu)先為所需充電時間較短的Kiva執(zhí)行充電，從而可有效縮短所有Kiva的累積等待時間。

由于實際工業(yè)現(xiàn)場中影響AGV運(yùn)行的因素較多，Kiva的充電調(diào)度也相應(yīng)更為復(fù)雜。下一步研究需要同時考慮Kiva運(yùn)行時的協(xié)同聯(lián)動與交通規(guī)劃、等待充電Kiva的隊列結(jié)構(gòu)、不同Kiva工作負(fù)荷下電池的充放電曲線及其使用壽命等。此外，為維持正常的車間內(nèi)物流運(yùn)作，進(jìn)行Kiva充電調(diào)度時也需同時確保正常執(zhí)行搬運(yùn)的Kiva數(shù)量，以達(dá)到生產(chǎn)過程的動態(tài)均衡。

附錄

表1 Kiva充電參數(shù)(M=5,N=60)

續(xù)表1

表2 Kiva充電參數(shù)(M=7,N=80)