考慮多車型的柔性制造車間雙向物料配送路徑優(yōu)化

徐 進， 張守京， 劉躍強

(西安工程大學(xué) 機電工程學(xué)院， 陜西 西安 710600)

隨著柔性制造企業(yè)的不斷發(fā)展，其生產(chǎn)模式正朝著個性化、多品種和小批量演變[1-2]。生產(chǎn)模式組織難度加大，因此生產(chǎn)加工所需的物料應(yīng)當(dāng)及時有效正確地送達(dá)各個工位，除了正向物流，往往還面臨著退單、產(chǎn)成品回收等逆向物流的問題。物料配送環(huán)節(jié)作為車間制造過程的重要組成部分，它的效率高低直接影響著制造過程的生產(chǎn)效率，因此，車間物料配送的研究就顯得格外重要。

車間物料配送路徑優(yōu)化問題是車輛路徑問題(vehicle routing problem，VRP)的一個分支，自1959年Dantzig等[3]提出了VRP至今，國內(nèi)外學(xué)者對其進行了大量的研究。Bouchra等[4]提出了遺傳算法和變鄰域搜索算法相結(jié)合的混合求解方法；Chen等[5]使用改進的蟻群算法和禁忌搜索算法進行求解；涂海寧等[6]提出了一種改進的蟻群算法求解裝配車間送料路徑尋優(yōu)模型；在車間物料配送方面，吳倩云等[7]構(gòu)建了考慮時間窗和裝載約束的最優(yōu)配置模型；黨少杰等[8]以配送路徑最短為目標(biāo)，建立了單任務(wù)和多任務(wù)的物料配送模型；馬磊磊等[9]構(gòu)建了基于模糊時間窗的多目標(biāo)模型，并提出了改進遺傳算法進行求解；在雙向物流車輛路徑問題方面，周蓉等[10]提出了一種自適應(yīng)并行遺傳算法；張守京等[11]提出了一種車間物料配送與余廢料回收協(xié)同的路徑優(yōu)化方法；孫寶鳳等[12]建立了基于實時信息的取送貨動態(tài)車輛路徑模型；NEPOMUCENO等[13]設(shè)計了快速隨機算法來求解車輛異構(gòu)的同時取送貨的車輛路徑問題(vehicle routing problem with simultaneous pick-up and delivery，VRPSPD)；Gong等[14]設(shè)計了一種2階段多目標(biāo)混合算法；馬艷芳等[15]考慮了環(huán)境的不確定性，提出一種基于模糊隨機算子的改進粒子群算法；在多車型車輛配送方面，Jamil等[16]運用螢火蟲算法研究多車型車輛情況下的路徑優(yōu)化問題；Wang等[17]提出一種改進自適應(yīng)遺傳算法，求解城市交通約束下的多種車型車輛路徑優(yōu)化問題；鮑偉等[18]考慮了軟時間窗并引入自適應(yīng)競爭策略證明了使用多車型能有效降低物流成本；劉思遠(yuǎn)等[19]結(jié)合多車型碳排放計算方法提出了一種改進的雙策略種群協(xié)同蟻群算法驗證了模型的有效性；狄衛(wèi)民等[20]提出了一種考慮動態(tài)擁堵的多車型綠色車輛路徑優(yōu)化方法。

筆者在柔性制造車間物料配送研究現(xiàn)狀的基礎(chǔ)上，分析以上文獻(xiàn)發(fā)現(xiàn)柔性制造車間目前存在如下問題：對于車間內(nèi)物料配送的VRP較少有研究考慮車間余廢料的回收，且研究重點多為求解算法的創(chuàng)新與融合；同時，在實際車間物料配送中，往往不只是1種型號的小車參與配送任務(wù)，通常有2種及以上不同的小車共同進行配送，但考慮多車型相關(guān)的研究大多數(shù)為車間外部冷鏈物流。為了提高小車?yán)寐?，有效地降低配送成本，因此在車間物料配送路徑優(yōu)化問題中考慮多種車型及回收顯得很有必要。綜上，筆者提出了一種考慮多車型的車間雙向物料配送路徑優(yōu)化策略，并以配送各成本總和為優(yōu)化目標(biāo)建立相應(yīng)的數(shù)學(xué)模型；同時為了提高遺傳算法進化后期的搜索效率，針對交叉變異概率進行改進；最后通過仿真實驗對模型和算法的可行性及有效性進行驗證。

1 模型的建立

1.1 問題描述

本研究主要是在滿足各個工位對物料數(shù)量不同需求的前提下，將訂單分配給不同型號的各個配送小車，最后小車將分配到的訂單依次對應(yīng)各個工位服務(wù)。在滿足車的載質(zhì)量、數(shù)量等約束下，計算出每個方案的總成本，最后選擇出總成本最低的那個配送方案。每個方案因選擇的車型及小車數(shù)量的配置大不相同，所需的配送總成本也就各不一樣。為了最大程度地節(jié)約成本，因此如何合理安排不同車型及小車數(shù)量進行配送顯得非常重要。

如圖1所示，在確定好方案之后，不同型號的小車從物料倉庫將工位所需的物料分別送至各個工位點，到達(dá)工位點后采取先卸載后裝載的順序直至配送任務(wù)完成，最后將回收的廢料等運到回收倉庫。

圖1 多車型配送示意圖Figure 1 Multi-vehicle distribution map

基于上述問題分析，假設(shè)以下條件成立：

1) 物料中心及各個工位的位置都已知且配送過程中的各個節(jié)點都能通過；

2) 物料中心和各型號的小車數(shù)量已知；

3) 每個工位的需求量及回收量已知，時間窗和最佳配送時間也已知；且各型號小車的最大載質(zhì)量及速度已知且恒定；

4) 每輛車只能對1個工位進行配送，及每個工位的任務(wù)不能拆分成由2輛及以上車輛進行配送；

5) 進行配送任務(wù)的車只能從物料中心出發(fā)，完成配送任務(wù)后返回物料中心；

6) 參與配送的小車任何時間載質(zhì)量不能超過該型號小車的最大載質(zhì)量；

7) 配送時間滿足各工位時間窗，超出時間窗則設(shè)置懲罰；

8) 假設(shè)裝卸無時間及成本消耗。

1.2 數(shù)學(xué)模型的構(gòu)建

根據(jù)以上描述，針對需要解決的問題，以總成本最低為目標(biāo)函數(shù)構(gòu)建多車型車間雙向物料配送的模型。

(1)

?i,j∈N,k∈K,m∈Mk。

(2)

?i∈N,k∈K,m∈Mk。

(3)

(4)

qi-hi≥0,?i∈N。

(5)

(6)

(7)

(8)

(9)

(10)

(11)

式(1)為包括發(fā)車的固定成本、運輸成本和時間懲罰成本的總成本最小的目標(biāo)函數(shù)；式(2)和式(3)為只能取0或1的決策變量；式(4)為進行配送車輛運輸貨物的容量不超過該型號車輛的最大容量；式(5)為任意工位的回收量不能超過需求量；式(6)為參與配送的小車數(shù)量要在該車型總數(shù)之下；式(7)為保證每個工位只能被某車型的某車輛服務(wù)1次；式(8)為小車的起點和終點都是物料中心；式(9)為小車配送至某工位后，必須從該工位離開才能再進行下一步移動；式(10)為小車要在工位要求的時間窗內(nèi)送達(dá)；式(11)為時間懲罰成本函數(shù)，當(dāng)小車到達(dá)工位的時間在時間窗外則產(chǎn)生時間懲罰成本。

2 改進遺傳算法求解模型

2.1 編碼與解碼

在求解的問題中往往不止1輛車1種車型進行配送，為了直觀地展示各小車的配送的任務(wù)，采用自然數(shù)編碼。km為k種型號的第m輛車，101，201和301表示3種不同型號的第1輛小車；1，2，3，…,N表示各個工位。

由4輛3種不同型號的小車執(zhí)行配送任務(wù)的染色體編碼示意圖如圖2所示。車型3的第1輛小車配送工位為6—7；車型1的第1輛小車配送工位為4—2—2*—8；車型1的第2輛小車配送工位為3—1；車型2的第1輛小車配送工位為5。

圖2 編碼示意圖Figure 2 Coding schematic

2.2 種群初始化

在算法正式開始求解之前，先對種群進行初始化操作；將各個工位分配給不同型號的不同小車，并按照優(yōu)先級順序依次進行配送，直至完成任務(wù)。

初始化步驟如下：

1) 隨機生成100條1～N個工位的染色體，將所有工位隨機分布在每條染色體上；

2) 從第1個工位開始給其分配小車，重復(fù)該操作至最后1個工位，并按照配送的優(yōu)先級給各車輛配送的工位進行重新排序，完成1條染色體的任務(wù)分配；

3) 重復(fù)上述步驟直至種群規(guī)模達(dá)到預(yù)定的數(shù)量。

2.3 適應(yīng)度函數(shù)

筆者以總成本最小為目標(biāo)函數(shù)，將總成本的倒數(shù)作為適應(yīng)度函數(shù)，適應(yīng)度函數(shù)如式(12)所示。

(12)

2.4 選擇操作

按照適應(yīng)度的大小將上一代種群從大到小進行排序，從中選擇適應(yīng)度前80%的個體，將把它們保留至下一代種群。

2.5 改進交叉操作

動態(tài)自適應(yīng)適用于進化后期，不適于進化前期，因為前期的優(yōu)秀個體有可能是局部最優(yōu)點，所以在進化前期設(shè)定Pc=0.9,Pm=0.1,恒定;在進化后期，采用動態(tài)自適應(yīng)交叉變異概率。根據(jù)選擇操作保留下的個體適應(yīng)度的不同來選擇不同的交叉變異概率。交叉概率選擇公式為：

(13)

式中：fmax和favg分別為上一代種群適應(yīng)度的最大值與平均值，f為進行交叉操作的2個個體適應(yīng)度的平均值。

當(dāng)種群中個體適應(yīng)度值小于種群平均適應(yīng)度值時，選擇增大交叉概率，加快新個體產(chǎn)生的速度；當(dāng)個體適應(yīng)度值大于種群平均適應(yīng)度值時，減小交叉概率，保留優(yōu)秀個體。選擇好交叉概率之后，進行交叉操作，具體操作如圖3所示，隨機產(chǎn)生2個交叉點1和5，將交叉點及其右側(cè)相鄰的片段依次置于另一個染色體的前端，最后剔除相同的基因，完成交叉。

圖3 交叉操作示意圖Figure 3 Schematic diagram of crossover operation

2.6 改進變異操作

同理，采用動態(tài)自適應(yīng)變異概率，變異概率選擇公式為：

(14)

式中fm為進行變異操作個體的適應(yīng)度。

如果變異概率Pm過小，不易產(chǎn)生新個體結(jié)構(gòu)；Pm過大，變成純粹的隨機搜索。當(dāng)沒達(dá)到最優(yōu)解，求解停滯不前的時候，可以適當(dāng)調(diào)整變異概率。當(dāng)隨機數(shù)的值小于變異概率，則進行變異操作。具體變異操作采用多點交換變異，如圖4所示，在進行變異操作的染色前半段隨機選擇2個基因5和1，然后和其對應(yīng)的后半段3和7進行交換生成新個體。

圖4 變異操作示意圖Figure 4 Schematic diagram of variation operation

2.7 求解步驟

改進遺傳算法流程如圖5所示，具體步驟如下：

1) 設(shè)置參數(shù)，初始化種群，計算種群的適應(yīng)度；

2) 按照初始種群適應(yīng)度的從大到小進行排序，選擇適應(yīng)度好的個體保留下來；

3) 進行交叉變異處理，生成新的個體重復(fù)上述步驟直至迭代次數(shù)為20；

4) 在進化后期執(zhí)行自適應(yīng)交叉變異操作，根據(jù)上一代種群進行交叉變異個體的適應(yīng)度大小選擇不同的交叉變異概率，產(chǎn)生新的個體，重復(fù)上述步驟直至迭代結(jié)束；

5) 保留最好個體。

圖5 改進遺傳算法求解流程圖Figure 5 Improved genetic algorithm solution flow chart

3 實例仿真實驗與分析

選擇某電動車生產(chǎn)車間中A1至A5生產(chǎn)裝配線作為研究對象，共32個工位的信息。用0工位表示物料倉庫，0*表示回收倉庫。以各個工位的最佳配送時間t*作為配送順序的依據(jù)，依次給每個工位進行服務(wù)。算法參數(shù)設(shè)置如下：種群規(guī)模為100，Pc=0.9,Pm=0.1,最大迭代次數(shù)為500，借助MATLAB 2016a進行實例仿真驗證。車輛相關(guān)參數(shù)如表1所示。

表1 車輛參數(shù)

物料倉庫、回收倉庫及各個工位信息如表2所示。

表2 倉庫及工位信息

3.1 結(jié)果對比及分析

如表3所示，在滿足相同的訂單要求下，考慮雙向配送策略的車輛裝載率要比單獨配送與單獨回收之和要高3.68%；在配送總成本方面，更是能減少1 242.8元之多，證明了考慮雙向物料配送策略的可行性及有效性。

表3 單配送單回收與雙向配送對比

表4～6分別為采用遺傳算法的單車型1、單車型2和單車型3的求解結(jié)果。只使用車型1，需要9輛才能完成訂單需求，總成本為3 205.13 元；只使用車型2，需要7輛完成訂單需求，總成本為3 142.46 元；只使用車型3，雖然只需要5輛就能完成訂單需求，但總成本為3 237.42 元。表7為遺傳算法求解多車型配送的結(jié)果，使用多種車型的小車共同進行配送求解結(jié)果總成本只需要2 985.08 元，相比只考慮單一車型所需總成本都要少。如圖6所示，在使用遺傳算法對實例求解的進化曲線中，可以明顯看出考慮多車型的優(yōu)越性，證明了多車型在車間雙向物料配送中的有效性和可行性。

表4 單采用車型1遺傳算法求解結(jié)果

表5 單采用車型2遺傳算法求解結(jié)果

表6 單采用車型3遺傳算法求解結(jié)果

表7 多車型遺傳算法求解結(jié)果

圖6 遺傳算法求解進化趨勢Figure 6 Genetic algorithm for solving evolutionary trends

3.2 遺傳算法改進前后對比分析

在上文的基礎(chǔ)上，進一步對遺傳算法進行了相應(yīng)的改進，表8為多車型在改進遺傳算法下求解的結(jié)果，共需6輛小車進行配送，總成本只需2 881.69 元。改進算法前后的進化曲線對比如圖7所示。采用改進遺傳算法求解方案總成本要較改進前低3.48%，證明了改進遺傳算法的可行性及有效性。

圖7 改進遺傳算法前后求解進化趨勢Figure 7 Solving evolutionary trends before and after improving genetic algorithm

表8 多車型改進遺傳算法求解結(jié)果

4 結(jié)論

筆者針對柔性制造車間出現(xiàn)的物料響應(yīng)不及時、車輛裝載率低等問題，提出了考慮多車型的車間雙向物料配送策略，并以總成本最小為優(yōu)化目標(biāo)構(gòu)建了對應(yīng)的數(shù)學(xué)模型，分別利用遺傳算法與改進遺傳算法進行求解。最后，借助MATLAB對某電動車生產(chǎn)車間進行實例仿真，結(jié)果表明：多車型相比傳統(tǒng)的單一車型更加適合現(xiàn)如今的柔性制造企業(yè)，能夠有效地降低配送成本，還能提高小車的利用率；改進后的遺傳算法與改進前算法求解結(jié)果進行對比，成本降低了103.4 元；相較于單車型3，成本更是降低了355.7元。驗證了改進算法的可行性，表明了自適應(yīng)遺傳算法在解決離散制造車間問題的有效性。

在本研究基礎(chǔ)上，今后將針對多車在配送過程中的動態(tài)交互及物料回收的不確定性進行研究，進一步貼近柔性制造車間的環(huán)境。