萬 波，盧 洲

（江漢大學(xué) 商學(xué)院，湖北 武漢 430056）

0 引言

近年來，云計(jì)算、物聯(lián)網(wǎng)和移動(dòng)通信等新技術(shù)的快速發(fā)展推動(dòng)著電子商務(wù)高速發(fā)展，進(jìn)而給傳統(tǒng)物流行業(yè)帶來了機(jī)遇與挑戰(zhàn)。傳統(tǒng)配送方式有著諸如快遞服務(wù)人員有限、投遞亂、快遞丟失等問題。高?？爝f一般都是集中放在快遞驛站，然后由快遞驛站的服務(wù)人員將師生的快遞掃碼登記以后，通過短信的形式告知客戶，這項(xiàng)工作不僅要耗費(fèi)大量的勞動(dòng)力，而且還容易出現(xiàn)錯(cuò)誤。此外快遞驛站的運(yùn)營時(shí)間并不是全天的，導(dǎo)致部分師生無法及時(shí)領(lǐng)取快遞。特別是“雙十一”活動(dòng)和開學(xué)季快遞量激增，快遞驛站的服務(wù)能力有限，取件時(shí)需要自己在大量的快遞中尋找，不僅浪費(fèi)了師生的時(shí)間，而且還降低了其對(duì)快遞服務(wù)的滿意度。

智能快遞柜是一套智能化的設(shè)備，具有快遞存儲(chǔ)、通信等功能。它可以識(shí)別和讀取包裹上客戶的相關(guān)信息，并將客戶包裹的位置和取件碼自動(dòng)發(fā)送到客戶的手機(jī)上[1]。此外，智能快遞柜具有存取操作簡單、24小時(shí)無人看管運(yùn)行、取件全程監(jiān)控和柜體根據(jù)實(shí)際需求安裝等優(yōu)點(diǎn)。在新冠疫情的影響下，智能快遞柜的使用可以減少人群接觸，實(shí)現(xiàn)無接觸式的快遞配送方式，不僅可以減少快遞配送過程中產(chǎn)生的成本，而且極大地滿足了師生隨時(shí)取件的需求，為在校師生提供便利的同時(shí)，也有利于學(xué)校減輕疫情防控的難度和保障師生的健康[2]。因此，對(duì)高校智能快遞柜進(jìn)行合理的選址和布局具有重要的現(xiàn)實(shí)意義。

1 文獻(xiàn)綜述

隨著電子商務(wù)的快速發(fā)展和新冠疫情的持續(xù)蔓延，在智能快遞柜的選址研究上，國內(nèi)學(xué)者分別采用了不同的算法模型進(jìn)行深入研究，如張夢露[3]運(yùn)用層次分析法對(duì)山東理工大學(xué)進(jìn)行智能快遞柜選址，旨在提升快遞配送效率。張西莎，等[4]在對(duì)社區(qū)樓棟分布和快遞接收量進(jìn)行調(diào)查的基礎(chǔ)上，建立集合覆蓋模型和運(yùn)用層次分析法對(duì)社區(qū)內(nèi)現(xiàn)有的智能快遞柜進(jìn)行重新選址。劉程程，等[2]在新冠疫情影響下提出了一種智能快遞柜的選址模型，旨在解決無接觸配送問題，并以哈爾濱香坊區(qū)為驗(yàn)證對(duì)象，結(jié)果表明該模型的使用能夠減少人員接觸。黃杜鵑，等[5]為了彌補(bǔ)鄉(xiāng)鎮(zhèn)智能快遞柜布局的空缺，運(yùn)用AHP-TOPSIS組合模型確定候選鄉(xiāng)鎮(zhèn)，然后利用Dijkstra算法來求解最優(yōu)選址方案。馮瑛杰，等[6]為避免突發(fā)事件的影響，構(gòu)建了緊急物流設(shè)施選址模型，設(shè)計(jì)了非支配遺傳算法對(duì)選址模型進(jìn)行求解。郭靜文，等[7]將遺傳算法運(yùn)用在城市消防站選址問題求解中，結(jié)果表明遺傳算法有助于平衡消防站布局中的安全性和經(jīng)濟(jì)性問題。劉善球，等[8]以物流配送中心為選址對(duì)象，結(jié)合建設(shè)成本等因素建立選址模型，并運(yùn)用遺傳算法對(duì)算例進(jìn)行求解，結(jié)果驗(yàn)證了遺傳算法在選址問題求解中的有效性。

對(duì)基于免疫算法的選址問題，國內(nèi)學(xué)者進(jìn)行了創(chuàng)新性的研究，如劉東運(yùn)，等[9]在研究同時(shí)送取貨選址路徑問題時(shí)，建立了倉儲(chǔ)成本和運(yùn)輸成本目標(biāo)和最小的選址模型，運(yùn)用混合免疫算法對(duì)其進(jìn)行求解，結(jié)果表明混合免疫算法和免疫算法的求解結(jié)果均優(yōu)于粒子群算法和模擬退火算法。淦艷，等[10]提出了由配送時(shí)間和需求量共同決定權(quán)值的選址模型，并運(yùn)用免疫算法求解該選址問題，通過實(shí)例分析發(fā)現(xiàn)與不帶配送時(shí)間相比，該模型得到的結(jié)果其配送距離和運(yùn)行時(shí)間更少。HUANG，等[11]在研究逆向物流中心設(shè)施選址時(shí)，將免疫算法模型引入到該問題的求解中，系統(tǒng)地探討了免疫算法的收斂性。該模型不僅為逆向物流網(wǎng)絡(luò)的設(shè)施選址策略優(yōu)化提供了一種新穎的解決方案，而且拓展了人工免疫系統(tǒng)的應(yīng)用領(lǐng)域，豐富了現(xiàn)有的人工免疫系統(tǒng)模型。仿真研究表明，與遺傳算法相比，免疫算法收斂速度更快，解更精確，更能保持抗體群的多樣性。

文獻(xiàn)[2-5]對(duì)智能快遞柜的選址研究主要采用層次分析法，并沒有采用其他方法進(jìn)行對(duì)比。文獻(xiàn)[6-8]中傳統(tǒng)的遺傳算法在求解復(fù)雜的選址問題時(shí)難以快速得出有效解，而改進(jìn)的非支配遺傳算法具有高計(jì)算復(fù)雜度，且隨著種群數(shù)的增加呈指數(shù)增長。文獻(xiàn)[9-11]在運(yùn)用免疫算法的同時(shí)引入了其他算法進(jìn)行比較，且求解結(jié)果均優(yōu)于遺傳算法。鑒于目前還沒有學(xué)者將免疫算法運(yùn)用到智能快遞柜選址研究中，本文試圖將免疫算法運(yùn)用到高校智能快遞柜選址方案的研究，以獲得更好的求解質(zhì)量。

2 模型建立

2.1 模型假設(shè)

為便于選址模型的建立，給出以下假設(shè)：（1）每個(gè)區(qū)域內(nèi)的布局?jǐn)?shù)量基于該區(qū)域內(nèi)需求點(diǎn)的學(xué)生人數(shù)；（2）區(qū)域內(nèi)的需求點(diǎn)用離散型需求點(diǎn)集合I表示，最終的選址點(diǎn)從設(shè)施點(diǎn)集合J中產(chǎn)生；（3）該模型考慮需求的全覆蓋、需求點(diǎn)就近分配給設(shè)施點(diǎn)、需求點(diǎn)單一分配給設(shè)施點(diǎn)及開放與關(guān)閉設(shè)施數(shù)目限制等約束條件。

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

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

I:需求點(diǎn)集合，I={1,2,...,n};

J:設(shè)施點(diǎn)集合，J={1,2,...,m};

dij:需求點(diǎn)i到設(shè)施候選點(diǎn)j的距離;

P:開放設(shè)施點(diǎn)的數(shù)量;

Cj:設(shè)施點(diǎn)j所能服務(wù)的數(shù)量，即設(shè)施點(diǎn)j的服務(wù)容量;

ωi:需求點(diǎn)i的需求量;

Xj:0-1變量，當(dāng)Xj=1時(shí)，表示在候選設(shè)施點(diǎn)j處安裝智能快遞柜；否則，Xj=0。

Yij:0-1變量，當(dāng)Yij=1時(shí)，表示需求點(diǎn)i處的師生由設(shè)施點(diǎn)j進(jìn)行服務(wù)，即在此處的智能快遞柜拿取快遞；否則，Yij=0。

2.3 模型構(gòu)建

根據(jù)需求點(diǎn)到所選擇的設(shè)施點(diǎn)之間的距離和需求量，可以得到師生的總出行距離，即基于P-中位模型的目標(biāo)函數(shù)為：

s.t.

目標(biāo)函數(shù)式（1）為最小化師生從需求點(diǎn)（教學(xué)樓、宿舍）到設(shè)施候選點(diǎn)（智能快遞柜）的總出行距離；式（2）確保每個(gè)需求點(diǎn)都有相應(yīng)的設(shè)施點(diǎn)服務(wù)，且僅被一個(gè)設(shè)施點(diǎn)服務(wù)；式（3）表示只有候選設(shè)施點(diǎn)處安裝了智能快遞柜，師生才可以去拿取快遞；式（4）、式（5）為決策變量的取值范圍。

3 算法介紹

選址模型的優(yōu)化求解大致分為精確算法和非精確算法兩類，精確算法能夠找到精確解，在簡單優(yōu)化問題的求解上有優(yōu)勢。隨著選址問題的規(guī)模越來越大，精確算法會(huì)出現(xiàn)難以求出最優(yōu)解的情況，從而促進(jìn)了以啟發(fā)式算法為代表的非精確算法的應(yīng)用[12]。經(jīng)典P-中位選址問題屬于NP-難問題[13]，即是一類計(jì)算時(shí)間復(fù)雜度大的問題，無法在短時(shí)間內(nèi)得到精確的解，基于此，人們退而求其次，運(yùn)用啟發(fā)式算法尋求決策問題的滿意解。

遺傳算法（Genetic Algorithm）是一種啟發(fā)式搜索算法，由美國J.H.Holland教授與他的同事和學(xué)生于1975年提出[14]。GA把問題參數(shù)編碼為染色體，再利用迭代的方式進(jìn)行選擇、交叉以及變異等運(yùn)算，將最大的適應(yīng)度個(gè)體作為最優(yōu)解[15]。但大量的實(shí)踐和研究表明，經(jīng)典遺傳算法存在局部搜索能力差和“早熟”等缺陷，不能保證算法收斂[16]。

Chun，等[17]提出了一種免疫算法（Immune Algorithm），實(shí)質(zhì)上是改進(jìn)的遺傳算法。根據(jù)體細(xì)胞和免疫網(wǎng)理論改進(jìn)了遺傳算法的選擇操作，從而保持了群體的多樣性，提高了算法的全局尋優(yōu)能力，克服了一般尋優(yōu)過程尤其是多峰函數(shù)尋優(yōu)過程中難處理的“早熟”問題[18]。通過在算法中加入免疫記憶功能，提高了算法的收斂速度。在現(xiàn)有的許多文獻(xiàn)中，出現(xiàn)了針對(duì)經(jīng)典遺傳算法的各種改進(jìn)算法，并取得了一定的成效[19-21]。因此，本文根據(jù)P-中位選址模型的具體特征，設(shè)計(jì)了免疫算法對(duì)其求解。

3.1 初始抗體群的產(chǎn)生

如果記憶庫非空，則初始抗體群從記憶庫中選擇生成。否則，在可行解空間隨機(jī)產(chǎn)生初始抗體群。本文采用簡單編碼方式。每個(gè)選址方案可形成一個(gè)長度為n的抗體（n表示設(shè)施點(diǎn)的數(shù)量），每個(gè)抗體代表被選為配送中心的需求點(diǎn)的序列。例如，考慮包含54個(gè)需求點(diǎn)的問題。1,2,…,54代表需求點(diǎn)的序號(hào)。從中選出8個(gè)作為智能快遞柜的設(shè)施點(diǎn)?？贵w[2 7 25 31 18 42 36 51]代表一個(gè)可行解，它表示2,7,25,31,18,42,36,51被選為智能快遞柜的設(shè)施點(diǎn)。

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

解的多樣性評(píng)價(jià)包括抗體與抗原之間親和力、抗體與抗體間親和力、抗體濃度和期望繁殖概率四個(gè)方面。

3.2.1 抗體與抗原之間的親和力。抗體與抗原之間的親和力用于表示抗體對(duì)抗原的識(shí)別程度，針對(duì)本文的選址模型設(shè)計(jì)親和力函數(shù)Av：

其中Fv為目標(biāo)函數(shù)；分母中第二項(xiàng)表示對(duì)違反距離約束條件的解給予懲罰，C是一個(gè)較大的正數(shù)，本文取C=3 000。

3.2.2 抗體與抗體間親和力。抗體的親和力反映了它們的相似程度。計(jì)算參考了Forrest，等提出的R位連續(xù)法，抗原的編碼方法不考慮排序。我們使用可變形R位連續(xù)方法來計(jì)算親和力，即：

其中L為抗體的長度，kv,s為抗體v和抗體s編碼中相同的位數(shù)。

3.2.3 抗體濃度?？贵w濃度Cv代表群體中相似抗體所占的比例，即：

其中，N為抗體總數(shù)；T為預(yù)先設(shè)定的一個(gè)閾值。

3.2.4 期望繁殖概率。在群體中，每個(gè)個(gè)體的期望繁殖概率由抗體與抗原間親和力Av和抗體濃度Cv兩部分共同決定，即：

其中α是常數(shù)。由式（9）可知，抗體與抗原之間的親和力越高且抗體濃度越低，抗體的期望繁殖概率就越高。這樣既鼓勵(lì)了適應(yīng)度高的個(gè)體，同時(shí)抑制了濃度高的個(gè)體，從而確保了個(gè)體的多樣性。

3.3 免疫操作

（1）選擇。按照輪盤賭法的選擇機(jī)制進(jìn)行選擇操作，個(gè)體被選擇的概率即為式（9）計(jì)算出的期望繁殖概率。

（2）交叉。本文采用單點(diǎn)交叉法進(jìn)行交叉操作。

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

4 算例分析

以江漢大學(xué)校園為例，根據(jù)小型區(qū)域（宿舍樓棟、教學(xué)樓）的劃分，共有54個(gè)需求點(diǎn)，準(zhǔn)備設(shè)置8個(gè)設(shè)施點(diǎn)。

通過百度地圖找出校園中每個(gè)需求點(diǎn)的經(jīng)緯度坐標(biāo)，對(duì)校園進(jìn)行實(shí)地調(diào)查，計(jì)算出每棟宿舍樓的居住人數(shù)，然后根據(jù)人數(shù)確定每棟宿舍樓的具體需求量，大學(xué)的教學(xué)樓等地由于情況特殊，學(xué)生上課的教室不固定，流動(dòng)性較大，因此各個(gè)教學(xué)樓的需求量根據(jù)各個(gè)學(xué)院的人數(shù)乘上一定的比例來確定。需求點(diǎn)和需求量的相關(guān)數(shù)據(jù)見表1。

表1 各需求點(diǎn)的需求量一覽表

4.1 利用EWM確定設(shè)施候選點(diǎn)

在整個(gè)校園內(nèi)初步選取了17個(gè)設(shè)施候選點(diǎn)，候選設(shè)施點(diǎn)包括在需求點(diǎn)中，利用EWM進(jìn)行初步篩選。候選設(shè)施點(diǎn)的初始指標(biāo)數(shù)據(jù)由以下幾個(gè)因素構(gòu)成：設(shè)施點(diǎn)附近的師生人數(shù)、一定距離內(nèi)是否有快遞驛站、是否位于主干道和女生所占比例[22]。在校園中，人數(shù)越多快遞量就會(huì)越大，所以人數(shù)的多少是非常重要的因素，本文主要是通過實(shí)地調(diào)查各個(gè)宿舍樓棟的寢室間數(shù)再乘以每個(gè)宿舍的人數(shù)就得出了每棟樓的具體人數(shù)；快遞驛站和快遞柜之間有一定的競爭關(guān)系，所以需求點(diǎn)距離快遞驛站越遠(yuǎn)，就越有利于智能快遞柜的選址；高校網(wǎng)購群體中，女生占據(jù)絕對(duì)比例[22]，所以女生比例越大的區(qū)域，對(duì)智能快遞柜的需求量就越大。通過收集相關(guān)的數(shù)據(jù)得到原始數(shù)據(jù)矩陣，通過對(duì)原始矩陣歸一化處理，得到歸一化矩陣。

對(duì)歸一化矩陣經(jīng)過一系列的計(jì)算，可得到4個(gè)評(píng)價(jià)指標(biāo)的信息熵值和權(quán)重值，結(jié)果見表2。將權(quán)重值與對(duì)應(yīng)的原始值相乘，便可得到17個(gè)候選設(shè)施點(diǎn)的綜合得分s=(5.02 6.44 5.55 7.86 6.12 8.69 7.10 6.67 6.17 4.96 6.04 5.45 5.74 6.99 5.57 5.26 5.25)。根據(jù)綜合得分s值的大小，選取綜合得分高的13個(gè)候選設(shè)施點(diǎn)：2、5、6、13、17、19、20、26、29、31、35、40、46號(hào)。

表2 信息熵值和權(quán)重值

4.2 算法求解與分析

本文采用免疫算法和遺傳算法對(duì)選址模型進(jìn)行求解。其參數(shù)設(shè)置是算法能夠有效運(yùn)行的關(guān)鍵，因此本文在算法參數(shù)的設(shè)置上參考了文獻(xiàn)[18,23]，具體的參數(shù)值見表3和表4。

表3 免疫算法參數(shù)一覽表

表4 遺傳算法參數(shù)一覽表

對(duì)免疫算法和遺傳算法的參數(shù)進(jìn)行設(shè)置之后，就可以在實(shí)驗(yàn)環(huán)境為AMDRyzen7 5800H CPU@3.2GHz，16GB內(nèi)存，操作系統(tǒng)為64位windows10，使用MatlabR2020a進(jìn)行編程。

（1）選址與分配情況。免疫算法選址分配情況見表5 ，遺傳算法選址分配情況見表6。

表5 免疫算法需求點(diǎn)對(duì)應(yīng)的設(shè)施點(diǎn)

表6 遺傳算法需求點(diǎn)對(duì)應(yīng)的設(shè)施點(diǎn)

免疫算法選址示意圖如圖1所示，遺傳算法選址示意圖如圖2所示。

圖1 免疫算法選址與分配情況

圖2 遺傳算法選址與分配情況

（2）求解質(zhì)量分析。通過兩種算法選址結(jié)果可以發(fā)現(xiàn)，免疫算法求解的選址點(diǎn)主要集中在宿舍樓群、師生每天經(jīng)過的主干道和圖書館附近，并且在選址點(diǎn)的分配上也是宿舍樓群下分配的多，符合實(shí)際情況。而遺傳算法求解的選址點(diǎn)在教學(xué)樓群分配的較多，這種分配方式既不符合高校師生的生活習(xí)慣，也沒有做到給師生提供便利的初衷。此外，北區(qū)是學(xué)校學(xué)生生活的主要區(qū)域，宿舍樓群龐大，而遺傳算法在選址點(diǎn)的分配上只分配了三個(gè)點(diǎn)，這將會(huì)給師生的取件帶來不便，尤其是在“雙十一”促銷活動(dòng)和開學(xué)期間。由表7中的目標(biāo)函數(shù)值和算法運(yùn)行時(shí)間可知，免疫算法最終求解的目標(biāo)值比遺傳算法小，且速度更快。通過上述比較發(fā)現(xiàn)免疫算法相比遺傳算法而言能夠獲得更為滿意的解。

表7 免疫算法和遺傳算法運(yùn)行結(jié)果比較

算法求解結(jié)果的差異在于免疫算法時(shí)對(duì)遺傳算法的改進(jìn)，此外遺傳算法在進(jìn)行全局搜索是容易進(jìn)入“早熟”狀態(tài)，而免疫算法做到了在尋優(yōu)過程中克服進(jìn)入“早熟”的問題，進(jìn)而得到全局最優(yōu)解。從圖2中的選址情況可以發(fā)現(xiàn)，遺傳算法提前進(jìn)入了“早熟”狀態(tài)，陷入了局部最優(yōu)解，導(dǎo)致選址點(diǎn)的分配出現(xiàn)不合理的情況。此外，免疫算法和遺傳算法在對(duì)個(gè)體的評(píng)價(jià)和選擇方式上也有所不同，遺傳算法對(duì)個(gè)體的評(píng)價(jià)主要是通過計(jì)算個(gè)體的適應(yīng)度得到的；而免疫算法則是通過計(jì)算親和度得到的，個(gè)體的選擇是以親和度為基礎(chǔ)進(jìn)行，且親和度包括抗體與抗原之間的匹配程度和抗體之間的相似程度，因此，免疫算法對(duì)個(gè)體的評(píng)價(jià)更加全面，求解出的結(jié)果也更加合理。

（3）算法收斂性分析。圖3中免疫算法在迭代運(yùn)行到30代就已經(jīng)收斂，而圖4中遺傳算法在180代之前收斂曲線一直處于震蕩狀態(tài)，直到迭代到180代時(shí)才開始收斂。通過以上數(shù)據(jù)對(duì)比發(fā)現(xiàn)，免疫算法相比遺傳算法而言具有較好的收斂性。

圖3 免疫算法收斂曲線

圖4 遺傳算法收斂曲線

算法收斂性的差異在于遺傳算法通過交叉、變異等遺傳操作產(chǎn)生新個(gè)體，而在免疫算法中，雖然交叉、變異等固有的遺傳操作也被廣泛應(yīng)用，但是新抗體的產(chǎn)生還可以借助克隆選擇、免疫記憶、疫苗接種等遺傳算法中所欠缺的機(jī)理。其中，免疫記憶的主要作用是當(dāng)免疫系統(tǒng)再次進(jìn)行免疫應(yīng)答時(shí)，可以加速優(yōu)化搜索過程；克隆選擇的主要作用是在抗原的刺激下，對(duì)抗體進(jìn)行快速大量的復(fù)制操作，提高抗體的濃度和加速親和度“成熟”的過程，從而可以快速的得到最優(yōu)解。同時(shí)免疫算法還對(duì)抗體的產(chǎn)生進(jìn)行促進(jìn)或者抑制，體現(xiàn)了免疫反應(yīng)的自我調(diào)節(jié)功能，保證了個(gè)體的多樣性。

（4）算法穩(wěn)健性分析。本文以江漢大學(xué)校園為對(duì)象，隨機(jī)產(chǎn)生100個(gè)算例，分別運(yùn)用免疫算法和遺傳算法進(jìn)行求解，發(fā)現(xiàn)免疫算法所求得的目標(biāo)函數(shù)值平均值小于遺傳算法，免疫算法運(yùn)行時(shí)間的平均值也小于遺傳算法，具體見表8。大量算例驗(yàn)證表明免疫算法具有較好的穩(wěn)健性。

表8 免疫算法的穩(wěn)健性分析

5 結(jié)語

本文構(gòu)建以取件距離最短為目標(biāo)的智能快遞柜選址優(yōu)化模型，并以江漢大學(xué)為研究區(qū)域，運(yùn)用免疫算法與遺傳算法進(jìn)行智能快遞柜選址研究。首先，對(duì)影響設(shè)施選址的因素運(yùn)用熵權(quán)法來計(jì)算其權(quán)重，確定設(shè)施候選點(diǎn)；然后根據(jù)高校特點(diǎn)構(gòu)建取件距離最短的選址優(yōu)化模型進(jìn)行選址，并分別采用免疫算法和遺傳算法對(duì)選址模進(jìn)行求解。結(jié)果表明相對(duì)于遺傳算法而言，免疫算法對(duì)求解該模型有更好的收斂性和可行性，對(duì)高校校園智能快遞柜選址有一定的參考作用。

今后，在算法方面，可以在經(jīng)典免疫算法的基礎(chǔ)上進(jìn)一步改進(jìn)或者使用混合算法進(jìn)行求解，以增加算法求解的快速性和準(zhǔn)確性；在模型建立上，可以在建立選址模型時(shí)考慮更多影響選址因素，如引入智能快遞柜和快遞公司成本最小和師生取件距離最小的多目標(biāo)決策問題，使建立的模型運(yùn)用范圍更廣和貼近實(shí)際需求。