基于聚類和二分圖匹配的物流派件調(diào)度方法

應(yīng) 毅,唐 立,劉定一,劉亞軍

(1.三江學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院,江蘇 南京 210012;2.會(huì)津大學(xué) 計(jì)算機(jī)科學(xué)與工程研究生院,日本 會(huì)津若松 965-8580;3.東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,江蘇 南京 210096)

隨著信息通信技術(shù)的快速發(fā)展和基于互聯(lián)網(wǎng)/移動(dòng)互聯(lián)網(wǎng)的各類應(yīng)用的普及,以商品購(gòu)銷為核心的電子商務(wù)逐漸成為經(jīng)濟(jì)增長(zhǎng)的新亮點(diǎn).電子商務(wù)物流的基本流程由倉(cāng)儲(chǔ)系統(tǒng)、運(yùn)輸主干網(wǎng)、“最后1 km”配送3個(gè)階段組成.作為最末端的服務(wù)機(jī)構(gòu),網(wǎng)點(diǎn)在物流網(wǎng)絡(luò)中承擔(dān)了包裹的派送和收取任務(wù).快遞人員從網(wǎng)點(diǎn)出發(fā),沿預(yù)先設(shè)置好的路線將包裹遞送到客戶手中,同時(shí)從客戶手中接收包裹,最后將所收包裹送回網(wǎng)點(diǎn).在此情況下,快遞人員頻繁往返于客戶和網(wǎng)點(diǎn)之間.該問(wèn)題在理論上可使用車輛路徑問(wèn)題(vehicle routing problem,VRP)進(jìn)行刻畫.車輛路徑問(wèn)題在1959年第1次被提出[1],現(xiàn)被廣泛應(yīng)用在物流分撥中心之間的車輛調(diào)度和路徑安排上.但網(wǎng)點(diǎn)配送服務(wù)與分撥中心的VRP又有較大不同,網(wǎng)點(diǎn)服務(wù)的客戶數(shù)量眾多,分布在城市的各個(gè)大街小巷,在地理位置上相對(duì)集中又整體分散.對(duì)于大規(guī)模VRP的求解可以通過(guò)聚類算法縮小問(wèn)題規(guī)模,降低求解難度.文獻(xiàn)[2]采用模糊系統(tǒng)聚類方法進(jìn)行客戶分類,運(yùn)用智能加權(quán)集成動(dòng)態(tài)屬性生成配送策略.文獻(xiàn)[3]考慮地理及環(huán)境因素進(jìn)行區(qū)域劃分,采用k-means聚類算法進(jìn)行車輛任務(wù)分配.文獻(xiàn)[4]結(jié)合k-means聚類和模糊聚類劃分配送區(qū)域,采用遺傳算法規(guī)劃車輛路徑.但傳統(tǒng)的聚類算法均采用客戶之間的直線距離構(gòu)造計(jì)算模型,未融入實(shí)際路徑信息.

地理信息系統(tǒng)(geographic information system,GIS)具備地理空間信息分析處理能力,能為物流管理尤其是物流配送過(guò)程提供地理空間計(jì)算支持和決策幫助.文獻(xiàn)[5]基于GIS路網(wǎng)描述的數(shù)學(xué)模型,建立啟發(fā)式-模擬退火算法進(jìn)行配送區(qū)域劃分的求解.文獻(xiàn)[6]基于GIS路徑數(shù)學(xué)模型通過(guò)模糊聚類算法對(duì)物流配送線路進(jìn)行劃分.文獻(xiàn)[7]借助GIS軟件采用VRPTW模型和禁忌搜索算法獲得在交通順暢和交通擁堵情況下的最優(yōu)配送路線.但以上研究?jī)H討論了配送問(wèn)題求解的距離最短[5-6]或時(shí)間最少目標(biāo)[7],未考慮任務(wù)分配的合理性和均衡性.針對(duì)此問(wèn)題,筆者依托ArcGIS平臺(tái),構(gòu)建智能物流信息系統(tǒng),提出“先分區(qū),后排班”的2階段調(diào)度策略,簡(jiǎn)單描述如下:首先通過(guò)地名地址檢索技術(shù)將分布密集的“客戶面”聚合成“配送點(diǎn)”;然后針對(duì)配送任務(wù)經(jīng)濟(jì)平衡目標(biāo),利用k-medoids聚類算法劃分派送區(qū)域;最后通過(guò)基于二分圖匹配的派件調(diào)度KM(Kuhn-Munkres)算法實(shí)現(xiàn)快遞人員的工作分配.試驗(yàn)證明這種混合了數(shù)據(jù)挖掘和圖論算法的網(wǎng)點(diǎn)派件調(diào)度方法,能使配送區(qū)域更加聚集,各快遞人員之間的工作分配更加均衡,有效提高末端物流的配送效率.

1 智能物流信息系統(tǒng)架構(gòu)

現(xiàn)代物流系統(tǒng)是在智能交通和信息技術(shù)的基礎(chǔ)上運(yùn)作的物流服務(wù)體系,通過(guò)對(duì)各物流環(huán)節(jié)的信息采集和數(shù)據(jù)處理,為物流企業(yè)提供高效管理手段,為客戶提供高質(zhì)量的服務(wù).

構(gòu)建的針對(duì)末端配送的智能物流信息系統(tǒng)由物流數(shù)據(jù)層、業(yè)務(wù)邏輯層、應(yīng)用服務(wù)層3部分組成,如圖1所示.

圖1 智能物流信息系統(tǒng)架構(gòu)

業(yè)務(wù)邏輯層是本系統(tǒng)的核心,包含Web Server和ArcGIS Server兩部分,Web Server由Java EE服務(wù)器JBoss和ArcGIS Web Adaptor組成.Web Adaptor組件使ArcGIS Server和傳統(tǒng)的Web服務(wù)器相結(jié)合,它是GIS服務(wù)使用者的唯一入口,接收客戶端的請(qǐng)求,然后把請(qǐng)求轉(zhuǎn)發(fā)給ArcGIS Server.與GIS相關(guān)的服務(wù)由ArcGIS Server負(fù)責(zé)提供,如:空間數(shù)據(jù)管理、地圖可視化和路徑分析等.

在應(yīng)用服務(wù)層,ArcGIS for Desktop是GIS資源(如電子地圖)的創(chuàng)建者,并通過(guò)ArcMap(ArcGIS for Desktop中的一個(gè)主要程序)連接到ArcGIS Server將本地資源發(fā)布為Web服務(wù).調(diào)度管理和移動(dòng)終端是GIS服務(wù)的使用者和消費(fèi)者,移動(dòng)端APP為快遞人員提供上報(bào)位置信息、接收調(diào)度指令等物流服務(wù)功能.

物流數(shù)據(jù)層負(fù)責(zé)數(shù)據(jù)存儲(chǔ):Oracle數(shù)據(jù)庫(kù)以表的形式保存地理數(shù)據(jù)對(duì)象;MySQL為Java EE應(yīng)用存儲(chǔ)普通業(yè)務(wù)數(shù)據(jù)(如客戶信息).

系統(tǒng)整體基于Java語(yǔ)言和Esri ArcGIS 10.4開發(fā)實(shí)現(xiàn).主要軟件包括:ArcGIS for Server,ArcGIS for Desktop,ArcGIS Run-time SDK for Java,ArcGIS Run-time SDK for Android,Oracle 11g R2.

2 配送區(qū)域劃分方法

物流末端的配送服務(wù)對(duì)象是密集分布在某一區(qū)域內(nèi)的眾多客戶,如果按照一般VRP模型,將眾多客戶直接作為路網(wǎng)節(jié)點(diǎn)進(jìn)行求解,問(wèn)題規(guī)模將會(huì)變得極為龐大,計(jì)算復(fù)雜耗時(shí).筆者提出“點(diǎn)面聚合,區(qū)域聚類”配送目標(biāo)劃分方法,首先通過(guò)地名地址檢索技術(shù)將一些分布較為密集的“客戶面”聚合成“配送點(diǎn)”,然后在派件量均衡的原則下利用k-medoids聚類算法劃分派送區(qū)域.這能較好地降低問(wèn)題規(guī)模,提高調(diào)度算法效率.

2.1 點(diǎn)面聚合

電商客戶特別是城區(qū)客戶分布較為密集,經(jīng)常有眾多客戶相鄰的現(xiàn)象,如同一個(gè)小區(qū)、同一座寫字樓.點(diǎn)面聚合用于合并距離過(guò)于接近的客戶,它將邏輯上松散的收件地址映射為相同的地理位置,例如“金貿(mào)新寓3棟1單元201室”和“金貿(mào)新寓7棟2單元302室”都聚合到“金貿(mào)新寓西北門”這一地址(地理坐標(biāo):32°03′97″N,118°76′16″E).這個(gè)映射過(guò)程由自開發(fā)的地名地址檢索組件[8]完成,它基于全文檢索引擎Lucene實(shí)現(xiàn),對(duì)于模糊查詢具有更好的搜索效率和準(zhǔn)確性.

2.2 區(qū)域聚類

劃分法聚類將n個(gè)數(shù)據(jù)對(duì)象組織成k個(gè)簇(k≤n),使在同一個(gè)簇中的對(duì)象是相似的,而不同簇中的對(duì)象是相異的,算法最終使得每個(gè)對(duì)象對(duì)于簇中心的偏離總和最小.聚類分析的常用劃分方法有k-means[9]和k-medoids,其中k-means算法適合發(fā)現(xiàn)球狀簇且對(duì)離群點(diǎn)敏感,考慮到配送區(qū)域的一般形狀不符合近似圓形,所以適合采用k-medoids算法.對(duì)點(diǎn)面聚合后的客戶地址使用k-medoids聚類進(jìn)行配送范圍劃分,可以使得到的區(qū)域比較緊密,并進(jìn)一步簡(jiǎn)化問(wèn)題規(guī)模.

k-medoids算法的思想:對(duì)n個(gè)對(duì)象,選擇k個(gè)對(duì)象oi(i=1,2,…,k)作為簇中心對(duì)象,剩余的對(duì)象根據(jù)其與簇中心對(duì)象的距離分配給最近的簇,初步形成k個(gè)簇Ci(i=1,2,…,k).絕對(duì)誤差標(biāo)準(zhǔn)E是數(shù)據(jù)集中所有對(duì)象p與簇Ci的代表對(duì)象oi的絕對(duì)誤差之和,定義為

(1)

式中:dist為求距離的函數(shù).

然后反復(fù)地用非中心對(duì)象orandom來(lái)替代簇中心對(duì)象oj(j=1,2,…,k),對(duì)對(duì)象進(jìn)行重新歸類.重新歸類會(huì)引起E發(fā)生變化,可以用成本函數(shù)來(lái)計(jì)算重新歸類前后E的變化.成本函數(shù)S表示E變化的累計(jì),定義為

(2)

若S為負(fù),說(shuō)明這種替換能夠減少E,oj可以被orandom替換;若S為正,表示oj可接受,本次迭代沒(méi)有變化.

2.2.1k值的確定

k-medoids算法需要給定簇?cái)?shù)k.在“先分區(qū),后排班”方法中,前期的配送區(qū)域劃分是為了之后的快遞人員排班,故k值確定為當(dāng)日在崗的快遞人員數(shù)量.

2.2.2初始簇中心的選擇

選擇合適的初始簇中心對(duì)象可以使算法快速收斂,根據(jù)以往的物流數(shù)據(jù),可以人為指定派送量較大的k個(gè)區(qū)域中心為初始的簇中心.

2.2.3對(duì)象間的距離計(jì)算

當(dāng)前,物流配送領(lǐng)域的聚類算法多采用歐式距離計(jì)算對(duì)象差異度,不符合實(shí)際配送的交通情況,因?yàn)橛行┑刂冯m然直線距離很近,但之間無(wú)路可達(dá),即使被分到同一個(gè)簇中也無(wú)法提高配送效率.因此,對(duì)象間的距離計(jì)算要符合城市路網(wǎng)的實(shí)際情況.在智能物流信息系統(tǒng)中,ArcGIS Network Analyst模塊具有交通路網(wǎng)分析功能,可以求解實(shí)際道路的最短路徑問(wèn)題.

2.2.4算法結(jié)束條件

k-medoids算法的時(shí)間復(fù)雜度為O(t×k×n2),其中t為迭代次數(shù),算法效率略低.結(jié)合實(shí)際應(yīng)用情況,改進(jìn)k-medoids算法,利用工作量均衡指標(biāo)使算法提前結(jié)束,優(yōu)化執(zhí)行效率.

在實(shí)際工作中,不同配送區(qū)域之間存在著工作量不均衡的問(wèn)題,派送量較大的區(qū)域需要加班加點(diǎn)完成,快遞人員的薪酬收入也與派送量相關(guān).區(qū)域間工作量的不均衡影響到配送服務(wù)的質(zhì)量,也帶來(lái)人員流失等管理問(wèn)題.需要合理的標(biāo)準(zhǔn)來(lái)平衡配送區(qū)域的工作負(fù)荷,使工作量基本均衡,工作時(shí)間大致相同.故以工作周期內(nèi)(0.5 d或1 d)派件量大體相等作為區(qū)域聚類算法結(jié)果優(yōu)劣的衡量標(biāo)準(zhǔn).

對(duì)于劃分好的k個(gè)簇,計(jì)算包裹數(shù)Pi(i=1,2,…,k)中的最大值Pmax、最小值Pmin、平均值Pavg,由于劃分的目的是使配送區(qū)域工作量均衡,即將Pmax和Pmin的差控制在合理范圍之內(nèi),ε表示可接受的工作量差異,在算法實(shí)現(xiàn)中由決策者根據(jù)實(shí)際情況確定,一般設(shè)置為10%～15%.則定義算法的結(jié)束條件為

(3)

當(dāng)此條件滿足時(shí),表示當(dāng)前的簇劃分能夠滿足工作量均衡的條件.

基于k-medoids的配送區(qū)域聚類算法如下:

輸入:

k,結(jié)果簇的個(gè)數(shù);

D,包含n個(gè)對(duì)象的數(shù)據(jù)集合,每個(gè)對(duì)象由收件地址的經(jīng)度/緯度和包裹數(shù)構(gòu)成;

O,k個(gè)初始簇中心對(duì)象;

ε,可接受的工作量差異.

輸出:k個(gè)簇的集合.

操作方法如下:

do

調(diào)用ArcGIS NAServer,計(jì)算剩余對(duì)象到k個(gè)簇中心對(duì)象的實(shí)際距離,按照就近原則分配到最近的簇;

計(jì)算k個(gè)簇的包裹數(shù);

if (Pmax-Pmin)/Pavg≤εthen 得到一個(gè)可行解,算法結(jié)束;

隨機(jī)選擇一個(gè)非簇中心對(duì)象orandom;

計(jì)算用orandom代替oj后產(chǎn)生的總代價(jià)S;

ifS<0 then用orandom代替oj,形成新的簇中心對(duì)象集合;

while簇集合不發(fā)生變化.

3 派件調(diào)度分配算法

圖論中的二分圖模型在資源分配、工作安排等問(wèn)題求解中有重要應(yīng)用,匈牙利算法和KM算法是二分圖最大匹配問(wèn)題的常見(jiàn)解法.在智能交通領(lǐng)域,文獻(xiàn)[10]利用二分圖構(gòu)建網(wǎng)約車-客戶匹配度.文獻(xiàn)[11]采用二分圖最大匹配算法求解外賣配送調(diào)度問(wèn)題.文獻(xiàn)[12]使用匈牙利算法求解以油耗最小為目標(biāo)的車輛調(diào)度模型.

在物流末端的派件調(diào)度中,假設(shè)可分配的快遞人員為Ri(i=1,2,…,k),待配送區(qū)域?yàn)镃j(j=1,2,…,k),分別計(jì)算每一組分配的代價(jià)得分,找出全局最優(yōu)的“快遞人員-配送區(qū)域”分配組合,使總代價(jià)最低.問(wèn)題可以轉(zhuǎn)化為傳統(tǒng)的完備匹配下的最大權(quán)匹配問(wèn)題:在一個(gè)二分圖內(nèi),左邊的快遞人員節(jié)點(diǎn)集合R,右邊的配送區(qū)域節(jié)點(diǎn)集合C,對(duì)于每組左右連接RiCj有權(quán)重Wij,即派送代價(jià),求一種匹配使得所有Wij的和最大.常見(jiàn)的二分圖權(quán)值為1(有邊)或0(無(wú)邊)[12],文中改進(jìn)權(quán)值定義,根據(jù)快遞人員對(duì)配送區(qū)域及路況的熟悉程度,定義Wij為

(4)

KM算法通過(guò)給每一個(gè)頂點(diǎn)一個(gè)頂標(biāo)來(lái)將最大權(quán)匹配問(wèn)題求解轉(zhuǎn)換為求二分圖完備匹配問(wèn)題.算法流程如下:① 初始化可行頂標(biāo)的值;② 用匈牙利算法在相等子圖尋找完備匹配;③ 若未找到完備匹配,則修改可行頂標(biāo)的值,擴(kuò)充相等子圖;④ 重復(fù)②、③直到找到相等子圖的完備匹配為止.

基于KM算法的派件人員調(diào)度分配過(guò)程如下:

輸入:

k,快遞人員/配送區(qū)域的個(gè)數(shù);

R，快遞人員集合(k個(gè));

C，配送區(qū)域集合(k個(gè));

Wij，派送代價(jià)權(quán)重.

輸出:快遞人員-配送區(qū)域最大權(quán)二分匹配M.

操作方法如下:

fori← 1 tokdo∥初始化頂標(biāo)

LCi=0;

forj← 1 tokdo

LRi=max(LRi,Wij);

fori← 1 tokdo

while TRUE do用匈牙利算法尋找完備匹配;

if 找到一個(gè)完備匹配then該匹配即為最大權(quán)二分匹配,算法結(jié)束;

forj← 1 tokdo∥更新頂標(biāo)

if visRjthenLRj=LRj-INF;

if visCjthenLCj=LCj+INF.

其中:visRj,visCj分別為頂點(diǎn)Rj,Cj被訪問(wèn)過(guò);INF為無(wú)窮大.

4 試驗(yàn)及討論

4.1 試驗(yàn)區(qū)域概況

順豐速運(yùn)漢北街營(yíng)業(yè)點(diǎn)為客戶提供自寄自取和送件、收件等上門服務(wù).網(wǎng)點(diǎn)配送范圍為湛江路、龍園南路、鳳凰東街、漢中門大街、莫愁湖西路、水西門大街構(gòu)成的五邊形區(qū)域,區(qū)域面積大約2.56 km2,服務(wù)蘇城苑、華陽(yáng)佳園、教工新村、西城嵐灣、鳳凰熙岸、莫愁新寓等眾多居民小區(qū),服務(wù)人口約9.5 萬(wàn)人.區(qū)域內(nèi)住宅小區(qū)多,人口密度大,對(duì)物流服務(wù)質(zhì)量要求高,通過(guò)對(duì)網(wǎng)點(diǎn)實(shí)際配送情況的調(diào)研,將設(shè)計(jì)的“先分區(qū),后排班”派件調(diào)度方法應(yīng)用于該區(qū)域,取得了較為成功的效果.

4.2 電子地圖制作

城市道路網(wǎng)在電子地圖中的表現(xiàn)形式為數(shù)字化的矢量地圖,GIS中矢量地圖按照?qǐng)D層組織,每個(gè)圖層存放一類專題或一類信息.本次試驗(yàn)所需的電子地圖制作步驟如下:① 以高德地圖南京市鼓樓區(qū)地圖為基礎(chǔ),使用ArcMAP建立配送區(qū)域的BaseMap;② 制作道路圖層,用于描述道路的靜態(tài)地理信息(如車輛通行限制、路口平交/立交、道路雙行/單行),為NAServer模塊計(jì)算最短路徑提供準(zhǔn)確數(shù)據(jù);③ 制作網(wǎng)點(diǎn)和客戶圖層,標(biāo)注網(wǎng)點(diǎn)和主要客戶的經(jīng)緯度數(shù)據(jù),經(jīng)緯度數(shù)據(jù)可以通過(guò)導(dǎo)航定位儀實(shí)地勘測(cè)或高德地圖抓取(如網(wǎng)點(diǎn)門店地理坐標(biāo)為32°04′07″N,118°75′58″E;蘇城南苑西南門坐標(biāo)為32°04′72″N,118°74′40″E).

4.3 試驗(yàn)結(jié)果分析

網(wǎng)點(diǎn)共有12名快遞服務(wù)人員,根據(jù)業(yè)務(wù)繁忙情況,一般有8～10人進(jìn)行上門服務(wù).1次快遞人員的派件調(diào)度指令在移動(dòng)端APP上推送.

2019年4月1日的實(shí)際派件調(diào)度情況如表1所示.根據(jù)當(dāng)日在崗快遞員數(shù)量(k=8),選擇西城嵐灣、鳳凰熙岸、教工新村、華陽(yáng)佳園等8個(gè)包裹量較大或人口較多的小區(qū)作為初始簇中心;采用實(shí)際道路最短路徑計(jì)算對(duì)象距離(調(diào)用ArcGIS NA模塊);并設(shè)置ε=15%,k-medoids配送區(qū)域聚類算法將網(wǎng)點(diǎn)覆蓋范圍劃分為8個(gè)配送責(zé)任區(qū),并保證派件量大致相等.派件調(diào)度KM算法根據(jù)快遞員對(duì)區(qū)域和路況的熟悉程度,將8個(gè)配送責(zé)任區(qū)分配給8位快遞員.

表1 4月1日的實(shí)際派件調(diào)度情況

2019年3月22日至4月10日網(wǎng)點(diǎn)整體的派件情況如表2所示,其中從4月1日起網(wǎng)點(diǎn)啟用了“先分區(qū),后排班”派件調(diào)度方法,派件量差異有明顯下降.

表2 網(wǎng)點(diǎn)整體派件情況

為了衡量新方法的有效性和優(yōu)越性,將提出的“先分區(qū),后排班”2階段調(diào)度算法與基于距離聚類的遺傳算法[4]、模糊聚類線路劃分算法[6]進(jìn)行了對(duì)比試驗(yàn).基于距離聚類的遺傳算法使用歐拉距離進(jìn)行k-means聚類,將派送包裹分成k個(gè)區(qū)域,再使用遺傳算法規(guī)劃k個(gè)快遞人員的配送路線;模糊聚類線路劃分算法基于GIS實(shí)際路徑通過(guò)模糊聚類方法對(duì)配送線路進(jìn)行劃分.對(duì)以上2種算法的路線結(jié)果在智能物流信息系統(tǒng)中統(tǒng)計(jì)總配送距離,與2階段調(diào)度算法的實(shí)際應(yīng)用情況進(jìn)行比較,如表3所示.

分析數(shù)據(jù)可知,在行駛距離方面,基于距離聚類的遺傳算法按直線距離最小原則將客戶分類,不可避免地增加了行駛距離,2階段調(diào)度算法在派件調(diào)度時(shí)考慮了快遞人員的路況經(jīng)驗(yàn),以保證總體最優(yōu)的分配組合,因此,快遞人員的實(shí)際行駛距離并不比算法規(guī)劃的差;在工作量方面,由于劃分配送區(qū)域時(shí)進(jìn)行了工作量均衡的約束,2階段調(diào)度算法要遠(yuǎn)好于其他2種算法,5日平均派件量差異各低13.3%,16.4%.綜上可知,相比傳統(tǒng)算法,設(shè)計(jì)的2階段調(diào)度算法,有效縮短了配送路徑距離,并對(duì)快遞人員的經(jīng)濟(jì)平衡優(yōu)化效果顯著.

表3 3種算法計(jì)算結(jié)果對(duì)比

5 結(jié) 論

現(xiàn)代物流系統(tǒng)已經(jīng)進(jìn)入了信息化、網(wǎng)絡(luò)化、智能化的發(fā)展階段.基于ArcGIS,Web和Android等關(guān)鍵技術(shù)構(gòu)建了支撐物流末端配送的智能物流信息系統(tǒng).在該系統(tǒng)中改進(jìn)k-medoids聚類算法和二分圖最大權(quán)匹配KM算法,提出“點(diǎn)面聚合,區(qū)域聚類”配送區(qū)域劃分方法和“先分區(qū),后排班”派件調(diào)度策略.通過(guò)試驗(yàn)驗(yàn)證了模型和算法的正確性和優(yōu)越性,有效提高了物流信息的管理效率.在智能系統(tǒng)下改進(jìn)傳統(tǒng)VRP模型進(jìn)行派件路徑規(guī)劃是進(jìn)一步研究的重點(diǎn),攬送混合業(yè)務(wù)下的人員調(diào)度也是一個(gè)較好的研究方向.