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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

(2)

Dij≤Z

(3)

(4)

Ej≤V

(5)

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

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

3 聚類算法

3.1 K均值聚類算法

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

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

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

(6)

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

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

(7)

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

3.2 改進(jìn)K均值聚類算法

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

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

單點(diǎn)密度的計(jì)算公式為

(8)

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

多點(diǎn)間距的計(jì)算公式為

(9)

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

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

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

4.1 帝王蝶簡介

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

4.2 標(biāo)準(zhǔn)帝王蝶優(yōu)化算法

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

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

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

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

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

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

遷移操作計(jì)算公式為

(9)

適應(yīng)環(huán)境操作計(jì)算公式為

(10)

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

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

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

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

(11)

(12)

5 仿真實(shí)驗(yàn)與分析

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

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

5.2 物流區(qū)域劃分

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

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

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

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

5.3 物流倉儲中心選址

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

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

6 結(jié)論

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