基于地域特征的物流倉(cāng)儲(chǔ)中心逆向選址算法

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

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

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

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

為此，，基于京津冀物流發(fā)展的實(shí)際情況之上，提出了一種KMBR(K-means in Monarch butterfly with roulette)算法，通過建立物流倉(cāng)儲(chǔ)中心選址的數(shù)學(xué)模型，基于機(jī)器學(xué)習(xí)聚類特征，對(duì)標(biāo)準(zhǔn)帝王蝶優(yōu)化算法進(jìn)行改進(jìn)，加入輪盤賭策略，為京津冀物流倉(cāng)儲(chǔ)中心選址的問題提供有力依據(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ū)和河北各地級(jí)市的政務(wù)中心是當(dāng)?shù)胤秶暮诵牡囟危蜆I(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為直轄市或省地級(jí)市;n為對(duì)應(yīng)直轄市或省地級(jí)市所屬的區(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ū)域所屬的直轄市或省地級(jí)市的生產(chǎn)總值之和。

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

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

2 物流倉(cāng)儲(chǔ)中心選址數(shù)學(xué)模型

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

(2)

Dij≤Z

(3)

(4)

Ej≤V

(5)

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

式(3)表示每個(gè)區(qū)域的所需物品都必須有一個(gè)物流倉(cāng)儲(chǔ)中心完成出倉(cāng)發(fā)貨；式(4)表示一個(gè)區(qū)域的所需物品只能從一個(gè)物流倉(cāng)儲(chǔ)中心完成出倉(cāng)發(fā)貨；式(5)表示每個(gè)區(qū)域的經(jīng)濟(jì)適用量都應(yīng)小于等于與其對(duì)應(yīng)物流倉(cāng)儲(chǔ)中心涉及的經(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ī)則：①?gòu)臄?shù)據(jù)集中隨機(jī)選擇指定數(shù)量的數(shù)據(jù)作為初始的質(zhì)心向量；②計(jì)算每個(gè)新加入的數(shù)據(jù)與各個(gè)質(zhì)心向量的距離，將該數(shù)據(jù)加入對(duì)應(yīng)距離最小的類別中；③重新計(jì)算質(zhì)心向量。

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

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

(6)

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

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

(7)

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

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

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

對(duì)初始的質(zhì)心向量選擇引入單點(diǎn)密度和多點(diǎn)間距參數(shù)因子。單點(diǎn)密度是指以某一點(diǎn)為核心，以指定長(zhǎng)度為半徑的圓內(nèi)其他數(shù)據(jù)個(gè)數(shù)。多點(diǎn)間距是指多個(gè)單點(diǎn)密度間對(duì)應(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為指定長(zhǎng)度距離。

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

(9)

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

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

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

4.1 帝王蝶簡(jiǎn)介

帝王蝶作為世界上最知名的昆蟲之一[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)生由粒子位置是否變動(dòng)來表示。該算法通過模擬帝王蝶在自然界中的遷徙行為，其基于以下4個(gè)規(guī)則。

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

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

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

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

基于上述規(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)，引入輪盤賭策略對(duì)標(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ù)字找到對(duì)應(yīng)的概率區(qū)間，便選擇該數(shù)據(jù)個(gè)體。

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

(11)

(12)

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

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

為驗(yàn)證所提出的算法在逆向求解物流倉(cāng)儲(chǔ)中心選址問題中的正確性和有效性，采用京津冀選址數(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

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

5.3 物流倉(cāng)儲(chǔ)中心選址

通過改進(jìn)帝王蝶算法對(duì)物流倉(cāng)儲(chǔ)中心進(jìn)行逆向選址，從京津冀選址數(shù)據(jù)集提供的地理位置和經(jīng)濟(jì)適用量進(jìn)行仿真實(shí)驗(yàn)，得出6個(gè)實(shí)際的經(jīng)緯度坐標(biāo)作為物流倉(cāng)儲(chǔ)中心的選址地點(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í)提出對(duì)應(yīng)區(qū)域內(nèi)的所有數(shù)據(jù)點(diǎn)到選址點(diǎn)的距離和作為評(píng)價(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)化算法對(duì)于選址策略具有更優(yōu)的求解結(jié)果，表現(xiàn)方式為對(duì)應(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)地逆向求解出物流倉(cāng)儲(chǔ)中心的具體地址。

6 結(jié)論

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