周宇陽(yáng)，張惠珍

（上海理工大學(xué)管理學(xué)院，上海 200093）

0 引言

合理的倉(cāng)庫(kù)選址對(duì)現(xiàn)代物流管理有著重要影響，通過對(duì)倉(cāng)庫(kù)進(jìn)行合理規(guī)劃，不僅可以節(jié)約配送成本，還可以提高客戶滿意度及企業(yè)的核心競(jìng)爭(zhēng)力［1］。倉(cāng)庫(kù)選址問題是一個(gè)經(jīng)典的組合優(yōu)化問題，該問題通過確定設(shè)施點(diǎn)的位置，將需求點(diǎn)分配給開放的設(shè)施點(diǎn)，確保每個(gè)需求點(diǎn)的需求均能被滿足，并使總成本最小化?，F(xiàn)如今，有容量的設(shè)施選址問題已成為物流管理、供應(yīng)鏈管理及運(yùn)籌優(yōu)化領(lǐng)域的研究熱點(diǎn)。李小川等［2］設(shè)計(jì)了改進(jìn)的煙花算法對(duì)物流配送中心選址問題進(jìn)行求解；李捷承等［3］針對(duì)物流配送設(shè)施選址的特點(diǎn)，設(shè)計(jì)了一個(gè)基于BIRCH（Balanced Iterative Reduc?ing and Clustering Using Hierarchies）聚類的物流設(shè)施選址算法，可較大程度地節(jié)約長(zhǎng)期運(yùn)營(yíng)成本；黃凱明等［4］對(duì)于物流網(wǎng)絡(luò)多層級(jí)設(shè)施選址—路徑規(guī)劃問題，建立了混合整數(shù)規(guī)劃數(shù)學(xué)模型，并提出量子進(jìn)化算法與遺傳算法協(xié)同的雙智能算法集成求解方案；陳勇等［5］建立了逆向物流網(wǎng)絡(luò)模型，考慮廢舊家電回收的數(shù)量、質(zhì)量、客戶需求量、回收中心對(duì)居民產(chǎn)生的負(fù)效用，為企業(yè)在物流設(shè)施選址及不同周期下的市場(chǎng)缺貨量、設(shè)施間流量分配等提供靈活的決策方案；張雨等［6］以時(shí)間路徑優(yōu)化為研究對(duì)象，對(duì)聚類算法和最小支撐樹法進(jìn)行改進(jìn)，構(gòu)建物流中心選址和物流配送區(qū)域劃分模型，以提升物流企業(yè)服務(wù)效率與服務(wù)質(zhì)量。在物流倉(cāng)庫(kù)選址模型中，考慮年運(yùn)行成本及倉(cāng)庫(kù)容量約束的研究較少。鑒于此，文中建立的有容量的倉(cāng)庫(kù)選址模型考慮了倉(cāng)庫(kù)年固定成本、車輛行駛成本和倉(cāng)庫(kù)容量約束，使得模型更具有實(shí)際應(yīng)用意義。

P-中位選址問題（P-Median）是一類典型的組合優(yōu)化問題，屬于NP-hard 問題，在設(shè)施選址、交通、物流等領(lǐng)域有著較為廣泛的應(yīng)用［7-8］。本文所建立的有容量的應(yīng)急醫(yī)療設(shè)施選址模型是對(duì)P-中位選址問題的一種擴(kuò)展，也屬于NP-hard 問題。對(duì)于NP-hard 問題的求解，精確算法很難在可接受的計(jì)算時(shí)間范圍內(nèi)提供最優(yōu)解［9］。雖然大多數(shù)元啟發(fā)式算法不能保證得到最優(yōu)解，但它們可以在合理的時(shí)間內(nèi)提供良好結(jié)果。已經(jīng)有不少學(xué)者將遺傳算法［10-12］、禁忌搜索算法［13］、蟻群優(yōu)化算法［14］、模擬退火算法［15］、免疫優(yōu)化算法［16］等元啟發(fā)式算法應(yīng)用到選址問題中。免疫優(yōu)化算法被發(fā)現(xiàn)是一種解決多種優(yōu)化問題的高效算法［17］，其利用免疫機(jī)制保持種群多樣性。此外，免疫優(yōu)化算法還具有自組織和魯棒性強(qiáng)的優(yōu)點(diǎn)，適用于求解選址優(yōu)化問題［18-20］。但是，免疫優(yōu)化算法的免疫操作較為簡(jiǎn)單，在求解過程中容易陷入局部最優(yōu)。因此，根據(jù)倉(cāng)庫(kù)選址問題的特點(diǎn)，對(duì)免疫優(yōu)化算法設(shè)計(jì)兩種交叉算子與變異算子，使得算法在迭代過程中平衡局部搜索和全局搜索。此外，對(duì)算法中的參數(shù)進(jìn)行測(cè)試，選取最優(yōu)參數(shù)組合方式，提高算法性能，降低算法求解運(yùn)行時(shí)間。

1 模型建立

本文建立的倉(cāng)庫(kù)選址模型考慮了設(shè)施點(diǎn)的容量、年建設(shè)成本和車輛行駛成本。有容量的倉(cāng)庫(kù)選址模型需從候選設(shè)施點(diǎn)集中選取部分作為設(shè)施點(diǎn)，為需求點(diǎn)提供貨物運(yùn)輸服務(wù)。保證每個(gè)需求點(diǎn)均由設(shè)施點(diǎn)提供服務(wù)，且設(shè)施點(diǎn)服務(wù)的總需求量不超過設(shè)施點(diǎn)的服務(wù)容量限制。在選址問題中，車輛的行駛費(fèi)用與設(shè)施點(diǎn)的建造費(fèi)用往往是相互矛盾的。建立較少的倉(cāng)庫(kù)可節(jié)省較多的建設(shè)費(fèi)用，但會(huì)增加車輛的交通成本，反之亦然。因此，構(gòu)建適當(dāng)數(shù)量的倉(cāng)庫(kù)可以幫助平衡倉(cāng)庫(kù)建設(shè)成本與車輛行駛成本。

1.1 模型假設(shè)

為便于選址模型建立，給出以下假設(shè)：①一個(gè)設(shè)施點(diǎn)可為多個(gè)需求點(diǎn)提供服務(wù)，但一個(gè)需求點(diǎn)僅由一個(gè)設(shè)施點(diǎn)提供服務(wù)；②車輛行駛成本與行駛距離之間存在簡(jiǎn)單線性關(guān)系；③區(qū)域內(nèi)的需求點(diǎn)擬用離散型變量分布點(diǎn)集N表示，候選設(shè)施點(diǎn)從點(diǎn)集M中產(chǎn)生；④設(shè)施點(diǎn)倉(cāng)庫(kù)建設(shè)為統(tǒng)一標(biāo)準(zhǔn)。

1.2 參數(shù)與決策變量定義

模型所用符號(hào)說明如下：

集合：

N：需求點(diǎn)的集合；

M：設(shè)施點(diǎn)的集合；

參數(shù)：

dij：i需求點(diǎn)到j(luò)設(shè)施點(diǎn)之間的距離，i∈N,j∈M；

p：設(shè)施點(diǎn)的個(gè)數(shù)；

B：設(shè)施點(diǎn)的建設(shè)成本；

r：計(jì)算設(shè)施點(diǎn)的折現(xiàn)率；

t：新建設(shè)一個(gè)設(shè)施點(diǎn)的使用年限；

k：道路曲折系數(shù)；

Di：需求點(diǎn)i的需求量；

G：設(shè)施點(diǎn)最大可服務(wù)的容量。

決策變量：

基于上述假設(shè)、定義的參數(shù)和決策變量，將倉(cāng)庫(kù)選址問題的數(shù)學(xué)模型表示為：

約束條件：

目標(biāo)函數(shù)（1）為設(shè)施點(diǎn)的年建設(shè)成本與車輛行駛成本之和。固定資產(chǎn)的價(jià)值可能會(huì)隨著時(shí)間而變化。在倉(cāng)庫(kù)的使用年限內(nèi)，將固定成本折算為年成本更為合理。貼現(xiàn)率r常用來表示建筑成本的當(dāng)前價(jià)值與未來價(jià)值的關(guān)系［21-22］。因此，目標(biāo)函數(shù)的第一部分為設(shè)施點(diǎn)的年建設(shè)成本，由建設(shè)成本與系數(shù)相乘得到［21］。目標(biāo)函數(shù)的第二部分是車輛行駛成本。約束條件（2）表示僅當(dāng)設(shè)施點(diǎn)j開放時(shí)，設(shè)施點(diǎn)j才可為需求點(diǎn)i提供運(yùn)貨服務(wù)。約束條件（3）表示需求點(diǎn)i僅由一個(gè)設(shè)施點(diǎn)提供服務(wù)。約束條件（4）表示設(shè)施點(diǎn)開放的個(gè)數(shù)為p。約束條件（5）為服務(wù)容量的約束，即設(shè)施點(diǎn)所服務(wù)的容量不可超過其容量上限。約束條件（6）、（7）是對(duì)決策變量xij、yj的取值范圍進(jìn)行約束。

2 求解倉(cāng)庫(kù)選址模型的免疫優(yōu)化算法

免疫優(yōu)化算法是一種基于生物免疫系統(tǒng)的智能優(yōu)化算法。在該算法中，模型中的目標(biāo)函數(shù)和解分別對(duì)應(yīng)于生物免疫系統(tǒng)中的“抗原”和“抗體”［18］。在算法迭代過程中，抗體與抗原之間的親和值逐漸提高，最終生成親和值最優(yōu)的抗體。免疫優(yōu)化算法流程如圖1 所示。免疫優(yōu)化算法在免疫選擇的作用下，反映了免疫記憶功能和免疫系統(tǒng)的自我調(diào)節(jié)功能。

Fig.1 Flow chart of immune optimization algorithm圖1 免疫優(yōu)化算法流程

考慮到有容量倉(cāng)庫(kù)選址模型的具體特征，設(shè)計(jì)改進(jìn)的免疫優(yōu)化算法，使其更適合有容量的倉(cāng)庫(kù)選址模型，并克服經(jīng)典免疫算法易陷入局部最優(yōu)解的問題。改進(jìn)的免疫優(yōu)化算法主要由3 部分構(gòu)成：①初始化：確定解的表達(dá)形式，隨機(jī)產(chǎn)生初始抗體，將滿足條件的一定數(shù)量的抗體保存，以便算法能夠快速地尋優(yōu)迭代；②抗體評(píng)價(jià)：抗體評(píng)價(jià)是通過計(jì)算抗體的親和力評(píng)價(jià)抗體優(yōu)劣，親和力計(jì)算包括抗體與抗原的親和值、抗體密度。將質(zhì)量高的若干抗體存入記憶庫(kù)中，以便算法快速收斂到最優(yōu)解；③遺傳操作：在遺傳操作中，利用單點(diǎn)交叉、二點(diǎn)交叉、變異算子生成子代抗體，既加強(qiáng)了對(duì)有希望空間的搜索利用，又能保持種群的多樣性，使其快速收斂到最優(yōu)解。

2.1 解的表示與初始化

倉(cāng)庫(kù)選址模型的選址方案可以形成長(zhǎng)度為l的抗體（l為開放設(shè)施點(diǎn)的數(shù)量），每個(gè)抗體表示開放設(shè)施點(diǎn)的序列，即解的序列。對(duì)于m個(gè)候選設(shè)施點(diǎn)中選取l個(gè)開放設(shè)施的選址問題，假設(shè)m個(gè)候選設(shè)施點(diǎn)的編號(hào)分別為1,2,…,m(m＞1)，則抗體l=[M1,M2,…,Ml］表示一個(gè)可行的解決方案，其中，M1,M2,…,Ml表示1,2,…,m中不重復(fù)的l個(gè)序號(hào)。

2.2 初始解生成

與經(jīng)典免疫優(yōu)化算法相同，初始解首先通過洗牌方式產(chǎn)生：將候選設(shè)施點(diǎn)集1,2,…,m(m＞1)的順序打亂，隨機(jī)選擇兩個(gè)不同位置的數(shù)字并進(jìn)行交換，執(zhí)行次。將交換后序列的前l(fā)個(gè)數(shù)字作為初始抗體。但由此產(chǎn)生的抗體具有隨機(jī)性，抗體質(zhì)量較差。因此，本文對(duì)抗體進(jìn)行判斷，選擇優(yōu)質(zhì)抗體作為初始抗體?？贵w中的每個(gè)設(shè)施點(diǎn)為Mj,(j∈M)，usdcap(j)為設(shè)施點(diǎn)j已服務(wù)的需求量，demandi為需求點(diǎn)i的需求量，Cj為j設(shè)施點(diǎn)的服務(wù)容量。將需求點(diǎn)i分配給離其最近且滿足容量約束（usdcap(j)+demandi≤C）j的設(shè)施點(diǎn)j，令xij=1，并更新usdcap(j)=usdcap(j)+demandi；遍歷完所有需求點(diǎn)i，如果demandi均能被滿足，且設(shè)施點(diǎn)所服務(wù)的總需求不超過該設(shè)施點(diǎn)的容量限制，則判定抗體合格；否則，重新產(chǎn)生新的抗體并檢驗(yàn)是否合格。本文在算法中設(shè)置記憶庫(kù)存儲(chǔ)高質(zhì)量的抗體，以保留優(yōu)秀抗體的優(yōu)秀特征，初始記憶庫(kù)中的抗體是隨機(jī)生成的合格抗體。將合格的P1個(gè)抗體與記憶庫(kù)中P2個(gè)抗體組成初始抗體群。

2.3 抗體與抗原親和值

抗體與抗原之間的親和值表示抗體對(duì)抗原的識(shí)別程度。通過式（8）計(jì)算抗體與抗原間的親和值，即適應(yīng)度值。

2.4 抗體間相似值

抗體間的相似值表示它們之間的相似性。本文采用Smith 等［23］提出的R-bit 連續(xù)法計(jì)算抗體相似值。當(dāng)兩個(gè)抗體有連續(xù)R 位或更多位置上具有相同編碼時(shí)，表示兩種抗體相似，否則表示兩種抗體不相似。

其中，tk,v為抗體k、v之間的相同位數(shù)，l為每個(gè)抗體的長(zhǎng)度。例如，抗體xk=［53 23 12 45 61 20 37 56 24 65 34 1］和xv=［25 39 53 32 11 47 12 16 15 19 45 5］的相同位數(shù)為3，則xk和xv之間的Sk,v為0.25。

2.5 抗體密度

抗體密度φk，即抗體濃度，表示群體中相似抗體的比例。

如果Sk,v＞R，則Bk,v=1，否則Bk,v=0。R 是預(yù)定義的閾值［23］。

2.6 期望繁殖概率

通過式（11）可計(jì)算抗體的期望繁殖概率，式（11）由抗體的親和值和抗體密度兩部分構(gòu)成。

其中，η為［0，1］區(qū)間內(nèi)的常數(shù)。

由式（11）可知，抗體與抗原的親合值越大，期望繁殖概率越高；抗體密度越大，期望繁殖概率越小。因此，式（11）不僅可以鼓勵(lì)選擇適應(yīng)度值好的抗體，而且可以抑制抗體間的密度，從而確保種群的多樣性。當(dāng)免疫優(yōu)化算法抑制高密度的抗體時(shí)，部分高密度的抗體可能已接近于最優(yōu)解，這樣會(huì)導(dǎo)致已求得的最優(yōu)解丟失。因此，本文采用精英保留策略：在更新記憶庫(kù)時(shí)，先將與抗原親和值高的P個(gè)抗體存入記憶庫(kù)中，保留抗體群中精英個(gè)體的優(yōu)秀特征；再提取前P1個(gè)抗體作為父代群體，按照期望繁殖概率進(jìn)行選擇和遺傳操作，以保持優(yōu)良抗體的特性。

2.7 遺傳操作

2.7.1 選擇

通過輪盤賭的機(jī)制進(jìn)行選擇操作，輪盤選擇法是一種比較受歡迎的選擇方法。根據(jù)抗體的期望繁殖概率，在父代群體P1中選擇兩個(gè)抗體。期望繁殖概率越大，被選擇的概率就越高。

2.7.2 交叉

交叉在遺傳操作中起著至關(guān)重要的作用，它可以提高抗體間的差異度，以便算法快速收斂到最優(yōu)解?？紤]是在整數(shù)編碼的遺傳操作環(huán)境下，本文使用時(shí)間復(fù)雜度低的兩種交叉操作方式：?jiǎn)吸c(diǎn)交叉和兩點(diǎn)交叉。對(duì)于兩種交叉方式的參數(shù)選擇，設(shè)置交叉率的范圍為θ∈[θmin,θmax]，隨機(jī)生成［0，1］之間的隨機(jī)數(shù)γ，若γ≤θ，則選擇單點(diǎn)交叉，反之，選擇兩點(diǎn)交叉操作。

單點(diǎn)交叉：給定兩個(gè)抗體parent1、parent2，首先在2 和l-1 之間隨機(jī)選擇一個(gè)交叉點(diǎn)q。交換兩個(gè)抗體在q點(diǎn)之后的元素，得到parent1,、parent2,。若parent1,中更改的序號(hào)r在parent1中已存在，則找到parent1中序號(hào)r所在的位置R，并找到parent2中R位置的序號(hào)r,，將parent1,中的序號(hào)r改為r,。重復(fù)此步驟，直到抗體中無重復(fù)序號(hào)，得到子代抗體child1和child2。

單點(diǎn)交叉操作如圖2 所示。對(duì)于親本抗體parent1=［10 2 21 13 9 17 6 23 4］和parent2=［11 8 20 1 15 12 21 14 5］，隨機(jī)選擇交叉點(diǎn)q=6。將兩個(gè)抗體第6 個(gè)位置后的元素交換得到parent1,=［10 2 21 13 9 12 21 14 5］，parent2,=［11 8 20 1 15 17 6 23 4］。在parent1,中有重復(fù)元素21，因此找到parent1中元素21 所在的第3 個(gè)位置，并找到parent2中位置3 的序號(hào)為20，將parent1,第7 個(gè)位置的元素改為20。最后，得到無重復(fù)元素的子代抗體child1=［10 2 21 13 9 12 20 14 5］和child2=［11 8 20 1 15 17 6 23 4］。

Fig.2 An example of one-point crossover圖2 單點(diǎn)交叉例子

兩點(diǎn)交叉：給定兩個(gè)親本抗體parent1、parent2，首先在2和l-1 之間隨機(jī)選擇兩個(gè)不同的交叉點(diǎn)q1、q2，交換兩個(gè)抗體交換q1和q2之間的元素，得到抗體parent1,、parent2,。與單點(diǎn)交叉相同，需要消除子代抗體中的重復(fù)元素，得到子代抗體child1、child2。

兩點(diǎn)交叉操作如圖3 所示。對(duì)于親本抗體parent1=［10 2 21 13 9 17 6 23 4］和parent2=［11 8 20 1 15 12 21 14 5］，隨機(jī)選擇兩個(gè)交叉點(diǎn)q1=4，q2=6。將兩個(gè)抗體q1和q2之間的元素交換，得到parent1,=［10 2 21 1 5 12 6 23 4］，parent2,=［11 8 20 13 8 17 19 14 5］。parent2,中有重復(fù)元素8，因此找到parent2中元素8 所在的第2 個(gè)位置，并找到parent1中第2個(gè)位置的元素為2，將parent2,第5 個(gè)位置的元素改為2。最后，得到無重復(fù)元素的子代child1=［10 2 21 1 5 12 6 23 4］和child2=［11 8 20 13 2 17 19 14 5］。

2.7.3 突變

突變指通過在抗體中引入隨機(jī)變異以增加種群多樣性，消除算法在無希望區(qū)域的停滯，探索新搜索區(qū)域的過程［24］。對(duì)于一個(gè)抗體，將其含有的元素記為child，即開放設(shè)施點(diǎn)的集合；抗體中不包含的元素記為Unopen，即未開放的設(shè)施點(diǎn)集合。隨機(jī)選擇候選設(shè)施點(diǎn)u∈child，未開放的設(shè)施點(diǎn)uˉ∈Unopen，將抗體中的u改為uˉ以實(shí)現(xiàn)突變操作。為了增加種群多樣性，重復(fù)此過程，直到突變率（突變次數(shù)）達(dá)到μ。

在實(shí)現(xiàn)突變的過程中，還應(yīng)考慮保護(hù)優(yōu)秀解的特征，因?yàn)樵诘^程中，可能已求得一些解接近于最優(yōu)解，直接對(duì)解執(zhí)行突變操作，可能會(huì)丟失已求得的優(yōu)秀解［24］。因此，在突變過程中選擇適應(yīng)度值fitness最好的進(jìn)行下一次迭代。如圖4 所示，假設(shè)抗體長(zhǎng)度l=3，突變率μ=3，當(dāng)候選設(shè)施點(diǎn)集為M={1,2,…,12}時(shí)，則需要對(duì)抗體執(zhí)行3 次突變操作，記錄每次突變操作的適應(yīng)度值，選擇適應(yīng)度值最優(yōu)的抗體進(jìn)入下一次迭代。

Fig.3 An example of two-point crossover圖3 兩點(diǎn)交叉的例子

Fig.4 An illustration of the mutation with μ=3，p=3 and N={}1,2,…,12圖4 μ=3，l=3，N={ 1,2,…,12 }的突變操作例子

3 算例分析

以上海市S 物流公司為案例，根據(jù)實(shí)地調(diào)研，S 物流公司每天由倉(cāng)庫(kù)向各網(wǎng)點(diǎn)運(yùn)輸貨物。該公司在上海市共有51 個(gè)網(wǎng)點(diǎn)分布，因此獲取51 個(gè)需求點(diǎn)的坐標(biāo)與需求量，并選取15 個(gè)候選倉(cāng)庫(kù)點(diǎn)，需求點(diǎn)的需求量為每天運(yùn)輸?shù)能囕v數(shù)。模型中各參數(shù)如表3 所示。需求點(diǎn)與設(shè)施點(diǎn)的相關(guān)數(shù)據(jù)如表1、表2 所示。

根據(jù)經(jīng)緯坐標(biāo)計(jì)算兩點(diǎn)之間的距離，使用式（12）將經(jīng)緯距離轉(zhuǎn)換為兩個(gè)節(jié)點(diǎn)i和j之間的實(shí)際行駛距離dij：

其中，(xi,yi)、(xj,yj)為兩個(gè)節(jié)點(diǎn)的經(jīng)度和緯度坐標(biāo)，6 370為地球半徑（km）。通過式/180 × π ×6 370 計(jì)算出兩點(diǎn)間的線性距離。抽取30組兩點(diǎn)間的線性距離，將其與百度地圖得到的實(shí)際行駛距離相比較，得到誤差值k。

3.1 算法參數(shù)靈敏度分析

參數(shù)的合理設(shè)置對(duì)算法的有效性和計(jì)算效率有著重要影響，算法中的參數(shù)：種群規(guī)模P=P1+P2（P1為父代群體數(shù)量,P2記憶庫(kù)容量）、迭代次數(shù)iter、記憶庫(kù)容量P2、交叉率的區(qū)間[θmin,θmax]、期望繁殖概率評(píng)估參數(shù)η、突變率μ需要進(jìn)行合理設(shè)置。參數(shù)調(diào)優(yōu)和參數(shù)控制是元啟發(fā)式算法中確定參數(shù)值的兩種常用方法［25］。參數(shù)調(diào)優(yōu)是將其他參數(shù)固定，僅變化需要測(cè)試的參數(shù)，找到求解效果最好的參數(shù)值；參數(shù)控制是將幾種參數(shù)的值進(jìn)行變化組合，找到最優(yōu)組合方式［25］。本文使用這兩種方法確定各參數(shù)值。在參數(shù)測(cè)試環(huán)節(jié)中，考慮到僅對(duì)一個(gè)案例進(jìn)行測(cè)試具有偶然性，因此將案例生成4 個(gè)不同規(guī)模的子案例并分別求解，測(cè)試參數(shù)對(duì)算法性能的影響，以尋找最優(yōu)參數(shù)組合。

3.1.1 迭代次數(shù)Iters

迭代次數(shù)在算法中起重要作用，迭代次數(shù)設(shè)置較高可能會(huì)浪費(fèi)算法運(yùn)行時(shí)間，迭代次數(shù)設(shè)置較低可能會(huì)提前結(jié)束搜索過程，無法找到最優(yōu)解。首先使用精確軟件CPLEX分別對(duì)4 個(gè)案例進(jìn)行求解，并得到最優(yōu)值；然后使用本文設(shè)計(jì)的免疫優(yōu)化算法對(duì)4 個(gè)案例分別獨(dú)立運(yùn)行10 次，取得平均結(jié)果與平均運(yùn)行時(shí)間。表4 給出了4 個(gè)案例的規(guī)模與求解情況，包括每個(gè)案例變量個(gè)數(shù)、約束條件個(gè)數(shù)、最優(yōu)解（Best）、結(jié)果平均值（BOV）、10 次求解中找到最優(yōu)解的數(shù)量（Found）、結(jié)果與最優(yōu)值的偏離程度（APD=、運(yùn)行平均時(shí)間（Time(s)）、求得最優(yōu)解的迭代次數(shù)（Iters）。

Table 1 Demands and coordinates of each demand node表1 需求點(diǎn)坐標(biāo)與需求量

Table 2 Coordinates of each facility node表2 設(shè)施點(diǎn)坐標(biāo)

Table 3 Other parameters in the model表3 模型中的其他參數(shù)

由表4 結(jié)果可知，4 個(gè)案例在150 次迭代內(nèi)均求得了最優(yōu)或接近最優(yōu)解。因此，本文設(shè)置迭代次數(shù)Iters=150。

3.1.2 種群規(guī)模P

設(shè)置種群規(guī)模，取6 個(gè)不同的參數(shù)值進(jìn)行測(cè)試。表5給出了不同的種群規(guī)模下，4 個(gè)案例進(jìn)行10 次運(yùn)行的平均測(cè)試結(jié)果，包括種群規(guī)模、平均運(yùn)行時(shí)間和APD（%）。從表5 可以看出，當(dāng)種群規(guī)模大于等于30 時(shí)，運(yùn)行時(shí)間和解的質(zhì)量較好。隨著種群規(guī)模的增大，算法計(jì)算時(shí)間也越長(zhǎng)。考慮到解的質(zhì)量和計(jì)算時(shí)間，本文設(shè)置種群規(guī)模P=30。

Table 4 Test results from 10 runs in 4 cases表4 4 個(gè)案例運(yùn)行10 次得到的測(cè)試結(jié)果

Table 5 Test results of population size表5 種群規(guī)模測(cè)試結(jié)果

3.1.3 記憶庫(kù)容量P2

記憶庫(kù)用于存儲(chǔ)每次迭代產(chǎn)生的精英抗體。精英抗體的數(shù)量在種群中占有一定比例。記憶庫(kù)容量設(shè)置過大時(shí)，算法容易陷入局部最優(yōu)；記憶庫(kù)容量設(shè)置過小時(shí)，尋找最優(yōu)解的計(jì)算時(shí)間會(huì)增加。因此，設(shè)置合理的記憶庫(kù)容量，對(duì)保留精英抗體的特征與維持種群的多樣性具有重要意義。通過設(shè)置6 個(gè)不同的比例，確定最合適的記憶庫(kù)容量。表6 給出了不同的記憶庫(kù)容量值，4 個(gè)案例運(yùn)行10 次的平均測(cè)試結(jié)果，其中，［X］表示不大于X 的最大整數(shù)。由表6 可以看出，當(dāng)記憶庫(kù)容量為［0.35*（P）］時(shí)，可以得到較好的解決方案。因此，設(shè)置P2=[0.35*(P)]，即P=30時(shí)，P2=10。

Table 6 Test results of memory capacity表6 記憶庫(kù)容量測(cè)試結(jié)果

3.1.4 交叉率［?min,?max］

交叉率用于決定抗體的交叉操作為兩點(diǎn)交叉或一點(diǎn)交叉，這對(duì)決定如何保留親本特征較為重要。在算法運(yùn)行時(shí)，與固定交叉率相比，可變的交叉率可以有更大的靈活性去探索更有前景的搜索區(qū)域。通過設(shè)置18 個(gè)不同的取值區(qū)間，確定最合適的交叉率區(qū)間。表7 給出了不同的交叉區(qū)間下，4 個(gè)案例運(yùn)行10 次的平均測(cè)試結(jié)果。由表7 所示的測(cè)試結(jié)果可以看出，在區(qū)間［0.5，1］和［0，0.9］內(nèi)，計(jì)算得到的APD（%）值和計(jì)算時(shí)間較好。

Table 7 Test results of crossover rate表7 交叉率測(cè)試結(jié)果

3.1.5 突變率μ

變異是遺傳操作的主要算子之一，通過變異可以搜索新的區(qū)域、逃離當(dāng)前局部最優(yōu)情況。確定合適的突變率可以決定抗體變異強(qiáng)度。突變率和交叉率一樣重要，會(huì)對(duì)改進(jìn)免疫優(yōu)化算法的計(jì)算效率產(chǎn)生較大影響。設(shè)置較小的突變率容易在尋優(yōu)過程中陷入局部最優(yōu)，設(shè)置較大的突變率會(huì)失去已得到的優(yōu)秀特征。表8 給出了4 個(gè)案例在不同突變率下運(yùn)行10 次的平均測(cè)試結(jié)果。從表8 可以看出，當(dāng)突變率為0.5 和0.6 時(shí)，免疫優(yōu)化算法的性能更好，可以在較短時(shí)間內(nèi)求得較好的解。

Table 8 Test results of mutation rate表8 突變率測(cè)試結(jié)果

3.1.6 參數(shù)η

期望繁殖概率表示對(duì)抗體進(jìn)行評(píng)估，參數(shù)η用于為抗體對(duì)抗原的識(shí)別程度、抗體密度賦予不同權(quán)重，以此得到抗體的期望繁殖概率。如表9 所示，當(dāng)參數(shù)η設(shè)置為0.8 或0.85 時(shí)，算法運(yùn)行時(shí)間較短，且APD（%）較低，求得解的質(zhì)量較高。

Table 9 Test results of parameter η表9 參數(shù)η 測(cè)試結(jié)果

3.1.7 交叉率、突變率和參數(shù)η的組合方式

不同的參數(shù)組合對(duì)算法性能也有很大影響。如上所述，交叉率、突變率和參數(shù)η有多個(gè)較優(yōu)值，將不同的參數(shù)進(jìn)行組合，得到8 種組合方式。使用每種組合方式對(duì)4 個(gè)案例各進(jìn)行10 次運(yùn)行求解，得到平均運(yùn)行時(shí)間與APD（%）值。不同參數(shù)組合的測(cè)試結(jié)果如表10 所示，從測(cè)試的運(yùn)行時(shí)間與APD（%）值可以看出，當(dāng)參數(shù)組合［?min,?max］=［0,0.9］、μ=0.5、η=0.8 時(shí)，算法求解時(shí)間與解的質(zhì)量最優(yōu)。

Table 10 Test results of different parameter combinations表10 不同參數(shù)組合的測(cè)試結(jié)果

基于上述討論和測(cè)試，算法參數(shù)設(shè)置情況為：迭代次數(shù)Iters=150、種群規(guī)模P=30、記憶庫(kù)容量P2=10、交叉率區(qū)間［?min,?max］=［0,0.9］、突變率μ=0.5、抗體評(píng)估參數(shù)η=0.8。

3.2 結(jié)果分析

通過上述改進(jìn)的免疫優(yōu)化算法及參數(shù)設(shè)置，對(duì)S 物流公司的案例進(jìn)行求解分析。實(shí)驗(yàn)環(huán)境為Intel（R）Core i5-8250u CPU @ 1.60GHz 8.00GB 內(nèi)存，操作系統(tǒng)為64 位Win?dows 10，使用Matlab R2017b 進(jìn)行編程。求解得到目標(biāo)函數(shù)為9.116 06×105，運(yùn)行時(shí)間為45.70s。所選擇的設(shè)施點(diǎn)為3、5、6、8、9、10、11、12、13、15，需求點(diǎn)與設(shè)施點(diǎn)分布情況如圖5 所示（彩圖掃OSID 碼可見）。圖5 中的黃色圓點(diǎn)為需求點(diǎn)，紅色星星為所選的設(shè)施點(diǎn)，綠色圓點(diǎn)表示未被選擇的設(shè)施點(diǎn)，連線表明需求點(diǎn)與設(shè)施點(diǎn)之間的關(guān)系。從圖5 可以看出，每個(gè)需求點(diǎn)均有指定的設(shè)施點(diǎn)進(jìn)行服務(wù)，且需求點(diǎn)均被分配給距離較近的設(shè)施點(diǎn)。表11 為設(shè)施點(diǎn)所服務(wù)的需求點(diǎn)和服務(wù)的總需求量，可以看出，每個(gè)設(shè)施點(diǎn)服務(wù)的總需求量均不超過服務(wù)容量限制。因此，本文的倉(cāng)庫(kù)選址模型有效可行，能夠解決物流公司的倉(cāng)庫(kù)選址與需求分配問題，并有效降低車輛成本與固定成本，提高企業(yè)對(duì)車輛及倉(cāng)庫(kù)的控制。

Table 11 Relationship between facility points and demand points表11 設(shè)施點(diǎn)與需求點(diǎn)分配情況

Fig.5 Distribution of facility and demand points圖5 設(shè)施點(diǎn)與需求點(diǎn)分布

為了驗(yàn)證改進(jìn)免疫優(yōu)化算法的有效性，本文使用改進(jìn)免疫優(yōu)化算法的求解結(jié)果與軟件CPLEX 精確求得的精確解進(jìn)行對(duì)比分析。如表12 所示，免疫優(yōu)化算法與CPLEX求解得到的結(jié)果相同，且免疫優(yōu)化算法運(yùn)行時(shí)間更短。因此，免疫優(yōu)化算法可有效地解決倉(cāng)庫(kù)選址問題。

Table 12 Comparison between improved immune optimization algorithm and CPLEX表12 改進(jìn)的免疫優(yōu)化算法與CPLEX 求解對(duì)比

為了驗(yàn)證改進(jìn)免疫優(yōu)化算法的求解性能，將其優(yōu)化結(jié)果與經(jīng)典免疫優(yōu)化算法的求解結(jié)果進(jìn)行對(duì)比分析。圖6 和圖7 分別為改進(jìn)的免疫優(yōu)化算法與經(jīng)典免疫優(yōu)化算法的收斂曲線。由圖6 和圖7 可以看出，改進(jìn)的免疫優(yōu)化算法無論是收斂速度，還是結(jié)果準(zhǔn)確度都優(yōu)于經(jīng)典免疫優(yōu)化算法。

Fig.6 Convergence curve of classical immune algorithm圖6 經(jīng)典免疫優(yōu)化算法收斂曲線

Fig.7 Convergence curve of improved immune algorithm圖7 改進(jìn)免疫優(yōu)化算法收斂曲線

4 結(jié)語(yǔ)

本文結(jié)合倉(cāng)庫(kù)設(shè)施選址特點(diǎn)，建立了考慮容量約束的倉(cāng)庫(kù)選址模型。根據(jù)選址模型特點(diǎn)，設(shè)計(jì)了改進(jìn)的免疫優(yōu)化算法對(duì)案例進(jìn)行求解。在算法中設(shè)計(jì)了兩種交叉算子和變異算子，使得算法可快速收斂到最優(yōu)解，降低算法運(yùn)行時(shí)間。本文還對(duì)改進(jìn)免疫優(yōu)化算法的參數(shù)進(jìn)行詳細(xì)分析，找到最優(yōu)參數(shù)組合方式，提高算法性能。最后，對(duì)案例進(jìn)行求解，驗(yàn)證了模型和算法的有效性與可行性。本文提出的倉(cāng)庫(kù)設(shè)施選址方法可為決策人員選擇最佳布局方案提供科學(xué)合理參考。

在下一步研究中，將進(jìn)一步細(xì)化影響倉(cāng)庫(kù)選址的各因素，并考慮服務(wù)時(shí)間窗的約束，更合理地在模型中體現(xiàn)車輛行駛實(shí)際情況，以增加模型求解的準(zhǔn)確性和實(shí)際應(yīng)用價(jià)值。