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

徐 進， 張守京， 劉躍強

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

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

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

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

1 模型的建立

1.1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

1.2 數學模型的構建

根據以上描述，針對需要解決的問題，以總成本最低為目標函數構建多車型車間雙向物料配送的模型。

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

2 改進遺傳算法求解模型

2.1 編碼與解碼

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

由4輛3種不同型號的小車執行配送任務的染色體編碼示意圖如圖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 種群初始化

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

初始化步驟如下：

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

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

3) 重復上述步驟直至種群規模達到預定的數量。

2.3 適應度函數

筆者以總成本最小為目標函數，將總成本的倒數作為適應度函數，適應度函數如式(12)所示。

(12)

2.4 選擇操作

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

2.5 改進交叉操作

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

(13)

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

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

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

2.6 改進變異操作

同理，采用動態自適應變異概率，變異概率選擇公式為：

(14)

式中fm為進行變異操作個體的適應度。

如果變異概率Pm過小，不易產生新個體結構；Pm過大，變成純粹的隨機搜索。當沒達到最優解，求解停滯不前的時候，可以適當調整變異概率。當隨機數的值小于變異概率，則進行變異操作。具體變異操作采用多點交換變異，如圖4所示，在進行變異操作的染色前半段隨機選擇2個基因5和1，然后和其對應的后半段3和7進行交換生成新個體。

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

2.7 求解步驟

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

1) 設置參數，初始化種群，計算種群的適應度；

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

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

4) 在進化后期執行自適應交叉變異操作，根據上一代種群進行交叉變異個體的適應度大小選擇不同的交叉變異概率，產生新的個體，重復上述步驟直至迭代結束；

5) 保留最好個體。

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

3 實例仿真實驗與分析

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

表1 車輛參數

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

表2 倉庫及工位信息

3.1 結果對比及分析

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

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

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

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

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

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

表7 多車型遺傳算法求解結果

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

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

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

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

表8 多車型改進遺傳算法求解結果

4 結論

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

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