基于改進多目標布谷鳥搜索算法的汽車裝配線物料配送調(diào)度

周炳海，李秀娟

（同濟大學機械與能源工程學院，上海 201804）

以多品種、小批量為特色的混流生產(chǎn)模式使得汽車裝配線所需零部件的種類和數(shù)量顯著增加，因而準時化物料配送調(diào)度對制造型企業(yè)降本增效具有重要意義[1-2].

目前，國內(nèi)外已有許多學者對汽車裝配線物料配送問題進行了較深入的研究.Emde[3]等構(gòu)建了禁忌搜索算法來解決裝配線物料配送系統(tǒng)中的車輛裝載和配送頻率問題.Fathi[4]等采用融合優(yōu)先級規(guī)則的改進粒子群算法解決了裝配線的零件補給問題.Peng[5]等采用一種基于物料超市模式的準時制交貨策略，解決了搬運車輛配送調(diào)度的多目標優(yōu)化問題.Zhou[6]等利用神經(jīng)網(wǎng)絡(luò)解決了裝配線物料配送的動態(tài)調(diào)度問題.文獻[3]和[7]在周期性物料配送的基礎(chǔ)上解決了具有預(yù)定路線的車輛調(diào)度和裝載問題.以上關(guān)于傳統(tǒng)燃料車輛在固定路徑下的物料配送模式往往存在著揀貨復(fù)雜、響應(yīng)速度慢、能耗大以及線邊庫存多等不足.點對點（Point-to-Point，PTP）物料配送模式[8-9]以其靈活性和時效性彌補了傳統(tǒng)配送模式的不足.本文在分析上述文獻的基礎(chǔ)上，研究了電動車輛（Electric Vehicles，EV）點對點物料配送問題，建立準時制物料配送問題的數(shù)學規(guī)劃模型，并提出求解該模型的改進多目標布谷鳥搜索算法.最后，通過仿真實驗驗證了所提出調(diào)度算法的可行性和有效性.

1 問題描述與模型建立

1.1 問題描述

圖1 所示為電動車輛點對點物料配送的示意圖.物料超市的配貨工人根據(jù)各個工位發(fā)出的補貨要求把零件事先分揀好并裝進標準大小的物料箱中.電動配送車輛在物料超市補貨完成后在各個配送任務(wù)的補貨時間窗內(nèi)對需求工位進行物料配送.考慮物料量和行駛距離帶來的電量變化，電動車輛必須在電量不足時返回換電站進行換電.

1.2 數(shù)學模型

為有效描述電動車輛點對點物料配送系統(tǒng)調(diào)度問題，做如下基本假設(shè)：1）電動車輛換電時間已知；2）在執(zhí)行首次配送任務(wù)前，所有車輛均為滿電狀態(tài)；3）車輛的行駛速度處于穩(wěn)定狀態(tài)；4）所有的車輛執(zhí)行配送任務(wù)時均從物料超市出發(fā)并返回物料超市；5）車輛的耗電速率和負載重量、行駛距離成正相關(guān)；6）換電站設(shè)置在物料超市旁邊，不計車輛因換電產(chǎn)生的額外行駛距離；7）線邊卸載物料時間很短，忽略不計.

圖1 裝配線點對點物料供應(yīng)Fig.1 The point-to-point part feeding for assembly lines

為方便描述，定義符號如下：

1）下標表示

K：可用車輛集合；

k：車輛編號，k∈K；

S：配送任務(wù)集合；

s：任務(wù)編號，s∈S；

T：配送行程集合；

t：配送行程序號，t∈T.

2）時間相關(guān)

β：一次換電時間間隔；

δ：小車在物料超市的補貨時長；

Es：任務(wù)s 最早補料時刻；

Ls：任務(wù)s 最晚補料時刻；

3）其他符號

Q：小車的滿電電量；

re：小車空載時的單位距離耗電量；

gs：任務(wù)s 需要配送的物料質(zhì)量；

γ：每增加單位質(zhì)量料箱時單位距離的耗電增量；

V：小車的行駛速度；

dms：配送任務(wù)s 對應(yīng)工作站與物料超市之間的距離；

Skst：小車k 第t 次配送執(zhí)行任務(wù)s 的起始電量；

Rkst：小車k 第t 次配送執(zhí)行完任務(wù)s 后返回物料超市的剩余電量；

fkst：二進制變量，小車k 在執(zhí)行完任務(wù)s 之后去充電為1，否則為0.

4）決策變量

xk：1，小車k 投入使用，否則為0；

ykst：1，小車k 在第t 次配送執(zhí)行任務(wù)s，否則為0.

此外，為了接下來更好地構(gòu)建數(shù)學模型，給出二元階躍函數(shù)的定義如下：

據(jù)上述問題描述、模型假設(shè)及符號定義，并參考文獻[2]和[3]的相關(guān)約束條件的表示方法，對汽車裝配線點對點物料配送調(diào)度問題建模如下：

目標函數(shù)：

其中：

約束如下：

模型中，式（2）～（4）為目標函數(shù)，表示最小化電動車輛數(shù)量以及最長物料搬運時間；式（5）表示每個配送任務(wù)僅被執(zhí)行一次；式（6）表示每輛小車在一次配送行程中只執(zhí)行一個配送任務(wù)；式（7）表示車輛在投入使用后才能執(zhí)行配送任務(wù)；式（8）表示每個配送任務(wù)的首次補料時間；式（9）～（10）表示補料任務(wù)必須在其時間窗內(nèi)完成；式（11）表示每個配送任務(wù)的結(jié)束時間；式（12）～（13）表示車輛每次行程結(jié)束的剩余電量；式（14）表示車輛執(zhí)行每個任務(wù)前的起始電量，這也是連接兩次配送任務(wù)的橋梁；式（15）表示車輛執(zhí)行首次配送任務(wù)前為滿電狀態(tài)；式（16）表示當小車的電量低于10%時返回換電站進行換電，從而減少因過放電對電池造成的損害[10]；式（17）定義了二進制變量.

2 算法構(gòu)建

本文研究的調(diào)度問題屬于NP-hard 問題，群智能算法能有效解決這類難題.布谷鳥搜索算法是Yang 等人提出的一種新型的群智能算法[11]，具有參數(shù)少、收斂性能穩(wěn)定、易于實現(xiàn)等優(yōu)點，已經(jīng)成功應(yīng)用于工程優(yōu)化、資源調(diào)度等領(lǐng)域[12-13].

為了有效地解決汽車裝配線準時化物料補給問題，本文提出一種基于混沌動態(tài)步長的多目標布谷鳥搜索算法.該算法基于混沌模型對搜索步長進行自適應(yīng)調(diào)整，并加入高斯變異和精英選擇策略來提高算法的全局搜索能力和解的質(zhì)量.此外，設(shè)計兩種局部搜索算子強化算法的深度尋優(yōu)能力.

2.1 解的編碼與解碼

采用基于車輛編號的融合編碼機制，將任務(wù)分配方案及其執(zhí)行序列融于同一編碼.如圖2 所示，編碼長度為S，代表任務(wù)總數(shù)，每個配送任務(wù)與一個實數(shù)編碼相對應(yīng)，其中編碼的整數(shù)部分表示負責該工位的車輛編號，小數(shù)部分按照升序排列，表示該車輛的任務(wù)執(zhí)行序列.

圖2 編碼方式Fig.2 Encoding presentation

2.2 任務(wù)分配規(guī)則

為增加初始解的多樣性，任務(wù)分配規(guī)則在公式（12）～（14）的基礎(chǔ)上以減少車輛空閑時間為原則，按照分級概率選擇配送任務(wù)，產(chǎn)生初始解.同時，讓不可行個體參與進化過程，賦予其被選擇的概率，從而利用不可行解所包含的進化信息，分級概率如式（18）所示，其中，ξ 為（0，1）之間的隨機數(shù).

假設(shè)種群規(guī)模為NP，編碼長度為S，可用車輛集合為K，其基本步驟為：

步驟1 初始化車輛編號k∈K，車輛k 的配送任務(wù)集合Jk=?，可執(zhí)行任務(wù)J={1，2，…，S}，車輛k剩余可執(zhí)行任務(wù)=J；

步驟3 生成一個（0，1）之間的隨機數(shù)p，隨機選擇任務(wù)s′∈，通過計算車輛k 執(zhí)行任務(wù)s′的補料時間，根據(jù)式（18）得出選擇概率.若p≤ps′，則選擇當前任務(wù)s′為車輛k 的下一配送任務(wù)，更新En′＞Ls′，n′∈}，Jk=Jk∪{s′}和J=J/{s′}.若繼續(xù)選擇下一任務(wù)，否則，當J ≠? 時，轉(zhuǎn)至步驟4，當J=? 時，轉(zhuǎn)至步驟5；

步驟4 整理車輛k 的任務(wù)集合{Jk}，k=k+1，返回步驟2；

步驟5 整理所有電動車輛的配送任務(wù)為[{J1}{J2}…{Jk}].

2.3 局部搜索機制

為了提高算法的局部搜索能力以適應(yīng)本文的電動車輛點對點物料配送問題，本文針對兩個目標函數(shù)，設(shè)計remove 算子和swap 算子進行目標優(yōu)化.

remove：找出配送次數(shù)最少的車輛k 的任務(wù)執(zhí)行序列Jk，將任務(wù)j∈Jk插入到其他車輛k′的任務(wù)執(zhí)行序列Jk′（Jk′≠?）中.為了減少時間沖突，插入位置為當最后一個任務(wù)從Jk中移除時，車輛k 從當前配送方案中移除.

swap：找到搬運時間最長的車輛k 的任務(wù)執(zhí)行序列Jk，將任務(wù)j∈Jk與其他車輛k′的任務(wù)j′∈Jk′（Jk′≠?）進行交換.為了提高任務(wù)可行性，任務(wù)j′的位置為argmin，交換條件為dmj＞dmj′.

2.4 基于混沌動態(tài)步長的多目標布谷鳥搜索算法

為了避免布谷鳥搜索算法在搜索過程中早熟，搜索步長α 在迭代初期應(yīng)保證足夠大，從而快速找到全局最優(yōu)解.隨著迭代次數(shù)增加，α 值應(yīng)逐步減小，使得算法趨于穩(wěn)定.本文采用Iterative 混沌映射模型函數(shù)對步長遞減系數(shù)進行自適應(yīng)調(diào)整，即

式中：it 表示當前迭代次數(shù)；λit表示第it 次迭代的步長縮減系數(shù)；b 是介于0 和1 之間的常數(shù)；αit表示第it 次迭代的搜索步長.通過自適應(yīng)levy 飛行得到變換后的鳥巢位置，即

引入任務(wù)分配規(guī)則和局部搜索機制以進一步提高算法的尋優(yōu)能力.

步驟1 初始化.結(jié)合任務(wù)分配規(guī)則生成NP 個個體X1，X2，…，XNP.

步驟2 鳥巢更新.對每一鳥巢的位置Xi，根據(jù)式（21）實現(xiàn)鳥巢位置的更新.

步驟3 鳥巢淘汰.根據(jù)發(fā)現(xiàn)概率pa=0.25[14]淘汰當前解后采用隨機游走方式生成相同數(shù)量的新解，即

步驟4 鳥巢擾動.為進一步增強算法的全局開發(fā)能力，采用高斯變異對鳥巢位置進行擾動.給定候選解Xi，擾動公式為

式中：Lbi，j和Ubi，j分別表示第i 個個體第j 個編碼的最小值和最大值，GM（Xi，j，σ）表示由正態(tài)分布產(chǎn)生的一個隨機數(shù)，其均值和標準差分別為Xi，j和σ.

根據(jù)文獻[15]的研究工作，σc=20.

步驟5 解的修復(fù).采用任務(wù)內(nèi)、外轉(zhuǎn)移規(guī)則進行修復(fù).任務(wù)內(nèi)前移：對任意車輛k，按編碼值大小升序排列，按照順序找到違反時間窗約束的任務(wù)kd，進行任務(wù)前移.將其向前轉(zhuǎn)移至與之相鄰的任務(wù)前，計算前kd個任務(wù)是否違反時間窗約束，若仍違反時間窗約束，則繼續(xù)前移動，直至kd移至第一個位置；任務(wù)內(nèi)后移：上述操作后，若解仍不可行，則按相同規(guī)則操作，直至該任務(wù)移至最后一個位置.任務(wù)外移：對剩余違反時間窗約束的任務(wù)重復(fù)操作，將無法通過任務(wù)內(nèi)轉(zhuǎn)移的任務(wù)轉(zhuǎn)移至另外一輛車輛k′.

步驟6 精英選擇.合并父代和子代種群，并對其進行Pareto 非支配排序，為了進一步為提高種群分布質(zhì)量，綜合考慮擁擠距離大小和距離波動，采用波動擁擠距離對個體進行排序，波動擁擠距離大的個體保留至下一代，計算如下：

算法流程圖如圖3 所示.

圖3 算法流程圖Fig.3 Framework of the algorithm

3 仿真實驗分析

3.1 參數(shù)分析

在基于Windows 10 操作系統(tǒng)的Core i5/2.5 GHz內(nèi)存4 GB 的計算機上進行.由于此問題的真實帕累托前沿很難得到，本文在進行實驗時采用以下方法獲得近似帕累托前沿：算法獨立運行多次后記錄每次的帕累托解集，從所有帕累托前沿中獲得新的帕累托解集作為近似前沿.參考文獻[16]的參數(shù)設(shè)置，實驗設(shè)置電池容量Q=100，車輛空載時單位距離耗電率re=0.1，每單位料箱質(zhì)量造成的耗電速率增量γ=0.2，小車速度V=2，工作站到物料超市的距離、時間窗長度和物料質(zhì)量分別在 [20，50]，[20，30]，[10，20] 的均勻分布中隨機生成.為了獲得更高質(zhì)量的解，根據(jù)文獻[17]對算法參數(shù)進行調(diào)優(yōu)，選取不同的參數(shù)組合進行多次實驗.當設(shè)置種群規(guī)模nPop=100，Levy 飛行搜索概率pc=0.8，擾動概率pr=0.4，局部搜索概率pl=0.5 時，算法以較高質(zhì)量求解.

為驗證任務(wù)分配規(guī)則以及局部搜索機制的有效性，將其與未采用任務(wù)分配規(guī)則和局部搜索算子的改進多目標布谷鳥搜索算法（Improved Multi-objective Cuckoo Search，IMCS）進行對比.算法運行時間設(shè)置為300 s，表1 記錄了不同問題規(guī)模下的求解結(jié)果.由表1 可知，結(jié)合任務(wù)分配規(guī)則和局部搜索機制的改進多目標布谷鳥搜索算法（IMCS-Task allocation rule-Local search，IMCS-TL）在對電動車輛進行調(diào)度時，平均車輛數(shù)量和最長搬運時間明顯低于IMCS 算法.對任務(wù)數(shù)為150 的情況進行分析，得到迭代結(jié)束時兩種算法的帕累托前沿，如圖4 所示.從圖中可以看出，IMCS-TL 算法的帕累托前沿能向更優(yōu)解逼近，這是因為IMCS-TL 算法在引入任務(wù)分配規(guī)則和局部搜索算子后，能夠合理地分配任務(wù)和確定任務(wù)執(zhí)行序列，減少車輛閑置時間并提高任務(wù)分配的均衡性.

3.2 數(shù)值分析

為測試本文提出的算法在求解電動車輛點對點物料配送調(diào)度問題時的整體性能，設(shè)計具有代表性的多目標優(yōu)化NSGA-II 和MOPSO 算法在相同運行時間下的對比計算實驗.三種規(guī)模的算法運行時間分別設(shè)置為120 s，240 s 和480 s，以帕累托解的個數(shù)（NF）、非支配解的最優(yōu)度（DPS）、解的均勻性（ES）、反世代距離（IGD）作為評價算法性能的指標，各項評價指標計算如下：

表1 不同問題規(guī)模下的結(jié)果對比Tab.1 Comparison of results between various tasks

圖4 任務(wù)數(shù)量為150 的帕累托前沿Fig.4 Pareto frontier with 150 tasks

3）解的均勻性指標：

式中：Di是xi與其最近鄰域解的歐式距離.ES 越小表示解分布越均勻.

4）反世代距離：

式中：P 為真實帕累托前沿面上的解集，用近似前沿代替；v 表示每個分布在真實帕累托前沿面上的個體；d（v，Q）表示v 與算法得到的解集之間的最小距離.IGD 越小，算法的綜合性能包括收斂性和分布性越好.

每種問題規(guī)模取三種任務(wù)情況進行仿真實驗，每個任務(wù)進行25 次實驗并取計算結(jié)果的平均值，如表2 所示，其中，加粗字體表示不同問題規(guī)模下各項評價指標的最優(yōu)值.對表2 中的計算結(jié)果進行分析可得出以下結(jié)論：

表2 三種算法的數(shù)值結(jié)果對比Tab.2 Numerical calculation results of three algorithms

1）根據(jù)表中的NF 指標值可知，IMCS-TL 算法獲得的非支配解的數(shù)量明顯多于NSGA-II 和MOPSO，并且隨著問題規(guī)模的擴大，它們之間的差距更明顯.

2）根據(jù)表中DPS 指標值可知，IMCS-TL 獲得的解的最優(yōu)度遠高于NSGA-II 和MOPSO，說明IMCSTL 能夠獲得更高質(zhì)量的解，具有更好的搜索能力.

3）根據(jù)表中ES 指標值可知，從解的均勻性來看，IMCS-TL 和NSGA-II 明顯優(yōu)于MOPSO 算法.IMCS-TL 在中大規(guī)模問題下獲得的解集比NSGA-II獲得的解集分布得更加均勻，這是由于IMCS-TL 采用任務(wù)分配策略和局部搜索算子后，IMCS-TL 更容易在當前解附近獲得新的鄰域解，從而提高解集分布的均勻性，算法具有更好的深度尋優(yōu)能力.

4）根據(jù)表中IGD 指標值可知，IMCS-TL 獲得的解的收斂性和分布性明顯優(yōu)于NSGA-II 和MOPSO，這是由于高斯變異和精英選擇策略產(chǎn)生并保留了更高質(zhì)量的解，算法的收斂性和分布性得以提高.

圖5 和圖6 分別以任務(wù)數(shù)為90 和250 的一組數(shù)據(jù)為例，給出了IMCS-TL、NSGA-Ⅱ和MOPSO 三種算法得到的帕累托解集.從圖中可以看出，當問題規(guī)模較小時，IMCS-TL 能獲得比NSGA-II 和MOPSO分布更廣的非支配解集，且解的最優(yōu)度更高.隨著問題規(guī)模的增大，IMCS-TL 算法與另外兩種算法相比優(yōu)勢更加明顯，說明其具有更好的全局搜索能力，可以向更優(yōu)的帕累托前沿逼近.

以上對比測試證明了在相同運行時間下，IMCS-TL 算法能夠找到更多且質(zhì)量更高的帕累托解集，驗證了IMCS-TL 在解決汽車裝配線點對點物料配送調(diào)度問題時的有效性.

圖5 任務(wù)數(shù)為90 的三種對比算法的帕累托前沿Fig.5 Pareto frontier of three algorithms with 90 tasks

圖6 任務(wù)數(shù)為250 的三種對比算法的帕累托前沿Fig.6 Pareto frontier of three algorithms with 250 tasks

4 結(jié)論與展望

1）本文研究了電動車輛點對點物料配送問題，并將原先復(fù)雜的混合優(yōu)化問題轉(zhuǎn)換為決策配送車輛和任務(wù)執(zhí)行序列的組合優(yōu)化問題，為解決汽車裝配線物料配送調(diào)度問題以及電動車輛在廠內(nèi)物流的應(yīng)用提供了新的研究思路.

2）針對該問題設(shè)計了將任務(wù)分配方案和配送序列相結(jié)合的融合編碼機制，并構(gòu)建了基于混沌動態(tài)步長的多目標布谷鳥搜索算法，引入任務(wù)分配規(guī)則、高斯變異和精英選擇策略以提升算法的綜合性能；通過設(shè)計針對該調(diào)度問題的局部搜索算子，提高算法的深度尋優(yōu)能力.實驗驗證了構(gòu)建的調(diào)度算法的有效性.

綜上可知，通過合理安排物料補給作業(yè)能夠?qū)崿F(xiàn)汽車裝配線的準時化物料供應(yīng)，從而保障生產(chǎn)作業(yè)的有序進行.本文著眼于穩(wěn)定生產(chǎn)環(huán)境下的調(diào)度問題，在實際生產(chǎn)環(huán)境中，車輛的故障和物流空間的擁擠等不確定因素將影響配送過程，后續(xù)可以進一步開展帶不確定因素的動態(tài)調(diào)度研究.