基于K-means算法的低碳疫苗配送中心選址研究

□ 周善添，蘇凌云，張 衡，徐瓏瑋

(江蘇大學 汽車與交通工程學院，江蘇 鎮江 212013)

1 前言

近年來，隨著經濟發展和人民生活水平的提高，人們在醫療安全方面的需求更加強烈，主要體現在年疫苗接種劑次穩步增長。數據顯示，國內疫苗市場的總規模由2017年的253億元增至2020年的640億元，2016-2020年的復合年均增長率為36.26%。中商產業研究院預測，2022年中國疫苗市場規模將達到893億元(不包含新冠肺炎疫苗)。隨著計劃免疫和常態化防疫工作的深入開展，未來的疫苗需求量預計會大幅度增長，這對我國的疫苗供應鏈提出了更高的要求。目前我國普遍采用的仍然是傳統疫苗供應鏈模式，在這種傳統的疫苗配送模式下，疫苗的中轉環節過多、路徑過長，造成疫苗在途時間增加，疫苗失活率高，二氧化碳排放量過多，因此對傳統供應鏈模式提出改進勢在必行。

物流中心是物流系統和供應鏈良好運行的關鍵因素[1]，集中配送是當前疫苗供應鏈改革的主要措施[2]，針對上述問題，我們提出對第三方物流配送中心模式進行改進。近年來，國內外部分學者對藥品物流多中心選址問題進行了研究。舒彤等[3]結合選址策略、庫存策略和客戶服務策略，構建了中斷風險下醫藥冷鏈配送中心多目標選址模型,并采用帶權逼近理想點法與遺傳算法進行求解。陳心媛[4]借助GIS大數據平臺定量分析決策點坐標，結合實際情況通過改進傳統重心法，優化物流中心選址。王凱成等[5]運用AHP法確定各指標權重，結合TOPSIS法比較各醫藥配送中心選址方案與正負理想點的距離，依據其相近度，選擇遠離負理想點的方案作為結果，最終確定藥品物流配送中心選址。Bayu Irwanto等[6]以甘肅省為例，采用重心法確定醫藥工業選址。Bayan Hamdan等[7]針對災后血液的配送問題，構建了一個雙目標穩健優化模型。國內外對物流配送中心包括醫藥物流配送中心的選址的研究已經相對成熟，但疫苗物流配送中心選址的相關研究少之又少。疫苗物流隸屬于醫藥品物流，但相對于醫藥物流，其時效性要求更加嚴格，疫苗的失活率與在途時長息息相關，因此對于疫苗配送中心的選址應重點考慮配送時間和距離因素，而K-means聚類算法在求解總距離最小簇中心點時具有良好的效果，同時K-means聚類算法在對大量復雜的數據進行聚類時具有良好的效果，能夠綜合考慮得到局部最優結果，且分簇結果更加均勻。

因此，本研究區別于傳統疫苗供應鏈模式，提出了物流中心結構疫苗供應鏈模式以及一種以碳排放量最小為目標，基于K-means聚類算法的疫苗配送中心的選址策略，并以手肘法選取最優K值，以上海市為例，驗證了其可行性及實際應用價值。其對于提高疫苗運輸效率、降低疫苗失活率、減少運輸途中產生的碳排放量具有重要作用。

2 疫苗供應鏈模式

2.1 傳統疫苗供應鏈模式

疫苗供應鏈是指疫苗從原料采購開始直至疫苗成品被送到消費者注射這個過程中所涉及的各個部門或企業以及最終消費者組成的供需網絡。按照我國管理體制，主要由原材料供應商、疫苗生產商、批發商、各級疾病控制中心和衛生防疫部門、接種單位組成。

我國傳統疫苗供應一直采用由疾病預防控制中心壟斷經營的計劃經濟管理模式[8]。在這種垂直結構的疫苗供應鏈模式中(如圖1所示)，各級疾控中心既是上一級疫苗供應的需求者，又是下一級疫苗需求的供應者。同時，各級疾控中心除了滿足下一級機構的需求外，還要直接供應疫苗給管轄區域內的疫苗接種單位，完成相應地區的人群接種。

這種結構存在著供應鏈利益分配與激勵機制問題以及供應壟斷、供應層次過多、配送路徑長、供應鏈運營監管機制不健全等矛盾。

2.2 基于物流中心模式的疫苗供應鏈系統

物流中心模式是指疫苗企業與第三方醫藥物流企業合作，根據業務需求設立物流中心，物流中心覆蓋管轄范圍內的疫苗配送。物流中心都備有疫苗庫存，疫苗企業接到CDC(中央配送中心)的訂單后，疫苗從當地的物流中心出發配送到CDC，物流費用按照物流操作環節收費。

在物流中心模式下，疫苗企業具有更強的供應鏈掌控能力，對疫苗配送的時效性更高、透明度更強、路徑更短、碳排放更低?；谖锪髦行哪Ｊ降囊呙绻溝到y結構如圖2所示。

圖2 基于物流中心模式的疫苗供應鏈模式

3 算法概述

3.1 K-means算法

K-means是一種迭代求解的聚類分析算法，高效可伸縮，O(NKt)計算復雜度為接近于線性(N是數據量，K是聚類總數，t是迭代輪數)；收斂速度快，原理相對通俗易懂，可解釋性強；聚類效果較好，同時為克服少量樣本聚類的不準確性，該算法本身具有優化迭代功能，在已經求得的聚類上再次進行迭代修正剪枝確定部分樣本的聚類，優化了初始監督學習樣本分類不合理的地方。

其基本思想：

①隨機選取數據集中的K個數據作為初始中心；

②運用歐式距離計算非中心點到聚類中心的距離，數據選定最近的中心作為一組；

③計算每組中非聚類中心到聚類中心的平均值作為新的聚類中心；

④重復②③步驟，直到聚類中心不再變化或者達到最大迭代次數。

歐式距離：

歐式距離的全稱為歐幾里得距離，主要用于度量空間中兩點之間的距離。對于給定的數據集X={Xn|n=1，2，…}，X中的每個對象有m個特征。例如：對象Xi=(xi1,xi2,…,xim)，其中，xi1,xi2,…,xim是對象Xi中m個特征的值。

歐式距離公式：

(1)

3.2 手肘法

手肘法是一種利用SSE和K值的關系圖確認最優K值的方式，SSE還可以替換為樣本點與聚類中心之間的歐式距離平均值，因此本研究選用SSE。其算法思想為數據集在K-means算法聚類下，隨著K的不斷增大，數據被分割得更詳細，聚類中心不斷增多，SSE逐漸減小。當K值小于真實聚類數時，隨著K值的增大，SSE值變化比較大，關系圖顯示兩點之間的連線會比較陡峭。當K與真實聚類數相等時，隨著K值的增大，SSE值的變化較小，關系圖顯示兩點間的連線會變得平緩。所以SSE值和K值的關系圖是一個“手肘型”的折線圖，“肘部”為最優K值。

(2)

式中:SSE為誤差平方和，Ci為第i個簇，Q為Ci的樣本點，Pi為Ci的質心。

4 模型構建

在實際情況中，城市疫苗接種點數量較多，接種數量龐大，而K-means聚類分析具有運算速度快、計算量小的優勢，因而適用于對大樣本數據進行分析處理并能夠有效縮短運算時間、提升運行效率[9]。本研究創新性提出物流中心模式疫苗供應系統，為城市疫苗需求點分區并選擇疫苗配送中心，由疫苗配送中心承擔疫苗配送任務。以每個區疫苗接種點到疫苗配送中心的運輸過程中產生的碳排放量之和最小為目標，本研究選取經緯度坐標作為距離的計算數據，建立K-means聚類模型及手肘法模型，其求解過程為，第一步，對城市疫苗接種點(即疫苗需求點)進行數據統計，根據數據初步確定該城市配送中心最大個數M；第二步，計算從K=1到K=M時各K值對應的疫苗配送中心位置并求解該K值對應的SSE值；第三步，繪制K=1到K=M時的SSE折線圖，若出現“肘部”則“肘部”對應K值為疫苗配送分區(即疫苗配送中心最佳數量)，該K值對應的疫苗配送中心位置即為最優疫苗配送中心位置，此時對應的配送產生的碳排放即為最優碳排放量；若未出現“肘部”則M值加1，計算K=M時配送中心位置及對應SSE值并重復第三步，直至出現“肘部”。流程如圖3所示。

圖3 疫苗配送中心求解流程

4.1 建立K-means聚類模型

已知模型樣本集{X}有m個疫苗接種點，K個疫苗配送分區{Sj,j=1,2,…,K}，建立聚類問題數學模型為

(3)

s.t

(4)

(5)

(6)

式(3)表示目標函數，K代表疫苗配送分區個數；Ek表示選擇K個疫苗配送分區時的配送產生的總二氧化碳排放量最小值(kg)；X代表第j個疫苗配送分區Sj中的疫苗接種點；nj代表某個疫苗配送分區中的疫苗配送中心；f表示燃料密度(kg/L)；e表示燃料的碳排放因子(CO2/kg)，即將油耗轉化為二氧化碳排放量的系數；a表示該車百公里油耗(L)；p表示經緯度實際距離轉化系數，即將經緯度坐標距離轉化為實際距離的系數(km/每一度弧長)。式(4)表示模型樣本只能分配到一個配送中心上。式(5)為求解樣本的均值向量公式。式(6)表示yij為0-1變量，yij為1時，表示樣本i分配到配送中心j上，否則為0。

4.2 建立手肘法模型

進行聚類分析之后，要通過手肘法確定最佳聚類數(K最佳)。手肘法的核心指標是誤差平方和(公式如式7所示)，用于表示聚類誤差，其值越大表示聚類細度越高，每個簇的聚合程度增加。當模擬聚類數KK最佳時，隨著K的增大會使所得到的每個簇的聚合程度趨向于穩定，故誤差平方和下降幅度會變得平穩，然后隨著K的繼續增大而趨于平緩，聚類中心將趨向于不再變化，此時“肘部”對應的位置即為最佳聚類數(K=K最佳)。

(7)

5 案例分析

5.1 實例相關數據

本研究以上海市為例，利用K-means聚類算法進行疫苗城市配送中心選址，并使用手肘法對K-means聚類結果進行分析，求解最優疫苗配送分區，同時求解出各K值對應的配送距離。疫苗經生產企業生產后交由第三方物流中心進行終端配送。在上海市及上海市區疾控中心在內的每個區級疾控中心轄區(除崇明區)內隨機選取3個鄉鎮級衛生服務中心作為配送對象(即疫苗接種點)，總計61個需求點(具體位置如圖4所示，經緯度如表1所示)，各需求點的位置由百度地圖測量獲得的經緯度表示。

圖4 疫苗接種點分布圖

表1 疫苗需求的經緯度

數據說明：

①本研究討論疫苗只進行一次單向配送，且每個需求點的需求量相同，選取的物流中心K值為1～10；

②疫苗配送選用依維柯CLW5040XLCN5柴油冷藏車作為運輸工具；

③由于崇明區位于崇明島上，位置特殊，其屬于孤立點，對本研究影響較大，不具有普適性，故而不做討論；

④經緯度坐標小數點后保留三位計算，并使用經緯度坐標進行兩點直線距離代替實際距離計算，經緯度坐標轉化為實際距離選取近似值111km/每一度弧長；

⑤燃料碳排放因子、燃料密度等相關計算數據如表2所示。

表2 相關計算數據

5.2 聚類與選址方案

本研究利用Dec-C++進行編程求解模型，對61個疫苗接種點進行聚類，經過迭代，得到不同K值的聚類結果，然后算出不同K值的SSE，畫出折線圖(如圖5所示)。

在考慮距離最短的情況下還要考慮成本問題，若聚類中心數目過多，會導致配送中心初期建設成本過高，后期的運營成本也會增加，故而于整體來說聚類中心數目越多，成本反而會增加，且疫苗儲存設備運作時會排放過多的二氧化碳，不符合綠色物流發展的理念。

結合手肘法，由SSE折線圖可以看出折線持續下降，且在K大于6后下降趨勢變得十分平緩，所以最優的聚類中心數目為6，即最佳配送中心個數為6(分區如圖6所示)。

從物流中心模式疫苗供應鏈各K值碳排放產生量與傳統疫苗供應鏈配送碳排放產生量對比圖(如圖7所示)及差值圖(傳統疫苗供應鏈碳排放減去各K值對應物流中心模式疫苗供應鏈碳排放得差值，如圖8所示)可以看出：通過手肘法選址得出的最優聚類中心數目較優，在K=6時配送產生的碳排放及配送距離相比傳統疫苗供應鏈減少效果更加明顯。

圖7 碳排放產生量對比圖

圖8 碳排放產生量差值圖

本次研究采用K-means聚類算法計算并采用手肘法選出K=6為最佳聚類中心數。K=6時，在物流中心模式疫苗供應鏈下單次配送距離約為381.1km，碳排放產生量約為101.5kg。傳統疫苗供應鏈單次配送距離約為658.6km，碳排放產生量約為175.4kg。物流中心模式疫苗供應鏈單次配送距離及碳排放相對傳統疫苗供應鏈減少約42.1%，碳排放量顯著下降。

由研究結果可見，基于物流中心模式的疫苗供應鏈具有很強的應用價值及實際意義，能夠顯著減少疫苗配送距離，提高疫苗配送效率，減少碳排放污染等，間接減少了疫苗失活率，具有較強的社會經濟效益。

6 總結

從目前掌握的實時數據來看，疫苗的需求量從2016-2021年穩步增長，且未來十年之內依舊處于增長趨勢。而疫苗本身具有的獨特性，使得它在運輸過程中對時效性要求非常高，據世界衛生組織的一項研究預估，全球每年有超過50%的疫苗被浪費，這在很大程度上是因為疫苗供應鏈系統及監管制度不完善。本研究通過對傳統疫苗供應鏈的改進，提出基于K-means聚類算法選取第三方疫苗配送中心的方法具有較大的應用前景。相對傳統疫苗供應鏈刪減不必要的中轉環節，省去的業務均由第三方物流承擔，直接減少了疫苗的在途時間，降低了疫苗的失活率，減少了資源的浪費。通過案例分析我們可以看出，相較于傳統疫苗供應鏈，第三方物流中心的存在可以使路徑大大縮短，物流中心模式疫苗供應鏈僅單次配送的距離和碳排放相對傳統疫苗供應鏈就可以減少約42.1%，而在未來十年內，疫苗需求量不斷上升的宏觀環境下，具有良好的實際應用價值和經濟效益。

由于K-means算法本身就具有缺陷，在應用算法時采用迭代的方法只能得到局部最優解，且本研究選取的數據集過少，不能全面覆蓋整個上海市，故得到的最優解并不能代表實際最優解；另外，本研究采用的經緯度實際距離轉化系數是一個大概常數值，而平均每一度的弧長是隨著緯度變化而變化的，因此在轉化為實際距離時存在細微的誤差；本研究假設只選擇一種車型進行單向配送，而實際配送應根據各疫苗接種點實際需求量采取多種車型配送。因此，對這些影響因素進行考慮是我們下一步的研究方向。