摘 要： 在分析了一類(lèi)配送中心選址問(wèn)題的基礎(chǔ)上，建立了該配送中心選址問(wèn)題的數(shù)學(xué)模型。提出一種具有雙重信息的遺傳算法編碼方案，并結(jié)合相應(yīng)的遺傳操作進(jìn)行求尋優(yōu)求解，最后通過(guò)實(shí)驗(yàn)證明了該方法的可行性和有效性。
關(guān)鍵詞： 雙重信息；遺傳算法；配送中心；模型
隨著市場(chǎng)競(jìng)爭(zhēng)的日益加劇，越來(lái)越多的企業(yè)認(rèn)識(shí)到，如何合理地設(shè)立分銷(xiāo)配送中心，加強(qiáng)對(duì)配送環(huán)節(jié)的有效管理，是提高企業(yè)競(jìng)爭(zhēng)力非常有效的途徑。配送是指在經(jīng)濟(jì)合理區(qū)域范圍內(nèi)里，配送中心根據(jù)客戶(hù)要求，對(duì)物品進(jìn)行揀選、加工、包裝、分割、組配等，并按時(shí)送達(dá)指定地點(diǎn)建立中間分銷(xiāo)配送中心[1]。科學(xué)建立配送中心，不僅可以使企業(yè)快速把握和響應(yīng)市場(chǎng)反應(yīng)，而且還能通過(guò)優(yōu)化的配送中心以及相應(yīng)的配送方案給企業(yè)節(jié)約很大的成本。
目前，越來(lái)越多的研究人員趨向于采用遺傳算法、拉格朗日松弛法、模擬退火算法等啟發(fā)式算法來(lái)達(dá)到或逼近該問(wèn)題的最優(yōu)解[2]。參考文獻(xiàn)[3]使用兩步驟近似法構(gòu)建在庫(kù)存和運(yùn)輸雙重能力約束下，每個(gè)周期配送中心的庫(kù)存成本計(jì)算方法，分別用遺傳算法、克隆選擇算法、粒子群算法求解所建立的模型；參考文獻(xiàn)[4]使用經(jīng)遺傳算法改進(jìn)的人工神經(jīng)網(wǎng)絡(luò)模型對(duì)糧食配送中心選址問(wèn)題進(jìn)行求解；參考文獻(xiàn)[5]采用以模擬退火的思想對(duì)遺傳算子參數(shù)進(jìn)行自適應(yīng)的改進(jìn)方法，解決以區(qū)域分銷(xiāo)中心選址為基礎(chǔ)的汽車(chē)零部件物流網(wǎng)絡(luò)優(yōu)化解決方案；參考文獻(xiàn)[6]采用改進(jìn)的遺傳算法求解帶有時(shí)間窗的單配送中心的車(chē)輛調(diào)度模型。遺傳算法具有隨機(jī)和多點(diǎn)搜尋特性[7]。本文對(duì)遺傳算法進(jìn)行改進(jìn)，設(shè)計(jì)一種具有雙重信息的編碼方案和相應(yīng)的遺傳操作，將之應(yīng)用到配送中心選址模型，使算法能夠有效地收斂到該模型的全局最優(yōu)解。
1 一類(lèi)配送中心選址數(shù)學(xué)模型
1.1 問(wèn)題描述
若某企業(yè)需要在某市建立若干個(gè)配送中心，現(xiàn)有m個(gè)備選配送中心和n個(gè)配送點(diǎn)，并且已知每個(gè)備選配送中心的建設(shè)費(fèi)用以及其建成后可具有的容量，以及配送中心向配送點(diǎn)配送時(shí)每單位重量需花費(fèi)的運(yùn)輸費(fèi)用和每個(gè)配送點(diǎn)的需求量，現(xiàn)需要從m個(gè)備選配送點(diǎn)中選擇若干個(gè)建設(shè)成配送中心，那么選取哪些備用配送中心以及如何分配這些配送中心的配送點(diǎn)，使得配送中心建設(shè)費(fèi)用以及向配送點(diǎn)配送時(shí)的花費(fèi)最少[8]。
1.2 數(shù)學(xué)模型
根據(jù)問(wèn)題描述，該類(lèi)配送中心選址問(wèn)題的數(shù)學(xué)模型描述如下：
式（1）表示總的建設(shè)費(fèi)用和運(yùn)輸費(fèi)用最小；式（2）表示對(duì)i點(diǎn)的需求量應(yīng)小于等于其容量；式（3）表示向配送點(diǎn)j配送的量應(yīng)大于等于其需求量；式（4）Ai為標(biāo)志整型變量，標(biāo)明第i個(gè)備選點(diǎn)是否被選中。
2 針對(duì)此模型的改進(jìn)遺傳算法
2.1 具有雙重信息的染色體編碼方案設(shè)計(jì)
傳統(tǒng)的遺傳算法染色體編碼經(jīng)常采用二進(jìn)制編碼。對(duì)于本文所提出的選址中心數(shù)學(xué)模型，如果采用二進(jìn)制編碼，可以用染色體的每個(gè)基因位相應(yīng)的下標(biāo)來(lái)代表每個(gè)備選配送中心，用染色體的每個(gè)基因位上的0-1值代表該備選配送中心是否被選中，若共有6個(gè)備選配送中心和8個(gè)配送點(diǎn)，則染色體長(zhǎng)度應(yīng)設(shè)置為6，如果某個(gè)染色體如圖1所示。
則表示1號(hào)、2號(hào)、6號(hào)備選配送中心被選中，利用這種編碼方案雖然可以表示出哪些備選配送中心被選中，但是從染色體上體現(xiàn)不出這些選出來(lái)的配送中心為哪些配送點(diǎn)進(jìn)行配送，如果要繼續(xù)確定這些配送中心的配送點(diǎn)，又需要在此基礎(chǔ)上進(jìn)行相應(yīng)的設(shè)計(jì)，這無(wú)疑會(huì)增加算法的復(fù)雜度和編程的工作量。
針對(duì)二進(jìn)制編碼的上述問(wèn)題，本文提出了一種具有雙重信息的染色體編碼方案，使染色體可以體現(xiàn)雙重信息，從染色體上既可以體現(xiàn)出哪些備選配送中心被選中，而且還可以體現(xiàn)出這些選出來(lái)的配送中心為哪些配送點(diǎn)進(jìn)行配送，這會(huì)很大程度上提高解決問(wèn)題的效率。具體方法是：若要從m個(gè)備選配送中心選擇若干個(gè)為n個(gè)配送點(diǎn)進(jìn)行配送服務(wù)，則設(shè)置染色體的長(zhǎng)度是n，染色體由n個(gè)[1，m]之間的整數(shù)構(gòu)成，如要從6個(gè)備選中心中選擇若干個(gè)為8個(gè)配送點(diǎn)服務(wù)，則染色體長(zhǎng)度為8，染色體由8個(gè)[1，6]之間的整數(shù)構(gòu)成。這樣染色體的每個(gè)基因位上的值就代表選中的配送中心的編號(hào)，而染色體的每個(gè)基因位相應(yīng)的下標(biāo)表示其所服務(wù)的配送點(diǎn)。如果某個(gè)染色體如圖2所示。
2.4 遺傳算法步驟設(shè)計(jì)
將上述改進(jìn)遺傳算法應(yīng)用到本文的配送中心選址模型求解中，具體步驟如下：
（1）設(shè)置遺傳算法基本參數(shù)：種群數(shù)量NIND，最大代數(shù)MAXGEN，代溝GGAP，交叉概率Pc，變異概率Pm，讀入各備選配送中心的建設(shè)費(fèi)用和建設(shè)之后的容量，以及各個(gè)配送點(diǎn)的需求和配送單位重量需要的運(yùn)輸費(fèi)用。
（2）產(chǎn)生初始種群：產(chǎn)生NIND行n列個(gè)范圍在[1，m]之間的隨機(jī)整數(shù)作為初始種群Chrom，其中n為配送點(diǎn)的個(gè)數(shù)，m為備用配送中心的個(gè)數(shù)。
（3）分別計(jì)算種群Chrom中各染色體的目標(biāo)值Objv，根據(jù)各自的目標(biāo)值按照代溝GGAP按前述方法進(jìn)行選擇操作，形成Selch。
（4）對(duì)Selch按照交叉概率Pc和變異概率Pm依次進(jìn)行交叉和變異操作，形成子代種群。
（5）記錄子代種群的最優(yōu)目標(biāo)值，并對(duì)子代種群按步驟（2）的方法產(chǎn)生若干個(gè)染色體對(duì)子代種群進(jìn)行補(bǔ)充。
（6）判斷Gen是否大于MAXGEN，是則退出，否則轉(zhuǎn)向步驟（3）。
3 仿真測(cè)試
假設(shè)某公司需要為其在某市的8個(gè)配送點(diǎn)選擇配送中心，需要從6個(gè)備選點(diǎn)選擇若干個(gè)對(duì)其進(jìn)行建設(shè)作為配送中心，那么選擇哪些備選點(diǎn)作為配送中心會(huì)使得建設(shè)費(fèi)用和運(yùn)輸費(fèi)用最小，其中8個(gè)配送點(diǎn)的需求量如表1所示，各個(gè)備選配送中心的建設(shè)費(fèi)用及容量如表2所示，各配送中心向配送點(diǎn)配送時(shí)每單位重量需花費(fèi)的運(yùn)輸費(fèi)用如表3所示。
采用上述改進(jìn)遺傳算法對(duì)此問(wèn)題進(jìn)行仿真測(cè)試，其中參數(shù)設(shè)置為：種群數(shù)量NIND=20，最大代數(shù)MAXGEN=100，代溝GGAP=0.7，交叉概率Pc=0.7。
程序運(yùn)行后的最優(yōu)解的染色體為：21121222，從該染色體可以得出：從6個(gè)備選配送中心中選擇1號(hào)、2號(hào)建設(shè)成為配送中心，其中1號(hào)配送中心為2號(hào)、3號(hào)、5號(hào)配送點(diǎn)配送服務(wù)，2號(hào)配送中心為1號(hào)、4號(hào)、6號(hào)、7號(hào)、8號(hào)配送點(diǎn)配送服務(wù)。
其中遺傳算法進(jìn)行100代時(shí)每代的最優(yōu)目標(biāo)值如圖3所示，從圖中可以看出，運(yùn)行到100代時(shí)得出最優(yōu)解，總的建設(shè)和運(yùn)輸費(fèi)用是804個(gè)單位值，進(jìn)化時(shí)每代的最優(yōu)目標(biāo)值從最初的1 655左右逐漸下降到804，說(shuō)明該算法有很好的尋優(yōu)能力，能有效地對(duì)這類(lèi)配送中心選址數(shù)學(xué)模型進(jìn)行優(yōu)化。
科學(xué)建立配送中心，不僅可以使企業(yè)快速把握和響應(yīng)市場(chǎng)，而且還能通過(guò)優(yōu)化的配送中心以及相應(yīng)的配送方案提高企業(yè)的市場(chǎng)競(jìng)爭(zhēng)力。本文針對(duì)一類(lèi)配送中心選址問(wèn)題出發(fā)，對(duì)其進(jìn)行數(shù)學(xué)建模，并提出一種具有雙重信息的編碼設(shè)計(jì)方案，使得從染色體編碼上不僅可以體現(xiàn)出哪些備選配送中心被選中，而且還可以體現(xiàn)出這些選出來(lái)的配送中心為哪些配送點(diǎn)進(jìn)行配送。通過(guò)仿真測(cè)試，證明了該方法在解決這一類(lèi)模型時(shí)的可行性和有效性。
參考文獻(xiàn)
[1] 謝天保，雷西玲，席文玲.物流配送中心配載車(chē)輛調(diào)度問(wèn)題研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（36）：237-240.
[2] 王喆.基于組合遺傳算法的鐵路危險(xiǎn)貨物辦理站點(diǎn)整合優(yōu)化[J].計(jì)算機(jī)應(yīng)用，2010，39（9）：2301-2304.
[3] 稅文兵，葉懷珍，張?jiān)姴?物流配送中心動(dòng)態(tài)選址模型及算法研究[J].計(jì)算機(jī)應(yīng)用研究，2010，27（12）：4476-4479.
[4] 許德剛，肖人彬.基于改進(jìn)神經(jīng)網(wǎng)絡(luò)的糧食配送中心選址決策研究[J].計(jì)算機(jī)應(yīng)用研究，2010，27（3）：887-890.
[5] 朱爽，王東.汽車(chē)零部件物流網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2011，37（12）：258-261.
[6] 施朝春，王旭，葛顯龍.帶有時(shí)間窗的多配送中心車(chē)輛調(diào)度問(wèn)題研究[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（34）：21-24.
[7] 李凈，袁小華，朱云飛.物流配送系統(tǒng)中車(chē)輛路徑問(wèn)題的實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（16）：3783-3786.
[8] 張玉芬，齊紅然，劉世普.一類(lèi)應(yīng)急服務(wù)設(shè)施選址問(wèn)題的模型及算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2009，39（14）：37-41.