車間物流問題的布谷鳥算法

廣東工業(yè)大學(xué)自動化學(xué)院 徐澤峰 蔡延光

1 引言

工廠車間普遍采用流水線生產(chǎn)模式。車間物流包括原料物流和工序間物流。

本文將車間物流問題建模為一類車輛路徑問題（VRP，vehicle routing problem）問題。VRP問題可簡單描述為，使用多輛車來為數(shù)個客戶配送貨物，要求規(guī)劃各車輛的路線來使總配送路線最短。VRP是NP難問題，提出至今仍吸引著研究者的目光，不斷為其提出求解效率更高的算法[1-2]。在原始VRP問題的基礎(chǔ)上，一些研究者根據(jù)實(shí)際問題具有的特點(diǎn)提出了新的問題模型。蔡婉君[3]等人研究了周期車輛路徑問題（PVRP，periodic vehicle routing problem），該問題將配送從CVRP中的一個周期擴(kuò)展到多個周期。在每個周期中，由于客戶需求不同，配送路線不同。Erdogan[4]等人提出了綠色車輛路徑問題（GVRP，green vehicle routing problem），該問題研究如何用燃料有限的車輛實(shí)施配送。為了完成長距離的配送，車輛需要在途中補(bǔ)充燃料。

本文提出車間物流問題（WVRP，workshop vehicle routing problem），研究如何規(guī)劃車輛向各工位輸送原料和在各工位間搬運(yùn)待加工產(chǎn)品的路線，以降低流水線生產(chǎn)周期。為WVRP設(shè)計一種布谷鳥算法來求解，并用實(shí)驗來驗證布谷鳥算法的有效性。

2 問題描述

車間內(nèi)有一條流水線。流水線上有n個工位。用一輛車來完成輸送原料和運(yùn)輸待加工產(chǎn)品的任務(wù)。為工位集合。用0表示倉庫。每兩工位或倉庫i和j間的行駛時間為tij。工位i生產(chǎn)一單位產(chǎn)品所需的原料重為qi。一單位待加工產(chǎn)品重為q。車的最大載重為Q。

其中，（1）保證序列$S$中的每個元素對應(yīng)倉庫或工位。（2）表示運(yùn)輸從倉庫開始。（3）表示序列$S$為循環(huán)序列，周期為$L$。（4）表示每個工位的每種訪問在一個周期內(nèi)只有一次。（5）（6）（7）（8）為載重變化的計算方式。（9）為載重的計算方式。（10）為最大載重的計算方式。（11）為裝卸顛倒次數(shù)的計算方式。（12）表示在運(yùn)輸期間車不允許超載。

3 算法設(shè)計

為車間物流問題設(shè)計一種布谷鳥算法來求解。這是一種群體算法。群體中包含NumUnits個個體。算法起始階段，為各個體生成初始解，然后進(jìn)入循環(huán)。在每輪循環(huán)中執(zhí)行如下操作：

（1）隨機(jī)取一個個體a，生成滿足levy分布的隨機(jī)整數(shù)l，對a執(zhí)行l(wèi)次發(fā)散操作，得到個體a1。

（2）隨機(jī)取一個個體b。若a1優(yōu)于b，則用a1替代b。

（3）所有個體執(zhí)行一次局部搜索操作。

（4）更新算法已獲得的最優(yōu)解。

（5）群體中比例為p的最劣個體用生成初始解的方法重新生成。

3.1 生成初始解

采用貪婪插入法來生成初始解。序列中兩個0及它們之間不含0的一段稱為一條線路。解初始時只有一條空線路，即只有首位兩個0，中間沒有其他點(diǎn)。每輪循環(huán)隨機(jī)取一點(diǎn)插入最優(yōu)位置，直到所有點(diǎn)插入完畢。

3.2 發(fā)散操作

引入超載懲罰。在評價解優(yōu)劣時使用的是解的評價值，評價值越低則解越優(yōu)。當(dāng)解為可行時，解的評價值等于其行駛時間。當(dāng)解不可行時，對解中的每一個超載點(diǎn)，將載重超出的量乘以超載懲罰系數(shù)f，加在解的行駛時間上，得到評價值。

發(fā)散操作隨機(jī)取解中的一個點(diǎn)，將其移動到解中隨機(jī)的新位置。發(fā)散操作可能極大地增加解的評價值，但是增強(qiáng)了算法跳出局部最優(yōu)的能力。

3.3 局部搜索操作

采用如下兩個鄰域作為局部搜索鄰域：

（1）移動一個非零點(diǎn)的位置；

（2）交換兩非零點(diǎn)的位置。一次局部搜索操作為取上述兩個鄰域中評價值最低的解，并用它來替代當(dāng)前解。若兩個鄰域中沒有更優(yōu)的解，則當(dāng)前解不變。

4 計算實(shí)驗

隨機(jī)生成算例并用軟件CPLEX來獲得算例的全局最優(yōu)解。CPLEX對較大算例的計算時間很長，故生成的算例規(guī)模較小，工位數(shù)從8到12。用布谷鳥算法對每個算例計算10次，取結(jié)果的平均值，并將其與全局最優(yōu)解對比，結(jié)果如表1所示。

表1

可以看到，布谷鳥算法對所有算例均獲得了全局最優(yōu)解，且求解時間短，求解結(jié)果穩(wěn)定，說明布谷鳥算法對WVRP是有效的。

5 結(jié)論

本文提出了車間物流問題，并設(shè)計了一種布谷鳥算法來求解該問題。實(shí)驗結(jié)果表明，布谷鳥算法對該問題是有效的。

后續(xù)研究可以針對車間物流問題提出求解效率更高的算法。

[1]Teymourian E,Kayvanfar V,Komaki G,etl．Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem[J]．Information Sciences,2016,334-335∶354-378．

[2]Vidal T,Crainic T G,Gendreau M,Prins C．Implicit depot assignments and rotations in vehicle routing heuristics[J]．European Journal of Operational Research,2014,237∶15-28．

[3]蔡婉君,王晨宇,于濱,楊忠振,姚寶珍．改進(jìn)蟻群算法優(yōu)化周期性車輛路徑問題[J]．運(yùn)籌與管理,2014,23(5)∶70-77．

[4]Erdogan S,Miller-Hooks E．A green vehicle routing problem[J]．Transportation Research Part E,2012,48∶100-114．