基于自適應(yīng)免疫算法的物流配送中心選址問(wèn)題研究

倪衛(wèi)紅 岳曉偉 邵建峰 錢(qián)偉民

摘要：關(guān)于配送中心選址問(wèn)題研究，采用免疫算法時(shí)單點(diǎn)交叉會(huì)產(chǎn)生超級(jí)個(gè)體以及固定概率會(huì)影響搜索能力的情況，分別以均勻交叉和自適應(yīng)化的方法，在原算法上做出改進(jìn)。并以實(shí)例驗(yàn)證該算法的可行性和有效性，與傳統(tǒng)免疫算法比對(duì)，能很好避免超級(jí)個(gè)體的產(chǎn)生同時(shí)搜索能力也有增強(qiáng)。該算法自適應(yīng)的變化更加符合個(gè)體在不同階段演變情況，相比傳統(tǒng)免疫算法，達(dá)到收斂速度快、魯棒性高的效果，進(jìn)而為選址問(wèn)題研究在原有基礎(chǔ)上匹配了一種更好的方法。

Abstract： To solve selection of logistics distribution center， the standard immune algorithm （SIA） has the problem of "super individual" in the operation of single-point crossover and the poor search ability by using fixed probability of crossover and mutation. We try to apply uniform crossover and self-adaptation to SIA. Then， the feasibility and effectiveness of the adaptive immune algorithm are verified by a calculation example. Compared with SIA， AIA makes further efforts to avoid the generation of "super individual". Meanwhile， the search ability is enhanced in a certain extent. In my opinion， the adaptive changes are better to conform to the real state of individual in different stages. The AIA has fast convergence speed and high robustness. It provides a better approach on location problem in the original basis.

關(guān)鍵詞：選址;優(yōu)化;自適應(yīng);均勻交叉;免疫算法

Key words： location;optimization;adaptation;uniform crossover;immune algorithm

中圖分類(lèi)號(hào)：TP311? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2018）36-0096-04

0? 引言

隨著經(jīng)濟(jì)的不斷增長(zhǎng)和交通運(yùn)輸?shù)目焖侔l(fā)展，物流產(chǎn)業(yè)正依托這有利的環(huán)境優(yōu)勢(shì)在全球范圍內(nèi)迅猛發(fā)展。在這種背景下，物流配送中心的選址問(wèn)題一直都是研究熱點(diǎn)。物流行業(yè)的快速發(fā)展也引發(fā)了行業(yè)競(jìng)爭(zhēng)的日趨白熱化，利潤(rùn)空間不斷壓縮，在此情況下，資源和成本就成為企業(yè)增加盈利的根本途徑[1-3]。因此，如何做到科學(xué)、合理地進(jìn)行配送中心選址，優(yōu)化物流網(wǎng)絡(luò)結(jié)構(gòu)和空間布局，是企業(yè)迫切需求的，同時(shí)也是相關(guān)學(xué)者不斷深入研究的方向[4]。

通常情況下，配送中心的選址問(wèn)題，就是在確定眾多需求點(diǎn)的基礎(chǔ)上，將一些需求點(diǎn)設(shè)置為配送中心，以此來(lái)滿(mǎn)足與其相關(guān)的需求點(diǎn)的需求限制，進(jìn)而構(gòu)成一系列的配送服務(wù)區(qū)域。在此基礎(chǔ)上，追求配送系統(tǒng)成本的最小化[3]。

當(dāng)前，在物流配送中心選址問(wèn)題上針對(duì)算法的運(yùn)用，專(zhuān)家學(xué)者進(jìn)行了大量的理論研究。其中，關(guān)于有競(jìng)爭(zhēng)的物流配送中心選址，高輝[5]等針對(duì)有競(jìng)爭(zhēng)選址模型高維性、非線(xiàn)性和非凸性的特性，給出了一種克隆選擇算法;而郜振華[6]等對(duì)于同樣的問(wèn)題，為了解決算法“早熟”問(wèn)題提出了一種混合遺傳算法;秦固[7]則用聚類(lèi)過(guò)程來(lái)映射配送中心選址問(wèn)題并將蟻群優(yōu)化算法作為解決多個(gè)物流配送中心選址問(wèn)題的方法;淦艷[8]等用權(quán)值來(lái)衡量影響選址的因素，然后用免疫算法解決問(wèn)題。受上述文獻(xiàn)的啟發(fā)，本文在文獻(xiàn)[9]的基礎(chǔ)上，對(duì)其提出的算法進(jìn)行自適應(yīng)等改進(jìn)，并做出比較，獲得了尋優(yōu)能力進(jìn)一步提升的良好效果。

1? 配送中心選址問(wèn)題的模型與算法

1.1 配送中心選址問(wèn)題模型假設(shè)

為了構(gòu)建模型，提出如下幾點(diǎn)假設(shè)：

①在已知物流配送中心服務(wù)區(qū)域需求總量的條件下，配送中心所承載的配送能力恒滿(mǎn)足其所服務(wù)的需求點(diǎn)總需求量;

②在配送中心輻射范圍內(nèi)，需求點(diǎn)僅能由與其相對(duì)應(yīng)的配送中心提供服務(wù);

③僅將配送中心與其所服務(wù)的需求點(diǎn)間的運(yùn)輸費(fèi)用作為模型的服務(wù)費(fèi)用;

④運(yùn)營(yíng)費(fèi)用僅考慮配送中心的日常費(fèi)用和車(chē)輛使用折舊費(fèi)用之和，其余費(fèi)用本文暫不考慮;

⑤以降低成本為優(yōu)化目標(biāo)，按工業(yè)工程標(biāo)準(zhǔn)化原則，可將營(yíng)運(yùn)費(fèi)用標(biāo)準(zhǔn)化限定，從而對(duì)成本達(dá)到有效化控制[10]。

1.2 配送中心選址問(wèn)題模型構(gòu)建

基于以上假設(shè)，本文考慮的選址因素較簡(jiǎn)單，但不乏具有代表性和通用性，主要有以下兩部分：①配送中心與其所服務(wù)的需求點(diǎn)之間的服務(wù)費(fèi)用;②配送中心基地運(yùn)營(yíng)費(fèi)用。建立如下的選址-分配數(shù)學(xué)模型：

目標(biāo)函數(shù)：

其中式（1）代表全部配送中心成本總和，構(gòu)成模型的目標(biāo)函數(shù)。第一部分代表模型的服務(wù)成本，剩下部分則代表模型的運(yùn)營(yíng)成本，si：需求點(diǎn)i的需求量，dij：物流配送中心和需求點(diǎn)間的距離，Xj：配送中心的運(yùn)營(yíng)費(fèi)用。

式（2）、（3）為假設(shè)（2）的數(shù)學(xué)語(yǔ)言，即確保每個(gè)需求點(diǎn)有且僅能夠由與其對(duì)應(yīng)的配送中心服務(wù)，Yij、Hj是兩個(gè)0-1變量，當(dāng)均為1時(shí)，表示配送中心j與需求點(diǎn)i的服務(wù)關(guān)系用Yij來(lái)表示，需求點(diǎn)j被設(shè)置為物流配送中心由Hj來(lái)表示，當(dāng)均為0時(shí)，則表示相反;

式（4）規(guī)定在n個(gè)需求點(diǎn)集合中，選出k個(gè)配送中心;

式（5）表示配送中心服務(wù)范圍能覆蓋其所服務(wù)的全部需求點(diǎn);

式（6）、（7）分別表示需求點(diǎn)和配送中心數(shù)量。

2? 配送中心選址問(wèn)題的AIA算法

2.1 自適應(yīng)免疫優(yōu)化算法介紹

首先，在眾多智能算法中，免疫算法（immune algorithm，IA）產(chǎn)生得比較晚，是由T-Fukuda等人在1998年提出的一種算法。IA逐漸被運(yùn)用在求解多態(tài)優(yōu)化問(wèn)題 [11]。類(lèi)似于遺傳算法模仿生物界的遺傳進(jìn)化規(guī)律，免疫算法同樣是受到生物學(xué)免疫系統(tǒng)學(xué)說(shuō)的啟發(fā)。受到人體免疫系統(tǒng)的多樣性產(chǎn)生和維持機(jī)制的啟發(fā)下，該算法的群體呈現(xiàn)出多樣性。這樣一來(lái)，在一般尋優(yōu)過(guò)程中產(chǎn)生的老大難問(wèn)題——“早熟”問(wèn)題可以得到解決，因此在處理多峰函數(shù)尋優(yōu)問(wèn)題時(shí)，本文認(rèn)為采用免疫算法雖然將會(huì)得到比較理想的全局最優(yōu)解，但仍有改進(jìn)之處。在此基礎(chǔ)上，提出自適應(yīng)免疫算法，并進(jìn)行對(duì)比[12]。

通常情況下，免疫算法具有以下具體實(shí)現(xiàn)步驟：

步驟1 ，對(duì)研究問(wèn)題進(jìn)行分析，然后構(gòu)建目標(biāo)函數(shù)和約束條件，表示抗原對(duì)機(jī)體的侵入。接著對(duì)編碼方式進(jìn)行設(shè)置，并在參數(shù)設(shè)置時(shí)，將Pc、Pm做出自適應(yīng)化。

步驟2， 產(chǎn)生初始抗體群。

步驟3，對(duì)抗體進(jìn)行評(píng)價(jià)。

步驟4，形成父代群體，并產(chǎn)生記憶細(xì)胞。

步驟5，以是否滿(mǎn)足算法終止條件作為能否跳出循環(huán)過(guò)程的依據(jù)。

步驟6，通過(guò)對(duì)算法進(jìn)行一系列操作來(lái)達(dá)到產(chǎn)生新群體的效果，如選擇、交叉、變異等操作。

步驟7，對(duì)步驟3至步驟6進(jìn)行重復(fù)操，直到終止條件被滿(mǎn)足，最后輸出結(jié)果。

如圖1為AIA的流程圖。

2.2 自適應(yīng)免疫算法求解問(wèn)題

2.2.1 編碼方法

此處將運(yùn)用自然數(shù)編碼方式。AIA將被選作為物流配送中心的需求點(diǎn)編號(hào)序列表示為長(zhǎng)度k是的個(gè)體。比如在一個(gè)擁有25個(gè)需求點(diǎn)的區(qū)域，首先用1-25的數(shù)來(lái)對(duì)各需求點(diǎn)進(jìn)行編號(hào)，再?gòu)倪@25個(gè)編號(hào)中挑選出5個(gè)來(lái)作為物流配送中心，因此像[7 5 21 16 23]的抗體，就表示為一個(gè)可行解，意思是編號(hào)7、5、21、16、23的需求點(diǎn)是配送中心。這樣的編碼方式完全滿(mǎn)足上述設(shè)置的約束條件。

2.2.2 免疫操作

①選擇：采用常見(jiàn)的輪盤(pán)賭選擇機(jī)制，依照期望繁殖概率來(lái)對(duì)抗體進(jìn)行遴選。該概率表達(dá)式為：

（Av、Cv均參照文獻(xiàn)[13]）。

②交叉：采用均勻交叉法來(lái)進(jìn)行交叉操作。

③變異：對(duì)抗體的變異采用常用的隨機(jī)變異位法。

相較于文獻(xiàn)[9]，在算法自適應(yīng)性和交叉操作兩方面做出了改進(jìn)，以下將分別對(duì)此進(jìn)行闡述。

首先，對(duì)于算法的自適應(yīng)這方面，本文在交叉概率、變異概率上設(shè)計(jì)自適應(yīng)變化，將這兩個(gè)概率都表示為關(guān)于進(jìn)化代數(shù)t的函數(shù)，參照文獻(xiàn)[14]，對(duì)其自適應(yīng)提出新的自適應(yīng)化，表示如下：

鑒于研究證明，在智能算法中Pc的大小與算法局部尋優(yōu)能力正相關(guān)，Pc數(shù)值越大，算法具備的搜索能力越強(qiáng)，種群的進(jìn)化速度越快;變異概率是與算法個(gè)體的適應(yīng)性負(fù)相關(guān)，Pm越小，抗體所具有的適應(yīng)能力則越強(qiáng)，存活下來(lái)的幾率就越大。在智能算法尋優(yōu)過(guò)程中，一般分為進(jìn)化初期、進(jìn)化中期、和進(jìn)化后期三個(gè)不同的階段。按這三個(gè)階段將Pc、Pm分為三段值，相較于文獻(xiàn)[9]這樣的通常算法中將Pc、Pm始終固定為一個(gè)值的情況，能夠做到在進(jìn)化速度和搜尋的解質(zhì)量中進(jìn)行權(quán)衡，使算法過(guò)程更加智能化，同時(shí)對(duì)于問(wèn)題也是更好的處理，進(jìn)而到達(dá)自適應(yīng)的變化。

此處，為了更加形象地表達(dá)以上自適應(yīng)過(guò)程，將用圖2、3來(lái)表示Pc、Pm在初期、中后期和后期三個(gè)階段的變化情況，并非代表真實(shí)函數(shù)關(guān)系。為了方便圖形表達(dá)，在圖中用k表示。

關(guān)于算法交叉操作方面，一般情況下，均采用單點(diǎn)交叉或者是雙點(diǎn)交叉，這兩種交叉法都能比較好保留父代的特征，但面臨很大概率產(chǎn)生超級(jí)個(gè)體的問(wèn)題。這將會(huì)造成算法陷入局部最優(yōu)。因此，本文在交叉操作時(shí)選用均勻交叉法，這樣在具備單雙交叉法優(yōu)點(diǎn)的同時(shí)又能很好避免超級(jí)個(gè)體的產(chǎn)生。該操作不僅需要兩個(gè)父代個(gè)體，同時(shí)還要引入一個(gè)隱碼。本文中，用0、1兩種字符來(lái)構(gòu)成與父代長(zhǎng)度相同的所需隱碼，通過(guò)此隱碼來(lái)決定各個(gè)基因位是否交叉。父代中基因位是否需要進(jìn)行交叉則由隱碼中該基因位是否為1來(lái)決定，反之不進(jìn)行交叉。特舉例說(shuō)明：

2.3 實(shí)例仿真

本文在文獻(xiàn)[13]數(shù)據(jù)的基礎(chǔ)上，對(duì)此算法的可行性和有效性進(jìn)行驗(yàn)證。同時(shí)，將本文提出來(lái)的AIA與SIA仿真結(jié)果進(jìn)行比對(duì)。設(shè)置基本參數(shù)：種群規(guī)模=50，記憶庫(kù)容量=10，迭代次數(shù)=100?；谕葪l件，得出圖4算法比對(duì)圖。從圖中明顯看出，利用AIA獲得的結(jié)果相較于SIA得出來(lái)的精度要更高。此外AIA在收斂速度、運(yùn)算速度及尋優(yōu)能力等方面均優(yōu)于SIA。

在與SIA對(duì)比后，為了進(jìn)一步測(cè)試自適應(yīng)免疫算法的性能。對(duì)于該配送中心選址問(wèn)題方案確定，運(yùn)用遺傳算法來(lái)仿真，并將其與AIA比對(duì)，如圖5所示。同樣，從上述的各種性能看，AIA也是優(yōu)于GA。

經(jīng)過(guò)以上對(duì)比，認(rèn)為能用AIA更好解決該問(wèn)題。于是用MATLAB多次求解，在眾多求得的配送中心選址方案中，[27 11 20 12 17 5]是最優(yōu)方案，其值為5.49×105。圖6、7分別是AIA算法收斂圖和物流配送中心選址方案。

3? 結(jié)論

針對(duì)物流配送中心的選址，本文在原有算法基礎(chǔ)上加入一種自適應(yīng)的交叉、變異算子并用均勻交叉操作替換常用的單雙點(diǎn)交叉操作。這兩個(gè)方面的改進(jìn)，不僅更好地避免了單雙點(diǎn)交叉操作中高概率產(chǎn)生“超級(jí)個(gè)體”的情況，進(jìn)而避免算法的“早熟”。由此，變化的Pc、Pm與算法不同階段的真實(shí)情況相符合，從而對(duì)抗體種群的多樣性起到更好的保持作用。AIA在具備較強(qiáng)尋優(yōu)能力的同時(shí)，收斂速度、求解精度和魯棒性均得到一定程度的改進(jìn)。因此，該算法作為算法求解選址問(wèn)題的研究是一種有效補(bǔ)充，具有一定的參考價(jià)值。此外，后續(xù)研究可在建模優(yōu)化方面加入更多工業(yè)工程相關(guān)專(zhuān)業(yè)知識(shí)，以對(duì)該問(wèn)題做更深層次的優(yōu)化。

參考文獻(xiàn)：

[1]魏娜.關(guān)于物流配送中心選址優(yōu)化問(wèn)題研究[D].東北財(cái)經(jīng)大學(xué)，2007.

[2]蔣利軍，蔣明，趙正佳.配送中心選址問(wèn)題研究文獻(xiàn)綜述[J]. 物流科技，2008，31（4）：31-33.

[3]Hua X， Hu X， Yuan W. Research optimization on logistics distribution center location based on adaptive particle swarm algorithm[J]. Optik - International Journal for Light and Electron Optics， 2016， 127（20）：8443-8450.

[4]Klose A， Drexl A. Facility location models for distribution system design[J]. European Journal of Operational Research， 2005， 162（1）：4-29.

[5]高輝，徐光輝，王哲人，等.克隆選擇算法在一類(lèi)有競(jìng)爭(zhēng)的物流配送中心選址問(wèn)題中的應(yīng)用[J].公路交通科技，2007，24（6）：144-147.

[6]郜振華，陳森發(fā).遺傳算法在有競(jìng)爭(zhēng)的物流配送中心選址中的應(yīng)用[J].公路交通科技，2005，22（8）：138-141.

[7]秦固.基于蟻群優(yōu)化的多物流配送中心選址算法[J].系統(tǒng)工程理論與實(shí)踐，2006，26（4）：120-124.

[8]淦艷，魏延，楊有.免疫算法在帶權(quán)值的物流配送中心選址中的應(yīng)用[J].重慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2015（5）：107-113.

[9]周梅芳，葉洪濤.基于免疫算法的物流配送中心選址[J].廣西科技大學(xué)學(xué)報(bào)，2012，23（3）：77-79.

[10]想田豐太郎.生產(chǎn)現(xiàn)場(chǎng)最優(yōu)分析法，圖解生產(chǎn)實(shí)務(wù)[M].東方出版社，2011：42.

[11]Wang C Y， Liu Z N. An Immunity-Based Algorithm for Distribution Center Location[J]. Advanced Materials Research， 2014， 971-973：1537-1542.

[12]葛紅.免疫算法與遺傳算法比較[J].暨南大學(xué)學(xué)報(bào)自然科學(xué)與醫(yī)學(xué)版，2003，24（1）：22-25.

[13]史峰，王輝，郁磊，等.MATLAB智能算法30個(gè)案例分析[M].北京航空航天大學(xué)出版社，2015：128.

[14]劉姝廷，金太東，王連生.一種改進(jìn)的自適應(yīng)遺傳算法[J]. 江西理工大學(xué)學(xué)報(bào)，2010，31（1）：59-61.