周炳海,李秀娟
(同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院,上海 201804)
以多品種、小批量為特色的混流生產(chǎn)模式使得汽車裝配線所需零部件的種類和數(shù)量顯著增加,因而準(zhǔn)時(shí)化物料配送調(diào)度對(duì)制造型企業(yè)降本增效具有重要意義[1-2].
目前,國(guó)內(nèi)外已有許多學(xué)者對(duì)汽車裝配線物料配送問題進(jìn)行了較深入的研究.Emde[3]等構(gòu)建了禁忌搜索算法來(lái)解決裝配線物料配送系統(tǒng)中的車輛裝載和配送頻率問題.Fathi[4]等采用融合優(yōu)先級(jí)規(guī)則的改進(jìn)粒子群算法解決了裝配線的零件補(bǔ)給問題.Peng[5]等采用一種基于物料超市模式的準(zhǔn)時(shí)制交貨策略,解決了搬運(yùn)車輛配送調(diào)度的多目標(biāo)優(yōu)化問題.Zhou[6]等利用神經(jīng)網(wǎng)絡(luò)解決了裝配線物料配送的動(dòng)態(tài)調(diào)度問題.文獻(xiàn)[3]和[7]在周期性物料配送的基礎(chǔ)上解決了具有預(yù)定路線的車輛調(diào)度和裝載問題.以上關(guān)于傳統(tǒng)燃料車輛在固定路徑下的物料配送模式往往存在著揀貨復(fù)雜、響應(yīng)速度慢、能耗大以及線邊庫(kù)存多等不足.點(diǎn)對(duì)點(diǎn)(Point-to-Point,PTP)物料配送模式[8-9]以其靈活性和時(shí)效性彌補(bǔ)了傳統(tǒng)配送模式的不足.本文在分析上述文獻(xiàn)的基礎(chǔ)上,研究了電動(dòng)車輛(Electric Vehicles,EV)點(diǎn)對(duì)點(diǎn)物料配送問題,建立準(zhǔn)時(shí)制物料配送問題的數(shù)學(xué)規(guī)劃模型,并提出求解該模型的改進(jìn)多目標(biāo)布谷鳥搜索算法.最后,通過仿真實(shí)驗(yàn)驗(yàn)證了所提出調(diào)度算法的可行性和有效性.
圖1 所示為電動(dòng)車輛點(diǎn)對(duì)點(diǎn)物料配送的示意圖.物料超市的配貨工人根據(jù)各個(gè)工位發(fā)出的補(bǔ)貨要求把零件事先分揀好并裝進(jìn)標(biāo)準(zhǔn)大小的物料箱中.電動(dòng)配送車輛在物料超市補(bǔ)貨完成后在各個(gè)配送任務(wù)的補(bǔ)貨時(shí)間窗內(nèi)對(duì)需求工位進(jìn)行物料配送.考慮物料量和行駛距離帶來(lái)的電量變化,電動(dòng)車輛必須在電量不足時(shí)返回?fù)Q電站進(jìn)行換電.
為有效描述電動(dòng)車輛點(diǎn)對(duì)點(diǎn)物料配送系統(tǒng)調(diào)度問題,做如下基本假設(shè):1)電動(dòng)車輛換電時(shí)間已知;2)在執(zhí)行首次配送任務(wù)前,所有車輛均為滿電狀態(tài);3)車輛的行駛速度處于穩(wěn)定狀態(tài);4)所有的車輛執(zhí)行配送任務(wù)時(shí)均從物料超市出發(fā)并返回物料超市;5)車輛的耗電速率和負(fù)載重量、行駛距離成正相關(guān);6)換電站設(shè)置在物料超市旁邊,不計(jì)車輛因換電產(chǎn)生的額外行駛距離;7)線邊卸載物料時(shí)間很短,忽略不計(jì).
圖1 裝配線點(diǎn)對(duì)點(diǎn)物料供應(yīng)Fig.1 The point-to-point part feeding for assembly lines
為方便描述,定義符號(hào)如下:
1)下標(biāo)表示
K:可用車輛集合;
k:車輛編號(hào),k∈K;
S:配送任務(wù)集合;
s:任務(wù)編號(hào),s∈S;
T:配送行程集合;
t:配送行程序號(hào),t∈T.
2)時(shí)間相關(guān)
β:一次換電時(shí)間間隔;
δ:小車在物料超市的補(bǔ)貨時(shí)長(zhǎng);
Es:任務(wù)s 最早補(bǔ)料時(shí)刻;
Ls:任務(wù)s 最晚補(bǔ)料時(shí)刻;
3)其他符號(hào)
Q:小車的滿電電量;
re:小車空載時(shí)的單位距離耗電量;
gs:任務(wù)s 需要配送的物料質(zhì)量;
γ:每增加單位質(zhì)量料箱時(shí)單位距離的耗電增量;
V:小車的行駛速度;
dms:配送任務(wù)s 對(duì)應(yīng)工作站與物料超市之間的距離;
Skst:小車k 第t 次配送執(zhí)行任務(wù)s 的起始電量;
Rkst:小車k 第t 次配送執(zhí)行完任務(wù)s 后返回物料超市的剩余電量;
fkst:二進(jìn)制變量,小車k 在執(zhí)行完任務(wù)s 之后去充電為1,否則為0.
4)決策變量
xk:1,小車k 投入使用,否則為0;
ykst:1,小車k 在第t 次配送執(zhí)行任務(wù)s,否則為0.
此外,為了接下來(lái)更好地構(gòu)建數(shù)學(xué)模型,給出二元階躍函數(shù)的定義如下:
據(jù)上述問題描述、模型假設(shè)及符號(hào)定義,并參考文獻(xiàn)[2]和[3]的相關(guān)約束條件的表示方法,對(duì)汽車裝配線點(diǎn)對(duì)點(diǎn)物料配送調(diào)度問題建模如下:
目標(biāo)函數(shù):
其中:
約束如下:
模型中,式(2)~(4)為目標(biāo)函數(shù),表示最小化電動(dòng)車輛數(shù)量以及最長(zhǎng)物料搬運(yùn)時(shí)間;式(5)表示每個(gè)配送任務(wù)僅被執(zhí)行一次;式(6)表示每輛小車在一次配送行程中只執(zhí)行一個(gè)配送任務(wù);式(7)表示車輛在投入使用后才能執(zhí)行配送任務(wù);式(8)表示每個(gè)配送任務(wù)的首次補(bǔ)料時(shí)間;式(9)~(10)表示補(bǔ)料任務(wù)必須在其時(shí)間窗內(nèi)完成;式(11)表示每個(gè)配送任務(wù)的結(jié)束時(shí)間;式(12)~(13)表示車輛每次行程結(jié)束的剩余電量;式(14)表示車輛執(zhí)行每個(gè)任務(wù)前的起始電量,這也是連接兩次配送任務(wù)的橋梁;式(15)表示車輛執(zhí)行首次配送任務(wù)前為滿電狀態(tài);式(16)表示當(dāng)小車的電量低于10%時(shí)返回?fù)Q電站進(jìn)行換電,從而減少因過放電對(duì)電池造成的損害[10];式(17)定義了二進(jìn)制變量.
本文研究的調(diào)度問題屬于NP-hard 問題,群智能算法能有效解決這類難題.布谷鳥搜索算法是Yang 等人提出的一種新型的群智能算法[11],具有參數(shù)少、收斂性能穩(wěn)定、易于實(shí)現(xiàn)等優(yōu)點(diǎn),已經(jīng)成功應(yīng)用于工程優(yōu)化、資源調(diào)度等領(lǐng)域[12-13].
為了有效地解決汽車裝配線準(zhǔn)時(shí)化物料補(bǔ)給問題,本文提出一種基于混沌動(dòng)態(tài)步長(zhǎng)的多目標(biāo)布谷鳥搜索算法.該算法基于混沌模型對(duì)搜索步長(zhǎng)進(jìn)行自適應(yīng)調(diào)整,并加入高斯變異和精英選擇策略來(lái)提高算法的全局搜索能力和解的質(zhì)量.此外,設(shè)計(jì)兩種局部搜索算子強(qiáng)化算法的深度尋優(yōu)能力.
采用基于車輛編號(hào)的融合編碼機(jī)制,將任務(wù)分配方案及其執(zhí)行序列融于同一編碼.如圖2 所示,編碼長(zhǎng)度為S,代表任務(wù)總數(shù),每個(gè)配送任務(wù)與一個(gè)實(shí)數(shù)編碼相對(duì)應(yīng),其中編碼的整數(shù)部分表示負(fù)責(zé)該工位的車輛編號(hào),小數(shù)部分按照升序排列,表示該車輛的任務(wù)執(zhí)行序列.
圖2 編碼方式Fig.2 Encoding presentation
為增加初始解的多樣性,任務(wù)分配規(guī)則在公式(12)~(14)的基礎(chǔ)上以減少車輛空閑時(shí)間為原則,按照分級(jí)概率選擇配送任務(wù),產(chǎn)生初始解.同時(shí),讓不可行個(gè)體參與進(jìn)化過程,賦予其被選擇的概率,從而利用不可行解所包含的進(jìn)化信息,分級(jí)概率如式(18)所示,其中,ξ 為(0,1)之間的隨機(jī)數(shù).
假設(shè)種群規(guī)模為NP,編碼長(zhǎng)度為S,可用車輛集合為K,其基本步驟為:
步驟1 初始化車輛編號(hào)k∈K,車輛k 的配送任務(wù)集合Jk=?,可執(zhí)行任務(wù)J={1,2,…,S},車輛k剩余可執(zhí)行任務(wù)=J;
步驟3 生成一個(gè)(0,1)之間的隨機(jī)數(shù)p,隨機(jī)選擇任務(wù)s′∈,通過計(jì)算車輛k 執(zhí)行任務(wù)s′的補(bǔ)料時(shí)間,根據(jù)式(18)得出選擇概率.若p≤ps′,則選擇當(dāng)前任務(wù)s′為車輛k 的下一配送任務(wù),更新En′>Ls′,n′∈},Jk=Jk∪{s′}和J=J/{s′}.若繼續(xù)選擇下一任務(wù),否則,當(dāng)J ≠? 時(shí),轉(zhuǎn)至步驟4,當(dāng)J=? 時(shí),轉(zhuǎn)至步驟5;
步驟4 整理車輛k 的任務(wù)集合{Jk},k=k+1,返回步驟2;
步驟5 整理所有電動(dòng)車輛的配送任務(wù)為[{J1}{J2}…{Jk}].
為了提高算法的局部搜索能力以適應(yīng)本文的電動(dòng)車輛點(diǎn)對(duì)點(diǎn)物料配送問題,本文針對(duì)兩個(gè)目標(biāo)函數(shù),設(shè)計(jì)remove 算子和swap 算子進(jìn)行目標(biāo)優(yōu)化.
remove:找出配送次數(shù)最少的車輛k 的任務(wù)執(zhí)行序列Jk,將任務(wù)j∈Jk插入到其他車輛k′的任務(wù)執(zhí)行序列Jk′(Jk′≠?)中.為了減少時(shí)間沖突,插入位置為當(dāng)最后一個(gè)任務(wù)從Jk中移除時(shí),車輛k 從當(dāng)前配送方案中移除.
swap:找到搬運(yùn)時(shí)間最長(zhǎng)的車輛k 的任務(wù)執(zhí)行序列Jk,將任務(wù)j∈Jk與其他車輛k′的任務(wù)j′∈Jk′(Jk′≠?)進(jìn)行交換.為了提高任務(wù)可行性,任務(wù)j′的位置為argmin,交換條件為dmj>dmj′.
為了避免布谷鳥搜索算法在搜索過程中早熟,搜索步長(zhǎng)α 在迭代初期應(yīng)保證足夠大,從而快速找到全局最優(yōu)解.隨著迭代次數(shù)增加,α 值應(yīng)逐步減小,使得算法趨于穩(wěn)定.本文采用Iterative 混沌映射模型函數(shù)對(duì)步長(zhǎng)遞減系數(shù)進(jìn)行自適應(yīng)調(diào)整,即
式中:it 表示當(dāng)前迭代次數(shù);λit表示第it 次迭代的步長(zhǎng)縮減系數(shù);b 是介于0 和1 之間的常數(shù);αit表示第it 次迭代的搜索步長(zhǎng).通過自適應(yīng)levy 飛行得到變換后的鳥巢位置,即
引入任務(wù)分配規(guī)則和局部搜索機(jī)制以進(jìn)一步提高算法的尋優(yōu)能力.
步驟1 初始化.結(jié)合任務(wù)分配規(guī)則生成NP 個(gè)個(gè)體X1,X2,…,XNP.
步驟2 鳥巢更新.對(duì)每一鳥巢的位置Xi,根據(jù)式(21)實(shí)現(xiàn)鳥巢位置的更新.
步驟3 鳥巢淘汰.根據(jù)發(fā)現(xiàn)概率pa=0.25[14]淘汰當(dāng)前解后采用隨機(jī)游走方式生成相同數(shù)量的新解,即
步驟4 鳥巢擾動(dòng).為進(jìn)一步增強(qiáng)算法的全局開發(fā)能力,采用高斯變異對(duì)鳥巢位置進(jìn)行擾動(dòng).給定候選解Xi,擾動(dòng)公式為
式中:Lbi,j和Ubi,j分別表示第i 個(gè)個(gè)體第j 個(gè)編碼的最小值和最大值,GM(Xi,j,σ)表示由正態(tài)分布產(chǎn)生的一個(gè)隨機(jī)數(shù),其均值和標(biāo)準(zhǔn)差分別為Xi,j和σ.
根據(jù)文獻(xiàn)[15]的研究工作,σc=20.
步驟5 解的修復(fù).采用任務(wù)內(nèi)、外轉(zhuǎn)移規(guī)則進(jìn)行修復(fù).任務(wù)內(nèi)前移:對(duì)任意車輛k,按編碼值大小升序排列,按照順序找到違反時(shí)間窗約束的任務(wù)kd,進(jìn)行任務(wù)前移.將其向前轉(zhuǎn)移至與之相鄰的任務(wù)前,計(jì)算前kd個(gè)任務(wù)是否違反時(shí)間窗約束,若仍違反時(shí)間窗約束,則繼續(xù)前移動(dòng),直至kd移至第一個(gè)位置;任務(wù)內(nèi)后移:上述操作后,若解仍不可行,則按相同規(guī)則操作,直至該任務(wù)移至最后一個(gè)位置.任務(wù)外移:對(duì)剩余違反時(shí)間窗約束的任務(wù)重復(fù)操作,將無(wú)法通過任務(wù)內(nèi)轉(zhuǎn)移的任務(wù)轉(zhuǎn)移至另外一輛車輛k′.
步驟6 精英選擇.合并父代和子代種群,并對(duì)其進(jìn)行Pareto 非支配排序,為了進(jìn)一步為提高種群分布質(zhì)量,綜合考慮擁擠距離大小和距離波動(dòng),采用波動(dòng)擁擠距離對(duì)個(gè)體進(jìn)行排序,波動(dòng)擁擠距離大的個(gè)體保留至下一代,計(jì)算如下:
算法流程圖如圖3 所示.
圖3 算法流程圖Fig.3 Framework of the algorithm
在基于Windows 10 操作系統(tǒng)的Core i5/2.5 GHz內(nèi)存4 GB 的計(jì)算機(jī)上進(jìn)行.由于此問題的真實(shí)帕累托前沿很難得到,本文在進(jìn)行實(shí)驗(yàn)時(shí)采用以下方法獲得近似帕累托前沿:算法獨(dú)立運(yùn)行多次后記錄每次的帕累托解集,從所有帕累托前沿中獲得新的帕累托解集作為近似前沿.參考文獻(xiàn)[16]的參數(shù)設(shè)置,實(shí)驗(yàn)設(shè)置電池容量Q=100,車輛空載時(shí)單位距離耗電率re=0.1,每單位料箱質(zhì)量造成的耗電速率增量γ=0.2,小車速度V=2,工作站到物料超市的距離、時(shí)間窗長(zhǎng)度和物料質(zhì)量分別在 [20,50],[20,30],[10,20] 的均勻分布中隨機(jī)生成.為了獲得更高質(zhì)量的解,根據(jù)文獻(xiàn)[17]對(duì)算法參數(shù)進(jìn)行調(diào)優(yōu),選取不同的參數(shù)組合進(jìn)行多次實(shí)驗(yàn).當(dāng)設(shè)置種群規(guī)模nPop=100,Levy 飛行搜索概率pc=0.8,擾動(dòng)概率pr=0.4,局部搜索概率pl=0.5 時(shí),算法以較高質(zhì)量求解.
為驗(yàn)證任務(wù)分配規(guī)則以及局部搜索機(jī)制的有效性,將其與未采用任務(wù)分配規(guī)則和局部搜索算子的改進(jìn)多目標(biāo)布谷鳥搜索算法(Improved Multi-objective Cuckoo Search,IMCS)進(jìn)行對(duì)比.算法運(yùn)行時(shí)間設(shè)置為300 s,表1 記錄了不同問題規(guī)模下的求解結(jié)果.由表1 可知,結(jié)合任務(wù)分配規(guī)則和局部搜索機(jī)制的改進(jìn)多目標(biāo)布谷鳥搜索算法(IMCS-Task allocation rule-Local search,IMCS-TL)在對(duì)電動(dòng)車輛進(jìn)行調(diào)度時(shí),平均車輛數(shù)量和最長(zhǎng)搬運(yùn)時(shí)間明顯低于IMCS 算法.對(duì)任務(wù)數(shù)為150 的情況進(jìn)行分析,得到迭代結(jié)束時(shí)兩種算法的帕累托前沿,如圖4 所示.從圖中可以看出,IMCS-TL 算法的帕累托前沿能向更優(yōu)解逼近,這是因?yàn)镮MCS-TL 算法在引入任務(wù)分配規(guī)則和局部搜索算子后,能夠合理地分配任務(wù)和確定任務(wù)執(zhí)行序列,減少車輛閑置時(shí)間并提高任務(wù)分配的均衡性.
為測(cè)試本文提出的算法在求解電動(dòng)車輛點(diǎn)對(duì)點(diǎn)物料配送調(diào)度問題時(shí)的整體性能,設(shè)計(jì)具有代表性的多目標(biāo)優(yōu)化NSGA-II 和MOPSO 算法在相同運(yùn)行時(shí)間下的對(duì)比計(jì)算實(shí)驗(yàn).三種規(guī)模的算法運(yùn)行時(shí)間分別設(shè)置為120 s,240 s 和480 s,以帕累托解的個(gè)數(shù)(NF)、非支配解的最優(yōu)度(DPS)、解的均勻性(ES)、反世代距離(IGD)作為評(píng)價(jià)算法性能的指標(biāo),各項(xiàng)評(píng)價(jià)指標(biāo)計(jì)算如下:
表1 不同問題規(guī)模下的結(jié)果對(duì)比Tab.1 Comparison of results between various tasks
圖4 任務(wù)數(shù)量為150 的帕累托前沿Fig.4 Pareto frontier with 150 tasks
3)解的均勻性指標(biāo):
式中:Di是xi與其最近鄰域解的歐式距離.ES 越小表示解分布越均勻.
4)反世代距離:
式中:P 為真實(shí)帕累托前沿面上的解集,用近似前沿代替;v 表示每個(gè)分布在真實(shí)帕累托前沿面上的個(gè)體;d(v,Q)表示v 與算法得到的解集之間的最小距離.IGD 越小,算法的綜合性能包括收斂性和分布性越好.
每種問題規(guī)模取三種任務(wù)情況進(jìn)行仿真實(shí)驗(yàn),每個(gè)任務(wù)進(jìn)行25 次實(shí)驗(yàn)并取計(jì)算結(jié)果的平均值,如表2 所示,其中,加粗字體表示不同問題規(guī)模下各項(xiàng)評(píng)價(jià)指標(biāo)的最優(yōu)值.對(duì)表2 中的計(jì)算結(jié)果進(jìn)行分析可得出以下結(jié)論:
表2 三種算法的數(shù)值結(jié)果對(duì)比Tab.2 Numerical calculation results of three algorithms
1)根據(jù)表中的NF 指標(biāo)值可知,IMCS-TL 算法獲得的非支配解的數(shù)量明顯多于NSGA-II 和MOPSO,并且隨著問題規(guī)模的擴(kuò)大,它們之間的差距更明顯.
2)根據(jù)表中DPS 指標(biāo)值可知,IMCS-TL 獲得的解的最優(yōu)度遠(yuǎn)高于NSGA-II 和MOPSO,說(shuō)明IMCSTL 能夠獲得更高質(zhì)量的解,具有更好的搜索能力.
3)根據(jù)表中ES 指標(biāo)值可知,從解的均勻性來(lái)看,IMCS-TL 和NSGA-II 明顯優(yōu)于MOPSO 算法.IMCS-TL 在中大規(guī)模問題下獲得的解集比NSGA-II獲得的解集分布得更加均勻,這是由于IMCS-TL 采用任務(wù)分配策略和局部搜索算子后,IMCS-TL 更容易在當(dāng)前解附近獲得新的鄰域解,從而提高解集分布的均勻性,算法具有更好的深度尋優(yōu)能力.
4)根據(jù)表中IGD 指標(biāo)值可知,IMCS-TL 獲得的解的收斂性和分布性明顯優(yōu)于NSGA-II 和MOPSO,這是由于高斯變異和精英選擇策略產(chǎn)生并保留了更高質(zhì)量的解,算法的收斂性和分布性得以提高.
圖5 和圖6 分別以任務(wù)數(shù)為90 和250 的一組數(shù)據(jù)為例,給出了IMCS-TL、NSGA-Ⅱ和MOPSO 三種算法得到的帕累托解集.從圖中可以看出,當(dāng)問題規(guī)模較小時(shí),IMCS-TL 能獲得比NSGA-II 和MOPSO分布更廣的非支配解集,且解的最優(yōu)度更高.隨著問題規(guī)模的增大,IMCS-TL 算法與另外兩種算法相比優(yōu)勢(shì)更加明顯,說(shuō)明其具有更好的全局搜索能力,可以向更優(yōu)的帕累托前沿逼近.
以上對(duì)比測(cè)試證明了在相同運(yùn)行時(shí)間下,IMCS-TL 算法能夠找到更多且質(zhì)量更高的帕累托解集,驗(yàn)證了IMCS-TL 在解決汽車裝配線點(diǎn)對(duì)點(diǎn)物料配送調(diào)度問題時(shí)的有效性.
圖5 任務(wù)數(shù)為90 的三種對(duì)比算法的帕累托前沿Fig.5 Pareto frontier of three algorithms with 90 tasks
圖6 任務(wù)數(shù)為250 的三種對(duì)比算法的帕累托前沿Fig.6 Pareto frontier of three algorithms with 250 tasks
1)本文研究了電動(dòng)車輛點(diǎn)對(duì)點(diǎn)物料配送問題,并將原先復(fù)雜的混合優(yōu)化問題轉(zhuǎn)換為決策配送車輛和任務(wù)執(zhí)行序列的組合優(yōu)化問題,為解決汽車裝配線物料配送調(diào)度問題以及電動(dòng)車輛在廠內(nèi)物流的應(yīng)用提供了新的研究思路.
2)針對(duì)該問題設(shè)計(jì)了將任務(wù)分配方案和配送序列相結(jié)合的融合編碼機(jī)制,并構(gòu)建了基于混沌動(dòng)態(tài)步長(zhǎng)的多目標(biāo)布谷鳥搜索算法,引入任務(wù)分配規(guī)則、高斯變異和精英選擇策略以提升算法的綜合性能;通過設(shè)計(jì)針對(duì)該調(diào)度問題的局部搜索算子,提高算法的深度尋優(yōu)能力.實(shí)驗(yàn)驗(yàn)證了構(gòu)建的調(diào)度算法的有效性.
綜上可知,通過合理安排物料補(bǔ)給作業(yè)能夠?qū)崿F(xiàn)汽車裝配線的準(zhǔn)時(shí)化物料供應(yīng),從而保障生產(chǎn)作業(yè)的有序進(jìn)行.本文著眼于穩(wěn)定生產(chǎn)環(huán)境下的調(diào)度問題,在實(shí)際生產(chǎn)環(huán)境中,車輛的故障和物流空間的擁擠等不確定因素將影響配送過程,后續(xù)可以進(jìn)一步開展帶不確定因素的動(dòng)態(tài)調(diào)度研究.