基于免疫算法的地下物流中轉(zhuǎn)分配節(jié)點(diǎn)選址研究

劉桂汝 魏赟

摘要：互聯(lián)網(wǎng)加速了物流業(yè)發(fā)展，地下物流網(wǎng)絡(luò)節(jié)點(diǎn)選址成為新的研究熱點(diǎn)。將二分K-均值算法和免疫算法相結(jié)合，對(duì)物流中轉(zhuǎn)分配節(jié)點(diǎn)（一、二級(jí)節(jié)點(diǎn)）選址進(jìn)行了研究。首先根據(jù)問題的約束條件和優(yōu)化目標(biāo)建立物流一、二級(jí)節(jié)點(diǎn)選址數(shù)學(xué)模型，然后采用二分K-均值算法和免疫算法求解最佳一、二級(jí)節(jié)點(diǎn)選址方案。對(duì)南京市仙林區(qū)110個(gè)物流節(jié)點(diǎn)分配方案進(jìn)行實(shí)驗(yàn)，結(jié)果表明該算法能很好地解決組合優(yōu)化問題。

關(guān)鍵詞：免疫算法；二分K-均值算法；地下物流系統(tǒng)；組合優(yōu)化；節(jié)點(diǎn)選址

DOIDOI：10.11907/rjdk.173155

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）008-0169-05

英文摘要Abstract：The Internet accelerates the development of the logistics industry.A more efficient underground logistics system in cities has become a new research hotspot.We propose an immune algorithm based on the transfer of distribution nodes （first and second levels of nodes） site selection.Firstly，by considering the constraints and optimization objectives of the problem，a mathematic model of first and second level nodes in logistics are established，and then the best one or two node location model is solved by immune algorithm.Finally，the test on the 110 logistics nodes in Xianlin District of Nanjing is conducted and it is concluded that 17 second-level relay nodes and nine first-level relay nodes need to be established，which verifies that the algorithm can well solve the combinatorial optimization problem.

英文關(guān)鍵詞Key Words：immune optimization algorithm ；bisecting K-means algorithm； underground logistics system； combinatorial optimization； node location

0 引言

隨著電商的發(fā)展，城市道路上流轉(zhuǎn)貨物越來越多。大型貨車的增多使道路越來越擁擠，地下物流系統(tǒng)[1]概念隨之提出，而物流中轉(zhuǎn)節(jié)點(diǎn)組合優(yōu)化模型因其未知數(shù)量多，非線性度和復(fù)雜度而困擾模型的求解。

免疫系統(tǒng)作為一種新興的生物信息處理機(jī)制近年受到關(guān)注。免疫算法[2-4]是受生物免疫系統(tǒng)啟發(fā)，在免疫學(xué)理論基礎(chǔ)上發(fā)展起來的一種新興智能計(jì)算方法。此算法強(qiáng)調(diào)群體中個(gè)體之間的信息交換，克服一般尋優(yōu)過程尤其是多峰函數(shù)尋優(yōu)過程中難處理的“早熟”問題，最終求得全局最優(yōu)解。本文通過二分K-均值算法[5]與免疫算法相結(jié)合解決組合優(yōu)化問題。二分K-均值算法不受初始化問題影響，因?yàn)檫@里不存在隨機(jī)點(diǎn)的選取，且每一步都保證了誤差最小。將110個(gè)物流節(jié)點(diǎn)進(jìn)行聚類，求解出二級(jí)中轉(zhuǎn)節(jié)點(diǎn)的位置，在此基礎(chǔ)上利用免疫算法以最少預(yù)算為約束對(duì)一級(jí)中轉(zhuǎn)節(jié)點(diǎn)進(jìn)行選取，驗(yàn)證了算法的可行性。

1 地下物流系統(tǒng)

地下物流系統(tǒng)（Underground Logistics System）[6-7]指城市內(nèi)部及城市間通過類似地鐵的地下管道運(yùn)輸貨物的供應(yīng)系統(tǒng)。該系統(tǒng)先將各地的貨物通過各種運(yùn)輸方式運(yùn)到城市外圍的物流園區(qū)、機(jī)場(chǎng)、火車貨運(yùn)站等，經(jīng)過處理后進(jìn)入地下。無人駕駛技術(shù)的出現(xiàn)，加速了地下物流系統(tǒng)的發(fā)展。除了需要考慮基本的運(yùn)輸單元以及為實(shí)現(xiàn)高度自動(dòng)化和準(zhǔn)確化而采用的自動(dòng)導(dǎo)航系統(tǒng)外，地下物流系統(tǒng)的網(wǎng)絡(luò)形態(tài)和中轉(zhuǎn)分配節(jié)點(diǎn)位置直接影響著物流系統(tǒng)的運(yùn)轉(zhuǎn)效率，也直接影響該系統(tǒng)結(jié)構(gòu)的合理性、工程投資以及經(jīng)濟(jì)效益和社會(huì)效益。本文將二分K-均值算法與免疫算法相結(jié)合，應(yīng)用于物流中轉(zhuǎn)節(jié)點(diǎn)選址問題中，最終從候選節(jié)點(diǎn)選出更為科學(xué)、合理的節(jié)點(diǎn)。

2 基于二分K-均值算法的二級(jí)中轉(zhuǎn)節(jié)點(diǎn)選取

在物流中心點(diǎn)確定過程中，二級(jí)中轉(zhuǎn)節(jié)點(diǎn)的選取問題是要得到局部最小而不是全局最小，二分K-均值算法可以很好地解決此問題。該算法首先將所有點(diǎn)作為一個(gè)簇，然后將簇一分為二，之后選擇其中一個(gè)簇繼續(xù)劃分，選擇哪一個(gè)簇進(jìn)行劃分取決于對(duì)其劃分是否可以最大程度降低SSE值。SSE值（誤差平方和）越小表示數(shù)據(jù)點(diǎn)越接近于質(zhì)心，聚類效果也越好。選擇SSE最大的簇進(jìn)行劃分，基于SSE的劃分過程不斷重復(fù)，直到得到用戶指定的簇?cái)?shù)目為止。

3 基于免疫算法的節(jié)點(diǎn)優(yōu)化

傳統(tǒng)算法[8]無法避免因節(jié)點(diǎn)位置、地下物流網(wǎng)結(jié)構(gòu)變化引起的干擾，降低了地下物流網(wǎng)節(jié)點(diǎn)分配的有效性。本文提出一種基于免疫優(yōu)化算法的地下物流網(wǎng)[9-10]中轉(zhuǎn)節(jié)點(diǎn)分配方法。免疫算法來源于生物免疫系統(tǒng)，生物免疫系統(tǒng)的概念與免疫算法的對(duì)應(yīng)關(guān)系如表1所示。

3.1 免疫算法流程

免疫算法流程如圖1所示，實(shí)現(xiàn)步驟如下：

①產(chǎn)生初始抗體群。隨機(jī)產(chǎn)生26個(gè)個(gè)體，并從記憶庫(kù)里抽取9個(gè)個(gè)體形成初始群體；

②對(duì)群體中的抗體進(jìn)行評(píng)價(jià)，評(píng)價(jià)以個(gè)體的期望繁殖率p為標(biāo)準(zhǔn)；

③形成父代群體。將初始群體按期望繁殖率p進(jìn)行降序排列，并提取前26個(gè)個(gè)體構(gòu)成父代群體，同時(shí)取前9個(gè)個(gè)體存入記憶庫(kù)；

④對(duì)結(jié)束條件進(jìn)行判斷，如果是則結(jié)束，否就進(jìn)行下一步操作；

⑤新群體產(chǎn)生?；诓襟E④的計(jì)算結(jié)果對(duì)抗體群體進(jìn)行選擇、交叉、變異等操作，得到新群體，再?gòu)挠洃泿?kù)中取出記憶的個(gè)體，共同構(gòu)成新一代群體；

⑥轉(zhuǎn)去執(zhí)行步驟③。

3.2 初始群體產(chǎn)生

如果記憶庫(kù)非空，則初始抗體群從記憶庫(kù)中選擇生成，否則在可行解空間隨機(jī)產(chǎn)生初始抗體群。此處采用簡(jiǎn)單編碼方式。每個(gè)選址方案可形成一個(gè)長(zhǎng)度為x的抗體（x表示一級(jí)節(jié)點(diǎn)個(gè)數(shù)），每個(gè)抗體代表選為一級(jí)節(jié)點(diǎn)的序列。例如，1～26是代表二級(jí)節(jié)點(diǎn)的序號(hào)，從中選擇9個(gè)作為一級(jí)節(jié)點(diǎn)，免疫算法所產(chǎn)生的[1，2，4，9，10，16，18，20，25]為產(chǎn)生的可行解，表示[1，2，4，9，10，16，18，20，25]被改變?yōu)橐患?jí)節(jié)點(diǎn)。

3.3 解的多樣性評(píng)價(jià)

由式（5）可見，個(gè)體適應(yīng)度值越高，則期望繁殖率越大；個(gè)體濃度越大，則期望繁殖率也越大。這樣既鼓勵(lì)了適應(yīng)度高的個(gè)體，又抑制了濃度高的個(gè)體，從而確保了個(gè)體多樣性。

3.4 免疫操作

選擇：依照輪盤賭選擇機(jī)制進(jìn)行，個(gè)體選擇概率為式（5）計(jì)算的期望繁殖概率；

交叉：基于免疫優(yōu)化算法的物流中轉(zhuǎn)節(jié)點(diǎn)選址模型[12-14]采用單點(diǎn)交叉操作；

變異：采用常用的變異方法，即隨機(jī)選擇變異位進(jìn)行變異操作。

4 實(shí)驗(yàn)結(jié)果分析

圖2所示為南京市仙林區(qū)貨運(yùn)區(qū)域劃分，小紅點(diǎn)為節(jié)點(diǎn)，紅點(diǎn)旁邊的數(shù)字代表貨運(yùn)站標(biāo)號(hào)，1、2、3、4代表4個(gè)物流園區(qū)?，F(xiàn)在需要再設(shè)置一些中轉(zhuǎn)分配節(jié)點(diǎn)（一級(jí)節(jié)點(diǎn)、二級(jí)節(jié)點(diǎn)）。由于一級(jí)節(jié)點(diǎn)與二級(jí)節(jié)點(diǎn)都遵循服務(wù)范圍3km，也就是說從一級(jí)節(jié)點(diǎn)、二級(jí)節(jié)點(diǎn)到路面上的服務(wù)節(jié)點(diǎn)范圍是3km，采用二分K-均值算法對(duì)這些小節(jié)點(diǎn)進(jìn)行聚類。

4.1 二分K-均值優(yōu)化二級(jí)節(jié)點(diǎn)分布

求解二級(jí)節(jié)點(diǎn)時(shí)，將交通貨運(yùn)區(qū)域劃分圖中的每個(gè)節(jié)點(diǎn)視為聚類對(duì)象，利用二分K-均值算法進(jìn)行聚類，所得的質(zhì)心[15]視為所求的二級(jí)節(jié)點(diǎn)。算法得出的二級(jí)節(jié)點(diǎn)（聚類中心點(diǎn)）個(gè)數(shù)及位置分布如圖3所示。由于二級(jí)節(jié)點(diǎn)要將每個(gè)區(qū)域的中心點(diǎn)覆蓋，經(jīng)過多次聚類，得出當(dāng)算法將所有區(qū)域聚成了17個(gè)簇時(shí)，能將所有的中心節(jié)點(diǎn)覆蓋，因此，選擇這17個(gè)聚類得到的質(zhì)心點(diǎn)作為二級(jí)節(jié)點(diǎn)。將這些二級(jí)節(jié)點(diǎn)與圖上的小節(jié)點(diǎn)連接，形成一個(gè)區(qū)域，這個(gè)區(qū)域就是二級(jí)節(jié)點(diǎn)的覆蓋范圍。

圖4為二級(jí)節(jié)點(diǎn)與小節(jié)點(diǎn)的連接圖，二級(jí)節(jié)點(diǎn)的具體位置及服務(wù)范圍（每個(gè)節(jié)點(diǎn)標(biāo)號(hào)）如表2所示。

由表2可知，二級(jí)節(jié)點(diǎn)服務(wù)范圍劃分存在一些不均衡狀況，比如1號(hào)二級(jí)節(jié)點(diǎn)的服務(wù)范圍只包含一個(gè)節(jié)點(diǎn)，說明該區(qū)域的貨運(yùn)流量比較稀疏。服務(wù)范圍不均衡狀況有助于確定一級(jí)節(jié)點(diǎn)的個(gè)數(shù)及分布情況。根據(jù)各個(gè)二級(jí)節(jié)點(diǎn)的服務(wù)范圍，可求出每個(gè)二級(jí)節(jié)點(diǎn)的實(shí)際貨運(yùn)量，具體結(jié)果見表3。

二級(jí)節(jié)點(diǎn)的實(shí)際貨運(yùn)量是其服務(wù)范圍內(nèi)所有節(jié)點(diǎn)通過地下物流系統(tǒng)運(yùn)輸?shù)呢浳锪窟M(jìn)出口總和，表3中的實(shí)際貨運(yùn)量是針對(duì)地下物流系統(tǒng)而言。1號(hào)二級(jí)節(jié)點(diǎn)的實(shí)際貨運(yùn)量為0，并不是說該節(jié)點(diǎn)所在的區(qū)域沒有貨運(yùn)流通，而是說明該區(qū)域的貨運(yùn)流量比較稀疏，交通比較暢通，不需要轉(zhuǎn)入地下物流系統(tǒng)進(jìn)行貨運(yùn)，所以其貨運(yùn)量為0。

4.2 免疫算法求解一級(jí)節(jié)點(diǎn)

表3中的實(shí)際貨運(yùn)量很多都超過了3 000t，而實(shí)際要求二級(jí)節(jié)點(diǎn)從地面收發(fā)貨物總量上限為3 000t，所以需要增添一級(jí)節(jié)點(diǎn)來分?jǐn)偠?jí)節(jié)點(diǎn)中多余的貨運(yùn)量。在滿足要求的前提下，通過免疫算法，對(duì)17個(gè)二級(jí)節(jié)點(diǎn)操作，在該方案下各需求點(diǎn)貨運(yùn)量權(quán)重[16]的距離和為5.68×105，得出總預(yù)算最小。算法收斂曲線如圖5曲線所示。

經(jīng)過免疫遺傳算法，將17個(gè)二級(jí)節(jié)點(diǎn)劃分成9部分，每部分對(duì)應(yīng)一個(gè)一級(jí)節(jié)點(diǎn)，從而得出一級(jí)節(jié)點(diǎn)的個(gè)數(shù)為9，且一級(jí)節(jié)點(diǎn)主要分布在二級(jí)節(jié)點(diǎn)比較密集的區(qū)域，這種分布有效緩解了二級(jí)節(jié)點(diǎn)貨運(yùn)量較大問題，從而確保了交通暢通。一級(jí)節(jié)點(diǎn)位置坐標(biāo)及服務(wù)范圍如表4所示。

一級(jí)節(jié)點(diǎn)的服務(wù)范圍由其所覆蓋的二級(jí)節(jié)點(diǎn)構(gòu)成，每個(gè)二級(jí)節(jié)點(diǎn)有各自的服務(wù)范圍，所以表中顯示一級(jí)節(jié)點(diǎn)的服務(wù)范圍較大。由一級(jí)節(jié)點(diǎn)的服務(wù)范圍可求得一級(jí)節(jié)點(diǎn)的實(shí)際貨運(yùn)量，結(jié)果如表5所示。

一級(jí)節(jié)點(diǎn)的實(shí)際貨運(yùn)量由其服務(wù)范圍內(nèi)所有二級(jí)節(jié)點(diǎn)的實(shí)際貨運(yùn)量構(gòu)成。要求一級(jí)節(jié)點(diǎn)從地面收發(fā)貨物總量上限為4 000t，表中顯示各一級(jí)節(jié)點(diǎn)的實(shí)際貨運(yùn)量都超出了4 000t，但是一級(jí)節(jié)點(diǎn)是在地下物流系統(tǒng)中運(yùn)行的，其貨運(yùn)量沒有明確限制。一級(jí)節(jié)點(diǎn)主要用來分擔(dān)二級(jí)節(jié)點(diǎn)貨運(yùn)壓力和緩解交通暢通度，通過設(shè)置9個(gè)一級(jí)節(jié)點(diǎn)，所有二級(jí)節(jié)點(diǎn)都能滿足3000t上限要求，從而保證交通暢通，所以選取的一級(jí)節(jié)點(diǎn)是合理的。

5 結(jié)語

針對(duì)地下物流系統(tǒng)中轉(zhuǎn)節(jié)點(diǎn)規(guī)劃問題，本文將二分K-均值算法和免疫算法相結(jié)合，對(duì)地下物流中轉(zhuǎn)節(jié)點(diǎn)進(jìn)行選址。其中免疫優(yōu)化算法既可利用免疫算子加強(qiáng)算法的全局搜索能力，又能充分利用待規(guī)劃問題中的全部特征信息，以準(zhǔn)確找到全局最優(yōu)解，收斂速度也很快，實(shí)例計(jì)算結(jié)果表明該算法實(shí)用可行。

參考文獻(xiàn)：

[1] CHEN Z L，DONG J J，REN R.Urban underground logistics system in China：opportunities or challenges [J].Underground Space，2017（2）：195-508.

[2] 王煦法，張顯俊.一種基于免疫原理的遺傳算法[J].小型微型計(jì)算機(jī)，1999，20（2）：117 -120.

[3] GONG M G，JIAO L C，ZHANG X R.A population-based artificial immune system for numerical optimization[J].Neu-Rocompuring.2008，72（1-3）：149-161.

[4] WOLDEMARIAM K M，YEN G G.Vaccine-enhanced artificial immune system for multimodal function optimization[J].IEEE Transaction.On Systems，Man，and Cybernetics，Part B：Cybernetics，2010，40（1）：218-228.

[5] 王超，吳小麗.地鐵隧道與鄰近高層構(gòu)筑物建設(shè)時(shí)序優(yōu)化研究[J].隧道建設(shè)，2012（5）：5-17.

[6] 李銳，李鵬，曲亞東，等.機(jī)器學(xué)習(xí)實(shí)戰(zhàn)[M].北京：人民郵電出版社，2013.

[7] 蔡自興.人工智能及其應(yīng)用[M].北京：清華大學(xué)出版社，2007：249-283.

[8] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numberische Mathematik，1959，1（1）：269-271.

[9] 高飛.MATLAB智能算法超級(jí)學(xué)習(xí)手冊(cè)[M].北京：人民郵電出版社，2011.

[10] 閆文濤.城市地下物流系統(tǒng)節(jié)點(diǎn)選址研究—以重慶市為例[D].重慶：重慶交通大學(xué)，2015.

[11] MITCHELL M，F(xiàn)ORREST S.Genetic algorithms and artificial life[M].Artificial Life，1994.

[12] 彭麗英.改進(jìn)的蟻群算法網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋優(yōu)化研究[J].計(jì)算機(jī)仿真，2011（9）：151-153.

[13] 姜陽(yáng)光，龐大鈞.基于集合覆蓋模型的城市 ULS 物流節(jié)點(diǎn)選址分析[J]，物流科技，2009（10）：54-55.

[14] 喬聯(lián)寶，朱華桂.危險(xiǎn)品配送中心選址及路線選擇問題研究[J].物流科技，2013（4）：37-42.

[15] 李蔚田，神會(huì)存.智能物流[M].北京：北京大學(xué)出版社，2013.

[16] 王四春.GP算法中適應(yīng)度函數(shù)的光滑擬合與調(diào)整參數(shù)方法研究 [J].自動(dòng)化學(xué)報(bào)，2006（3）：23-30.

（責(zé)任編輯：杜能鋼）