馬磊磊，王 強

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

0 引言

由于市場需求多變，裝配車間的生產(chǎn)過程時刻都有可能產(chǎn)生各種不確定因素(緊急插單、訂單取消、交貨期變更)導(dǎo)致生產(chǎn)計劃重排。同時生產(chǎn)車間環(huán)境復(fù)雜多變，各種擾動隨機出現(xiàn)，這對生產(chǎn)裝配車間物料配送提出更高的要求，因此企業(yè)急需新的技術(shù)來處理各種不確定因素下物料配送問題［1］。

面對實際的生產(chǎn)車間中不確定因素條件下的物料配送要求的不斷提高，一些學(xué)者對此進行了研究。李運霞等［2］針對路徑柔性車間調(diào)度問題，提出一種多種群遺傳算法，并驗證其可行性。曹二保等［3］均研究了模糊需求條件下路徑規(guī)劃問題。張建勇等［4-6］分別對各種模糊的工位需求、旅行時間、預(yù)約時間等條件下的車輛路徑規(guī)劃問題進行了研究。李晉航等［1］在多模糊信息條件下，構(gòu)建了機會約束規(guī)劃模型，并對傳統(tǒng)遺傳算法進行改進，研究了不同因子的設(shè)置對路徑規(guī)劃結(jié)果的影響。

在以往的車輛路徑問題的研究中不僅僅需要考慮各種不確定因素，還要考慮配送過程中工位對服務(wù)時間偏好程度、配送車輛行駛距離、車輛載荷率和車輛數(shù)等多目標(biāo)的優(yōu)化。王君等［7］首先在模糊預(yù)約時間描述的基礎(chǔ)上提出滿意度表示的新方法，然后構(gòu)建多目標(biāo)優(yōu)化模型，通過實例驗證了所提出算法解決多目標(biāo)優(yōu)化問題的有效性。GAO Gui-bing［8］等用多目標(biāo)進化算法研究了混合生產(chǎn)系統(tǒng)下物料配送路徑問題。Tang［9］等把VRPFDT分成兩個階段的子問題:第一階段是通常的帶時間窗的車輛路徑問題，以車輛行駛距離為優(yōu)化目標(biāo);第二階段在最小化車輛行駛距離的基礎(chǔ)上，對顧客的滿意度進行優(yōu)化求解，但在此過程中無法做到同時使多個目標(biāo)都達(dá)到優(yōu)化的目的。

物料配送中車輛路徑規(guī)劃問題是整個生產(chǎn)車間裝配環(huán)節(jié)的重要問題，該問題的求解結(jié)果將在一定程度上決定生產(chǎn)車間的裝配效率以及企業(yè)制造過程的物流成本。因此，本文在前述研究的基礎(chǔ)上，給出模糊預(yù)約時間的一種新的表示方法，以工位滿意度為一個優(yōu)化目標(biāo)構(gòu)建多目標(biāo)優(yōu)化模型，并且對傳統(tǒng)遺傳算法進行改進，采用可行插入法生成初始種群以加快收斂速度，提出狹義基因相似度的概念避免相似度高的個體交叉操作，同時將雙變異機制加入到變異過程控制全局解空間的搜索范圍和收斂速度，最后通過實例驗證模型和算法的有效性和可行性。

1 物料配送問題描述

1.1 問題描述

每個工位由倉庫部門發(fā)出的配送工具進行服務(wù)，任意一個配送工具所服務(wù)的各個工位的物料需求量Qi之和不得大于最大運載能力Q。配送工具滿載物料離開倉庫，為所需要物料的工位配送物料，最后回到倉庫。在一次物料配送過程中，所有工位的集合為{Xi，i=0，1，2，…，N}，其中X0代表配送中心，配送工具的集合為{Vk，k=0，1，2，…，K }，每個工位物料需求量和服務(wù)時間窗已知，并且每個工位有且僅有一個配送工具服務(wù)一次。

1.2 模糊預(yù)約時間和工位滿意度

2 數(shù)學(xué)模型建立

2.1 決策變量

2.2 多目標(biāo)數(shù)學(xué)模型(P)

根據(jù)上述問題的描述，構(gòu)建了以下數(shù)學(xué)模型:

2.2.1 優(yōu)化目標(biāo):

2.2.2 約束條件:

式中，N為工位數(shù);K為配送工具數(shù);Q為運載能力;Qi為工位i的需求量;Dij為從工位i和j間的距離;Ti為在工位i的服務(wù)時間;Tij為從工位i到工位j的行駛時間;Wi為在工位i處的等待時間;ti為開始服務(wù)工位i的時間。

式(2)～式(5)表示目標(biāo)函數(shù)，依次為配送工具行駛距離、使用數(shù)量、工位滿意度、運載率;式(6)表示不得在時間窗外對開始服務(wù);式(7)表示運載能力約束;式(8)表示每個工位有且僅有一個配送工具服務(wù);式(9)～式(10)表示兩變量xijk和yik之間的關(guān)系;式(11)～式(12)表示配送工具由倉庫離開，最后駛回倉庫;式(13)為支路消除約束。

3 用改進的遺傳算法求解模型

生產(chǎn)車間物料配送路徑規(guī)劃問題是一個NP問題。目前，許多啟發(fā)式算法在解決多目標(biāo)多約束優(yōu)化問題時都有其自身的缺陷，如進行求解時收斂速度慢易發(fā)生未成熟收斂、全局尋優(yōu)能力和局部搜索能力不均衡［11-12］。因此，本文對遺傳算法進行改進以求解問題(P)，即基于遺傳算法的進化方式借鑒遺傳算法的編碼方式［13］，同時運用行插入法得到初始種群，交叉操作中用狹義基因相似度區(qū)分染色體的相似性，將雙變異率加入到進化過程的變異操作。

3.1 構(gòu)造染色體，產(chǎn)生初始種群

初始種群生成的質(zhì)量決定了算法搜索的起始點，高質(zhì)量的種群可加速算法的收斂提高求解效率。張建勇［6］等所研究初始種群生成步驟中，當(dāng)前配送工具路徑不存在可行插入位置時，新開一配送工具，而本文在此基礎(chǔ)上進行改進，如步驟4所述。

定義1:最佳插入位置既在當(dāng)前路徑的可行插入位置的集合中，使工位的綜合滿意度值最大的位置［6］。

初始可行種群生成步驟如下:

步驟1:將N個工位隨機排列，得到工位序列集合X={x1，x2，…，xN}，然后從左向右依次分配給車輛，最后初始化配送路徑編號Car_Code=0;

步驟2:置Car_Code=Car_Code+1，新開配送工具，其路徑編號為Car_Code，將當(dāng)前X中最左邊工位安排給該新路徑，從X中刪除該工位;

步驟3:判斷X是否為空。如果是，轉(zhuǎn)步驟5;否則轉(zhuǎn)步驟4。

步驟4:取當(dāng)前集合X中最左邊的工位，判斷當(dāng)前配送工具路徑是否存在可行插入位置。若存在，則將其插入當(dāng)前配送工具路徑的最佳插入位置，轉(zhuǎn)步驟3;若不存在，依次按配送工具路徑編號從小到大判斷是否存在，若存在則將其插入該路徑的最佳插入位置，轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟2;

步驟5:計算生成的可行染色體的最佳開始服務(wù)時間，使該染色體的工位平均滿意度達(dá)到最大;

步驟6:重復(fù)步驟2～步驟5，當(dāng)生成可行染色體達(dá)到規(guī)定數(shù)量時停止。

其中，可行插入位置及最佳開始服務(wù)時間的確定如下:

(1)可行插入位置的確定

設(shè)已建立的某配送工具的可行配送路徑為(x1，x2，...，xi，...，xp)，在工位 xi處的開始服務(wù)時間為txi，則配送工具到達(dá)工位的最大推遲時間為［7］:

在其可行路徑中第i個工位后(xi和xi+1之間，若i=0時即x1之前)插入一個工位xs后該路徑仍是可行的，則應(yīng)滿足:

條件2:時間約束條件:

①配送工具達(dá)到工位s的時間不得晚于該工位時間窗的下限，既 txi+Txi+Txi，s≤ LTs，當(dāng) i=0 時，txi=Txi=0，Tx1，s=T0，s;

②當(dāng)i≤p－1時，配送工具到達(dá)工位Xi+1必須滿足:max{txi+Txi+Txi，s，ETs}+Ts+Ts，xi+1≤ txi+1+max_pone(xi+1)－Wxi+1。

(2)最佳開始服務(wù)時間的確定

在以上操作得到的可行路徑中，工位綜合滿意度不是最佳的。在張建勇［6］最佳開始服務(wù)時間的確定方法研究基礎(chǔ)上，本文是從配送工具路徑的最后面的工位進行時間的調(diào)整，省去了確定不可推部分，同時在最大可推遲量的計算上有所改進。

最佳開始服務(wù)時間的計算步驟如下:

步驟 1:假設(shè)某配送工具配送路徑為 (x1，x2，......，xp)。

步驟2:將該配送工具路徑劃分為若干個片段(xi，xi+1，xi+2，…，xj)，滿足條件 Wxi+1=Wxi+2= ...=Wxj=0，且有:i≠1時，Wxi≠0;Wxj＜ p時，Wxj+1≠0。

步驟4:取當(dāng)前配送工具路徑中已調(diào)整片段的前一片段按照步驟3的方法進行調(diào)整;若該片段與當(dāng)前配送工具路徑中的后一片段形成新的片段，則重新對新形成的片段進行調(diào)整;否則轉(zhuǎn)步驟5。

步驟5:繼續(xù)重復(fù)步驟4，直到完成該配送工具路徑中所有工位開始服務(wù)時間的確定。

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

根據(jù)每個個體優(yōu)化目標(biāo)值及權(quán)重參數(shù)計求解其適應(yīng)度。求解函數(shù)如下所示:

其中，hk表示第k個染色體;dk、vk、uk、lk分別表示染色體hk的行駛距離、配送工具使用總數(shù)、工位平均滿意度、配送工具運載率;dmax、vmax、umax、lmax分別表示當(dāng)前種群中染色體的最大行駛距離、最大配送工具使用數(shù)、最大工位平均滿意度、最大運載率;αi(i=1，2，3，4)為權(quán)重系數(shù)。

3.3 用狹義基因相似度區(qū)分染色體的相似性

為避免標(biāo)準(zhǔn)遺傳算法存在的缺陷，防止可能出現(xiàn)的大量相似個體的交叉，本文采用狹義基因相似度概念來區(qū)分染色體的相似性。

定義2:狹義基因相似度Mxy是兩個染色體x、y中，具有相同工位路線的所有工位數(shù)量與總工位數(shù)之比［1，14］。如染色體 09320480675010 和 04806750310290的相同路徑有06750和0480(包含5個工位)，工位總數(shù)為9，則Mxy=5/9。當(dāng)且僅當(dāng)染色體等價時(Mxy=1)，狹義基因相似度為1。

3.4 雙變異率的改進遺傳算法

通過狹義基因相似度概念的定義，避免相似高的染色體交叉操作。同時將雙變異機制加入傳統(tǒng)遺傳算法中控制全局解空間搜索范圍和收斂速度。

雙變異率［14］，既局部小變異率和全局大變異率，其出現(xiàn)的位置、起到的作用以及面對的對象是不一樣的。當(dāng)交叉操作產(chǎn)生的個體數(shù)TempPop_size小于種群個體數(shù)Pop_size時，表明由選擇操作產(chǎn)生的個體間的相似度高。為了提高染色體的多樣性，擴大算法的搜索區(qū)域，保證染色體的解充滿整個可行解空間，避免局部收斂，對交叉后的種群進行局部小變異。為了保持解種群的優(yōu)良性，局部變異的概率Local_Pm取值范圍一般為0.07～0.15。對變異操作產(chǎn)生的種群，首先以選擇操作來淘汰一批不良染色體，然后計算兩個體間的基因相似度，對小于某規(guī)定值Mxy'的個體進行交叉操作。狹義基因相似度概念的加入，成功的避免了相似個體間的交叉操作，抑制未成熟收斂。同時，計算每一代交叉操作的個體適應(yīng)度值以及運用輪盤賭法選擇較優(yōu)個體，然后對該群體以大變異率Global_Pm進行全局大變異，以保證整個過程的全局性。

3.5 改進遺傳算法步驟

改進遺傳算法操作步驟如下:

步驟1:運用3.1的方法生產(chǎn)初始種群;

步驟2:用如圖1的流程對種群進行交叉變異操作;

步驟3:適應(yīng)度函數(shù)計算;

步驟4:用輪盤賭法選擇染色體;

步驟5:對Step4中產(chǎn)生的新一代種群中每一個染色體按3.1相同的方法重新分配保證可行性;

步驟6:重復(fù)步驟2～5直到完成給定的循環(huán)次數(shù);

步驟7:找出最優(yōu)個體，既配送路徑的最優(yōu)方案。改進遺傳算法具體操作流程如圖1所示:

圖1 改進遺傳算法流程圖

4 實例驗證

生產(chǎn)車間某次物料配送中，有9個工位和一個倉庫，配送工具的運載力為12個單位，各工位的服務(wù)時間、預(yù)約時間和需求量如表1所示，各工位間的行駛時間及行駛距離如表2所示;改進遺傳算法基本參數(shù)，取種群大小Pop_size=100，迭代次數(shù)Max_gen=200，選擇概率Px=0.8，交叉概率Pc=0.8，雙變異概率 Local_Pm=0.1 和 Global_Pm=0.2。

表1 各工位信息表

表2 工位間距離和行駛時間表

根據(jù)上述算法利用Matlab仿真，對不同權(quán)重設(shè)置情況下進行計算，結(jié)果如表3所示。

從表3中可以看出，優(yōu)化目標(biāo)權(quán)重參數(shù)的設(shè)置對實驗結(jié)果有很大的影響。d、l與v密切相關(guān)，即d隨著v的增加而呈現(xiàn)增加的趨勢，l隨著v的增加呈降低的趨勢;而u與d、v、l等目標(biāo)相對立，即u的提高是以d和v的增加以及l(fā)的降低為代價的。

為證明本文所提出的改進遺傳算法的有效性，以改進遺傳算法分別取權(quán)重α1=1、α2=1、α3=1，與傳統(tǒng)的遺傳算法相應(yīng)的單目標(biāo)求解作對比(由于l與v成反比例關(guān)系，所以在此不作α4=1分析)。采用傳統(tǒng)遺傳算法計算本例，初始種群大小為100，選擇概率、交叉概率均為 0.8，變異概率為 0.1。

圖2 配送工具行駛距離收斂比較

圖3 配送工具使用數(shù)收斂比較

圖4 工位平均滿意度收斂比較

如圖2所示取α1=1時，改進遺傳算法在30代以后呈現(xiàn)穩(wěn)定下降的趨勢，至55代收斂;而傳統(tǒng)遺傳算法在中后期收斂速度很慢，直到126代才開始收斂。如圖3所示取α2=1時，改進的遺傳算法基本無波動現(xiàn)象，從整個圖像看兩者下降的趨勢，既開始點和收斂點的連線，改進遺傳算法的斜率明顯大于傳統(tǒng)遺傳算法的斜率。如圖4所示取α3=1時，同樣改進遺傳算法收斂速度快，隨著迭代次數(shù)的增加呈現(xiàn)穩(wěn)定上升的趨勢。綜上所述，由圖2、3、4的收斂圖可知，顯然改進遺傳算法優(yōu)于傳統(tǒng)遺傳算法。

5 結(jié)論

(1)本文運用模糊預(yù)約時間窗，考慮了工位對時間窗的偏好，同時使工位期望服務(wù)時間是在時間窗內(nèi)服從正態(tài)分布的隨機變量，且以工位的滿意度為其中的一個優(yōu)化目標(biāo)，更切實際地解決不確定因素下的物料配送問題。

(2)針對傳統(tǒng)遺傳算法存在易發(fā)生未成熟收斂及其收斂速度低等缺陷，本文采用可行插入法生成初始種群以加快收斂速度。提出狹義基因相似度的概念避免相似度高的個體交叉操作，同時將雙變異機制加入到變異過程更好地控制全局解空間的搜索范圍和收斂速度。

(3)采用線性加權(quán)模型解決多目標(biāo)優(yōu)化問題中的權(quán)重選擇問題，設(shè)置不同的權(quán)重因子其求解的結(jié)果亦有很大的不同，決策者可以根據(jù)生產(chǎn)車間物料配送的實際要求選擇不同權(quán)重參數(shù)。

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

［2］李運霞，杜鵑，孫王路.基于多種群遺傳算法的路徑柔性車間調(diào)度問題［J］.組合機床與自動化加工技術(shù)，2014(3):152－155.

［3］曹二保，賴明勇，張漢江.模糊需求車輛路徑問題研究［J］.系統(tǒng)工程，2007，25(11):14 －18.

［4］張建勇，郭耀煌，李軍.模糊需求信息條件下的車輛路徑問題研究［J］.系統(tǒng)工程學(xué)報，2004，19(1):74 －78.

［5］張建勇，李軍.具有模糊旅行時間的VRP的一種混合遺傳算法［J］.管理工程學(xué)報，2006，20(4):13－16.

［6］張建勇，李軍，郭耀煌.具有模糊預(yù)約時間的VRP混合遺傳算法［J］.管理科學(xué)學(xué)報，2005，8(3):64－71.

［7］王君，李波.帶模糊預(yù)約時間的車輛路徑問題的多目標(biāo)禁忌搜索算法［J］.計算機集成制造系統(tǒng)，2011，17(4):858－866.

［8］GAO Guibing，ZHANG Guojun，HUANG Gang，ZHU Haiping，GU Peihua.Solving material distribution routing problem in mixed manufacturing systems with a hybrid multi-objective evolutionary algorithm［J］.J.Cent.South Univ.2012，19:433－442.

［9］TANG Jiafu，PAN Zhendong，F(xiàn)UN G R Y K，et al.Vehicle routing problem with fuzzy time windows［J］.Fuzzy Sets and Systems，2009，160(5):683 －695.

［10］趙燕偉，李川，張景玲，等.一種新的求解多目標(biāo)隨機需求車輛路徑問題的算法［J］.計算機集成制造系統(tǒng)，2012，18(3):523－530.

［11］劉明周，張明偉，蔣增強，等.基于混合粒子群算法的多目標(biāo)柔性Job-Shop調(diào)度方法［J］.農(nóng)業(yè)機械學(xué)報，2008，39(5):122－127.

［12］葛茂根，劉明周，錢芳，等.基于JIT的多目標(biāo)總裝準(zhǔn)時物料配送方法研究［J］.中國機械工程，2011，22(23):2834－2838.

［13］齊曉寧，汪永超，賈婧，等.基于遺傳算法的面向綠色制造的車間調(diào)度優(yōu)化［J］.組合機床與自動化加工技術(shù)，2012(10):16－18.

［14］王杰，馬雁，王非.一種雙變異率的改進遺傳算法及其仿真研究［J］.計算機工程與應(yīng)用，2008，44(3):57 －59.