• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      基于改進(jìn)的K-means聚類的多區(qū)域物流中心選址算法①

      2019-08-22 02:31:52魯玲嵐秦江濤
      計算機系統(tǒng)應(yīng)用 2019年8期
      關(guān)鍵詞:聚類距離物流

      魯玲嵐, 秦江濤

      (上海理工大學(xué) 管理學(xué)院,上海 200093)

      區(qū)域配送中心配送規(guī)模較大,用戶較多,是物流中重要節(jié)點. 其合理的物流規(guī)劃不僅關(guān)系到是否能達(dá)到資源利用的效益最大化,滿足客戶的物流需求,保證物流時效性,也決定著投入物流成本的高低. 多區(qū)域物流配送中心選址需確定配送中心最佳數(shù)目、位置及覆蓋范圍. 聚類算法將一整個區(qū)域劃分,以此來確定配送中心數(shù)目以及其覆蓋范圍,非常適用于多配送中心的選址問題. 諸如K-means的聚類算法通常用于多區(qū)域配送中心的選址,但它們的初始聚類中心是隨機的,易陷入局部極小解,且K值不同導(dǎo)致聚類效果各異[1],并且有些城市地處偏僻,常被作為噪音數(shù)據(jù)排除,最主要的是由于山川、河流的阻礙,兩地之間的歐式距離并不能用來衡量實際的運輸距離.

      1 目前主要K-means聚類劃分方法綜述

      K-means聚類算法技術(shù)較為成熟,操作便捷,經(jīng)常被用于選址中對區(qū)域的劃分上. 考慮到該聚類方法對區(qū)域劃分時存在的劣勢,許多學(xué)者對該聚類方法進(jìn)行了改進(jìn). 朱培芬結(jié)合密度的思想,在可選范圍中優(yōu)先考慮邊緣點,具有良好的全局收斂性[2],但并未科學(xué)衡量距離因子,也未曾考慮物流需求等重要影響因子. 谷煒提出兩階段K-means聚類算法,在傳統(tǒng)K-means聚類后,通過不斷迭代來檢驗是否滿足配送時間最少的收斂條件,最終確定聚類結(jié)果[3],避免了算法陷入局部最優(yōu),但不斷的迭代大大增加了算法的運算時間. 于曉寒考慮到河流、公路等地理障礙,以“障礙距離”為差異度量標(biāo)準(zhǔn),站點工作量為約束,提出基于障礙距離的約束聚類算法[4],但距離并不是簡單的空間距離,雖其在抽象意義上是同質(zhì)的,但諸如城市這樣實質(zhì)的經(jīng)濟主體,距離明顯包含了更多的非空間因素.

      本文針對選址的實際情況,以城市經(jīng)濟引力模型為基礎(chǔ),考慮到距離的“非空間因素”,重新定義了對象間度量距離的因子. 同時把密度的思想引入K-means算法以解決K值不確性問題,并提出類內(nèi)差分均值的概念確定最優(yōu)聚類數(shù). 借助改進(jìn)的K-means聚類算法完成西北地區(qū)物流網(wǎng)絡(luò)的劃分,實現(xiàn)分區(qū)后,分別在這些區(qū)域中利用重心法對配送中心進(jìn)行最終的確定. 并通過和傳統(tǒng)K-means聚類結(jié)果對比,來驗證改進(jìn)后方法更優(yōu).

      2 改進(jìn)的K-means聚類算法和重心法

      2.1 改進(jìn)K-means聚類對區(qū)域劃分

      (1) 將密度思想引入K-means算法

      基于傳統(tǒng)K-means算法易受噪聲和孤立點影響的事實,本文將密度的思想引入K-means算法來確定k個聚類中心. 不僅可以避免噪聲數(shù)據(jù)干擾,而且可以有效降低算法時間復(fù)雜度. 考慮到M維空間的n維數(shù)據(jù)點Xi(i=0,1,2,···,n-1) 其基本思路如下:計算每個數(shù)據(jù)點Xi的密度. j=0,1,2···n-1. ra為正數(shù),定義為該點的領(lǐng)域半徑,取當(dāng)i取一個值時,k=0,1,2,···,n-1,Xi的密度指標(biāo)記為Di具體計算公式如下:

      根據(jù)式(1)獲取所有樣本點的密度指數(shù),按照從大到小的順序排列,選取前k個數(shù)據(jù)點作為聚類中心.

      (2) 基于經(jīng)濟引力模型對距離的定義

      在度量兩個城市之間相似度的過程中,把距離的概念僅定義為兩個城市間的空間距離是不可取的,為了更科學(xué)的衡量距離且更加有效的運用于實際情況,本文以居民可支配收入作為衡量城市間的經(jīng)濟引力因子,交通運輸時間作為衡量城市間的距離因子. 相應(yīng)的公式如下:

      式(2)中MiMj分別為城市i 和城市j的居民人均可支配收入指標(biāo). 居民人均可支配收入是衡量居民消費能力的重要指標(biāo),在消費性支出中包括食品煙酒、衣著、居住、生活用品以及其他用品和服務(wù). 隨著科技的進(jìn)步,出現(xiàn)了越來越多樣化的消費渠道. 這里主要考慮線上和線下消費. 在物流網(wǎng)絡(luò)建設(shè)不完善的地區(qū),居民線上消費遇到較大限制,消費被迫轉(zhuǎn)到線下,這些地區(qū)物流需求遠(yuǎn)遠(yuǎn)不及實際的消費需求,用居民的可支配收入來衡量物流需求更為現(xiàn)實. Dij為城市i和城市j的交通距離,本文以車輛在兩座城市之間行駛一趟的交通時間來衡量. u作為調(diào)節(jié)物流網(wǎng)絡(luò)劃分時受地區(qū)居民消費水平影響的程度. 一般來說,u越大,則說明在區(qū)域物流網(wǎng)絡(luò)劃分時,各地區(qū)的居民消費水平的吸引力占主導(dǎo)地位,城市間的距離因素被較大程度的弱化; 反之u越小,則認(rèn)為各地區(qū)的居民消費水平影響較弱,城市間的距離因素主導(dǎo)地位越強; u為0時,距離等價于歐式距離.

      (3) k值的確定

      聚類的目的是使同一類的樣本點間相似度高,而不同類間相似度低. 為精確測量聚類結(jié)果,進(jìn)一步確定k值. 本文采用計算類內(nèi)差分均值的評估方法. 計算樣本點與各自聚類中心的距離之和的平均值. 值越小,總的聚類距離越小,類間相似度越高,聚類效果越好; 反之,值越大,聚類距離越大,類間相似度越低,聚類效果越差. 用內(nèi)類差均值的方法衡量最佳聚類個數(shù),以達(dá)到修建最少的配送中心實現(xiàn)最大區(qū)域的覆蓋.

      2.2 重心法

      重心法是一種簡單可行的選址方法,通常用于解決連續(xù)點的單個配送中心選址問題,其唯一的決策依據(jù)是運輸成本. 應(yīng)用時,它對候選位置沒有任何限制,在已知各個備選地點的位置、物流需求量、各個備選地點的直線距離的前提下,運用重心法可以很好地確定配送中心的位置. 其運算方便,計算速度快,通過幾次迭代就能計算出理論位置. 但此種方法只適用于確定單一配送中心,對于確定多個配送中心的選址問題,此法并不適用[5].

      3 多區(qū)域配送中心選址模型

      針對多區(qū)域配送中心選址問題,本文采用目前比較主流的兩階段模型:第一階段把所有的需求點劃分為若干個配送區(qū)域,第二步階段選取相應(yīng)區(qū)域中最佳配送中心[6-8]. 借助該模型的選址步驟,本文首先用改進(jìn)的k-means聚類對區(qū)域進(jìn)行劃分,確定需建立配送中心的個數(shù)以及其配送范圍. 然后運用重心法在劃分的區(qū)域中選取合適的配送中心位置.

      3.1 基于改進(jìn)的K-means聚類對區(qū)域劃分

      本文運用MyEclipse Professional 2014軟件,采用JAVA語言,在Win10 64位系統(tǒng)環(huán)境下運行.其中按照樣本大小和聚類個數(shù)k值的關(guān)系,這里n為樣本的大小. 具體操作步驟如下:

      1) 存儲數(shù)據(jù),對數(shù)據(jù)進(jìn)行歸一化處理.

      2) 按照式(1)計算城市密度,按密度從大到小的順序排列,取排序前m個城市作為聚類中心候選點.

      3) 取前k個候選點作為聚類中心,按照式(2)計算當(dāng)k取不同值時的距離因子,這里u=0.1,當(dāng)u=0.1時,最能科學(xué)均衡經(jīng)濟引力與距離之間的影響力. 按照最小距離原則分配n-k 個城市樣本. 得到種聚類結(jié)果.

      5)結(jié)束,輸出最優(yōu)聚類結(jié)果.

      3.2 重心法對單一區(qū)域配送中心選址

      在上一階段過程中確定了配送中心的個數(shù)以及其覆蓋范圍的問題,但聚類過程中選取的聚類中心僅僅考慮到了城市交通的密度,而未考慮其他因素,不足以認(rèn)為是最合適的配送中心地址. 需結(jié)合單一配送選址模型在各個區(qū)域中對聚類中心進(jìn)行修正,從而確定單一區(qū)域配送中心的最佳位置,本文選取重心法來進(jìn)行此階段工作.

      4 評估模型建立

      區(qū)域物流中心選址模型是帶有復(fù)雜約束的非線性規(guī)劃模型,在構(gòu)建評估模型時先明確如下假設(shè):(1) 中心容量總是可以滿足所覆蓋需求點的需求量,并由該中心供應(yīng)的所有單位的需求量確定. (2) 一個需求點僅由一個物流配送中心供應(yīng). (3) 從物流中心到需求點通過零擔(dān)物流的方式進(jìn)行配送,且不考慮裝載的問題,僅以最大車載量進(jìn)行運算. (4) 運輸費用僅由運價、實際運輸路程決定,不考慮裝卸等人工成本. (5) 配送中心每輛車每天僅往需求點配送一趟. 基于以上5條假設(shè)建立衡量選址是否有效的模型. 目標(biāo)函數(shù)是各個配送中心到需求點的運輸費用之和最小,目標(biāo)函數(shù)為:

      式(3)中i表示配送中心,其取值為0,1,2,···,k-1,k表示配送中心個數(shù). j為配送中心所供應(yīng)需求點個數(shù),Ni表示第i個配送中心需求點集合. mij表示配送中心i到需求點j的計費里程,以km為單位. wij表示配送中心i到需求點j運輸貨物的重量,以kg為單位. J表示從配送中心i到需求點j的單位運價,以元/kg*km為單位.

      5 實例分析

      5.1 數(shù)據(jù)來源與處理

      西北地區(qū)地域廣闊,自然資源豐富,但地區(qū)天氣惡劣,城市之間道路險阻較多,交通十分不便,物資運輸上的不便是西北地區(qū)電子商務(wù)的發(fā)展主要阻礙. 本文對西北物流網(wǎng)絡(luò)進(jìn)行研究,由于新疆地區(qū)地域物流管理體制較混亂,機構(gòu)多元化,多采用外包的物流模式,這里主要討論除新疆之外的37個地級市的物流區(qū)域配送中心選址問題. 本次共采集37個城市間交通時間數(shù)據(jù)共703條記錄. 選取甘肅、青海、陜西、寧夏2016年的統(tǒng)計年鑒中選取四省的城鎮(zhèn)居民可支配收入. 并對已有數(shù)據(jù)進(jìn)行了歸一化處理,來消除數(shù)據(jù)量綱的影響.

      為驗證方法的正確性和實用性,抽象實驗數(shù)據(jù)為:零擔(dān)運輸?shù)臋C動車輛車身均為5~7米,車載量20 000 kg,平均行駛速度68 km/h. 考慮到西北地區(qū)一體化趨勢日益明顯,可忽略地域的運價費用差異,這里單位運價均定1元/kg*km. 通過城鎮(zhèn)居民可支配收入折算成每日的需求量以及配送所需車輛如表1所示.

      表1 城鎮(zhèn)每日物流需求量以及所需配送車輛量化表

      5.2 改進(jìn)方法選址求解

      (1) 確定聚類中心候選點,本文取前10位城市以及相應(yīng)密度,從結(jié)果看出,嘉峪關(guān)、酒泉、西安等作為當(dāng)前交通的樞紐中心,是聚類中心的首選. 在區(qū)域劃分中把密度思想引入是合理有效的. 結(jié)果如表2如下.

      表2 前10城市密度

      (2) 通過類內(nèi)差分均值評估,繪制曲線圖觀察最適k值. 從折線圖很直觀看出,當(dāng)k=6時,曲線出現(xiàn)拐點,達(dá)到最小值,當(dāng)k=7,8時類內(nèi)差均值小范圍增加,證明當(dāng)建立6個配送中心時物流網(wǎng)絡(luò)已經(jīng)達(dá)到了較好的覆蓋效果. 隨著配送中心的增多,覆蓋效果反而降低. 即當(dāng)37個城市被分為6類時,類間的相似度越高,聚類結(jié)果越好. 如圖1所示.

      確定最佳聚類個數(shù)后,根據(jù)改進(jìn)的K-means算法聚類,當(dāng)k=6時,聚類結(jié)果如表3所示.

      圖1 3~8個聚類的類內(nèi)差分均值

      表3 k=6時的城市分區(qū)結(jié)果

      (3) 把每個區(qū)域中城市作為物流服務(wù)需求點,人均可支配收入作為需求量,用重心法修正的配送中心結(jié)果如下,區(qū)域一:張掖,區(qū)域二:寶雞,區(qū)域三:嘉峪關(guān),區(qū)域四:銅川市,區(qū)域五:共和縣,區(qū)域六:白銀.配送中心地址及其輻射區(qū)域如圖2所示.

      圖2 西北四省配送中心地址及其覆蓋城市圖

      5.3 結(jié)果評估

      本文參照傳統(tǒng)的K-means算法對配送中心選址結(jié)果進(jìn)行對比. 在傳統(tǒng)的K-means算法中把城市之間的直線距離作為相似性度量的因子,以每個城市之間的經(jīng)緯度計算城市距離,設(shè)置k=6,閾值為0.000 001,共迭代50次,得到區(qū)域劃分后,再用重心法選出各個區(qū)域的配送中心. 以式(3)計算運輸成本,實驗結(jié)果如表4所示.

      表4 配送中心選址效果對比

      從配送中心選址效果對比中可以看出,對比傳統(tǒng)的K-means聚類算法,改進(jìn)后的算法每天可節(jié)約運輸成本41 626 420元,配送時間可節(jié)省30.62小時. 在保證配送時效的同時也節(jié)約了運輸成本,在一定程度上說明改進(jìn)后的算法較傳統(tǒng)的算法在實際中能創(chuàng)造更好的經(jīng)濟效益.

      6 結(jié)論

      通過本文分析,得出以下結(jié)論:在進(jìn)行區(qū)域劃分時,考慮當(dāng)?shù)氐膶嶋H情況越來越受到學(xué)者們的重視,本文以城市運輸距離與居民消費能力的指標(biāo)相結(jié)合,重新定義了對象間的相似性度量的距離因子,區(qū)域劃分后后,利用重心法對聚類中心進(jìn)行修正,科學(xué)的選出了每個區(qū)域內(nèi)的配送中心,更符合西北地區(qū)發(fā)展的實際情況. 為了驗證改進(jìn)方法的有效性,本文對比傳統(tǒng)Kmeans聚類對區(qū)域進(jìn)行劃分后選址結(jié)果,實驗可知:較傳統(tǒng)的K-means聚類,改進(jìn)后的算法不僅節(jié)省了配送時間,而且大大降低了運輸成本,具有很好的實際運用價值,為西北物流建設(shè)提供了參考. 但本文考慮的是西北地區(qū)這一宏觀的區(qū)域性概念,還有地處偏僻的部落并未考慮在內(nèi),因此劃分的區(qū)域未能全部覆蓋,想要在西北地區(qū)完成物流的全部覆蓋及其布局,還需要一些發(fā)展的契機,有待以后學(xué)者們?nèi)ヌ剿?

      猜你喜歡
      聚類距離物流
      本刊重點關(guān)注的物流展會
      “智”造更長物流生態(tài)鏈
      汽車觀察(2018年12期)2018-12-26 01:05:44
      算距離
      基于DBSACN聚類算法的XML文檔聚類
      電子測試(2017年15期)2017-12-18 07:19:27
      每次失敗都會距離成功更近一步
      山東青年(2016年3期)2016-02-28 14:25:55
      基于改進(jìn)的遺傳算法的模糊聚類算法
      基于低碳物流的公路運輸優(yōu)化
      愛的距離
      母子健康(2015年1期)2015-02-28 11:21:33
      一種層次初始的聚類個數(shù)自適應(yīng)的聚類方法研究
      決戰(zhàn)“最后一公里”
      商界(2014年12期)2014-04-29 00:44:03
      乡宁县| 新河县| 石柱| 邵武市| 泌阳县| 正安县| 久治县| 忻州市| 花垣县| 错那县| 营口市| 儋州市| 城固县| 读书| 多伦县| 云和县| 南召县| 来凤县| 尖扎县| 西吉县| 湟中县| 嘉义县| 前郭尔| 锡林郭勒盟| 含山县| 彭泽县| 中牟县| 萍乡市| 晋中市| 宁晋县| 霍城县| 广安市| 鄄城县| 宁阳县| 葫芦岛市| 搜索| 盐津县| 泗水县| 安新县| 丹棱县| 濉溪县|