汽車裝配線電動車配送路徑及換電站選址優(yōu)化

周炳海 譚芬

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

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

中圖分類號：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)境污染的問題日益凸顯，發(fā)展綠色生產(chǎn)物流成為制造業(yè)發(fā)展的必然趨勢[1].電動小車（Electric Vehicle， EV）由于其清潔、節(jié)能等優(yōu)點逐步被用來取代傳統(tǒng)燃料小車進(jìn)行廠外“最后一公里”以及廠內(nèi)的物料配送[2].如何采用EV進(jìn)行汽車混流裝配線的物料配送對制造企業(yè)的節(jié)能減排、降成本增效益具有重要意義.

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

1.3 問題性質(zhì)

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

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

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

2.1 DPR問題

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

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

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

3.1 鳥巢編碼方式

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

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

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

3.4.1 Crossover算子

3.5 重建鳥巢

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

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

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

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

4.3 算法有效性驗證

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

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

為了進(jìn)一步驗證本文構(gòu)建的IDCS算法的搜索性能，利用IDCS算法求解中、大規(guī)模算例，并將其與文獻(xiàn)[13]、[14]中的實數(shù)遺傳算法（RGA）、改進(jìn)人工蜂群算法（MABC）進(jì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）作為算法收斂性能的評價指標(biāo).PR=V（H，T，Y）Best（Y），其中V（H，T，Y）表示算法H在迭代T次后對算例Y的求解結(jié)果，Best（Y）表示對算例Y求解獲得的參照最優(yōu)值.由于上文已驗證的本文構(gòu)建的IDCS算法的有效性，因此，下文將IDCS算法對算例Y經(jīng)過1 000次迭代后的結(jié)果作為Best（Y）.PR值能很好地反應(yīng)出算法的收斂性能，其值越小，表明算法的收斂性能越好.圖5給出了問題規(guī)模S=50時迭代次數(shù)對三種算法的PR值的影響.

5 結(jié) 論

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

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

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

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

參考文獻(xiàn)

[1] 聶凱，謝丹鳳，李巍.新能源汽車城市物流碳排放模型的構(gòu)建與分析[J].湖南大學(xué)學(xué)報（自然科學(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é)報（自然科學(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)動態(tài)無功優(yōu)化[J]. 湖南大學(xué)學(xué)報（自然科學(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ī)集成制造系統(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.