張敬濤 陳江行

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

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

中圖分類號：F252.14

文獻標識碼：A

0引言

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

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

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

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

1問題建模

1.1問題描述

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

1.2模型建立

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

（2）客戶點每月的物流流量需求恒定。

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

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

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

2.1算法設計

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

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

3實例分析

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

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

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

4結束語

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