基于模糊時間窗的再制造裝配車間物料配送研究*

張銘鑫，陳鴻海

(合肥工業(yè)大學(xué) 機械與汽車工程學(xué)院,合肥　230009)

?

基于模糊時間窗的再制造裝配車間物料配送研究*

張銘鑫，陳鴻海

(合肥工業(yè)大學(xué) 機械與汽車工程學(xué)院,合肥230009)

針對再制造裝配工位物料需求種類、時間的不確定性問題，提出基于模糊時間窗的再制造裝配車間物料配送路徑優(yōu)化方法。在對再制造裝配車間物料配送特點研究的基礎(chǔ)上，綜合考慮再制造倉庫物料種類分類(再制造件庫、再利用件庫和新品庫)和后續(xù)裝配成本的需求，在滿足生產(chǎn)線平衡條件下，以工位滿意度為約束條件，以最小配送成本為目標，建立帶模糊時間窗的物料配送路徑優(yōu)化模型，并通過云遺傳算法對模型進行求解，利用云模型云滴的隨機性和穩(wěn)定性的優(yōu)點，設(shè)計動態(tài)的交叉和變異概率，提高算法的搜索效率。最后，通過實例驗證了模型和算法的有效性。

再制造；物料配送；云遺傳算法；模糊時間窗

0　引言

再制造是將可利用廢舊品經(jīng)過分類拆解、清洗檢查、修復(fù)加工、重新裝配和調(diào)整檢測等工序，恢復(fù)到“新品”狀態(tài)的過程[1]。與傳統(tǒng)制造的過程相比，再制造過程存在著大量的不確定性因素[2]，主要表現(xiàn)為回收件數(shù)量、質(zhì)量和時間的不確定性。再制造裝配過程中使用的零部件不僅包括新品零部件、還有再利用件和再制造件，因此再制造車間中的物料倉庫也統(tǒng)分為三類：新品庫、再利用件庫和再制造件庫。新品庫中的物料是由外部采購來補充，因此可以隨時供需車間物料需求；再利用件庫中物料是由廢舊件經(jīng)過拆卸直接回收利用，因此其局限于一定的數(shù)量；再制造件庫中的物料是由廢舊品經(jīng)過不同的修復(fù)工序后到達“新品”質(zhì)量要求時，補充進來的，因此由于受到再制造件的修復(fù)率和修復(fù)時間的波動影響，再制造件庫的物料量呈隨機分布的狀態(tài)。再制造庫存零部件種類和數(shù)量的不確定性導(dǎo)致再制造車間物料配送問題比起一般的物流車輛路徑規(guī)劃問題(Vehicle Routing Problem,VRP)更復(fù)雜。VRP是近幾十年來運籌規(guī)劃領(lǐng)域研究熱點之一。目前，有關(guān)VRP問題的研究，已有大量文獻。蔣麗等[3]提出一種以工位為中心的生產(chǎn)物流配送思想，建立車間配送優(yōu)化調(diào)度模型，并用遺傳算法求解該模型。李晉航等[4]在考慮作業(yè)車間內(nèi)工位物料需求信息、運輸時間和時間窗信息不確定性基礎(chǔ)上，建立了模糊信息條件下以最小化運輸距離為目標的機會約束物料配送車輛規(guī)劃模型并采用改進的混合智能算法求解。Muller等[5]應(yīng)用遺傳模擬退火算法和兩階段啟發(fā)式算法相結(jié)合，求解帶時間窗的車輛調(diào)度問題，并取得了一定效果。Repoussis P.P.等[6]利用混合智能算法求解開放式物料配送路徑問題，并結(jié)合實例驗證了模型和算法的可行性。Thibaut Vidal等[7]針對多屬性車輛路徑問題，提出一個基于組件的啟發(fā)式框架。Martin Reed等[8]針對多級車輛路徑問題，提出一種蟻群擴展算法，通過k-means聚類預(yù)處理大大減少了計算時間，提高算法求解效率。

綜上所述，目前的VRP問題研究文獻主要面向于傳統(tǒng)制造車間的物流路徑優(yōu)化問題。再制造裝配車間由于物料到達的類型和時間的不確定性所引起的裝配方案是不同的。再制造車間的物料配送問題，不僅要考慮車輛路徑優(yōu)化問題，同時還要兼顧由于物料種類不同而引起的后續(xù)裝配工位的物料成本問題。

本文在借鑒相關(guān)文獻研究成果的基礎(chǔ)上，結(jié)合再制造裝配車間物料配送的情況，提出基于模糊時間窗的再制造車間物料配送方法，以工位滿意度來表征工位物料類型所引起的物料成本的變化，在考慮后續(xù)裝配成本的前提下，優(yōu)化物料配送方案。

1　再制造裝配車間物料配送模型構(gòu)建

1.1模糊時間窗

由于再制造裝配過程中，新品件、再利用件和再制造件在誤差、成本、質(zhì)量和數(shù)量等方面的差異，導(dǎo)致裝配方案呈現(xiàn)多樣化特點。裝配工位的零部件種類的不確定性導(dǎo)致工位的物料需求時間也在一定范圍內(nèi)波動。對于再制造車間而言，相對來說，新品件的采購成本大，再制造件修復(fù)成本次之，再利用件拆卸成本最小，因此，為了降低產(chǎn)品最終成本，裝配車間希望在滿足交貨期的前提下，盡量使用再利用件和再制造件，最后考慮新品件。按照生產(chǎn)計劃節(jié)拍，物料在時間窗[ta,tb]內(nèi)到達，優(yōu)先配送再利用件或再制造件，盡量避免配送新品件。因此，本文采用模糊時間窗來描述物料到達的時間的不確定性，利用模糊時間窗的隸屬度函數(shù)來表征不同的物料類型在時間窗[ta,tb]內(nèi)到達時對后續(xù)裝配成本的影響。

圖1　模糊時間窗

模糊時間窗[9]是一種反映顧客偏好的時間窗，可以表示為時間t的凸函數(shù)，如圖1所示。ta和tb分別表示工位i對所需物料到達時間的最早限制和最晚限制，tm表示物料在該時間點到達時，工位滿意度為1。離該時間點越遠，工位的滿意度就越低。為了保證生產(chǎn)計劃的正常執(zhí)行，物料到達時間落在[ta,tb]之外，工位滿意度為0。同時為了區(qū)分不同的物料類型到達時，對工位滿意度的影響，本文采用冪函數(shù)來表征隸屬度函數(shù)，如式(1)所示。

(1)

1.2模型構(gòu)建

(1)問題描述

再制造裝配車間物料配送車輛路徑優(yōu)化問題一般描述為：一個物料倉庫有M個物料庫位(其中再制造件有m1個庫位，再利用件有m2個庫位，新品件有m3個庫位，M=m1+m2+m3)，擁有K輛物料小車(一次配送容量為q)，負責(zé)對裝配線N個工位進行物料配送，工位i的物料需求量為gi(gi

(2)假設(shè)條件

①配送開始時，物料小車從物料倉庫出發(fā)(其初始位置為0)，到達指定配送工位，再返回物料倉庫，一個配送循環(huán)結(jié)束。

②每個工位只能由一輛物料小車配送物料。

③工位所需物料和不能超過物料倉庫的總的存儲量。

④物料小車不能超過其最大行駛距離。

⑤忽略物料小車初始出發(fā)時間。

(3)變量

M：物料配送中心M=1+2+…+m，N：裝配線工位集合N=1+2+…+n，K：物料小車集合K=1+2+…+k，cij：物料庫位j到工位i的滿載運輸成本，c’ij：工位i到物料庫位j的空載運輸成本，dij：工位i到物料庫位j的距離，ti：物料小車k到達工位i的時間，α：表示車間工位滿意度的最小值。

xik=1表示工位i由物料小車k配送，否則xik=0；

yij=1表示工位i的物料由物料庫位j供應(yīng)，否則yij=0；

xijk=1表示物料小車k由第i個工位回到物料倉庫，再由物料倉庫到第j個工位配送，否則xijk=0；

(4)配送模型

(2)

模型中，式(2)是以配送成本最小為目標函數(shù)；式(3)保證工位配送時間不超過模糊時間窗；式(4)保證每個工位所需物料一次只能由一個物料庫位配送；式(5)保證每個工位一次只能由一輛配送小車配送；式(6)和(7)保證每個工位都被服務(wù)到，且保證一個工位只能由一個物料庫位為其服務(wù)；式(8)保證工位滿意度大于設(shè)定值。

2　模型求解

再制造車間物料配送問題是一種復(fù)雜的組合優(yōu)化問題。遺傳算法是求解組合優(yōu)化問題的一類高效并行全局搜索算法。

2.1云遺傳算法

傳統(tǒng)的遺傳算法采用固定的概率進行交叉和變異操作，存在著早熟收斂和易于陷入局部最優(yōu)的缺點，影響算法的求解效率。因此，在遺傳算法進化搜索過程中動態(tài)調(diào)整交叉和變異概率成為遺傳算法進化的方向。在遺傳算法中引入云模型理論[10]，利用云模型云滴的隨機性和穩(wěn)定性的優(yōu)點，由云模型的X條件云發(fā)生器來控制遺傳算法進化搜索過程中的交叉和變異概率的自適應(yīng)過程，在確保最大適應(yīng)度周圍的優(yōu)秀個體維持正態(tài)云模型穩(wěn)定傾向性的同時，提高適應(yīng)度較低個體的搜索能力，提高了算法在搜索精度和范圍上的準確性。交叉概率Pc和變異概率Pm的自適應(yīng)公式以及云遺傳算法流程圖如下所示。

(1)自適應(yīng)交叉概率Pc的算法：

He= En/C2

(2)自適應(yīng)變異概率Pm的算法：

Ex= f

He= En/C4

(3)云遺傳算法流程圖如圖2所示。

圖2　云遺傳算法流程圖

2.2編碼

一般的VRP問題都采用一維自然數(shù)編碼方式。由于再制造車間物料配送問題涉及車輛分配和工位用料方案的選擇，因此本文采用二維自然數(shù)編碼方式。例如6個工位，3類物料倉庫和2輛物料小車的配送方案矩陣M表示：

式中：x為工位編號，y為物料倉庫編號，z為車輛編號。工位1、2采用再利用件庫3的物料，工位3、4、5采用再制造件庫2的物料，工位6采用新品件庫的物料；物料小車1負責(zé)工位1、2、5的物料配送，物料小車2負責(zé)工位3、4、6的物料配送。

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

適應(yīng)度函數(shù)是算法中評價個體優(yōu)劣的函數(shù)，用于指導(dǎo)算法中進化的搜索方向，適應(yīng)度值高的個體優(yōu)先遺傳到下一代種群中。對于某配送矩陣，在滿足約束條件的基礎(chǔ)上，除了其配送成本越小越好以外，還希望其工位滿意度越大越好。因此其適應(yīng)度函數(shù)由目標函數(shù)和工位.滿意度函數(shù)轉(zhuǎn)化而成fi：

2.4選擇操作

本文采用保留最佳個體和輪盤賭相結(jié)合的方式生成下一代種群。將上一代種群中的個體按適應(yīng)度值從大到小排列，選擇最優(yōu)的父代個體，直接進入下一代種群；剩下的個體采用輪盤賭的方式生成。該方法既能避免有效基因的損失，又能使高適應(yīng)度值的個體以更大的概括生存，從而提高算法的全局收斂性和計算效率。

2.5交叉操作

對于選擇操作得到的種群，由云模型X條件發(fā)生器算法根據(jù)適應(yīng)度來生成概率Pc，隨機選取兩個父代對應(yīng)基因段位置進行交叉操作。

2.6變異操作

為了維持種群的多樣性，由云模型X條件發(fā)生器算法根據(jù)適應(yīng)度生成概率Pm，進行變異操作。隨機選取兩個父代基因段，保持工位編號順序不變的情況下，對配送中心編號和車輛編號進行變異，產(chǎn)生新的配送方案。

3　實例驗證

以某再制造主減速器主錐總成裝配線為例，該裝配線共有8個工位、3類物料倉庫(m1為新品庫、m2為再制造件庫、m3為再利用件庫)、由兩臺物料小車負責(zé)配送物料，物料倉庫到各工位的距離如表1所示，為簡化計算，本文通過距離來表征運輸成本，物料小車的滿載成本是運輸距離的1.5倍，空載成本是運輸距離的1.0倍，車間要求工位滿意度α≥0.6，各工位模糊時間窗如表2所示。

表1　物料倉庫到各工位的距離

表2　各工位的模糊時間窗

本實例是在MatlabR2009上實現(xiàn)云遺傳算法，設(shè)種群規(guī)模為50，最大迭代次數(shù)為50，C1=C3=3.0，C2=C4=10，k1=k3=1.0，k2=k4=0.5，計算結(jié)果如表3所示，最優(yōu)配送路徑如表4所示。

由表3和表4可知，兩輛物料小車經(jīng)過45.2min完成了一次物料配送，在滿足車間工位滿意度的前提下(0.65>0.6)，最小的配送成本為1930單位，裝配工位優(yōu)先采用再利用件庫和再制造件庫的物料，為了不影響生產(chǎn)節(jié)拍，s5和s8工位采用再新品件庫物料。

表3　計算結(jié)果

表4　最優(yōu)配送路徑

4　結(jié)論

針對再制造車間物料配送的復(fù)雜性，通過模糊時間窗來表征再制造車間物料需求的波動性，通過工位滿意度來表征物料類型對后續(xù)裝配成本的影響，在此基礎(chǔ)上，構(gòu)建了再制造裝配車間的物料配送模型。針對遺傳算法存在的缺點，利用云模型云滴的隨機性和穩(wěn)定性特點，在遺傳算法中應(yīng)用云模型理論進行交叉和變異的自適應(yīng)優(yōu)化，提高了算法的求解效率，為再制造裝配車間物料配送問題的研究開拓了思路。

[1]LundRT.Remanufacturing[J].TechnologyReview,1984,87(2):18-23.

[2]GuideVDR,WassenhoveLNV.Managingproductreturnsforremanufacturing[J].ProductionandOperationsManagement,2001,10(2):142-155.

[3] 蔣麗,丁斌,藏曉寧.以工位為中心的生產(chǎn)物流配送優(yōu)化[J].計算機集成制造系統(tǒng),2009,15(11):2153-2159.

[4] 李晉航,黃剛,賈艷.多模糊信息條件下的物料配送路徑規(guī)劃問題研究[J].機械工程學(xué)報, 2011, 47(1): 124-131.

[5]MullerJApproximativesolutionstothebicriterionVechicleRoutingProblemwithTimeWindows[J].EuropeanJournalofOperationalResearch,2010,202(141):223-231.

[6]RepooussisPP，TarantilisCD，BraysyO.Ahybridevolutionstrategyfortheopenvehicleroutingproblem[J].Computers&OperationsResearch,2010,37(3):443-455.

[7]ThibautVidal,TeodorGabrielCrainic,MichelGendreau,etal.Aunifiedsolutionframeworkformulti-attributevehicleroutingproblems[J]EuropeanJournalofOperationalResearch,2014,234(3):658-673.

[8]MartinReed,AlikiYiannakou,RoxanneEvering.Anantcolonyalgorithmforthemulti-compartmentvehicleroutingproblem[J].AppliedSoftComputing, 2014,15: 169-176.

[9]ChengR,GenM.Fuzzyvehicleroutingandschedulingproblemusinggeneticalgorithms[J].GeneticAlgorithmsandSoftComputing, 1996,683-709.

[10] 王偉鑫,王旭,葛顯龍.任務(wù)可拆分的多模式多項目調(diào)度模型與算法[J].計算機集成制造系統(tǒng), 2014,20(6): 1388-1397.

(編輯李秀敏)

Research on Material Distribution of Remanufacturing Assembly Workshop Base on Fuzzy Time Windows

ZHANG Ming-xin，CHEN Hong-hai

(School of Mechanical and Automotive Engineering, Hefei University of Technology, Hefei 230009,China)

Aiming at the uncertainty of the material demand and processing time, the optimization method based on the fuzzy time window for the material distribution in the re-assembly shop. Analyzing the attributes of the material distribution in the re-assembly shop, the categories of the materials (re-manufactured parts, re-used parts, new parts) and the cost of the succeeding assembly are both considered. Under the balance condition of the production line, using the satisfaction degree as the constraint and the minimizing the distribution cost as the target, an optimization model based on the fuzzy time window for the material distribution is established. The cloud genetic algorithm is adapted for solving this model. Due to the randomness and stability of the cloud droplet, design the dynamic crossover and mutation probability to improve the searching efficiency. Finally, a study case is taken to verify the feasibility and effectiveness of the model.

remanufacturing；material distribution；cloud genetic algorithm；fuzzy time windows

1001-2265(2015)11-0133-04DOI:10.13462/j.cnki.mmtamt.2015.11.037

2015-01-27

國家重點基礎(chǔ)研究發(fā)展計劃資助項目(973計劃，2011CB013406)

張銘鑫(1980—)，男，河北張家口人，合肥工業(yè)大學(xué)講師，博士研究生，研究方向為生產(chǎn)系統(tǒng)建模與仿真，(E-mail)zhmxcatchpp@163.com。

TH186;TG506

A