張守京，張 儀

(西安工程大學(xué)1.機(jī)電工程學(xué)院；2.西安市現(xiàn)代智能紡織裝備重點(diǎn)實(shí)驗(yàn)室,陜西 西安710048)

激烈的全球化競(jìng)爭(zhēng)以及市場(chǎng)環(huán)境的不可預(yù)測(cè)性迫使離散制造企業(yè)的生產(chǎn)模式向多品種、小批量轉(zhuǎn)變。該生產(chǎn)模式的產(chǎn)品結(jié)構(gòu)較為復(fù)雜，產(chǎn)品物料種類繁多。一方面，物料能否準(zhǔn)確、及時(shí)、高效地送達(dá)工位直接影響到生產(chǎn)能否正常進(jìn)行；另一方面，因訂單變化、加工異常所產(chǎn)生的剩余物料以及殘次品等余-廢料資源處理不及時(shí)、占用生產(chǎn)空間，也在一定程度上影響了企業(yè)生產(chǎn)的順利進(jìn)行。車間工位物料配送、余-廢料資源回收處理均需對(duì)運(yùn)輸小車進(jìn)行調(diào)度以及運(yùn)輸路徑規(guī)劃(vehicle routing problem，VRP)。工位物料配送和余-廢料資源回收協(xié)同優(yōu)化問題在一定程度上與裝卸一體化車輛路徑問題

(vehicle routing problem with simultaneous pickup and delivery，VRPSPD)類似，均需考慮配送和回收需求，即運(yùn)輸小車將物料配送至工位同時(shí)將余-廢料從工位處回收，并滿足工位處物料先卸載后裝載的順序。這能夠有效減少物流資源浪費(fèi)，提高車間運(yùn)輸小車?yán)寐?、降低物流運(yùn)輸成本[1]。

目前，眾多研究學(xué)者對(duì)離散制造車間物料配送VRP問題以及逆向物流中VRPSPD相關(guān)問題進(jìn)行了深入的研究。在物料配送的VRP問題上，文獻(xiàn)[2]針對(duì)車間作業(yè)環(huán)境的不確定性，提出了計(jì)及漂移瓶頸的時(shí)變物料配送路徑優(yōu)化方法，在動(dòng)態(tài)物料配送路徑的優(yōu)化問題上給出了新的解決思路。文獻(xiàn)[3]對(duì)多自動(dòng)導(dǎo)引車物料配送路徑規(guī)劃問題進(jìn)行分析，并將自動(dòng)導(dǎo)引車使用數(shù)目、行駛費(fèi)用和時(shí)間窗偏離費(fèi)用作為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，求解物料配送路徑規(guī)劃問題。文獻(xiàn)[4]以實(shí)時(shí)和多源制造數(shù)據(jù)為基礎(chǔ)，設(shè)計(jì)了車間物料搬運(yùn)的動(dòng)態(tài)優(yōu)化模型，實(shí)現(xiàn)了物料配送的動(dòng)態(tài)優(yōu)化。文獻(xiàn)[5]考慮生產(chǎn)節(jié)拍波動(dòng)引起的物料需求時(shí)間變化，建立了帶模糊軟時(shí)間窗的物料配送路徑優(yōu)化模型，并結(jié)合動(dòng)態(tài)規(guī)劃-模擬退火算法對(duì)模型進(jìn)行求解。VRPSPD[6]最初由Min[7]在1989年提出，解決了在車輛數(shù)確定和車輛負(fù)載能力有限的條件下，1個(gè)中心圖書館與22個(gè)地方圖書館之間圖書發(fā)送與回庫(kù)的問題。文獻(xiàn)[8]在節(jié)點(diǎn)需求小于等于車輛容量的VRPSPD基礎(chǔ)上，引入節(jié)點(diǎn)訪問次數(shù)限制，將節(jié)點(diǎn)需求與車輛容量關(guān)系擴(kuò)展到允許節(jié)點(diǎn)需求大于車輛容量的情形。文獻(xiàn)[9]采用遺傳算法求解VRPSPD問題，并利用Augerat數(shù)據(jù)集進(jìn)行驗(yàn)證，結(jié)果證明該方法具有較好的穩(wěn)定性。文獻(xiàn)[10]以最小化總成本、最小化車輛數(shù)目等為目標(biāo)，采用聯(lián)合進(jìn)化遺傳算法進(jìn)行求解，取得了較好的求解效果。

本文在離散制造車間物料流循環(huán)現(xiàn)狀和上述文獻(xiàn)研究[11]基礎(chǔ)上，分析得出離散制造車間生產(chǎn)過程中存在以下問題。1)工位物料配送不及時(shí)，滿意度較低；2)車間內(nèi)部分生產(chǎn)物流以單向流動(dòng)為主，未形成有效物流閉循環(huán)，例如，物料配送或物料回收過程均存在空車行駛狀態(tài)；3)工位余-廢料資源處理不及時(shí)，資源循環(huán)利用率低并占用一定生產(chǎn)空間。針對(duì)以上問題，結(jié)合車間物料流循環(huán)與VRPSPD相關(guān)研究，本文提出了車間物料再循環(huán)策略。將物料配送和余-廢料資源回收相結(jié)合，實(shí)現(xiàn)車間內(nèi)物料流閉循環(huán)流動(dòng)；并以物料流循環(huán)總成本為優(yōu)化目標(biāo)構(gòu)建數(shù)學(xué)模型，最后借助遺傳算法對(duì)該問題進(jìn)行求解，通過實(shí)例對(duì)模型和算法的有效性、可行性進(jìn)行了驗(yàn)證。

1離散制造車間生產(chǎn)環(huán)境分析

1.1 車間生產(chǎn)環(huán)境布局與物流分析

通過對(duì)離散制造車間內(nèi)部環(huán)境分析[12-13]，構(gòu)建其生產(chǎn)環(huán)境布局。如圖1所示，左側(cè)為3類存儲(chǔ)中心，產(chǎn)品庫(kù)包括半成品庫(kù)和成品庫(kù)；物料庫(kù)包括原材料庫(kù)、零部件庫(kù)、設(shè)備維修備件庫(kù)；余-廢料資源庫(kù)主要存儲(chǔ)車間生產(chǎn)過程中產(chǎn)生的廢料、邊角料、殘次品等。右側(cè)有16個(gè)生產(chǎn)工位，每個(gè)工位均設(shè)有1個(gè)物料緩存區(qū)、1個(gè)產(chǎn)成品放置區(qū)[14]，工位四周為行駛路徑。

圖1車間生產(chǎn)環(huán)境布局Figure 1 Workshop production environment layout

物料流循環(huán)流程以原材料、零部件配送和余-廢料、產(chǎn)成品回收為主[15]，其循環(huán)流程如圖2所示。實(shí)際車間物料流循環(huán)中物料配送和余-廢料、產(chǎn)成品回收過程均采用分階段、單任務(wù)模式，即以物料配送、余-廢料回收分別作為單個(gè)作業(yè)任務(wù)。該模式分工明確、簡(jiǎn)單易行，但同時(shí)易造成運(yùn)輸資源浪費(fèi)、運(yùn)輸成本較高。本文針對(duì)車間生產(chǎn)物流循環(huán)過程整體研究，將物料配送與余-廢料資源回收需求共存的工位作為研究對(duì)象，提出物料配送與余-廢料資源回收協(xié)同優(yōu)化的物料再循環(huán)策略以改變現(xiàn)有車間生產(chǎn)物流模式，實(shí)現(xiàn)車間內(nèi)有效物流閉循環(huán)。

圖2物料流循環(huán)Figure 2 Material flow cycle

1.2考慮余-廢料資源回收的物料再循環(huán)策略

車間內(nèi)余-廢料資源處理步驟如圖3所示。其中，工位余-廢料資源回收方式[16]主要有2種方式。1)定期回收，按照車間余-廢料資源回收計(jì)劃，在一定的時(shí)間周期內(nèi)進(jìn)行回收，但是容易出現(xiàn)余-廢料過多占用工位存儲(chǔ)空間的狀況；2)定量回收，根據(jù)工位余-廢料資源存儲(chǔ)箱容量設(shè)置相應(yīng)警戒線，當(dāng)存儲(chǔ)箱內(nèi)余-廢料資源存儲(chǔ)量達(dá)到警戒線時(shí)進(jìn)行回收。定量回收和定期回收均易造成資源循環(huán)利用率低、運(yùn)輸成本高、占用較多生產(chǎn)空間等問題，影響正常生產(chǎn)。

圖3余-廢料資源處理Figure 3 Disposal of remaining material and abandoned material resources

生產(chǎn)過程中，因車間生產(chǎn)環(huán)境等不確定因素，需要對(duì)工位進(jìn)行實(shí)時(shí)物料補(bǔ)充。同時(shí)，結(jié)合工位余-廢料資源回收不確定性，將物料配送與余-廢料資源回收協(xié)同考慮，構(gòu)成物料配送與余-廢料資源回收協(xié)同優(yōu)化任務(wù)，該任務(wù)執(zhí)行過程如圖4所示。其中，紅色線條表示小車行駛路徑；黃色箭頭表示物料卸載；藍(lán)色箭頭表示余-廢料裝載。任務(wù)規(guī)則如下。

圖4物料配送和余-廢料資源回收路徑規(guī)劃Figure 4 Material distribution and recycling of remaining materials and abandoned material resources path planning

1)各工位處余-廢料回收量不超過運(yùn)輸小車最大裝載量。

2)任務(wù)執(zhí)行過程中，工位物料卸載優(yōu)先于余-廢料資源裝載。

3)工位需求物料不可拆分配送，余-廢料資源可拆分回收。

2問題描述及數(shù)學(xué)模型

2.1問題描述

車間內(nèi)含有裝載量為Q的運(yùn)輸小車K臺(tái)，共有N個(gè)工位需要物料配送，N*個(gè)工位余-廢料資源待回收處理，各工位所需物料和待回收的余-廢料資源數(shù)量、種類等均已知。物料再循環(huán)任務(wù)為運(yùn)輸小車將物料庫(kù)中的物料配送至各工位處并將所配送工位的余-廢料資源回收。運(yùn)輸小車最終將工位余-廢料資源回收至余-廢料資源庫(kù)則任務(wù)完成。該任務(wù)需要滿足以下約束條件。

1)車輛約束。運(yùn)輸小車啟動(dòng)、停止、碰撞、裝卸時(shí)間等忽略不計(jì)，行駛速度恒定；所有小車同時(shí)從物料庫(kù)出發(fā)，完成任務(wù)后返回倉(cāng)庫(kù)；每輛小車可以服務(wù)多個(gè)工位，每個(gè)工位只能由一輛小車服務(wù)。

2)工位約束。每個(gè)工位的物料需求量不超過運(yùn)輸小車的最大裝載量，并且工位優(yōu)先執(zhí)行物料卸載，再執(zhí)行余-廢料裝載。

3)時(shí)間窗約束[17]。如式(1)所示，物料在[RTi,LTi]內(nèi)送達(dá)工位時(shí)，不存在懲罰；在RTi之前到達(dá)工位，懲罰因子為α，α=10；在LTi之后到達(dá)工位，懲罰因子為β，β=30。

2.2模型構(gòu)建

模型參數(shù)如表1所示。

表1模型參數(shù)Table 1 Model parameters

根據(jù)以上論述，車間物料配送和余-廢料資源回收協(xié)同優(yōu)化模型表示為

上述模型中，目標(biāo)函數(shù)為最小化車輛運(yùn)輸總成本，包括運(yùn)輸小車指派成本，運(yùn)輸小車行駛距離成本即物料配送距離成本與余-廢料資源回收距離成本，需求工位時(shí)間窗懲罰成本。式中，i、j=0表示物料庫(kù)或余-廢料資源庫(kù)；u=15，λ=1.5；式(2)為目標(biāo)函數(shù)；式(4)表示工位i處去掉該工位物料需求量后的小車實(shí)際裝載量大于該工位資源回收量時(shí)，小車回收量取該工位實(shí)際資源待回收量，否則，以該工位處小車剩余最大裝載量回收余-廢料資源；式(5)表示有K臺(tái)運(yùn)送車輛從物料庫(kù)出發(fā)；式(6)表示每個(gè)工位只被服務(wù)1次且僅有1輛小車執(zhí)行任務(wù)；式(7)表示滿足工位物料需求量和車輛最大載荷量情況下，運(yùn)輸小車數(shù)量不超過車間內(nèi)最大小車數(shù)量；式(8)表示每輛小車的裝載容量不能超過小車最大載荷量。

3模型求解

本文主要研究車間物料配送和余-廢料資源回收協(xié)同優(yōu)化問題，即在滿足物料配送時(shí)間窗要求前提下，采用物料再循環(huán)策略對(duì)車間工位需求物料進(jìn)行配送，并對(duì)工位余-廢料資源進(jìn)行回收處理，從而優(yōu)化運(yùn)輸小車行駛路徑，并利用遺傳算法進(jìn)行求解，其運(yùn)算流程如圖5所示。

圖5遺傳算法流程Figure 5 Genetic algorithm flow

3.1染色體編碼

在離散制造車間物料配送和余-廢料資源回收、車輛分配、工位物料及余-廢料方案選擇基礎(chǔ)上，采用三層自然數(shù)編碼方式編碼。例如，8個(gè)工位，3個(gè)物料庫(kù)，1個(gè)余-廢料資源庫(kù)和3輛物料小車的運(yùn)輸方案矩陣M表示為

式中，x為工位編號(hào)，其中自然數(shù)表示物料配送的工位；*標(biāo)記的自然數(shù)表示余-廢料資源回收工位；y為物料庫(kù)編號(hào)；z為車輛編號(hào)。工位4、7需要原材料，工位1、3、6需要零部件，工位2、5、8需要半成品部件，工位2、3、5、6、8含有待回收余-廢料資源。車輛1負(fù)責(zé)工位1、5、8的物料配送并將工位1和工位8的余-廢料資源進(jìn)行回收，以此類推；M表示3輛車輛運(yùn)輸任務(wù)，車輛1為0-1-5-5*-8-8*-0，車輛2為0-3-3*-6-6*-7-0，車輛3為0-2-2*-4-0。

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

適應(yīng)度函數(shù)如式(9)所示，以個(gè)體i目標(biāo)值C(i)倒數(shù)作為適應(yīng)度函數(shù)，適應(yīng)度值越大，則目標(biāo)值越小。

3.3 種群初始化

種群規(guī)模為100，交叉概率Pc為0.95，變異概率Pm為0.08。初始種群的生成過程如下。

步驟1根據(jù)需求工位數(shù)量確定第1層染色體基因編號(hào)范圍[1,N1]，根據(jù)車間存儲(chǔ)庫(kù)即物料庫(kù)和余-廢料資源庫(kù)確定第2層染色體基因編號(hào)范圍[1,N2]，根據(jù)工位物料需求量和車輛最大載荷量確定第3層染色體基因編號(hào)范圍[1,N3]。

步驟2滿足第1層基因數(shù)等于最大需求工位數(shù)并且工位基因編號(hào)無重復(fù)情況下，對(duì)每層染色體基因分別生成一個(gè)隨機(jī)數(shù)ri∈[1，Ni]。

步驟3按照工位最佳配送時(shí)間，調(diào)整個(gè)體基因序列，將個(gè)體基因序列進(jìn)行降序排列，每輛小車所能運(yùn)輸?shù)乃泄の淮硪粭l物料配送路徑。

步驟4重復(fù)執(zhí)行上述步驟，直至達(dá)到初始種群規(guī)模。

3.4選擇操作

選擇操作采用精英保留策略和輪盤賭選擇結(jié)合的方法。首先計(jì)算種群中染色體適應(yīng)度值，將上一代種群中的所有個(gè)體按照適應(yīng)度值升序排列，各個(gè)個(gè)體被選擇的機(jī)率與自身適應(yīng)度值成正比，選擇適應(yīng)度值最大的父代個(gè)體直接保留至下一代種群，并對(duì)剩余個(gè)體采用輪盤賭選擇。

3.5交叉操作

交叉操作如圖6所示。首先，隨機(jī)選擇染色體交叉區(qū)域；其次，識(shí)別已選擇的染色體交叉區(qū)域，如果交叉區(qū)域中存在相同的工位基因值，則將其作為交叉操作的父代基因，否則，進(jìn)行下一區(qū)域搜索，直到搜索到相同工位基因值，進(jìn)行交叉操作。交叉后的染色體根據(jù)式(7)和式(8)判斷是否為非可行解，是則重新執(zhí)行交叉操作[18]。

圖6染色體交叉Figure 6 Chromosomal crossover

3.6變異操作

隨機(jī)數(shù)小于變異概率Pm，則進(jìn)行變異操作，變異過程如圖7所示。由于每個(gè)工位需要物料種類和數(shù)量及待回收余-廢料資源是確定的，因此，在保持工位編號(hào)和物料庫(kù)編號(hào)不變的情況下對(duì)車輛的編號(hào)進(jìn)行隨機(jī)變異，產(chǎn)生新的配送方案。同時(shí)，根據(jù)式(7)和式(8)檢測(cè)變異后的染色體是否為非可行解，是則重新對(duì)染色體執(zhí)行變異，直至產(chǎn)生有效染色體。

圖7染色體變異Figure 7 Chromosomal mutation

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

某離散制造車間內(nèi)設(shè)置有物料庫(kù)、余-廢料資源庫(kù)以及16個(gè)生產(chǎn)工位。其中，各工位物料和余-廢料資源清單如表2所示；物料配送中心到各工位以及各工位之間的的距離如表3所示；各工位時(shí)間窗如表4所示。由式(8)以及物料配送總量得出共需要3輛運(yùn)輸小車，小車最大載荷量是100 kg，行駛速度v=1 m/s，算例在Matlab r2014a上運(yùn)算。

表2工位物料及余-廢料清單1)Table 2 Workspace remaining material and abandoned material list

表3工位與配送中心間以及工位間的距離Table 3 Distance between station and distribution center and between station and station m

表4工位時(shí)間窗Table 4 Station time window

在進(jìn)行仿真實(shí)驗(yàn)之前，對(duì)算法中包含的交叉、變異概率類型分析，遺傳算法種群大小為100，迭代次數(shù)為100。在車間均為16工位的情況下，分別對(duì)算法中交叉概率(0.5～0.95)和變異概率(0.01～0.1)的取值范圍進(jìn)行分析，每種類型運(yùn)算20次，結(jié)果如表5所示。根據(jù)表5分析得出，變異概率在0.06～0.1范圍內(nèi)能更快收斂得出最優(yōu)值，交叉概率在0.75～0.95范圍內(nèi)算法運(yùn)算比較充分，獲得最優(yōu)值迭代次數(shù)較小。因此，本文選取交叉概率Pc=0.95，變異概率Pm=0.08。

經(jīng)過求解，算法在50次運(yùn)行實(shí)驗(yàn)中，平均18代出現(xiàn)收斂現(xiàn)象，遺傳算法迭代過程如圖8所示；運(yùn)輸小車行駛路徑如圖9所示；物流總成本為 2 817.5，統(tǒng)計(jì)實(shí)驗(yàn)運(yùn)行50次，最優(yōu)結(jié)果如表6所示。①號(hào)小車配送路徑為0-1-1*-2-2*-3-3*-15-15*-12-12*-16-16*-0；其中，車輛配送時(shí)裝載率為99%和回收時(shí)裝載率為89%；運(yùn)輸時(shí)間為12.40 min。②號(hào)小車運(yùn)輸路徑為0-8-8*-13-13*-5-5*-9-9*-0；其中，車輛配送時(shí)裝載率為88%和回收時(shí)裝載率為81%；運(yùn)輸時(shí)間為10.35 min。③號(hào)小車配送路徑為0-7-7*-10-10*-14-14*-11-11*-4-4*-6-6*-0；其中，車輛配送時(shí)裝載率為91%和回收時(shí)裝載率為84%；運(yùn)輸時(shí)間為11.50 min。

綜上，本文采用車間物料再循環(huán)策略，在滿足工位時(shí)間窗、工位物料需求的同時(shí)實(shí)現(xiàn)了車間余-廢料資源及時(shí)、有效回收。車間物料配送和余-廢料資源回收總運(yùn)輸成本為2 817.5 元；通過與未采用物料再循環(huán)策略車間物料配送與余-廢料資源回收對(duì)比發(fā)現(xiàn)，總運(yùn)輸成本達(dá)到 5 279.8 元，降低了46.6%的運(yùn)輸成本，車輛利用率相比單一運(yùn)輸任務(wù)有所提高并實(shí)現(xiàn)了小車間均衡使用。

5結(jié)束語(yǔ)

本文以離散制造車間生產(chǎn)環(huán)境為研究對(duì)象，對(duì)車間物料流循環(huán)進(jìn)行深入分析，提出了物料配送與余-廢料資源回收協(xié)同優(yōu)化的物料再循環(huán)策略，滿足了車間物料準(zhǔn)確、及時(shí)配送以及余-廢料資源實(shí)時(shí)、有效回收。同時(shí)，降低了車間物料配送和余-廢料資源回收成本，并實(shí)現(xiàn)了生產(chǎn)物流的閉循環(huán)。未來將在物料配送和余-廢料回收過程中車間物流成本總體優(yōu)化的基礎(chǔ)上，對(duì)配送和回收的雙時(shí)間窗優(yōu)化分析，并在啟發(fā)式算法上進(jìn)行相應(yīng)改進(jìn)，實(shí)現(xiàn)生產(chǎn)車間內(nèi)物料配送與回收雙向動(dòng)態(tài)優(yōu)化。

表5交叉、變異概率類型分析Table 5 Chromosomal crossover,mutation probability type analysis

圖8算法迭代過程Figure 8 Algorithm iterative process

圖9車輛行駛路徑Figure 9 Vehicle driving path

表6 進(jìn)化100代最優(yōu)分配結(jié)果Table 6 Optimal distribution results after 100 generations of evolution