張敬濤 陳江行

摘要：在我國(guó)物流業(yè)飛速發(fā)展的背景下，文章主要研究考慮流量均衡的多配送中心選址問題，由此更好地處理物流選址中的實(shí)際需求。除去經(jīng)典選址問題中對(duì)于距離因素的考量，納入了對(duì)于配送中心之間物流流量均衡因素的考慮，并建立了相應(yīng)的數(shù)學(xué)模型。設(shè)計(jì)了一種帶約束的改進(jìn)K-means聚類算法來求解該問題，最后采用當(dāng)?shù)仄髽I(yè)的實(shí)際數(shù)據(jù)驗(yàn)證模型和算法的有效性，并對(duì)比分析了與經(jīng)典聚類算法的不同之處。

關(guān)鍵詞：配送中心選址;K-means算法;整數(shù)規(guī)劃

中圖分類號(hào)：F252.14

文獻(xiàn)標(biāo)識(shí)碼：A

0引言

隨著我國(guó)物流業(yè)務(wù)量的逐年增長(zhǎng)，配送中心作為物流網(wǎng)絡(luò)中的基礎(chǔ)節(jié)點(diǎn)，扮演著越來越重要的角色。關(guān)于配送中心的選址問題，除了需要考慮距離的因素外，其他復(fù)雜因素例如當(dāng)?shù)亟煌ㄇ闆r，經(jīng)濟(jì)發(fā)展因素，服務(wù)范圍等也需要納入考量。本文研究了考慮物流流量均衡的多配送中心選址問題，即為了服務(wù)若干客戶點(diǎn)，除了考慮與客戶點(diǎn)之間的距離，還應(yīng)保證各個(gè)配送中心所服務(wù)的客戶的物流流量需求差異較小，使得每個(gè)配送中心的利用率相對(duì)均衡。圖l為該問題的一個(gè)簡(jiǎn)單例子：三個(gè)配送中心分別覆蓋的客戶點(diǎn)的物流流量分別為250，230和280，若規(guī)定流量差異最大為50，則這種情況可視為各配送中心之間流量均衡。

目前國(guó)內(nèi)外關(guān)于多配送中心選址的研究已經(jīng)較為深入，其中聚類分析的思想是一種常見且重要的思想。其主要思路是將客戶群通過聚類分成若干簇（客戶群的子集），從而將多配送中心選址問題簡(jiǎn)化為若干個(gè)單配送中心選址問題。秦固、段華薇翻、饒良良以及Liu和Zhang人利用蟻群算法對(duì)客戶點(diǎn)進(jìn)行聚類然后分別求解單配送中心選址問題。ESNAF和KUCUKDENIZ、毛海軍等、陳磊等則通過模糊聚類的方法，建立指標(biāo)體系，將備選配送中心劃分為若干類，然后在每一類中選擇最優(yōu)的配送中心。葉潯宇和孔繼利等對(duì)客戶點(diǎn)采用聚類分析進(jìn)行分類后，利用重心法進(jìn)行配送中心的選址。

除去上述方法，K-means作為一種經(jīng)典的聚類方法，也在選址問題研究中得到了廣泛應(yīng)用。王信波等采用隨機(jī)采樣K-means方法進(jìn)行GIS中心的選址。馬大奎和陳銘通過K-means算法將全國(guó)二級(jí)城市進(jìn)行聚類，并以此進(jìn)行物流成本分析。Li等計(jì)二階段的K-means算法，將配送中心的承載能力和轄射半徑作為約束條件構(gòu)建社區(qū)物流網(wǎng)絡(luò)。劉威和王云婷等在K-means算法基礎(chǔ)上分別利用模糊規(guī)則的證據(jù)推理法（ERA）和層次分析法對(duì)選址方案進(jìn)行進(jìn)一步的優(yōu)化。

本文將提出一種改進(jìn)的K-means算法，將K-means算法與整數(shù)規(guī)劃方法集成，使得該算法可以高效處理選址問題中的約束，滿足選址問題中的一些現(xiàn)實(shí)需求。

1問題建模

1.1問題描述

考慮流量均衡的多配送中心選址問題可以描述為：給定n個(gè)客戶點(diǎn)，設(shè)每個(gè)客戶點(diǎn)i的位置為（xi，yi），月訂單量為qi?，F(xiàn)需要建造m個(gè)相同規(guī)模的配送中心，要求決策這m個(gè)配送中心的位置，確定每個(gè)客戶點(diǎn)所屬的配送中心，使得客戶點(diǎn)與所屬配送中心的距離總和最短，并且任意兩個(gè)配送中心的物流流量差值不超過給定閾值ε。

1.2模型建立

根據(jù)上述問題建立該選址問題的數(shù)學(xué)模型M。。模型中包含了以下基本假設(shè)：（1）任意一個(gè)坐標(biāo)位置均能建設(shè)配送中心;

（2）客戶點(diǎn)每月的物流流量需求恒定。

本問題的決策變量為每個(gè)配送中心的位置，即（aj，bj），以及0-1變量Oij，Oij=1表示客戶點(diǎn)i由配送中心j服務(wù)，否則不由配送中心j服務(wù)。模型M構(gòu)建如下：

上述模型說明如下：式（1）為目標(biāo)函數(shù)，即客戶點(diǎn)與所屬配送中心的距離之和最小化。式（2）表示每個(gè)客戶點(diǎn)只能由一個(gè)配送中心服務(wù)。式（3）表示任意兩個(gè)配送中心之間的月物流流量差值不得超過閾值ε。

2集成流量均衡約束的K-means聚類算法

2.1算法設(shè)計(jì)

上述問題的數(shù)學(xué)模型M目標(biāo)函數(shù)中含有非線性項(xiàng)，為非線性混合整數(shù)規(guī)劃，因此無法直接使用規(guī)劃求解器進(jìn)行求解。本文以在選址問題中廣泛應(yīng)用的聚類算法為基礎(chǔ)，在K-means算法的基礎(chǔ)上集成整數(shù)規(guī)劃方法，提出集成流量均衡約束的K-means聚類算法來獲得該問題的較優(yōu)解。區(qū)別于傳統(tǒng)的K-means算法直接將客戶點(diǎn)分配至最近的配送中心的策略，本算法通過整數(shù)規(guī)劃求解得到滿足給定約束的最優(yōu)客戶點(diǎn)分配方案。

本文算法的基本思路為：在K-means算法的框架下，通過上一次迭代得到的簇（每個(gè)配送中心所服務(wù)的客戶集合）計(jì)算本次迭代的配送中心的坐標(biāo)，由此模型M中的決策變量（ai，bi）轉(zhuǎn)化為已知量，數(shù)學(xué)模型轉(zhuǎn)化為僅有決策變量Oij的0-1整數(shù)規(guī)劃問題，此時(shí)模型M可使用規(guī)劃求解器求解得到符合要求的簇，并進(jìn)入下一次迭代，如此反復(fù)迭代，直至坐標(biāo)的變化量不再超過給定的闊值θ，即令△a與△b分別為上一代與本代橫縱坐標(biāo)差值，當(dāng)滿足△a≤θ且△b≤θ時(shí)，算法終止。算法流程圖如圖2所示。

3實(shí)例分析

本文采用當(dāng)?shù)匾患移囍圃炱髽I(yè)的真實(shí)數(shù)據(jù)作為驗(yàn)證及分析算例。該汽車廠在江浙滬地區(qū)共有124個(gè)客戶點(diǎn)，擬建立5個(gè)相同規(guī)模的配送中心用于服務(wù)該區(qū)域內(nèi)的所有客戶，并且要求各配送中心之間所處理的客戶月物流流量均衡。在此數(shù)值實(shí)驗(yàn)中，分別采用考慮流量均衡約束的改進(jìn)K-means算法以及經(jīng)典的K-means算法進(jìn)行計(jì)算，并對(duì)比計(jì)算結(jié)果。

本實(shí)驗(yàn)運(yùn)行于Intel Core i5-7200U（3.1Ghz）和8GB內(nèi)存的計(jì)算機(jī)上，并采用CPLEX12.8求解改進(jìn)K-means算法中的整數(shù)規(guī)劃模型M。實(shí)驗(yàn)中坐標(biāo)變動(dòng)閾值設(shè)為0.005，流量差異閾值設(shè)為500。實(shí)驗(yàn)結(jié)果對(duì)比如表1、圖3和圖4所示（白色標(biāo)記為配送中心位置）：

從實(shí)驗(yàn)結(jié)果中可以看出，傳統(tǒng)K-means算法的客戶點(diǎn)距離總和要優(yōu)于本文的改進(jìn)K-means算法。其原因在于改進(jìn)K-means算法需要兼顧流量均衡約束，從而損失了距離上的最優(yōu)性。從各配送中心月物流流量結(jié)果中，可得到兩組數(shù)據(jù)的極差分別為366和55 986。改進(jìn)K-means算法在控制流量均衡性上要遠(yuǎn)好于傳統(tǒng)K-means算法。在實(shí)際物流活動(dòng)中，若根據(jù)傳統(tǒng)K-means算法求解得到的結(jié)果建造配送中心，則1號(hào)配送中心每月需處理訂單61286件，而2號(hào)配送中心每月只需處理5 300件。由此會(huì)造成1號(hào)配送中心的物流能力無法匹配其物流流量，而2號(hào)配送中心則將處于物流資源閑置的狀態(tài)。反觀改進(jìn)K-means算法的求解結(jié)果，各配送中心的流量較為均衡，避免了上述問題的出現(xiàn)。

4結(jié)束語

本文針對(duì)多配送中心選址問題，在考慮實(shí)際物流活動(dòng)中流量均衡約束的基礎(chǔ)上，構(gòu)建了該問題的數(shù)學(xué)模型，并提出一種改進(jìn)的K-means算法來求解該問題。實(shí)驗(yàn)結(jié)果表明相較于傳統(tǒng)K-means算法，本文算法能夠很好地解決流量均衡約束下的多配送中心選址問題。此外，本文的算法框架同樣適用于選址問題中的一些其它約束，其拓展性將在今后進(jìn)行更深入的研究。