許彥宸，戴 韜

（東華大學，上海 200051）

1 引言

隨著國民經濟的快速發(fā)展以及網絡的普及，越來越多的人習慣并且喜歡在網上購物，網上購物及一些O2O 服務的核心要素是其背后的配送體系，其中配送中心（配送站）的選址是一個影響最終響應速度的核心基礎問題。由于我國幅員遼闊、客戶需求井噴式涌現(xiàn)，無論是全國范圍的全國性配送問題還是一個城市內的區(qū)域性配送問題，都面臨著海量需求點的基本挑戰(zhàn)，而現(xiàn)有的物流選址模型及算法往往只能求解十幾個到幾十個需求點的基礎問題。因此，提出一種求解海量需求的多配送中心選址算法有非常強的理論與現(xiàn)實意義。

2 文獻綜述

多設施選址問題一般可以轉化為P-中值問題，該問題是由Hakimi 在1964年所提出，具體是指在已知需求點位置、待建中心的數量以及待選點位置集合的情況下，為P 個中心找到合適的位置，并為每個需求點指定一個中心，使得所有需求點到各自對應的中心點的總加權成本最低[11]。對于P-中值問題，學術界有多種求解方法和不同的思路，例如：Hansen等采用變領域搜索算法求解該問題[1]，而變領域搜索算法是常用的求解優(yōu)化問題的算法之一，而P-中值問題的目標就是優(yōu)化總加權成本；Mladenovi 等利用元啟發(fā)式算法求解P-中值問題[2]，Colmenar等采用高級貪婪隨機自適應搜索方法來求解[3]，該方法可以對傳統(tǒng)的貪婪算法進行改進以降低其陷入局部最優(yōu)解的可能性；Griffith等利用選址問題中的空間屬性，使用空間自相關性方法對P-中值問題進行求解[4]；Youkyung Won則采用廣義細胞形成的方法求解大規(guī)模多目標P-中值問題[5]；Drezner 等采用改進的啟發(fā)式算法求解平面P-中值問題[6]，取得了顯著的效果；Stefanello等對容量受限的P-中值問題進行了求解[7]；Carrizosa 等在網格上利用平方和為指標對數據進行聚類以求解P-中值問題[8]；而王飛飛和林文則對利用改進的重心—因次分析法求解3PL 配送中心選址問題進行研究并將其與P-中值問題進行聯(lián)系[9]；張彩慶和趙璐利用改進的P-中值模型對電網檢修公司分部選址問題進行研究[10]等。

3 基本模型與算法局限性分析

P-中值模型的數學表達式如下：

上述表達式中各符號的含義如下：i為需求點的編號、j為待建物流中心的編號；D為每個物流網點的需求量（一般與該網點所輻射的轄區(qū)內的人口數量成正相關）；W為物流中心與物流網點之間的加權成本（由距離、時間等因素共同決定）；Y 為0/1 決策變量，取0 表示物流中心j 不為需求點i 提供服務，而取1則表示物流中心j為需求點i提供服務；X同樣也為0/1決策變量，取0表示該點不建物流中心，取1則表示該點建物流中心。M為所有網點的集合，而N則為待建物流中心備選點的集合。

式（1）是P-中值問題的目標，即加權成本的最小化；式（2）是對物流中心和需求點的關系的約束，具體是指每一個需求網點必須屬于一個物流中心且只能屬于一個物流中心；式（3）是對待建物流中心的數量進行約束；式（4）是要求需求點必須能被其所屬的物流中心輻射到；式（5）是指在當前的j 位置是否建立物流中心；式（6）是指物流中心和物流網點之間僅有兩種關系，物流網點屬于物流中心與物流網點不屬于物流中心[11]。

顯然，P-中值問題是一個NP-Hard問題[12]。而求解P-中值問題的傳統(tǒng)方法是需要先經過考察，預先指定N個備選點（N＞P），隨后使用貪心算法或啟發(fā)式算法等方法求解。其缺點在于：第一，在指定N個備選點的過程中，可能會受到多個方面的影響（如決策專家的水平等），使得所選擇的N個備選點與潛在的正確的P個中心點的位置相去甚遠，后續(xù)的計算過程也只是徒勞無功。第二，求解P-中值問題的傳統(tǒng)算法只能求解規(guī)模較小的問題，一般為100個需求點以下。而如果超過該規(guī)模，計算的精度和速度都會受到影響。

對于本文所要研究的問題（以下簡稱本問題）而言，傳統(tǒng)的P-中值問題的解決方案無法在付出合理成本的情況下解決。理由是：本問題的規(guī)模遠超傳統(tǒng)的P-中值問題的解法所能解決的規(guī)模（從表1可以得知）；此外，本問題并沒有指定P 的值，因此N 個備選點的位置也無法確定。如果要進行多次嘗試，就要多次確定備選點，所要花費的計算成本是非常巨大的，甚至可能在有效時間內無法得到可行的滿意解。

表1 本文的需求規(guī)模與其他文獻的對比

4 算法設計

4.1 流程圖

本文提出的K-Means分類算法與重心法結合的算法邏輯如圖1所示。

圖1 K-Means算法結合重心法的算法邏輯

4.2 算法的詳細描述

重心法是求解設施選址問題中最簡單的問題—單一設施選址問題的常用方法之一[17]，數學表達式如下：

前文已經提及，本文所要解決的問題規(guī)模遠超傳統(tǒng)的P-中值問題的規(guī)模，因此需要一個新的方法，而聚類算法就是一個很好的選擇。聚類算法的基本思想是將所給數據分為若干簇，使簇內的數據有較高的相似度，而簇間的數據則具有較大的差異性。K-Means算法是數據挖掘中的一種聚類算法，其具有算法思想簡單、實現(xiàn)方便；算法的收斂速度較快以及能方便處理海量數據等優(yōu)點。

基礎K-Means算法的步驟如下：

步驟1：獲取最大迭代次數Iter及數據集D；

步驟2：隨機選擇K個點為初始的簇中心；

步驟3：對于每個數據點，分別計算該點與K 個簇中心的距離,與該點距離最?。ㄒ卜Q作相似度最大）的簇中心將是該點所屬的簇;

步驟4：重新計算K 個簇的中心，中心為該簇內所有點的算術平均值；

步驟5：若迭代次數到達最大迭代次數或當前的簇中心集合與上一次迭代相比沒有變化，則轉到步驟6；反之則轉到步驟3；

步驟6：輸出數據集的分類結果（K 個簇中心的位置、每個點所屬的簇以及簇內誤差平方和等）。

可以注意到，K-Means算法在步驟2選擇初始的簇中心集合時是隨機進行的，這樣會擁有非?？斓乃俣炔⑶以撍惴ǖ膶崿F(xiàn)非常簡單，但是這樣的結果是以精確率為代價換來的。因此，Arthur等便提出一種對選取K 個初始點的方式進行改進的K-Means 算法，被稱為K-Means++[18]。另外，在Arthur 等的論文中，其中有些數據集的規(guī)模超過1 000。因此，本文使用K-Means算法改進算法是合理的。本文使用的改進算法主要針對基礎算法的第2步，通過修改初始化K 個中心的方法改善了這個缺點，在減少迭代次數的同時并沒有降低該算法的速度及其實現(xiàn)的簡單性，其詳細步驟描述如下：

步驟1：獲取最大迭代次數Iter及數據集D。

步驟2.1：從數據集D 中隨機選擇一個點c1作為初始的第一個簇中心；

步驟2.2：選擇下一個簇中心ci，而數據集中剩余的任意點x'，成為ci的概率是，其中 D（x）是指點x到已確定的聚類中心的距離；

步驟2.3：重復步驟2.2，直至有K 個初始中心被確定。

步驟 3 至步驟 6：與基礎 K-Means 的步驟 3-6 相同。

從中可以看出，K-Means++與K-Means的區(qū)別僅僅在于步驟2（初始化K個中心的方法上）的不同，其余的步驟完全相同。因此，在實踐過程中，僅需要將剛剛的K-Means算法中初始化的部分略作改動即可獲得較大的速度方面的提升以及迭代次數的減少。另一點需要注意的則是，盡管在算法步驟5的原始描述的其中一個終止條件是本次迭代結束之后的簇中心集合與上一次迭代結束之后的簇中心集合相比沒有變化，在實踐的過程中往往利用公式來評判該次聚類的效果[13]，其中為第k個簇的中心，E則是簇內誤差的平方和。在實踐過程中，通常要求，其中δ是一個充分小的正數。

基于上述分析，本文的基本思路是先將所有的需求點劃分為K 個簇，然后將每一簇視為單一設施選址問題利用重心法進行求解[3]。雖然，K-Means++算法的K 值也無法確定，但是可以利用循環(huán)結構解決傳統(tǒng)的P-中值問題在每次運算之前都需要花大量計算時間去決策的備選點集合的確定問題，可以極大地減少最終的總時間。

根據現(xiàn)實配送管理問題的背景，我們需要讓盡量多的需求點在約定的配送距離以內，因此提出以噪音率衡量最終的選址結果。具體是將與其所屬的中心點之間的距離大于給定覆蓋半徑的需求點記為噪音點。

具體的數學表達式如下：

其中，式（9）用于計算每個需求點到其所屬中心點的距離，其中k 表示第i 個需求點屬于第k 類。而式（10）中Noise Rate的下標d則表示噪音率受到給定的配送中心覆蓋半徑d的影響。

5 算例實驗

5.1 數據預處理

為求解上述問題并驗證本文所提出方式的可行性，本文選用“數據超市”中公開的“百度地圖POI-全國各城市快遞網點數據”的示例數據[19]進行驗證，共1 000條數據。盡管初始數據一共有16個特征，但是僅需要使用lat（緯度）和lng（經度）兩個特征，在設施選址問題的領域內這種特征的選取方法也是較為常見的[20]。對經過處理的數據執(zhí)行可視化操作，如圖2所示。

圖2 所有需求點的位置

從圖2中可以看出，該樣本的分布基本符合中國各地區(qū)的快遞情況，因此這份數據是可信的。

5.2 實驗結果分析

該算法在CPU為i5-8250U的筆記本電腦上運行的時間在330s 至350s 之間。因此，該方法可以在合理時間內解決大量需求點的選址問題。

僅考慮待建中心數量和噪音率的關系。在給定覆蓋半徑為120km 的條件下，繪制出結果圖，如圖3所示。從圖3中可以看出，該算法最終是收斂的。但在某些情況下，隨著物流中心的個數增加，噪音率同樣也會有所波動，這是本文算法作為啟發(fā)式算法的一個缺點。

為了保持問題的一般性，我們不假設任何與運營相關的效益與成本系數，因此僅以噪音率來刻畫配送中心的收益。通過圖3發(fā)現(xiàn)，在新建100個左右配送站點時，新建站點邊際收益迅速下降，當配送站點數量超過175時，收益更是幾乎沒有任何增加。單從圖上來看，100個左右的配送站點可能是較為可行的結果，若現(xiàn)實最終的數量在此范圍附近時，需要逐一計算每個點的加權成本加以確定。

將覆蓋半徑也作為變量加入到考慮中來，繪制出的結果如圖4所示。從圖中可以發(fā)現(xiàn)，在任何變量的搭配下該方法都可以收斂，因此該方法是現(xiàn)實可行的。

6 總結

本文首先提出需求點數量巨大、配送中心數量未知的多配送中心選址問題，并指出傳統(tǒng)的求解該類型問題的方法無法在有效時間內解決。因此本文提出一種基于K-Means算法和重心法結合的算法求解該問題，并提出使用K-Means++算法改進基礎算法進行需求點的分類。由于一般的K-Means算法中的“距離平方和”指標并不能準確的反映配送問題的實際分類效果，因此，本文又提出了“噪音率”指標來刻畫配送管理背景下需求點與配送中心的平均距離。最后，本文選用公開的數據集（共計1 000 個需求點）驗證了算法的合理性。本文提出的分類結合重心法的方式為解決現(xiàn)實中海量需求的配送站點選擇問題提供了一種新的思路。

圖3 待建配送中心個數與噪音率的關系

圖4 待建中心個數、覆蓋半徑和噪音率之間的關系