基于自適應免疫算法的物流配送中心選址問題研究

倪衛紅 岳曉偉 邵建峰 錢偉民

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

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.

關鍵詞：選址;優化;自適應;均勻交叉;免疫算法

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

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

0? 引言

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

通常情況下，配送中心的選址問題，就是在確定眾多需求點的基礎上，將一些需求點設置為配送中心，以此來滿足與其相關的需求點的需求限制，進而構成一系列的配送服務區域。在此基礎上，追求配送系統成本的最小化[3]。

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

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

1.1 配送中心選址問題模型假設

為了構建模型，提出如下幾點假設：

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

②在配送中心輻射范圍內，需求點僅能由與其相對應的配送中心提供服務;

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

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

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

1.2 配送中心選址問題模型構建

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

目標函數：

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

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

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

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

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

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

2.1 自適應免疫優化算法介紹

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

通常情況下，免疫算法具有以下具體實現步驟：

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

步驟2， 產生初始抗體群。

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

步驟4，形成父代群體，并產生記憶細胞。

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

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

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

如圖1為AIA的流程圖。

2.2 自適應免疫算法求解問題

2.2.1 編碼方法

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

2.2.2 免疫操作

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

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

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

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

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

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

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

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

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

2.3 實例仿真

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

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

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

3? 結論

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

參考文獻：

[1]魏娜.關于物流配送中心選址優化問題研究[D].東北財經大學，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]高輝，徐光輝，王哲人，等.克隆選擇算法在一類有競爭的物流配送中心選址問題中的應用[J].公路交通科技，2007，24（6）：144-147.

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

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

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

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

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

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

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