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

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

中圖分類號：TP311? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2018）36-0096-04

0? 引言

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

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

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

1? 配送中心選址問題的模型與算法

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

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

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

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

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

④運營費用僅考慮配送中心的日常費用和車輛使用折舊費用之和，其余費用本文暫不考慮;

⑤以降低成本為優(yōu)化目標，按工業(yè)工程標準化原則，可將營運費用標準化限定，從而對成本達到有效化控制[10]。

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

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

目標函數(shù)：

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

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

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

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

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

2? 配送中心選址問題的AIA算法

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

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

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

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

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

步驟3，對抗體進行評價。

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

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

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

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

如圖1為AIA的流程圖。

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

2.2.1 編碼方法

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

2.2.2 免疫操作

①選擇：采用常見的輪盤賭選擇機制，依照期望繁殖概率來對抗體進行遴選。該概率表達式為：

（Av、Cv均參照文獻[13]）。

②交叉：采用均勻交叉法來進行交叉操作。

③變異：對抗體的變異采用常用的隨機變異位法。

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

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

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

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

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

2.3 實例仿真

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

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

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

3? 結(jié)論

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

參考文獻：

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

[2]蔣利軍，蔣明，趙正佳.配送中心選址問題研究文獻綜述[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]高輝，徐光輝，王哲人，等.克隆選擇算法在一類有競爭的物流配送中心選址問題中的應(yīng)用[J].公路交通科技，2007，24（6）：144-147.

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

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

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

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

[10]想田豐太郎.生產(chǎn)現(xiàn)場最優(yōu)分析法，圖解生產(chǎn)實務(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].暨南大學學報自然科學與醫(yī)學版，2003，24（1）：22-25.

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

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