苗將，張仰森,2*，李劍龍，刁艷茹

(1.北京信息科技大學計算機學院，北京 100101；2.國家經(jīng)濟安全預警工程北京實驗室，北京 100044)

隨著京津冀區(qū)域經(jīng)濟的快速發(fā)展，完善京津冀區(qū)域物流一體化，將是京津冀高質(zhì)量發(fā)展的突破口。物流是中國社會經(jīng)濟發(fā)展的重要組成部分，物流與經(jīng)濟之間相互影響、共同發(fā)展[1]，是區(qū)域經(jīng)濟發(fā)展引擎中的重要齒輪[2]。物流倉儲中心選址作為物流配送路徑的根本源頭，很大程度上決定了完成物流配送所需要的時間，對于大幅提升物流配送效率具有重要意義[3]。

王勇等[4]提出了一種基于數(shù)學視角物流倉儲中心選址策略，即求一個點到多個確定點的距離最小。該方法屬于數(shù)學正向求解，距離參數(shù)權(quán)重過于苛刻，缺少其他復雜約束條件支撐。物流倉儲中心選址問題具有較多復雜的約束條件，具有非確定性多項式困難(non-deterministic polynomial hard,NP-hard)的性質(zhì)。舒孝珍[5]提出了一種非線性規(guī)劃模型求解物流倉儲中心選址策略，注重了多級指標選取和計算。劉善球等[6]提出了一種基于遺傳算法模型的物流倉儲中心選址策略，通過引入概率的適應與突變增強求解能力。李衛(wèi)星[7]提出了一種基于灰狼算法的物流倉儲中心選址策略，通過引入擾動因子跳出局部最優(yōu)。孟軍等[8]提出了一種基于飛蛾算法的物流倉儲中心選址策略，通過引入非線性慣性權(quán)重增加意外影響。雖然這些算法對于解決物流倉儲中心選址問題起到了一定的效果，但仍陷入局部最優(yōu)、搜索重點偏差和收斂速度慢等缺點。

為此，，基于京津冀物流發(fā)展的實際情況之上，提出了一種KMBR(K-means in Monarch butterfly with roulette)算法，通過建立物流倉儲中心選址的數(shù)學模型，基于機器學習聚類特征，對標準帝王蝶優(yōu)化算法進行改進，加入輪盤賭策略，為京津冀物流倉儲中心選址的問題提供有力依據(jù)。

1 構(gòu)建選址數(shù)據(jù)集

1.1 京津冀地區(qū)中心坐標

隨著北京原密云和延慶撤縣設區(qū)、天津原薊縣撤縣設區(qū)，當?shù)厝藛T正式加入直轄市的管制，享受各種政策直接幫扶，促進政府資源的調(diào)度[9]。北京、天津各區(qū)和河北各地級市的政務中心是當?shù)胤秶暮诵牡囟?，就業(yè)、居住、醫(yī)療、教育等資源都緊緊圍繞，是人口集中的密集點。故通過百度地圖開發(fā)者文檔功能，確立各行政中心經(jīng)度和緯度。

1.2 各地區(qū)經(jīng)濟適應量

北京和天津作為直轄市，其郵政管理局并未公布各區(qū)詳細的物流數(shù)據(jù)，故提出經(jīng)濟適應量參數(shù)作為替代[10]。經(jīng)濟適應量的數(shù)學模型為

(1)

式(1)中:m為直轄市或省地級市;n為對應直轄市或省地級市所屬的區(qū)域;Eij為當?shù)貐^(qū)域的經(jīng)濟適應量;Pij為當?shù)貐^(qū)域的常住人口;Yij為當?shù)貐^(qū)域的15～69歲人口比例;Gij為當?shù)貐^(qū)域的生產(chǎn)總值;Tij,total為當?shù)貐^(qū)域所屬的直轄市或省地級市的生產(chǎn)總值之和。

對區(qū)域進行脫密處理，以相應代號進行指代。故京津冀選址數(shù)據(jù)集如表1所示。

表1 選址數(shù)據(jù)集Table 1 Location data set

2 物流倉儲中心選址數(shù)學模型

提出的物流倉儲中心選址問題為，從X個直轄市和省地級市所屬的區(qū)域中，確定Y個出發(fā)點作為物流倉儲中心[11]。由于各物流倉儲中心所處地理位置不同、面向區(qū)域不同，故建立帶多種約束條件的物流倉儲中心選址數(shù)學模型為

(2)

Dij≤Z

(3)

(4)

Ej≤V

(5)

式中：C為代價函數(shù)；X為直轄市和省地級市所屬的區(qū)域的數(shù)目；Y為物流倉儲中心數(shù)目；Ej為第j個區(qū)域的經(jīng)濟適應量；Dij為第i個物流倉儲中心與第j個區(qū)域之間的距離；Tij為第i個物流倉儲中心向第j個區(qū)域出倉發(fā)貨；Z為當前區(qū)域到最遠物流倉儲中心的距離；V為當前區(qū)域物流倉儲中心涉及的經(jīng)濟適用量總量。

式(3)表示每個區(qū)域的所需物品都必須有一個物流倉儲中心完成出倉發(fā)貨；式(4)表示一個區(qū)域的所需物品只能從一個物流倉儲中心完成出倉發(fā)貨；式(5)表示每個區(qū)域的經(jīng)濟適用量都應小于等于與其對應物流倉儲中心涉及的經(jīng)濟適用量總量。

3 聚類算法

3.1 K均值聚類算法

聚類是一個將相似數(shù)據(jù)分類的過程[12]，同類數(shù)據(jù)相似度盡可能大，異類數(shù)據(jù)相似度盡可能小。K均值聚類算法是一種無監(jiān)督迭代聚類算法，采用歐氏距離作為相似度指標，力求同類數(shù)據(jù)與所在類的誤差平凡和達到最小。K均值聚類算法基于以下規(guī)則：①從數(shù)據(jù)集中隨機選擇指定數(shù)量的數(shù)據(jù)作為初始的質(zhì)心向量；②計算每個新加入的數(shù)據(jù)與各個質(zhì)心向量的距離，將該數(shù)據(jù)加入對應距離最小的類別中；③重新計算質(zhì)心向量。

基于上述規(guī)則，得出K均值聚類算法的迭代公式如下。

數(shù)據(jù)到質(zhì)心向量距離的計算公式為

(6)

式(6)中：Xi為第i個對象；Cl為第l個聚類的中心；Xit為第i個對象的第t個屬性；Cjt為第j個聚類中心的第t個屬性。

質(zhì)心向量更新計算公式為

(7)

式(7)中：Sl為第l個聚類中對象的個數(shù)。

3.2 改進K均值聚類算法

K均值聚類算法初始選擇質(zhì)心向量時是一個隨機選取，單純的隨機選取易產(chǎn)生不同的聚類結(jié)果。且在更新質(zhì)心向量時以各類均值為依據(jù)，若聚類中有一個遠心點便破壞了聚類效果的緊密性。針對京津冀地域京津緊密，冀分散的特點，對K均值聚類算法進行改進。

對初始的質(zhì)心向量選擇引入單點密度和多點間距參數(shù)因子。單點密度是指以某一點為核心，以指定長度為半徑的圓內(nèi)其他數(shù)據(jù)個數(shù)。多點間距是指多個單點密度間對應的距離。聚類效果一般遵循同類距離較小，異類距離較大的準則。但在引入單點密度和多點間距參數(shù)因子后，如果兩個點的密度都較大，且兩個點之間距離較小，但這樣的兩個點都選做質(zhì)心向量得到的聚類效果也是很好。改進K均值聚類算法的迭代公式如下。

單點密度的計算公式為

(8)

式(8)中：Sij為點i到點j之間的距離；Sb為指定長度距離。

多點間距的計算公式為

(9)

式(9)中：Pi為點i的單點密度;most為所有數(shù)據(jù)的單點密度最大值；SiI為點i到對應單點密度中最遠點I的距離。

對應單點密度和多點間距的乘積較好的體現(xiàn)了各個數(shù)據(jù)點的綜合性能，然后由高到低篩選并選取指定數(shù)量的乘積值，根據(jù)乘積值對應的數(shù)據(jù)作為初始質(zhì)心向量。

4 帝王蝶優(yōu)化算法

4.1 帝王蝶簡介

帝王蝶作為世界上最知名的昆蟲之一[13]，是鱗翅目中唯一的一種遷移性蝴蝶。大部分帝王蝶為躲避北美的嚴寒，每年秋季都要從洛基山出發(fā)，向墨西哥中部進軍。而剩余部分的帝王蝶則選擇留下來，通過適應環(huán)境進行生存。

4.2 標準帝王蝶優(yōu)化算法

帝王蝶優(yōu)化算法(Monarch butterfly optimization，MBO)是受帝王蝶遷移和適應環(huán)境的啟發(fā)，于2015年提出的一種優(yōu)化算法。在MBO中，每只蝴蝶都看成一個粒子，決策變量的產(chǎn)生由粒子位置是否變動來表示。該算法通過模擬帝王蝶在自然界中的遷徙行為，其基于以下4個規(guī)則。

(1)所有的帝王蝶只位于陸地1(美國北部)和陸地2(墨西哥)，即理想化的將整個帝王蝶種群由陸地1和陸地2的帝王蝶組成。

(2)每只子代帝王蝶都是由陸地1或陸地2的帝王蝶通過生育(遷移)產(chǎn)生的，即帝王蝶通過遷移產(chǎn)生了相應位置的變動。

(3)為了維護種群數(shù)量恒定，一只父代帝王蝶只能生育一只子代帝王蝶，且生育完成父代帝王蝶就會死去。若新生子代帝王蝶沒有表現(xiàn)出更好地適應度，則子代帝王蝶被拋棄，父代帝王蝶保持完整(適應環(huán)境)，即通過適應環(huán)境避免位置的變動。

(4)通過遷徙或適應環(huán)境獲得最好適應度的帝王蝶，將自動運用到下一次選擇中，該行為無法被任何操作終止，即確保了帝王蝶種群質(zhì)量不會隨著選擇的增加而下降。

基于上述規(guī)則，標準帝王蝶優(yōu)化算法的迭代公式如下。

遷移操作計算公式為

(9)

適應環(huán)境操作計算公式為

(10)

4.3 改進帝王蝶優(yōu)化算法

標準帝王蝶優(yōu)化算法具有一定的搜索能力和收斂魯棒性，但當陷入局部最優(yōu)解問題時，缺乏有效手段打破該局部極值，全局搜索能力不斷降低，最終導致無法搜索出全局最優(yōu)結(jié)果。根據(jù)京津冀區(qū)域的人口分布特點，引入輪盤賭策略對標準帝王蝶優(yōu)化算法進行改進。

輪盤賭策略可以將個體數(shù)據(jù)被選中的概率與經(jīng)濟適用量數(shù)值大小構(gòu)建正比關(guān)系，同時也能防止經(jīng)濟適用量較小的數(shù)據(jù)直接被丟棄。輪盤賭策略基于以下規(guī)則:①數(shù)據(jù)個體的選擇概率，即經(jīng)濟適應度數(shù)值大小越高的數(shù)據(jù)，它被選中的概率就越大；②不同數(shù)據(jù)個體的概率累積，即將數(shù)據(jù)個體的選擇概率從大到小進行累積，總和概率為1；③選擇隨機個體，即通過隨機生成0～1的數(shù)字找到對應的概率區(qū)間，便選擇該數(shù)據(jù)個體。

基于上述規(guī)則，輪盤賭策略的迭代公式為

(11)

(12)

5 仿真實驗與分析

5.1 實驗數(shù)據(jù)和環(huán)境

為驗證所提出的算法在逆向求解物流倉儲中心選址問題中的正確性和有效性，采用京津冀選址數(shù)據(jù)集作為選址算例。采用Python框架進行相關(guān)模型的編碼實現(xiàn)，在Windows10操作系統(tǒng)上采用Intel core i7-10750H處理器進行模型的訓練和調(diào)試。

5.2 物流區(qū)域劃分

為驗證改進K均值聚類算法在區(qū)域劃分的優(yōu)秀性能，通過在京津冀選址數(shù)據(jù)集上劃分6個區(qū)域，并與K均值聚類算法、K-modes聚類算法、K-medians聚類算法進行比較。同時提出了一種新的比較方法，通過引入固定點(114,36)作為起始點，再運用迪杰斯特拉算法得出6個區(qū)域的路徑和，其路徑和越小，所代表的聚類算法性能越優(yōu)秀。改進K均值聚類算法區(qū)域劃分結(jié)果如表2所示，4種聚類算法實驗結(jié)果如表3所示。

表2 區(qū)域劃分結(jié)果Table 2 Regional division results

表3 4種聚類算法聚類比較Table 3 Clustering comparison of four clustering algorithms

對于京津冀選址數(shù)據(jù)集劃分6個區(qū)域問題，改進K均值聚類算法取得了最小的路徑和。因為改進K均值聚類算法是對K均值聚類算法進行了改進，增加了判定函數(shù)，故運算時間略高于K均值聚類算法，但同比低于K-modes聚類算法和K-medians聚類算法。故改進K均值聚類算法具有較好的區(qū)域劃分性能。

5.3 物流倉儲中心選址

通過改進帝王蝶算法對物流倉儲中心進行逆向選址，從京津冀選址數(shù)據(jù)集提供的地理位置和經(jīng)濟適用量進行仿真實驗，得出6個實際的經(jīng)緯度坐標作為物流倉儲中心的選址地點，并與標準鯨魚算法(whale algorithm，WA)、標準螢火蟲算法(Firefly algorithm，F(xiàn)A)和標準蝙蝠算法(bat algorithm，BA)得出的結(jié)果進行比較。同時提出對應區(qū)域內(nèi)的所有數(shù)據(jù)點到選址點的距離和作為評價標準，距離和越小，該選址地點越優(yōu)秀。改進帝王蝶算法求得的選址地點如表4所示，4種優(yōu)化算法實驗結(jié)果如表5所示。

表4 6個區(qū)域選址地點Table 4 Six regional site selection sites

表5 4種優(yōu)化算法選址性能比較Table 5 Comparison of location selection performance of four optimization algorithms

可以看出，相較于其他3種優(yōu)化算法而言，改進帝王蝶優(yōu)化算法對于選址策略具有更優(yōu)的求解結(jié)果，表現(xiàn)方式為對應區(qū)域內(nèi)的所有數(shù)據(jù)點到選址點的距離和最小。改進帝王蝶算法的迭代次數(shù)明顯較小，算法運行時間也是最少，表明改進帝王蝶算法有著較高的收斂速度和求解速度?？傮w而言，相較于其他3種優(yōu)化算法，改進帝王蝶算法可以更加快速、精準地逆向求解出物流倉儲中心的具體地址。

6 結(jié)論

針對京津冀實際地域的物流倉儲中心選址缺失的情況，考慮到人口、物流和經(jīng)濟三者之間的關(guān)系，提出一種基于聚類特征的改進帝王蝶優(yōu)化算法，在滿足精確求解選址前提的情況下，注重提高算法的全局搜索能力，提高了算法的收斂速度和經(jīng)度，通過完成其他函數(shù)的對比試驗，驗證了算法的有效性，使其更加契合實際問題的解決。最終通過對算法構(gòu)建模型，并完成仿真實驗和相關(guān)分析，結(jié)果表明所提算法符合實際的需求，求解結(jié)果、迭代次數(shù)和收斂時間均優(yōu)于其他算法，使得物流運輸時間和成本都進一步降低。