均勻克隆選擇算法在城市配送中心選址中的應用

孫 欣，王宇嘉，林煒星

(上海工程技術(shù)大學 電子電氣工程學院，上海 201620)

0 引言

隨著中國互聯(lián)網(wǎng)經(jīng)濟的快速發(fā)展，在一定的程度上帶動了中國電子商務(wù)的行進腳步。現(xiàn)在，不論是“六一八年中購物節(jié)” 還是“雙十一全球購物節(jié)”等一些電商購物促銷活動，城市物流配送的時效性變得非常重要，尤其是一些大城市的消費者們，需求量和購買力都非常大，此時城市配送中心的選址就成為提高時效性的關(guān)鍵[1]。城市配送中心是物流配送系統(tǒng)的重要支撐，也是面向客戶的主要戰(zhàn)略部署，更是城市配送中心點和需求點之間的重要紐帶。一個合適的城市配送中心選址方案可以很大程度上減少物流運輸費用、提高經(jīng)濟效益、減少環(huán)境污染等[2]。

城市配送中心選址問題是指在某些約束條件下，使運營成本最低、總運輸?shù)臅r間最短、總運輸?shù)木嚯x最短等目標達到最優(yōu)，屬于NP-hard問題[3]。沈默等[4]分析了重心法的優(yōu)缺點，并將重心法應用在電商蘇寧的物流配送中心選址問題上。劉倩等[5]提出了一種物流運籌學的方法解決物流配送中心選址問題，并在實例中驗證了該方法的有效性。但是，傳統(tǒng)的數(shù)學方法計算得出的理論結(jié)果，會與實際位置產(chǎn)生一定的偏差，而且計算時間長，所占內(nèi)存空間也非常大，從而給求解帶來了困難。

近年來，啟發(fā)式選址算法成為眾多學者研究選址問題的有效工具[6]。文獻[7]中引入一種領(lǐng)域均值和邊界緩沖墻的粒子群優(yōu)化算法求解物流配送中心選址問題，當需求量越大，算法效果越佳。文獻[8]中引入博弈的思想，將物流配送與客戶利益放在一起考慮，建立雙層規(guī)劃模型。文獻[9]中使用一種Logistic混沌系統(tǒng)方法，將其與果蠅優(yōu)化算法相結(jié)合，實現(xiàn)配送路徑達到最優(yōu)，節(jié)約運輸成本。文獻[10]中提出了一種Laplace分布偽反向新的搜索機制來改善蜘蛛猴優(yōu)化算法，增強算法的收斂性和可行性。但是，上述的啟發(fā)式算法自身存在一定缺陷。在尋找最優(yōu)解的過程中，會出現(xiàn)搜索精度不高，優(yōu)化結(jié)果不理想的情況。在城市配送中心選址問題上，會搜索出一些局部最優(yōu)解,不容易得到最好的中心選址配送方案。因此，能夠?qū)ふ乙环N全局優(yōu)化的啟發(fā)式算法就特別關(guān)鍵。

人工免疫優(yōu)化算法啟發(fā)于生物的免疫系統(tǒng)機制，是在眾多國內(nèi)外學者們研究中逐漸發(fā)展起來的一種進化算法，利用免疫系統(tǒng)防護策略讓抗體種群的多樣性得到保障。人工免疫優(yōu)化算法具有強大的自我調(diào)節(jié)能力，能夠擺脫一些實際優(yōu)化問題中出現(xiàn)的陷入局部最優(yōu)，能夠得到全局的最優(yōu)解，因而被眾多學者廣泛應用[11]。文獻[12]中引入配送時間和與需求量共同決定綜合權(quán)值的免疫優(yōu)化算法來驗證配送時間對物流配送中心選址問題的實際影響。文獻[13]中引用了一種免疫疫苗接種的方法，對克隆選擇算進行一些改進，并將該方法應用于倉儲布局優(yōu)化設(shè)計中。Dou等[14]提出了一種免疫wolf-column混合算法來求冷藏食品的配送中心選址問題。Ping等[15]提出一種基于相似性向量距離選擇的方法改善人工免疫算法解決物流配送中心位置問題的收斂性。

但是，求解城市配送中心選址問題上的免疫優(yōu)化算法仍然會存在“早熟”現(xiàn)象，會導致收斂的效果不理想，收斂速度比較慢等一些問題。針對上述問題，本文提出了一種均勻克隆選擇算法（Uniform Clone Selection Algorithm，UCSA）。通過均勻克隆選擇策略減少計算量，加快收斂速度，克隆后的抗體采用全局變異策略增加了種群多樣性。同時，本文引入基因清除策略，避免抗體種群早熟，提高抗體種群的收斂性。最終，使用該算法解決實際的城市配送中心選址問題。

1 選址問題描述

城市配送中心選址問題可以歸結(jié)為一個好的配送中心選址方案能夠使物流運輸?shù)馁M用最小化，并且配送的效率最大化。本文對城市配送中心選址數(shù)學模型做出以下假設(shè)：

1）城市配送中心存儲的商品規(guī)模可以實現(xiàn)其在配送范圍內(nèi)所有需求點的商品需求量；

2）某個區(qū)域內(nèi)的需求點有且只由一個城市配送中心提供所需要的商品，不允許交叉供貨；

3）一個城市配送中心可以同時供應其配送區(qū)域范圍內(nèi)的多個需求點；

4）在城市配送中心選址問題中，城市配送中心的地址是從各個需求點中產(chǎn)生，而且城市配送中心的數(shù)量是固定的；

5）忽略城市配送中心與生產(chǎn)廠商之間的物流運費；

6）不考慮時間因素。

基于上述假設(shè)，本文建立以城市配送范圍內(nèi)的各個需求點的需求量與城市配送中心到需求點的距離乘積最小化為優(yōu)化目標的數(shù)學模型。該數(shù)學模型需要在滿足上述約束條件下，能夠從規(guī)定城市配送區(qū)域內(nèi)的n個需求點里面找到m個作為整個城市的配送中心來配送商品，如式(1)～式(6)所示。該模型的目標函數(shù)及約束條件為：

其中，N={1,2,L,n}是城市配送范圍內(nèi)的所有需求點序號集合；Ci為到城市內(nèi)的各個需求點i的物流配送距離小于S的城市配送中心選址備選方案集合（其中，S為被選擇為城市配送中心服務(wù)各個需求點的最大配送距離），i∈N,Ci?N；Ri表示需求點i的需求量；Dij是中心j與需求點i的最近距離；Zij為0～1的一個變量，它表示區(qū)域內(nèi)需求點i和城市配送中心j的供求關(guān)系，當Zij=1時，意味著城市配送中心j給城市所在區(qū)域內(nèi)的需求點i提供配送服務(wù),否則Zij=0；hj是0～1的一個變量，當hj=1時，意味著城市所在區(qū)域內(nèi)的需求點j被選擇作為城市配送中心，否則hj=0；p表示城市配送中心數(shù)。

2 均勻克隆選擇算法

2.1 克隆選擇算法

Burnet等[16]在1959年提出生物免疫系統(tǒng)中識別抗原的細胞會被保留下來并進行細胞增殖活動，否則會被淘汰，克隆選擇學說類似于達爾文的進化論，也就是所謂的“物競天擇，適者生存”進化法則。生物免疫系統(tǒng)會產(chǎn)生很多抗體細胞，這一過程被稱作克隆擴增。De Castro等[17]在2002受到免疫系統(tǒng)克隆選擇理論的啟發(fā)，提出了克隆選擇算法。其中，克隆選擇過程與達爾文的進化思想類似,不同的是它應用于生物免疫系統(tǒng)內(nèi)識別抗原的細胞群體，是一種基于免疫系統(tǒng)自身的進化算法。

在基本的克隆選擇算法（Clone Selection Algorithm,CSA）中，主要涉及三種操作，即克隆、超突變和選擇。基本的一個CSA流程描述如圖1所示。

圖1 CSA流程圖

2.2 均勻克隆選擇策略

在求解城市配送中心選址問題中，抗原識別表示為城市配送中心選址的問題識別，抗原表示為待優(yōu)化目標函數(shù)和約束條件，抗體表示為每一個城市配送中心選址的備選方案。克隆表示為利用均勻選擇策略產(chǎn)生新的子代抗體。抗體選擇表示為利用全局變異策略和基因清除策略去除多余抗體。

現(xiàn)舉例說明如下：本文采用的是實數(shù)編碼方式，在城市配送中心選址問題中存在31個需求點，編號為1～31，從中選擇其中6個作為整個城市的配送中心地址，假設(shè)被選中的候選方案中的一個編號為[1,2,3,4,5,6]，那么它就構(gòu)成一個抗體xi，記作xi=[1,2,3,4,5,6]，i=[1,2,L,n]，抗體長度記為L，L表示城市配送中心選址的數(shù)量，所有的抗體xi構(gòu)成了的抗體種群記為x={x1,x2,L,xn}。

在UCSA中，抗體與抗原之間的親和度，通常作為適應度評估，表示抗體的優(yōu)劣性，如式(7)所示：

F(xi)為抗體xi對應的目標函數(shù)值，F(xiàn)min、Fmax分別表示目標函數(shù)最大、最小值，A(xi)是親和度。親和度計算公式可根據(jù)實際問題進行設(shè)計。按照式(7)計算得出的目標函數(shù)值越小，則親和度越高。

在UCSA中，抗體之間的親和度,區(qū)別于上述的適應性評估，它是為評估抗體種群中抗體xi與抗體xj之間的相似度S(xi,xj)。計算公式如式(8)所示：

式(8)中，β表示抗體xi與抗體xj相同的位數(shù)，L為抗體長度,(i,j=1,2,L,n)。

在UCSA中，抗體在整個種群中的濃度大小可以表示種群多樣性的好壞，抗體的濃度越大，抗體種群的多樣性就越差。抗體xi在所有抗體中所占的相似度來表示抗體濃度C(xi)。計算公式如式(9)所示：

在UCSA中，采用均勻克隆選擇策略進行抗體增殖，每一次只選擇親和度排在前m抗體作為父代，之后按照濃度的高低來決定每一個被選擇的父代抗體的克隆數(shù)目是多少。計算公式如式(10)所示：

2.3 全局變異策略

克隆后的每一個抗體實行單一變異方式，不能滿足抗體種群多樣性和抗體分布均勻的需求，基于此類不足，對免疫克隆操作后的抗體進行全局變異，將被克隆后的抗體基因一分為二，前半段基因進行高斯變異，后半段基因進行柯西變異。變異過后的抗體，仍然需要與原抗體按照親和度進行更新，保留親和度更高的抗體。

高斯變異之所以被大家如此喜歡，是因為它能夠在很小范圍內(nèi)具有良好的搜索能力，并且它在處理城市配送中心選址優(yōu)化問題中，能夠在抗體種群中以較大的概率產(chǎn)生較小的變異值。高斯變異形式如式(12)所示：

其中N(0,1)表示的是均值為0，方差為1的一維正態(tài)分布隨機數(shù)。高斯變異的本質(zhì)是充分利用當前抗體種群的信息進行擾動，這樣就有利于跳出局部最優(yōu)，從而使均勻克隆選擇算法進行全局搜索，達到收斂的目的。

柯西變異與高斯變異不同，它能夠產(chǎn)生一個遠離原點的隨機數(shù)，所以搜索范圍要比高斯變異更大一些。柯西變異的形式如式(13)所示：

其中C(0,1)表示以0為中心，尺度參數(shù)為1的Cauchy分布隨機數(shù)。柯西變異之后的抗體產(chǎn)生的變化更大，這樣就可以使均勻克隆選擇算法能夠跳出局部最優(yōu)，同時也能夠提高了搜索的速度。

2.4 抗體種群的補充與更新

本文提出的均勻克隆選擇算法中，如果抗體種群在進行克隆前抗體數(shù)量少于預期或者親和度較差，或者克隆后抗體數(shù)量較少，這時利用MATLAB中的隨機函數(shù)，產(chǎn)生一些候選抗體補充抗體種群。在處理復雜約束條件下的非線性優(yōu)化問題時，往往存在早熟收斂問題，停滯是一種常見且難以避免的情況。在種群進化前期設(shè)置一個自我更新檢測機制，如果迭代前T次，抗體xi沒有變化，那么它將被親和度值排在它前面的抗體隨機替換。計算公式如式(14)所示：

當抗體種群中的抗體數(shù)量超過設(shè)定值的時候，則按照基于歸一化目標函數(shù)值的歐幾里德距離進行刪減，直到不再超出設(shè)定值為止，那些親和度高且分布均勻的抗體會被保留下來，這樣就可以保證了種群的多樣性，防止均勻克隆選擇算法出現(xiàn)收斂速度非常慢，甚至抗體退化的現(xiàn)象。計算公式如式(15)所示：

地方政府應注重推動本地產(chǎn)業(yè)與技術(shù)創(chuàng)新的融合發(fā)展。通過產(chǎn)業(yè)的發(fā)展和承接以及產(chǎn)業(yè)集聚的溢出效應促進各地區(qū)技術(shù)創(chuàng)新能力的提高，并利用知識、技術(shù)的創(chuàng)新帶動產(chǎn)業(yè)發(fā)展，吸引更多的產(chǎn)業(yè)集聚。此外，政府在產(chǎn)業(yè)集聚的成長與持續(xù)過程中，要鼓勵建立資源信息共享、人才技術(shù)等方面的長期有效的合作機制，從而降低企業(yè)的學習成本，提高集聚區(qū)域內(nèi)各企業(yè)之間的信任程度，為集聚企業(yè)的創(chuàng)新行為創(chuàng)造良好的氛圍。

綜上所述，本文提出的UCSA流程如圖2所示，UCSA步驟如下：

圖2 UCSA流程圖

1）設(shè)置均勻克隆選擇算法的基本參數(shù)。

2）初始抗體種群生成，記為x={x1,x2,L,xn}。

3）計算抗體與抗原的親和度，利用式(7)，計算抗體種群中每一個抗體的A(xi)值，將所有抗體按照親和度降序排列，取前m名抗體作為父代抗體，記為Xc={x1,x2,L,xm}。

4）使用均勻克隆選擇策略決定克隆數(shù)量，利用式(8)計算抗體xi與抗體xj之間的相似度B(xi,xj)，利用式(9)計算抗體濃度C(xi)，利用式(10)計算父代抗體的克隆數(shù)量Qxi。克隆后生成的抗體種群記為

5）對克隆后的抗體采用全局變異策略，按照式(12)，式(13)進行高斯變異和柯西變異，得到新的抗體子代，變異后記為，xi與需要再一次評估親和度。

6）抗體種群更新，按照式(15)，計算歐幾里德距離，對抗體種群進行篩選，以此保證種群的多樣性。

7）基因清除策略，按照式(14)，如果抗體xi迭代次數(shù)小于T次，而且xi迭代后沒有變化，那么它將被親和度值排在它前面的抗體中隨機選擇一位替換為。

8）記憶細胞更新，選擇C個抗體存儲到記憶細胞中，并且計算記憶細胞與抗原匹配度，并且計算記憶細胞與抗原匹配度。

9）滿足終止條件，結(jié)果輸出，否則重復步驟3）～8）。

3 實驗結(jié)果

3.1 參數(shù)設(shè)置

為了證明均勻克隆選擇算法在城市配送中心選址問題上的有效性，選擇31個城市配送需求點的具體實例。城市位置坐標和需求量按照表1給出。本次實驗是在win10操作系統(tǒng)，inter(R) Core(TM)，i5-8250U處理器的PC上操作完成，使用的仿真軟件為MATLAB,版本為2019b。

表1 31個城市位置坐標和其對應的需求量

首先，設(shè)置均勻克隆選擇算法的基本參數(shù)，抗體種群規(guī)模E=100、預設(shè)父代抗體個數(shù)m=20、克隆調(diào)節(jié)參數(shù)θ=2、最大迭代次數(shù)Itermax=100、迭代設(shè)定值T=10、配送中心數(shù)L=6、記憶細胞數(shù)C=10，Qxi取值范圍為[1,10]，C(xi)取值范圍為[0.2,1]。

本文采用MATLAB 2019b軟件進行實驗仿真，并對參考文獻[7]中的改進粒子群算法，參考文獻[9]中的改進果蠅優(yōu)化算法，文獻[13]中的改進克隆選擇算法，以及本文提出的均勻克隆選擇算法分別在6個城市配送中心選址問題上進行求解。在31個城市需求點中選出6個需求點作為城市配送中心共有種方案，每個算法各自運行30次，實驗最后對4個算法的仿真結(jié)果進行對比，具體實驗結(jié)果如表2所示。

表2 4種算法實驗結(jié)果對比

3.2 實驗對比分析

從表2 的實驗結(jié)果可以看出，文獻[7]最優(yōu)值為592880，文獻[9]最優(yōu)值為568820，文獻[13]最優(yōu)值為550581，本文所提的均勻克隆選擇算法最優(yōu)值為549600，從實驗結(jié)果可以看出，本文所提算法的最優(yōu)值最小，收斂性最好。這就表示在城市配送中心選址問題中，本文算法提供的中心選址方案是所有算法中運輸費用最低、配送效率最高的，優(yōu)化效果也是最好的。從表2中還可以看出，文獻[7]迭代次數(shù)為45,文獻[9]迭代次數(shù)為38，文獻[13]迭代次數(shù)為18，本文所提算法迭代次數(shù)為14，對比實驗結(jié)果可知，本文所提算法比文獻[7,9,13]所提算法收斂速度更快，運行時間最短，僅為9s。綜上所述，均勻克隆選擇算法在求解6個城市配送中心選址問題上優(yōu)化效果最佳。四種算法的收斂曲線圖如圖3所示。

圖3 4種算法收斂曲線對比圖

在同等實驗條件下，經(jīng)過30次實驗仿真后，本文所提的均勻克隆選擇算法在城市配送中心選址問題上的最優(yōu)實驗結(jié)果的最優(yōu)適應度值，平均適應度值收斂過程曲線如下圖4所示，最優(yōu)城市配送中心選址圖如圖5所示。

圖4 均勻克隆選擇算法收斂曲線圖

圖5 均勻克隆選擇算法城市配送中心選址圖

本文所提的均勻克隆選擇算法在城市配送中心選址問題上的最優(yōu)解決方案如表3所示，表3中城市配送中心對應的城市中心編號為[5,9,12,17,20,27]，該6個中心點為其他各個需求點提供配送服務(wù)的具體配送方案如表3所示。

表3 均勻克隆選擇算法在城市配送中心選址上的最優(yōu)解決方案

4 結(jié)語

以城市配送中心選址問題建立以城市配送范圍內(nèi)的各個需求點的需求量與城市配送中心到需求點的距離乘積最小化為優(yōu)化目標的數(shù)學模型，并提出均勻克隆選擇算法求解該模型。該算法采用一種均勻克隆選擇策略，提高收斂速度，利用全局變異策略，增加了抗體種群的多樣性。最后，引入基因清除策略，避免抗體種群出現(xiàn)“早熟”的現(xiàn)象。實驗結(jié)果表明，與其它3種算法相比，本文所提算法的收斂速度更快，迭代次數(shù)更少，運輸成本最小，配送效率最高，在求解多約束條件下的城市配送中心選址問題上取得令人滿意的優(yōu)化結(jié)果。