周炳海 譚芬

摘 要：考慮將電動(dòng)小車用來(lái)進(jìn)行基于廠內(nèi)循環(huán)配送策略的汽車裝配線的物料配送，提出了汽車裝配線電動(dòng)車配送路徑及換電站選址問(wèn)題，以最小化系統(tǒng)總成本為優(yōu)化目標(biāo)建立了數(shù)學(xué)規(guī)劃模型.針對(duì)這一復(fù)雜的混合優(yōu)化問(wèn)題，對(duì)該問(wèn)題的性質(zhì)進(jìn)行了分析，提出了兩階段動(dòng)態(tài)規(guī)劃算法獲取小規(guī)模問(wèn)題的最優(yōu)解；對(duì)于中、大規(guī)模問(wèn)題，通過(guò)種群分割技術(shù)并在Lévy飛行中融入深度鄰域搜索算子構(gòu)建了改進(jìn)型離散布谷鳥(niǎo)算法.最后，進(jìn)行了仿真實(shí)驗(yàn)，分別對(duì)比了兩階段動(dòng)態(tài)規(guī)劃算法，實(shí)數(shù)遺傳算法及改進(jìn)人工蜂群算法在解決該問(wèn)題方面的性能，結(jié)果表明改進(jìn)型離散布谷鳥(niǎo)算法的有效性以及在算法穩(wěn)定性、搜索深度以及收斂性三個(gè)方面的較大優(yōu)勢(shì).

關(guān)鍵詞：廠內(nèi)物料配送；超市；電動(dòng)小車；換電站；Lévy飛行；深度鄰域搜索

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

Abstract：Considering employing the electric vehicles to deliver parts to stations for automotive assembly lines based on inplant milkrun delivery strategy， an electric vehicle delivery routing and battery swap station location problem was presented， and a mathematical programming model with an objective function of minimizing total cost of the system was set up. To tackle this complicated problem， the property was analyzed， and a twophase dynamic programming method was adopted to obtain the global optimum for small scale problems. For medium and large scale problems， both the population decomposition strategy and the depth neighborhood search operator based on Lévy flight were applied to develop an improved discrete cuckoo search algorithm. Finally， through the comparison of the twophase dynamic programming method， real genetic algorithm and modified artificial bee colony algorithm， the simulation experiments were carried out to illustrate the effectiveness and great advantages in stability， deep searching ability and convergence of the algorithm.

Key words： inplant material delivery； supermarket； electric vehicles； battery swap station； Lévy flight； depth neighborhood search

隨著經(jīng)濟(jì)的不斷發(fā)展，能源危機(jī)和環(huán)境污染的問(wèn)題日益凸顯，發(fā)展綠色生產(chǎn)物流成為制造業(yè)發(fā)展的必然趨勢(shì)[1].電動(dòng)小車（Electric Vehicle， EV）由于其清潔、節(jié)能等優(yōu)點(diǎn)逐步被用來(lái)取代傳統(tǒng)燃料小車進(jìn)行廠外“最后一公里”以及廠內(nèi)的物料配送[2].如何采用EV進(jìn)行汽車混流裝配線的物料配送對(duì)制造企業(yè)的節(jié)能減排、降成本增效益具有重要意義.

近年來(lái)，許多國(guó)內(nèi)外學(xué)者對(duì)汽車混流裝配系統(tǒng)中的物料準(zhǔn)時(shí)化配送調(diào)度問(wèn)題進(jìn)行了較深入的研究.Emde等[3]對(duì)基于物料超市的循環(huán)配送問(wèn)題進(jìn)行了建模分析，分別研究了路徑和配送次數(shù)問(wèn)題，并在多項(xiàng)式時(shí)間內(nèi)求解；Fathi等[4]由此構(gòu)建了循環(huán)配送問(wèn)題的多目標(biāo)配送調(diào)度模型，并提出了融合優(yōu)先級(jí)規(guī)則算法以優(yōu)化配送次數(shù)和線邊庫(kù)存.Golz等[5]以德國(guó)某汽車制造商為例，以最小化小車司機(jī)為目標(biāo)研究了其路徑、調(diào)度和裝載問(wèn)題.上述文獻(xiàn)都是考慮傳統(tǒng)小車的物料配送，而EV配送的不同點(diǎn)在于一是節(jié)能減排，二是由于其電量有限、可行駛里程較傳統(tǒng)燃料車較短，需要考慮到電量的補(bǔ)給工作.

而關(guān)于EV配送的電動(dòng)車輛路徑問(wèn)題（Electric Vehicle Routing Problem， EVRP）多是對(duì)廠外物料進(jìn)行配送.Artmeier等[6]第一次引進(jìn)了EV并考慮小車的能耗成本，通過(guò)改進(jìn)經(jīng)典的最短路徑法來(lái)研究“最優(yōu)能耗”路徑；Schneider等[2]提出了帶時(shí)間窗的可充電車輛路徑問(wèn)題，小車采用在客戶點(diǎn)充電方式補(bǔ)給電量.Yang等[7]采用更換電池方式補(bǔ)給電量，隨之而來(lái)的便是換電站（Battery Swap Station， BSS）選址問(wèn)題.目前有兩種充電方式：直接充電和換電池.從效率和成本方面考慮，本文選擇換電池的方式來(lái)補(bǔ)給電量.上述文獻(xiàn)中每個(gè)客戶僅被訪問(wèn)一次，不同于裝配車間需要進(jìn)行多次物料配送.

為此，本文在上述文獻(xiàn)的基礎(chǔ)上，提出了汽車裝配線電動(dòng)車配送路徑優(yōu)化及換電站選址優(yōu)化問(wèn)題，通過(guò)決策EV的配送路徑及BSS位置來(lái)構(gòu)建優(yōu)化模型，提出了兩階段動(dòng)態(tài)規(guī)劃算法和改進(jìn)型離散布谷鳥(niǎo)算法以最小化配送系統(tǒng)的總成本.

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

1.1 問(wèn)題描述

對(duì)于汽車混流裝配車間的工位段S，物料超市負(fù)責(zé)暫存和分揀S所需的物料.考慮到車間突發(fā)情況多，為了使得小車的柔性更高，EV由人員駕駛操作，根據(jù)配送列表將各工位所需的物料在需要的時(shí)間送達(dá)，實(shí)現(xiàn)對(duì)工位段S多頻次、小批量的物料配送.裝配線不允許缺貨，EV的電量不允許降為0，即需在BSS對(duì)小車補(bǔ)給電量.在超市附近有一系列換電站BSSs的備選點(diǎn)，需要決策的就是在備選BSSs中選擇合適的BSS進(jìn)行換電池操作以及EV的配送路徑使得系統(tǒng)的總成本最小.

為有效描述要研究的優(yōu)化問(wèn)題，作如下基本假設(shè)：1）系統(tǒng)選用節(jié)拍時(shí)間作為基本的時(shí)間單位；2）計(jì)劃期內(nèi)的需求已知；3）不考慮EV負(fù)載對(duì)電池耗電量的影響；4） EV采用循環(huán)配送策略進(jìn)行物料配送；5）各EV的配送路線不允許交叉（no overlapping）；6） EV可在各個(gè)備選換電站（Battery Swap Station， BSS）進(jìn)行換電池操作，且在所負(fù)責(zé)工位段進(jìn)行配送時(shí)不允許中斷，即換電池操作只允許在到達(dá)第一個(gè)工位之前或離開(kāi)最后一個(gè)工位之后進(jìn)行；7）每輛EV最多進(jìn)行一次換電池操作.

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

為方便形式化描述，現(xiàn)定義符號(hào)，見(jiàn)表1～表4.

據(jù)上述問(wèn)題描述、模型假設(shè)及符號(hào)定義，對(duì)汽車裝配線電動(dòng)車配送路徑及換電站選址問(wèn)題建模如下：

目標(biāo)函數(shù)（1）表示最小化包括BSS建設(shè)成本、EV使用成本及運(yùn)輸成本的系統(tǒng)總成本；約束（2）～（4）表示每輛EV至少負(fù)責(zé)配送1個(gè)工位并且配送區(qū)域不重復(fù)；約束（5）表示每次配送不能超過(guò)EV的容量；約束（6）表示每輛EV最多進(jìn)行一次換電池操作；約束（7）表示EV到達(dá)某節(jié)點(diǎn)的電量；約束（8）表示EV離開(kāi)某節(jié)點(diǎn)的電量，其中，當(dāng)EV離開(kāi)BSS換完電池后變?yōu)闈M電量；約束（9）表示EV首次從超市出發(fā)的電量為Pk；約束（10）表示EV從超市離開(kāi)的電量等于前一次配送到達(dá)超市的電量；約束（11） ～（12）表示變量的取值范圍.

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

為了進(jìn)一步深入分析問(wèn)題，針對(duì)上述構(gòu)建的優(yōu)化模型，給出了相關(guān)的引理、定理.

2 兩階段動(dòng)態(tài)規(guī)劃算法

由于各小車的配送路線不交叉，配送距離和需求僅與當(dāng)前小車負(fù)責(zé)的配送區(qū)域有關(guān)，因此，提出兩階段動(dòng)態(tài)規(guī)劃法（Twostage Dynamic Programming， TSDP）來(lái)解決該問(wèn)題：第一步確定最優(yōu)工位劃分方案，即解決EV配送路徑的問(wèn)題（Dynamic Programming Routing， DPR）；第二步解決相應(yīng)小車的BSS站點(diǎn)問(wèn)題（Dynamic Programming BSS， DPB）.

2.1 DPR問(wèn)題

3 改進(jìn)型離散布谷鳥(niǎo)算法

布谷鳥(niǎo)搜索算法（Cuckoo Search， CS）是由Yang等[8]在2009年提出的一種新興的啟發(fā)式群體智能優(yōu)化算法.該算法基于布谷鳥(niǎo)寄生育雛的習(xí)性，并結(jié)合一些鳥(niǎo)類和果蠅Lévy飛行的行為.CS算法結(jié)構(gòu)較簡(jiǎn)單、控制參數(shù)較少，且Lévy飛行的高隨機(jī)性增強(qiáng)了算法探索解空間的性能.研究表明CS算法比粒子群算法（PSO）、遺傳算法（GA）以及人工蜂群算法（ABC）等群體智能算法求解效率更高，目前已成功應(yīng)用于多種工程優(yōu)化問(wèn)題的研究.因此，本文針對(duì)研究問(wèn)題的特性提出改進(jìn)型離散型布谷鳥(niǎo)算法（Improved Discrete Cuckoo Search， IDCS）.

本文實(shí)行種群分割技術(shù)，根據(jù)各鳥(niǎo)巢適應(yīng)度的不同將布谷鳥(niǎo)分為三大種群，不同子群體中的鳥(niǎo)巢采用不同的搜索方法，從而保持種群搜索的多樣性.對(duì)前Pd部分的優(yōu)秀布谷鳥(niǎo)NPbest進(jìn)行精英保留策略[9]；對(duì)前Pc部分的較優(yōu)布谷鳥(niǎo)NPbetter在Lévy飛行中融入深度鄰域搜索算子來(lái)獲取新解，提高CS算法局部進(jìn)行精細(xì)搜索的能力，提高收斂速度[10]；另外，對(duì)于種群中Pa部分的較差個(gè)體NPworse采取重建技術(shù)，利用其隨機(jī)擾動(dòng)性引導(dǎo)算法跳出局部最優(yōu).

3.1 鳥(niǎo)巢編碼方式

鳥(niǎo)巢1，…，Npop采用變長(zhǎng)三層混合編碼方式，Npop為鳥(niǎo)巢的數(shù)量，也即種群規(guī)模的大小，編碼長(zhǎng)度表示該優(yōu)化方案所采用的EV總數(shù).編碼的第一層為分區(qū)層，表示各EV負(fù)責(zé)配送區(qū)域的最后一個(gè)工位；編碼的第二、三層為BSS層，第二層表示對(duì)應(yīng)EV換電池的BSS所在備選點(diǎn)，其中0表示不需要換電池；第三層表示EV何時(shí)進(jìn)行換電池操作，1表示EV在離開(kāi)超市后換電池，0表示EV在到達(dá)超市前進(jìn)行換電池.假設(shè)有|S|=12個(gè)工位、|F|=5個(gè)BSS備選點(diǎn)，如圖2所示，給出了兩鳥(niǎo)巢1、2的編碼示意圖.

3.4 基于Lévy飛行的深度鄰域搜索

CS算法運(yùn)用Lévy飛行的高隨機(jī)性來(lái)進(jìn)行全局搜索.標(biāo)準(zhǔn)的CS算法是用來(lái)解決連續(xù)優(yōu)化問(wèn)題，通過(guò)Lévy分布產(chǎn)生隨機(jī)數(shù)來(lái)確定搜索的距離.而在組合優(yōu)化問(wèn)題中，解空間比較復(fù)雜，解之間的距離也不能用數(shù)學(xué)形式很好地去刻畫，因此，離散CS算法需要根據(jù)離散問(wèn)題的特性來(lái)定義搜索的距離.所以，根據(jù)Lévy分布產(chǎn)生的隨機(jī)數(shù)來(lái)確定搜索的步長(zhǎng)或深度[11].在本文提出的IDCS中，在鳥(niǎo)巢之間增加信息交換即交叉操作以加快算法的收斂速度，此外，在Lévy飛行部分嵌入了結(jié)合問(wèn)題特征的深度鄰域搜索算子，提高算法的精細(xì)搜索能力，具體包括：交叉算子（Crossover）、BSS層交換算子（BSSswap）、BSS層插入算子（BSSinsert）、BSS層反轉(zhuǎn)算子（BSSinverse）.

3.4.1 Crossover算子

3.5 重建鳥(niǎo)巢

在標(biāo)準(zhǔn)的CS算法中，n個(gè)巢中有Pa部分將會(huì)被新的鳥(niǎo)巢取代，這些鳥(niǎo)巢由于不夠好，所以很容易被宿主鳥(niǎo)發(fā)現(xiàn)從而無(wú)法保留至下一代.因此，需要重建鳥(niǎo)巢，重建技術(shù)包括變異、合并、拆分算子，使得鳥(niǎo)巢的長(zhǎng)度分別為保持不變，減1，加1，如圖4所示.

由于試驗(yàn)參數(shù)為三因素四水平，因此選用L16（43）的正交表，如表6所示.對(duì)于每種試驗(yàn)方案，IDCS算法運(yùn)行20次，選用其平均值作為評(píng)價(jià)指標(biāo)，試驗(yàn)結(jié)果的統(tǒng)計(jì)分析見(jiàn)表7.

由表7可知，種群規(guī)模Npop對(duì)IDCS算法性能影響最大，Npop值偏大將會(huì)導(dǎo)致較多的計(jì)算時(shí)間，Npop值偏小又會(huì)使得搜索不充分；Pc和Pa值很好地平衡了算法搜索的深度和廣度.

綜上，當(dāng)問(wèn)題規(guī)模S=30時(shí)IDCS算法的參數(shù)設(shè)置如下：種群規(guī)模Npop=120，執(zhí)行基于Lévy飛行的深度鄰域搜索操作的種群比例Pc=0.6，執(zhí)行變異操作的種群比例Pa=0.25.

4.3 算法有效性驗(yàn)證

由于TSDP算法具有指數(shù)級(jí)別的時(shí)間復(fù)雜度，隨著問(wèn)題規(guī)模|S|的擴(kuò)大，所需的計(jì)算時(shí)間急劇增加，故用其來(lái)解決小規(guī)模問(wèn)題.因此，為驗(yàn)證IDCS算法的有效性，首先將其與TSDP算法在小規(guī)模算例下進(jìn)行比較，將計(jì)算時(shí)間設(shè)置為1 200 s，是可接受的TSDP算法運(yùn)行的時(shí)間.針對(duì)每個(gè)算例，IDCS算法運(yùn)行20次，問(wèn)題規(guī)模參數(shù)和測(cè)試結(jié)果如表8所示（符號(hào)”-=”表示TSDP算法無(wú)法在規(guī)定時(shí)間內(nèi)獲取最優(yōu)解或無(wú)法比較）.其中，C*、CPU1為TSDP算法所得的最優(yōu)目標(biāo)函數(shù)值和相應(yīng)的運(yùn)行時(shí)間，、CPU2為IDCS算法運(yùn)行20次的平均值和平均運(yùn)行時(shí)間.

由表8可知，IDCS算法可以有效地解決小規(guī)模問(wèn)題.各算例求得結(jié)果的平均值與TSDP算法求得的最優(yōu)值的絕對(duì)偏差Δ值雖然隨著問(wèn)題規(guī)模的擴(kuò)大而增大，但各算例優(yōu)化結(jié)果的百分比偏差（percentage deviation，PD）[12]在區(qū)間[0，0.23]內(nèi).

為了進(jìn)一步驗(yàn)證本文構(gòu)建的IDCS算法的搜索性能，利用IDCS算法求解中、大規(guī)模算例，并將其與文獻(xiàn)[13]、[14]中的實(shí)數(shù)遺傳算法（RGA）、改進(jìn)人工蜂群算法（MABC）進(jìn)行比較分析，包括不同問(wèn)題規(guī)模下優(yōu)化結(jié)果的百分比偏差PD值以及標(biāo)準(zhǔn)差σ值分析，其中，百分比偏差PD值可以反映算法的搜索深度，標(biāo)準(zhǔn)差σ值反映出了算法的穩(wěn)定性，PD值越大，表明本文構(gòu)建的IDCS算法的搜索深度較其他算法更優(yōu).σ值越小，表明算法的穩(wěn)定性更好.三種算法的優(yōu)化結(jié)果如表9所示.可以很明顯地看出IDCS算法的搜索深度和穩(wěn)定性均優(yōu)于其它兩種算法.

4.4 算法收斂性能分析

此外，本文根據(jù)文獻(xiàn)[15]中提出的解的優(yōu)度（performance ratio，PR）作為算法收斂性能的評(píng)價(jià)指標(biāo).PR=V（H，T，Y）Best（Y），其中V（H，T，Y）表示算法H在迭代T次后對(duì)算例Y的求解結(jié)果，Best（Y）表示對(duì)算例Y求解獲得的參照最優(yōu)值.由于上文已驗(yàn)證的本文構(gòu)建的IDCS算法的有效性，因此，下文將IDCS算法對(duì)算例Y經(jīng)過(guò)1 000次迭代后的結(jié)果作為Best（Y）.PR值能很好地反應(yīng)出算法的收斂性能，其值越小，表明算法的收斂性能越好.圖5給出了問(wèn)題規(guī)模S=50時(shí)迭代次數(shù)對(duì)三種算法的PR值的影響.

5 結(jié) 論

1）提出了汽車裝配線電動(dòng)車配送路徑及換電站選址問(wèn)題，對(duì)企業(yè)的節(jié)能減排、降成本增效益具有重要意義；

2）將該問(wèn)題劃分為兩個(gè)子問(wèn)題，并構(gòu)建了TSDP算法以獲得小規(guī)模問(wèn)題的最優(yōu)解，并證明該算法具有指數(shù)級(jí)別的復(fù)雜度；

3）構(gòu)建IDCS算法求解中、大規(guī)模問(wèn)題，通過(guò)在Lévy飛行中融入深度鄰域搜索算子提高算法精細(xì)搜索的能力；

4）通過(guò)將IDCS算法與TSDP算法在小規(guī)模問(wèn)題下進(jìn)行比較，并與其它算法進(jìn)行對(duì)比，驗(yàn)證其有效性.

參考文獻(xiàn)

[1] 聶凱，謝丹鳳，李巍.新能源汽車城市物流碳排放模型的構(gòu)建與分析[J].湖南大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，42（9）：134-140.

NIE K， XIE D F， LI W. Modeling and analysis of the carbon emission of new energy vehicle in urban logistics industry[J]. Journal of Hunan University（Natural Sciences）， 2015，42（9）：134-140.（In Chinese）

[2] SCHNEIDER M， STENGER A， GOEKE D. The electric vehiclerouting problem with time windows and recharging stations[J]. Transportation Science， 2014， 48（4）： 500-520.

[3] EMDE S， BOYSEN N. Optimally routing and scheduling tow trains for JITsupply of mixedmodel assembly lines[J]. European Journal of Operational Research， 2012， 217（2）： 287-299.

[4] FATHI M， RODRIGUEZ V， ALVAREZ M J. A novel memetic ant colony optimizationbased heuristic algorithm for solving the assembly line part feeding problem[J]. The International Journal of Advanced Manufacturing Technology， 2014， 75（1/4）： 629-643.

[5] GOLZ J， GUJJULA R， GüNTHER H O， et al. Part feeding at highvariant mixedmodel assembly lines[J]. Flexible Services and Manufacturing Journal， 2012， 24（2）： 119-141.

[6] ARTMEIER A， HASELMAYR J， LEUCKER M， et al. The shortest path problem revisited： Optimal routing for electric vehicles[C]//Annual Conference on Artificial Intelligence. Berlin Heidelberg： Springer， 2010： 309-316.

[7] YANG J， SUN H. Battery swap station locationrouting problem with capacitated electric vehicles[J]. Computers & Operations Research， 2015， 55： 217-232.

[8] YANG X S， DEB S. Cuckoo search via Lévy flights[C]//World Congress on Nature & Biologically Inspired Computing. IEEE， 2009： 210-214.

[9] 張 泉，杜亞星，張林峰，等.基于遺傳算法的單U地源熱泵鉆孔內(nèi)熱阻研究[J].湖南大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，41（9）：100-105.

ZHANG Q， DU Y X， ZHANG L F， et al. A study on the heat resistance of single U pipe in the ground source heat pump system based on genetic algorithm[J]. Journal of Hunan University（Natural Sciences）， 2014，41（9）：100-105.（In Chinese）

[10]何禹清， 彭建春， 文明， 等. 基于改進(jìn)遺傳算法的配電網(wǎng)動(dòng)態(tài)無(wú)功優(yōu)化[J]. 湖南大學(xué)學(xué)報(bào)（自然科學(xué)版），2010， 37（3）： 38-43.

HE Y Q， PENG J C， WEN M， et al. Dynamic reactive power optimization method for distribution network based on improved genetic algorithm[J]. Journal of Hunan University（Natural Sciences）， 2010， 37（3）：38-43.（In Chinese）

[11]WANG J， WANG L， SHEN J. A hybrid discrete cuckoo search for distributed permutation flowshop scheduling problem[C]//2016 IEEE Congress on Evolutionary Computation （CEC）. IEEE， 2016： 2240-2246.

[12]SINGH M R， MAHAPATRA S S. A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks[J]. International Journal of Advanced Manufacturing Technology， 2011， 62（1/4）：267-278.

[13]ALNAHHAL M， NOCHE B. A genetic algorithm for supermarket location problem[J]. Assembly Automation， 2015， 35（1）： 122-127.

[14]周炳海， 劉子龍. 考慮衰退的流水車間生產(chǎn)與預(yù)防性維護(hù)集成調(diào)度方法[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2016， 22（5）： 1273-1279.

ZHOU B H， LIU Z L. Integrated scheduling method of production and preventive maintenance in flow shops with degradations[J]. Computer Integrated Manufacturing Systems， 2016，22（5）： 1273-1279. （In Chinese）

[15]QU P， MASON S J. Metaheuristic scheduling of 300mm lots containing multiple orders[J]. IEEE Transactions on Semiconductor Manufacturing， 2005， 18（4）： 633-643.