基于智能算法的高校智能快遞柜選址問題研究

萬 波，盧 洲

（江漢大學 商學院，湖北 武漢 430056）

0 引言

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

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

1 文獻綜述

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

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

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

2 模型建立

2.1 模型假設

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

2.2 參數與決策變量定義

模型所用符號說明如下：

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

J:設施點集合，J={1,2,...,m};

dij:需求點i到設施候選點j的距離;

P:開放設施點的數量;

Cj:設施點j所能服務的數量，即設施點j的服務容量;

ωi:需求點i的需求量;

Xj:0-1變量，當Xj=1時，表示在候選設施點j處安裝智能快遞柜；否則，Xj=0。

Yij:0-1變量，當Yij=1時，表示需求點i處的師生由設施點j進行服務，即在此處的智能快遞柜拿取快遞；否則，Yij=0。

2.3 模型構建

根據需求點到所選擇的設施點之間的距離和需求量，可以得到師生的總出行距離，即基于P-中位模型的目標函數為：

s.t.

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

3 算法介紹

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

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

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

3.1 初始抗體群的產生

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

3.2 解的多樣性評價

解的多樣性評價包括抗體與抗原之間親和力、抗體與抗體間親和力、抗體濃度和期望繁殖概率四個方面。

3.2.1 抗體與抗原之間的親和力。抗體與抗原之間的親和力用于表示抗體對抗原的識別程度，針對本文的選址模型設計親和力函數Av：

其中Fv為目標函數；分母中第二項表示對違反距離約束條件的解給予懲罰，C是一個較大的正數，本文取C=3 000。

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

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

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

其中，N為抗體總數；T為預先設定的一個閾值。

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

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

3.3 免疫操作

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

（2）交叉。本文采用單點交叉法進行交叉操作。

（3）變異。采用常用的變異方法，即隨機選擇變異位進行變異。

4 算例分析

以江漢大學校園為例，根據小型區域（宿舍樓棟、教學樓）的劃分，共有54個需求點，準備設置8個設施點。

通過百度地圖找出校園中每個需求點的經緯度坐標，對校園進行實地調查，計算出每棟宿舍樓的居住人數，然后根據人數確定每棟宿舍樓的具體需求量，大學的教學樓等地由于情況特殊，學生上課的教室不固定，流動性較大，因此各個教學樓的需求量根據各個學院的人數乘上一定的比例來確定。需求點和需求量的相關數據見表1。

表1 各需求點的需求量一覽表

4.1 利用EWM確定設施候選點

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

對歸一化矩陣經過一系列的計算，可得到4個評價指標的信息熵值和權重值，結果見表2。將權重值與對應的原始值相乘，便可得到17個候選設施點的綜合得分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)。根據綜合得分s值的大小，選取綜合得分高的13個候選設施點：2、5、6、13、17、19、20、26、29、31、35、40、46號。

表2 信息熵值和權重值

4.2 算法求解與分析

本文采用免疫算法和遺傳算法對選址模型進行求解。其參數設置是算法能夠有效運行的關鍵，因此本文在算法參數的設置上參考了文獻[18,23]，具體的參數值見表3和表4。

表3 免疫算法參數一覽表

表4 遺傳算法參數一覽表

對免疫算法和遺傳算法的參數進行設置之后，就可以在實驗環境為AMDRyzen7 5800H CPU@3.2GHz，16GB內存，操作系統為64位windows10，使用MatlabR2020a進行編程。

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

表5 免疫算法需求點對應的設施點

表6 遺傳算法需求點對應的設施點

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

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

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

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

表7 免疫算法和遺傳算法運行結果比較

算法求解結果的差異在于免疫算法時對遺傳算法的改進，此外遺傳算法在進行全局搜索是容易進入“早熟”狀態，而免疫算法做到了在尋優過程中克服進入“早熟”的問題，進而得到全局最優解。從圖2中的選址情況可以發現，遺傳算法提前進入了“早熟”狀態，陷入了局部最優解，導致選址點的分配出現不合理的情況。此外，免疫算法和遺傳算法在對個體的評價和選擇方式上也有所不同，遺傳算法對個體的評價主要是通過計算個體的適應度得到的；而免疫算法則是通過計算親和度得到的，個體的選擇是以親和度為基礎進行，且親和度包括抗體與抗原之間的匹配程度和抗體之間的相似程度，因此，免疫算法對個體的評價更加全面，求解出的結果也更加合理。

（3）算法收斂性分析。圖3中免疫算法在迭代運行到30代就已經收斂，而圖4中遺傳算法在180代之前收斂曲線一直處于震蕩狀態，直到迭代到180代時才開始收斂。通過以上數據對比發現，免疫算法相比遺傳算法而言具有較好的收斂性。

圖3 免疫算法收斂曲線

圖4 遺傳算法收斂曲線

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

（4）算法穩健性分析。本文以江漢大學校園為對象，隨機產生100個算例，分別運用免疫算法和遺傳算法進行求解，發現免疫算法所求得的目標函數值平均值小于遺傳算法，免疫算法運行時間的平均值也小于遺傳算法，具體見表8。大量算例驗證表明免疫算法具有較好的穩健性。

表8 免疫算法的穩健性分析

5 結語

本文構建以取件距離最短為目標的智能快遞柜選址優化模型，并以江漢大學為研究區域，運用免疫算法與遺傳算法進行智能快遞柜選址研究。首先，對影響設施選址的因素運用熵權法來計算其權重，確定設施候選點；然后根據高校特點構建取件距離最短的選址優化模型進行選址，并分別采用免疫算法和遺傳算法對選址模進行求解。結果表明相對于遺傳算法而言，免疫算法對求解該模型有更好的收斂性和可行性，對高校校園智能快遞柜選址有一定的參考作用。

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