遺傳算法在車間物流配送優(yōu)化中的應(yīng)用

時(shí) 振，李壯闊（桂林電子科技大學(xué)，廣西 桂林 541004）

1 車間物流配送優(yōu)化問題的動態(tài)規(guī)劃模型

假設(shè)配送中心有K輛搬運(yùn)設(shè)備，每輛搬運(yùn)設(shè)備的載重量為Qk（k=1,2,…,K），其一次配送的最大行駛距離為Dk，需要向L個(gè)加工點(diǎn)送貨，每個(gè)加工點(diǎn)的需求量為qi（i=1,2,…,L），加工點(diǎn)i到j(luò)的運(yùn)距為dij，配送中心到各加工點(diǎn)的距離為d0j（ij=1,2,…,L）。再設(shè)nk為第k輛搬運(yùn)設(shè)備配送的加工點(diǎn)數(shù)（nk=0表示未使用第k輛搬運(yùn)設(shè)備），用集合Rk表示第k條路徑，其中的元素rki表示加工點(diǎn)rki在路徑k中的順序?yàn)閕，令rk0=0表示配送中心，則可建立如下車間物流配送優(yōu)化問題的數(shù)學(xué)模型：

車間物流配送采用動態(tài)規(guī)劃模型，總體描述為：從配送中心用多輛搬運(yùn)設(shè)備向多個(gè)加工點(diǎn)送貨，每個(gè)加工點(diǎn)的位置和需求量一定，每輛搬運(yùn)設(shè)備的載重量一定，要求合理安排搬運(yùn)設(shè)備路線，使總運(yùn)距最短，并滿足以下條件：

（1）每條配送路徑上各加工點(diǎn)的需求量之和不超過搬運(yùn)設(shè)備載重量；

（2）每條配送路徑的長度不超過搬運(yùn)設(shè)備一次配送的最大行駛距離；

（3）每個(gè)加工點(diǎn)的需求必須滿足只能由一輛搬運(yùn)設(shè)備送貨。

考慮了上述車間物流配送優(yōu)化問題的約束條件和優(yōu)化目標(biāo)后，開始建立車間物流配送優(yōu)化問題的數(shù)學(xué)模型，描述如下：

上述模型中，式（1）為目標(biāo)函數(shù)；式（2）保證每條路徑上各加工點(diǎn)的需求量之和不超過搬運(yùn)設(shè)備的載重量；式（3）保證每條配送路徑的長度不超過搬運(yùn)設(shè)備一次配送的最大行駛距離；式（4）表明每條路徑上的加工點(diǎn)數(shù)不超過總加工點(diǎn)數(shù)；式（5）表明每個(gè)加工點(diǎn)都得到配送服務(wù)；式（6）為每條路徑的加工點(diǎn)的組成；式（7）限制每個(gè)加工點(diǎn)僅能由一輛搬運(yùn)設(shè)備送貨；式（8）為當(dāng)?shù)趉輛搬運(yùn)設(shè)備服務(wù)的客戶數(shù)≥1時(shí)，說明該輛搬運(yùn)設(shè)備參加了配送，則取sign（nk）=1，當(dāng)?shù)趉輛搬運(yùn)設(shè)備服務(wù)的客戶數(shù)＜1時(shí)，表示未使用該輛搬運(yùn)設(shè)備，因此取sign（nk）=0。

2 車間物流配送優(yōu)化問題的遺傳算法

遺傳算法以群體中的所有個(gè)體為操作對象，每個(gè)個(gè)體對應(yīng)研究問題的一個(gè)解。選擇、交叉和變異是遺傳算法的三個(gè)主要操作算子，另外還有編碼方法、初期群體的確定和適應(yīng)性評估等因素，針對車間物流配送優(yōu)化問題的特點(diǎn)，構(gòu)造出求解該問題的遺傳算法。

（1）編碼方法的確定。根據(jù)車間物流配送優(yōu)化問題的特點(diǎn)，筆者采用了簡單直觀的自然數(shù)編碼方法，用0表示配送中心，用1、2、…、L表示各加工點(diǎn)。由于在配送中心有K輛搬運(yùn)設(shè)備，則最多存在K條配送路徑，每條配送路徑都始于配送中心，也終于配送中心。為了在編碼中反映車輛配送的路徑，采用了增加K－1個(gè)虛擬配送中心的方法，分別用L+1、L+2、…、L+K－1表示。這樣，1、2、…、L+K－1，這L+K－1個(gè)互不重復(fù)的自然數(shù)的隨機(jī)排列就構(gòu)成一個(gè)個(gè)體，并對應(yīng)一種配送路徑方案。例如，對于一個(gè)有7個(gè)加工點(diǎn)，用3輛搬運(yùn)設(shè)備完成配送任務(wù)的問題,則可用1、2、…、9（8、9表示配送中心），這9個(gè)自然數(shù)的隨機(jī)排列，表示物流配送路徑方案。如個(gè)體129638547 表示的配送路徑方案為：路徑 1：0－1－2－9，路徑 2：9－6－3－8，路徑 3：8－5－4－7－0，共有 3 條配送路徑；個(gè)體 573894216 表示的配送路徑方案為：路徑 1：0－5－7－3－8，路徑 2：9－4－2－1－6－0，共有 2 條配送路徑。

（2）初始群體的確定。隨機(jī)產(chǎn)生一種1～L+K－1，這L+K－1個(gè)互不重復(fù)的自然數(shù)的排列，即形成一個(gè)個(gè)體。設(shè)群體規(guī)模為N，則通過隨機(jī)產(chǎn)生N個(gè)這樣的個(gè)體，即形成初始群體。

（3）適應(yīng)度評估。對于某個(gè)個(gè)體所對應(yīng)的配送路徑方案，要判定其優(yōu)劣，一是要看其是否滿足配送的約束條件；二是要計(jì)算其目標(biāo)函數(shù)值（即各條配送路徑的長度之和）。根據(jù)配送路徑優(yōu)化問題的特點(diǎn)所確定的編碼方法，隱含能夠滿足每個(gè)加工點(diǎn)都得到配送服務(wù)及每個(gè)加工點(diǎn)僅由一輛搬運(yùn)設(shè)備配送的約束條件，但不能保證滿足每條路徑上各加工點(diǎn)需求量之和不超過搬運(yùn)設(shè)備載重量及每條配送路線的長度不超過搬運(yùn)設(shè)備一次配送的最大行駛距離的約束條件。為此，對每個(gè)個(gè)體所對應(yīng)的配送路徑方案，要對各條路徑逐一進(jìn)行判斷，看其是否滿足上述兩個(gè)束條件，若不滿足，則將該條路徑定為不可行路徑，最后計(jì)算其目標(biāo)函數(shù)值。對于某個(gè)個(gè)體j，設(shè)其對應(yīng)的配送路徑方案的不可行路徑數(shù)為Mj（Mj=0表示該個(gè)體對應(yīng)一個(gè)可行解），其目標(biāo)函數(shù)值為Zj，則該個(gè)體的適應(yīng)度Fj可用下式表示：

式中，G為對每條不可行路徑的懲罰權(quán)重，可根據(jù)目標(biāo)函數(shù)的取值范圍取一個(gè)相對較大的正數(shù)。

（4）選擇操作。將每代群體中的N個(gè)個(gè)體按適應(yīng)度由大到小排列，排在第一位的個(gè)體性能最優(yōu)，將它復(fù)制一個(gè)直接進(jìn)入下一代，并排在第一位。下一代群體的另N－1個(gè)個(gè)體需要根據(jù)前代群體的N個(gè)個(gè)體的適應(yīng)度，采用賭輪選擇法產(chǎn)生。具體地說，就是首先計(jì)算上代群體中所有個(gè)體適應(yīng)度的總和（ΣFj），再計(jì)算每個(gè)個(gè)體的適應(yīng)度所占的比例（Fj/Σ Fj），以此作為其被選擇的概率。這樣的選擇方法既可保證最優(yōu)個(gè)體生存至下一代，又能保證適應(yīng)度較大的個(gè)體以較大的機(jī)會進(jìn)入下一代。

（5）交叉操作。對通過選擇操作產(chǎn)生的新群體，除排在第一位的最優(yōu)個(gè)體外，另N－1個(gè)個(gè)體要按交叉概率Pc進(jìn)行配對交叉重組。筆者采用了一種類似OX法的交叉方法，現(xiàn)舉例說明：①隨機(jī)在父代個(gè)體中選擇一個(gè)交配區(qū)域，如兩父代個(gè)體及交配區(qū)域選定為：A=47|8563|921，B=83|4691|257；②將B的交配區(qū)域加到A的前面，A的交配區(qū)域加到 B 的前面，得:A′=4691｜478563921｜，B′=8563｜834691257｜；③在 A′、B′中自交配區(qū)域后依次刪除與交配區(qū)相同的自然數(shù)，得到最終的兩個(gè)個(gè)體為：A″=469178532，B″=856349127。與其他交叉方法相比，這種方法在兩父代個(gè)體相同的情況下仍能產(chǎn)生一定程度的變異效果，這對維持群體的多樣化特性有一定的作用。

（6）變異操作。由于在選擇機(jī)制中采用了保留最佳樣本的方式，為保持群體內(nèi)個(gè)體的多樣化，采用了連續(xù)多次對換的變異技術(shù)，使個(gè)體在排列順序上有較大變化。變異操作是以概率Pm發(fā)生的，一旦變異操作發(fā)生，則用隨機(jī)方法產(chǎn)生交換次數(shù)J，對所需變異操作的個(gè)體的基因進(jìn)行J次對換（對換基因的位置也是隨機(jī)產(chǎn)生的）。

3 用matlab程序進(jìn)行實(shí)驗(yàn)計(jì)算和結(jié)果分析

根據(jù)上述遺傳算法編制了matlab程序，并對一個(gè)某配送中心使用2輛搬運(yùn)設(shè)備對8個(gè)加工點(diǎn)進(jìn)行送貨的車間物流配送優(yōu)化問題實(shí)例進(jìn)行了實(shí)驗(yàn)計(jì)算。設(shè)搬運(yùn)設(shè)備的載重量為8×103kg，每次配送的最大行駛距離為40km，配送中心與各加工點(diǎn)之間、各加工點(diǎn)相互之間的距離及各加工點(diǎn)的需求量見表1。根據(jù)上述實(shí)例的特點(diǎn)，在實(shí)驗(yàn)計(jì)算中采用了以下參數(shù)：群體規(guī)模取20，交叉概率和變異概率分別取0195和0105，進(jìn)化代數(shù)取50，變異時(shí)基因換位次數(shù)取5，對不可行路徑的懲罰權(quán)重取100km。對上述問題，利用計(jì)算機(jī)隨機(jī)求解10次，得到的計(jì)算結(jié)果見表2。

表1 配送中心與加工點(diǎn)之間的距離（/km）及各加工點(diǎn)的需求量

表2 車間物流配送優(yōu)化問題的遺傳算法計(jì)算結(jié)果

從表中數(shù)據(jù)可以看出，10次運(yùn)行得到的結(jié)果均優(yōu)于節(jié)約法所得的結(jié)果79.5km。而且第5次還得到了該問題的最優(yōu)解67.5km，其對應(yīng)的配送路徑方案為：路徑1：0-4-7-6-0；路徑2：0-2-8-5-3-1-0?？梢?，利進(jìn)遺傳算法可以方便有效地求得車間物流配送優(yōu)化問題的近似最優(yōu)解。

4 結(jié) 論

合理確定車間物流配送是提高服務(wù)質(zhì)量、降低配送成本、增加經(jīng)濟(jì)效益的重要手段，而采用啟發(fā)式算法求解是車間物流配送優(yōu)化問題重要的研究方向。因此，筆者構(gòu)造了求解車間物流配送優(yōu)化問題的遺傳算法模型，而且實(shí)驗(yàn)結(jié)果也表明，遺傳算法是一種性能優(yōu)良的啟發(fā)式搜索算法，利用該方法可以方便有效地求得物流配送路徑優(yōu)化問題的近似最優(yōu)解。同時(shí)對解決類似的組合優(yōu)化問題具有一定的參考價(jià)值。

[1]陳國良，王煦法,等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996.

[2]姜大立，楊西龍，杜文.車輛路徑問題的遺傳算法研究[J].系統(tǒng)工程理論與實(shí)踐，1999,19(6):40-44.

[3]蔡希賢，夏士智.物流合理化的數(shù)量方法[M].武漢：華中工學(xué)院出版社，1985.