徐 進(jìn)， 張守京， 劉躍強(qiáng)

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

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

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

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

1 模型的建立

1.1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)以上描述，針對(duì)需要解決的問題，以總成本最低為目標(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ā)車的固定成本、運(yùn)輸成本和時(shí)間懲罰成本的總成本最小的目標(biāo)函數(shù)；式(2)和式(3)為只能取0或1的決策變量；式(4)為進(jìn)行配送車輛運(yùn)輸貨物的容量不超過該型號(hào)車輛的最大容量；式(5)為任意工位的回收量不能超過需求量；式(6)為參與配送的小車數(shù)量要在該車型總數(shù)之下；式(7)為保證每個(gè)工位只能被某車型的某車輛服務(wù)1次；式(8)為小車的起點(diǎn)和終點(diǎn)都是物料中心；式(9)為小車配送至某工位后，必須從該工位離開才能再進(jìn)行下一步移動(dòng)；式(10)為小車要在工位要求的時(shí)間窗內(nèi)送達(dá)；式(11)為時(shí)間懲罰成本函數(shù)，當(dāng)小車到達(dá)工位的時(shí)間在時(shí)間窗外則產(chǎn)生時(shí)間懲罰成本。

2 改進(jìn)遺傳算法求解模型

2.1 編碼與解碼

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

由4輛3種不同型號(hào)的小車執(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 種群初始化

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

初始化步驟如下：

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

2) 從第1個(gè)工位開始給其分配小車，重復(fù)該操作至最后1個(gè)工位，并按照配送的優(yōu)先級(jí)給各車輛配送的工位進(jìn)行重新排序，完成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)度的大小將上一代種群從大到小進(jìn)行排序，從中選擇適應(yīng)度前80%的個(gè)體，將把它們保留至下一代種群。

2.5 改進(jìn)交叉操作

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

(13)

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

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

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

2.6 改進(jìn)變異操作

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

(14)

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

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

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

2.7 求解步驟

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

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

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

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

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

5) 保留最好個(gè)體。

圖5 改進(jìn)遺傳算法求解流程圖Figure 5 Improved genetic algorithm solution flow chart

3 實(shí)例仿真實(shí)驗(yàn)與分析

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

表1 車輛參數(shù)

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

表2 倉庫及工位信息

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

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

表3 單配送單回收與雙向配送對(duì)比

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

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

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

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

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

圖6 遺傳算法求解進(jìn)化趨勢Figure 6 Genetic algorithm for solving evolutionary trends

3.2 遺傳算法改進(jìn)前后對(duì)比分析

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

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

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

4 結(jié)論

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

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