周炳海， 費(fèi)芊然

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院， 上海 201804)

目前關(guān)于混流裝配線物料配送問(wèn)題的研究，多以最小化碳排放或耗電量為目標(biāo)，考慮能耗的研究較少.如Xiao等[1]提出模擬退火算法，解決以最小化碳排放為目標(biāo)的車輛路徑問(wèn)題(vehicle routing problem，VRP)；Ilgin等[2]則以最小化車輛總行駛距離和耗電量為目標(biāo)解決VRP問(wèn)題.

混流裝配線邊的零件進(jìn)料問(wèn)題為NP-hard問(wèn)題[3]，因此精確算法只適合求解小規(guī)模的零件配送問(wèn)題；而求解大規(guī)模的零件配送問(wèn)題常用元啟發(fā)式算法，如Fathi等[4]提出一種改進(jìn)粒子群優(yōu)化算法解決以多載量小車運(yùn)輸行程和運(yùn)載量為優(yōu)化目標(biāo)的裝配線零件進(jìn)料問(wèn)題，Nouri 等[5]則考慮多個(gè)機(jī)器人的車間機(jī)器人路徑規(guī)劃問(wèn)題，并提出基于鄰域的遺傳算法來(lái)優(yōu)化作業(yè)完成時(shí)間.

在分析上述文獻(xiàn)基礎(chǔ)上，本文提出了考慮能耗的零件配送問(wèn)題，引入“轉(zhuǎn)運(yùn)”策略以減少能耗，即允許送料機(jī)器人對(duì)配送物料進(jìn)行拆分、交換等操作，并構(gòu)建變鄰域搜索策略的改進(jìn)型離散差分進(jìn)化算法對(duì)送料機(jī)器人進(jìn)行調(diào)度，以期最小化配送系統(tǒng)的送料機(jī)器人團(tuán)隊(duì)規(guī)模及總能耗.

1 數(shù)學(xué)建模

1.1 問(wèn)題描述

在線邊超市配送系統(tǒng)[6]中，裝配所需的物料統(tǒng)一存放在裝配工位旁的線邊超市中，送料機(jī)器人根據(jù)生產(chǎn)計(jì)劃對(duì)各目標(biāo)工位的JIS(just-in-sequence)料箱進(jìn)行配送.機(jī)器人在配送過(guò)程中能量耗盡時(shí)需進(jìn)行充能，且在此期間無(wú)法執(zhí)行配送任務(wù)，因此需要重新分配補(bǔ)料任務(wù)，極大地增加了調(diào)度的復(fù)雜度.

送料機(jī)器人的能耗主要與其載重及行駛距離有關(guān)[7]，為了減少配送過(guò)程中的機(jī)器人能耗，本文提出圖1所示的 “轉(zhuǎn)運(yùn)”策略，即在配送過(guò)程中，允許送料機(jī)器人將其配送任務(wù)內(nèi)的物料暫存在線邊超市或工位處，交由其他送料機(jī)器人進(jìn)行配送.該策略可以有效地縮短送料機(jī)器人配送任務(wù)中的行駛距離并優(yōu)化載重分配，從而減少能耗.許多學(xué)者已經(jīng)建立了若干能耗模型，用以確定單位行駛距離的能耗與機(jī)器人載重量之間的關(guān)系.基于Qiu等[8]的研究，本文采用式(1)計(jì)算機(jī)器人r在工位s和s′之間行駛的能耗：

(1)

為了解決考慮能耗的機(jī)器人物料配送調(diào)度問(wèn)題，做出如下具體假設(shè):① 機(jī)器人裝卸料的能耗忽略不計(jì)；②機(jī)器人往來(lái)物料超市的工位間的速度為定值；③機(jī)器人的充電時(shí)間為定值，機(jī)器人返回后最早可于下一節(jié)拍開始工作；④同一機(jī)器人完成的不同補(bǔ)貨任務(wù)的補(bǔ)貨時(shí)間不能重疊；⑤不同機(jī)器人在同個(gè)工位進(jìn)行的不同補(bǔ)貨任務(wù)的時(shí)間不能重疊；⑥物料自物料超市出發(fā)可經(jīng)由多個(gè)機(jī)器人配送到目標(biāo)工位；⑦物料的轉(zhuǎn)運(yùn)操作只能在物料超市和各工位處發(fā)生；⑧機(jī)器人在一個(gè)節(jié)拍中最多補(bǔ)料一趟；⑨機(jī)器人的載重量和工位庫(kù)存容量均用標(biāo)準(zhǔn)化箱的數(shù)量表示.

1.2 數(shù)學(xué)模型

1) 參數(shù)及其定義：

S裝配線的工位集合，且工位s=1,2,…,|S|；

R送料機(jī)器人集合，且機(jī)器人r=1,2,…,|R|；

T調(diào)度期間的生產(chǎn)節(jié)拍總數(shù)；

dst工位s在節(jié)拍t的物料需求量；

Bs工位s處JIS物料箱的容量；

Cr送料機(jī)器人r的物料配送能力；

v送料機(jī)器人的配送速度；

lss′工位s與s′之間的距離，且s,s′∈S∪{0}，其中{0}表示線邊超市；

tr送料機(jī)器人r卸載單位物料的時(shí)間；

m送料機(jī)器人未載重時(shí)的質(zhì)量；

2) 決策變量：

kn送料機(jī)器人在工位n時(shí)對(duì)應(yīng)的配送物料量；

ξ機(jī)器人最低電量閾值.

3) 數(shù)學(xué)模型：

minf={f1,f2}；

(2)

s.t.

?s∈S；t=1,2,…,T.

(3)

?r∈R；t=1,2,…,T.

(4)

?r∈R；t=1,2,…,T.

(5)

(6)

(7)

?s∈S；1≤t

(8)

?r∈R；t,t′=1,…,T；t≠t′；

(9)

(10)

?r∈R；t=1,2,…,T；

(11)

(12)

(13)

zrt∈{0,1};?r∈R;t=1,…,T.

(14)

式(2)為目標(biāo)函數(shù)，包含兩個(gè)目標(biāo)，分別為最小化機(jī)器人團(tuán)隊(duì)規(guī)模和最小化機(jī)器人總能耗.約束(3)和(4)分別表示工位容量限制和機(jī)器人配送能力限制；約束(5)和(6)保證每個(gè)機(jī)器人均從線邊超市出發(fā)并返回；約束(7)確保任意機(jī)器人在某一時(shí)間僅在一個(gè)工位補(bǔ)料；約束(8)可避免不同機(jī)器人在同一時(shí)刻對(duì)同一工位進(jìn)行補(bǔ)料的情況；約束(9)保證了機(jī)器人連續(xù)兩次補(bǔ)料任務(wù)的時(shí)間差；約束(10)表示機(jī)器人到達(dá)工位時(shí)的電量；約束(11)確保機(jī)器人每次配送時(shí)的電量不低于安全電量；約束(12)～(14)為二進(jìn)制變量.

1.3 問(wèn)題性質(zhì)

2 變鄰域搜索策略的改進(jìn)型離散差分進(jìn)化算法(VNS-MDDE)

由于混流裝配線邊的零件配送問(wèn)題為NP-hard問(wèn)題[3]，采用啟發(fā)式算法可以更有效地在可接受時(shí)間內(nèi)解決問(wèn)題.多目標(biāo)差分進(jìn)化算法是基于群體智能理論的優(yōu)化算法，具有較強(qiáng)的魯棒性和全局尋優(yōu)能力.本文構(gòu)建變鄰域搜索策略的改進(jìn)型離散差分進(jìn)化算法VNS-MDDE(multi-objective discrete differential evolution algorithm with variable neighborhood search)，在多目標(biāo)差分進(jìn)化算法的基礎(chǔ)上引入變鄰域搜索策略進(jìn)行局部?jī)?yōu)化.

2.1 編碼

VNS-MDDE算法采用混合雙層編碼方式，如圖2所示，編碼的長(zhǎng)度為優(yōu)化問(wèn)題中裝配線工位的總數(shù)|S|的兩倍，其中后|S|個(gè)工位為轉(zhuǎn)運(yùn)工位.第一層編碼表示機(jī)器人服務(wù)工位的詳細(xì)信息，第二層表示機(jī)器人的配送物料量.

2.2 種群初始化

選擇合適的初始種群能加快算法的收斂并影響解的優(yōu)劣.根據(jù)上述編碼形式，本文采用最近鄰啟發(fā)式(NNH)算法構(gòu)建初始可行解，步驟如下：

① 令t=1.

② 選取機(jī)器人r=1，從超市出發(fā)隨機(jī)服務(wù)某個(gè)工位s.如果服務(wù)該工位可行時(shí)，即滿足約束(3)～(14)，則前往工位s=s+1，否則該機(jī)器人返回超市，下一個(gè)機(jī)器人從超市出發(fā)(r=r+1).直到所有工位s的物料需求均被滿足為止.

③t←t+1.

④ 重復(fù)步驟②和③，直至t=T為止.

重復(fù)上述步驟②～⑤共N次，生成初始種群.

2.3 變異運(yùn)算

本文算法采用的是差分進(jìn)化算法(differential evolution algorithm，簡(jiǎn)稱DE)中標(biāo)準(zhǔn)的變異策略DE/rand/1[9].根據(jù)一般的DE變異算子的結(jié)構(gòu)，在第G次迭代時(shí)，在種群中隨機(jī)選擇3個(gè)個(gè)體，通過(guò)把2個(gè)個(gè)體之間的加權(quán)向量差加到第3個(gè)個(gè)體上來(lái)產(chǎn)生新的變異個(gè)體Vi(G).本文采用如下針對(duì)整數(shù)規(guī)劃和混合整數(shù)規(guī)劃的變異算子來(lái)生成變異個(gè)體：

Vi(G)=Xa(G-1)⊕F?(Xb(G-1)-Xc(G-1)).

(15)

式中：a,b,c∈{1,…,N}是隨機(jī)選擇的，且a≠b≠c≠i；F∈[0,1]是控制偏差變量放大的變異常數(shù)因子.等式(15)的等號(hào)右側(cè)由兩部分運(yùn)算組成.第一部分表示兩個(gè)個(gè)體Xb和Xc之間的加權(quán)差，用下列等式表示：

Δi(G)=F?(Xb(G-1)-Xc(G-1))?

(16)

其中Δi(G)=δi1(G),…,δi,T-1(G)是臨時(shí)變量，rand(j)是[0,1]之間的隨機(jī)數(shù).第二部分表示Δi(G)和目標(biāo)個(gè)體的加和，用下列等式表示：

Vi(G)=Xa(G-1)⊕Δi(G)?

vij(G)=xaj(G-1)⊕δij(G)=

(18)

式中 %表示模運(yùn)算符，用來(lái)計(jì)算其左邊的整數(shù)除以其右邊的整數(shù)得到的余數(shù).

2.4 交叉運(yùn)算

交叉算子是指將變異個(gè)體的參數(shù)與另外預(yù)定的目標(biāo)個(gè)體按一定規(guī)則混合來(lái)產(chǎn)生試驗(yàn)個(gè)體.其中通過(guò)將變異個(gè)體和父代個(gè)體Xi(G-1)組合得到交叉?zhèn)€體Ui(G)，交叉?zhèn)€體的形成過(guò)程如下：

2.5 選擇運(yùn)算

在交叉運(yùn)算之后，選擇算子將決定試驗(yàn)個(gè)體是否可以保存至下一次迭代.本文將使用非支配排序方法將種群分成各個(gè)非支配層，隨后計(jì)算各層級(jí)每個(gè)個(gè)體的擁擠度[10]，最后在Ui(G)和Xi(G-1)中選擇優(yōu)者成為Xi(G).

2.6 局部?jī)?yōu)化

為了增強(qiáng)其局部搜索的能力，本文在每次迭代過(guò)程中加入變鄰域搜索策略(VNS)，對(duì)結(jié)構(gòu)鄰域內(nèi)的解進(jìn)行搜尋改進(jìn).VNS的思路是在不同的鄰域結(jié)構(gòu)N1,…,Nk之間進(jìn)行搜索.從第一個(gè)鄰域結(jié)構(gòu)開始進(jìn)行局部搜索，直到無(wú)法進(jìn)一步地改進(jìn)為止.本文提出的鄰域結(jié)構(gòu)如下：

隨機(jī)交換(random exchange，RE)：隨機(jī)選擇Z對(duì)機(jī)器人，交換其服務(wù)工位的配送物料量.

隨機(jī)轉(zhuǎn)移(random remove，RR)：隨機(jī)刪除機(jī)器人r在周期t的配送任務(wù)，將其配送物料隨機(jī)分配給其他機(jī)器人配送.

貪婪轉(zhuǎn)移(greedy shift，GE)：該鄰域結(jié)構(gòu)依據(jù)貪婪算法的思想，將周期t內(nèi)配送距離最長(zhǎng)的機(jī)器人的配送任務(wù)刪除，并逐個(gè)分配到使機(jī)器人配送距離增加最少的配送計(jì)劃中.

轉(zhuǎn)運(yùn)(optional transfer，OT)：根據(jù)性質(zhì)3選擇Z對(duì)機(jī)器人執(zhí)行轉(zhuǎn)運(yùn)操作.

2.7 計(jì)算復(fù)雜度

VNS-MDDE算法流程如圖3所示.當(dāng)裝配線工位數(shù)、機(jī)器人數(shù)量和生產(chǎn)節(jié)拍分別為|S|，|R|和T時(shí)，算法的時(shí)間復(fù)雜度為O(|S|·|R|·T)；隨著工位數(shù)、生產(chǎn)節(jié)拍數(shù)及待分配機(jī)器人數(shù)量的增加，計(jì)算復(fù)雜度將會(huì)大幅上升.VNS-MDDE基本操作及最壞情況下的復(fù)雜度如下：

① 在一次迭代中從候選解中找出非支配解O(2N)；

② 用非支配排序和擁擠度計(jì)算方法，從數(shù)量為2N的候選解中選取N個(gè)解：O(4N2)+O(2N×lb(2N))；

③ 選取解在鄰域結(jié)構(gòu)中進(jìn)行優(yōu)化，即O(N×Z).

因此，VNS-MDDE算法的復(fù)雜度約為O(4N2)，可見該算法的計(jì)算復(fù)雜度合理，可以有效地得出最優(yōu)解.

3 實(shí)驗(yàn)與分析

為了測(cè)試本文提出的VNS-MDDE算法的性能，在Intel Core i5-7300U，2.71GHz CPU，8GB RAM內(nèi)存的計(jì)算機(jī)上使用MATLAB(2016a)對(duì)該算法進(jìn)行了實(shí)驗(yàn).

3.1 實(shí)驗(yàn)參數(shù)

為了驗(yàn)證算法的有效性，基于文獻(xiàn)[11]中汽車混流裝配線零件進(jìn)料問(wèn)題及線邊超市的相關(guān)實(shí)驗(yàn)參數(shù)構(gòu)建實(shí)驗(yàn)算例.零件需求和工位初始庫(kù)存均依據(jù)均勻分布隨機(jī)生成，分別為[rnduni(0,4) ]和[rnduni(2,4) ]，其中[·]表示四舍五入取整.每個(gè)機(jī)器人的最大載重Fmax為10箱，裝配線的周期時(shí)間t和機(jī)器人在相鄰工位及超市間的行走時(shí)間tw分別為90 s和5 s.

NSGA-II和IBEA的結(jié)構(gòu)和本文算法的結(jié)構(gòu)相似，并具有權(quán)威性且應(yīng)用廣泛，因此將本文提出的VNS-MDDE算法與這兩個(gè)標(biāo)桿算法進(jìn)行比較；此外，本文還將與最新的MOEA/CT算法[12]進(jìn)行比較，該算法在MOEA算法的基礎(chǔ)上提出了坐標(biāo)轉(zhuǎn)換策略、外部檔案更新策略及多樣性維護(hù)策略，以提高帕雷托前沿解集的多樣性和收斂性.算法參數(shù)的設(shè)置如表1所示.

表1 多目標(biāo)算法參數(shù)Table 1 Parameters of multi-objective algorithms

3.2 性能參數(shù)

本文是多目標(biāo)算法，用單一性能指標(biāo)很難較好地評(píng)價(jià)多目標(biāo)算法的性能，因此本文使用下列性能指標(biāo)測(cè)試算法：

①非支配解的數(shù)量：λA=|NA|，其中NA表示算法A中找到的非支配解數(shù)量，非支配解的數(shù)量越多表示決策者選擇范圍越大.

③分布度指標(biāo)：

3.3 算法對(duì)比實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證VNS-MDDE算法的性能，將其與標(biāo)桿算法NSGA-II，IBEA和MOEA/CT算法的測(cè)試結(jié)果進(jìn)行對(duì)比.算例分為大、中、小三個(gè)規(guī)模，針對(duì)每個(gè)算例，各個(gè)算法均獨(dú)立運(yùn)行15次.分別計(jì)算三個(gè)規(guī)模下每個(gè)算法測(cè)試的三個(gè)性能指標(biāo)λA，φA，Δ的平均值，如表2所示.

表2 算法的實(shí)驗(yàn)結(jié)果Table 2 Experiment results of algorithms

根據(jù)表2的實(shí)驗(yàn)結(jié)果，可以得出如下結(jié)論：

①根據(jù)表中λA指標(biāo)值可知，VNS-MDDE算法找出的非支配解數(shù)量遠(yuǎn)多于NSGA-II和IBEA，并且隨著問(wèn)題規(guī)模的增加，它們之間的差距逐漸增大.

②根據(jù)表中φA指標(biāo)值可知， VNS-MDDE找出的解的質(zhì)量遠(yuǎn)優(yōu)于NSGA-II和IBEA.比如在小規(guī)模問(wèn)題中，NSGA-II和IBEA找出的非支配解集中大約有93%的解受到由VNS-MDDE得到的非支配解集中的解支配，而僅有5%的解支配VNS-MDDE算法找到的非支配解集中的解.這可以說(shuō)明VNS-MDDE算法具有更優(yōu)的搜索能力.

③根據(jù)表中Δ指標(biāo)值可以看出，VNS-MDDE算法找出的非支配解的分布度值比其他算法更小，表明VNS-MDDE能進(jìn)行更好的全局搜索.

④ VNS-MDDE算法和MOEA/CT算法在性能上相差不大，MOEA/CT算法在數(shù)量和分布度方面略優(yōu)于本文算法；但是由于VNS-MDDE算法考慮了轉(zhuǎn)運(yùn)策略，而其他算法并無(wú)體現(xiàn)，因此其在尋優(yōu)能力上表現(xiàn)最好.

除了算法運(yùn)行結(jié)果對(duì)比，各算法運(yùn)行時(shí)間對(duì)比如圖4所示，當(dāng)問(wèn)題規(guī)模較小時(shí)(如組別1～6)，4種算法的運(yùn)行時(shí)間都很短，均低于500 s，其中，VNS-MDDE,NSGA-II和IBEA的運(yùn)行時(shí)間基本相等.隨著問(wèn)題規(guī)模的擴(kuò)大，各算法運(yùn)行時(shí)間均有較大的增幅，尤其是MOEA/CT算法；但總體而言，各算法均在可接受的時(shí)間內(nèi)解決機(jī)器人物料配送問(wèn)題，并獲得較優(yōu)解.

以上對(duì)比測(cè)試證明了VNS-MDDE算法的有效性，表明該算法在處理大規(guī)?；炝髌囇b配線物料配送問(wèn)題時(shí)能夠提供滿意解.

3.4 鄰域結(jié)構(gòu)分析

為分析各鄰域結(jié)構(gòu)對(duì)算法的影響，對(duì)|S|=20，T=30規(guī)模的算例進(jìn)行重復(fù)實(shí)驗(yàn)，統(tǒng)計(jì)非支配解數(shù)量，結(jié)果如圖5所示.圖5直觀地展現(xiàn)了各鄰域結(jié)構(gòu)對(duì)算法結(jié)果的影響，可以看出，OT的非支配解值的分布集中，RR次之，RE分布較散；鄰域結(jié)構(gòu)GE和OT均對(duì)非支配解具有優(yōu)化作用，由此可知，轉(zhuǎn)運(yùn)可有效改善機(jī)器人物料配送的能源利用率.

4 結(jié) 語(yǔ)

本文對(duì)混流裝配線線邊集成超市的物料配送問(wèn)題進(jìn)行了研究，并提出了轉(zhuǎn)運(yùn)策略以降低能耗.針對(duì)該組合優(yōu)化問(wèn)題，采用最近鄰啟發(fā)式算法構(gòu)建初始解，并在改進(jìn)型離散差分進(jìn)化算法的基礎(chǔ)上引入變鄰域策略進(jìn)行局部搜索，構(gòu)建了變鄰域搜索策略的改進(jìn)型離散差分進(jìn)化算法(VNS-MDDE).最后，通過(guò)與NSGA-II，IBEA和MOEA/CT算法的對(duì)比驗(yàn)證了本文算法的可行性和優(yōu)越性，該算法可有效地減少送料機(jī)器人的使用數(shù)量并降低能耗.后續(xù)可以對(duì)隨機(jī)交換、隨機(jī)轉(zhuǎn)移、貪婪轉(zhuǎn)移，以及轉(zhuǎn)運(yùn)等鄰域結(jié)構(gòu)進(jìn)行更深入的研究，以提高VNS-MDDE在求解大規(guī)模問(wèn)題時(shí)的效率和效果.