基于GIS的時(shí)空聚類算法在多中心聯(lián)合配送問題中的應(yīng)用

梁辰 周峻旭

摘? 要：針對(duì)多中心聯(lián)合配送的車輛路徑問題，構(gòu)建了一種既考慮需求點(diǎn)時(shí)間窗口相近性又考慮地理空間鄰近性的聚類算法，首先設(shè)計(jì)了時(shí)空距離計(jì)算方法，然后運(yùn)用DBSCAN進(jìn)行時(shí)空聚類，并將聚類結(jié)果應(yīng)用于GIS路徑求解中。最后，構(gòu)造算例分析驗(yàn)證了模型和算法的有效性和可靠性，為快速有效地解決此類問題提供了一種新的思路。

關(guān)鍵詞：時(shí)空聚類;多配送中心;聯(lián)合配送;車輛路徑問題;GIS

中圖分類號(hào)：F252.14??? 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： Aimed at vehicle routing problem in joint distribution among multi centers， a clustering algorithm was developed with consideration both in time window adjacency and geographical spatial proximity. Time-space distance was first calculated and then DBSCAN clustering was applied to the time-space distribution of demand points， path solving was last carried out based on GIS. Finally， an example was tested to verify the effectiveness and reliability of the proposed model and algorithm， demonstrating a new thought for this kind of problems.

Key words： time-space clustering; multi-depot; joint distribution; vehicle routing problem; GIS

0? 引? 言

現(xiàn)有配送模式多采用自營物流對(duì)配送中心覆蓋范圍內(nèi)的消費(fèi)者進(jìn)行輻射式配送，單一配送中心獨(dú)立配送的模式割離了配送區(qū)域之間的關(guān)聯(lián)性，物流資源共享程度低，運(yùn)力供給與配送需求在時(shí)空上呈現(xiàn)失衡現(xiàn)象，因此，普遍造成車輛閑置率高、空載率高、忙閑不均、迂回運(yùn)輸?shù)葐栴}[1]。在考慮商品運(yùn)輸種類特點(diǎn)的基礎(chǔ)上，探索通過第三方物流或在共同配送聯(lián)盟方式，實(shí)現(xiàn)多中心聯(lián)合配送具有顯著必要性，不但可以減少配送及作業(yè)環(huán)節(jié)中的成本，提高整體物流服務(wù)水平，而且能使車輛和配送中心等物流設(shè)施資源得以充分的利用，提升物流配送效率，實(shí)現(xiàn)配送行業(yè)的降本增效。

在多中心聯(lián)合配送模式下，車輛可從任意一個(gè)配送中心出發(fā)，逐一行駛到任務(wù)列表中的各個(gè)需求點(diǎn)，待完成任務(wù)后則不必一定返回初始配送中心，可結(jié)束配送任務(wù)?？恐寥我庖粋€(gè)配送中心，等待后續(xù)指令。相比單一配送中心配送模式，聯(lián)合配送采用半開放式配送路徑，可以靈活地選擇最優(yōu)配送中心作為起始和終止節(jié)點(diǎn)，能夠快速響應(yīng)需求，節(jié)省因往返始發(fā)配送中心的空載、返程等行駛里程，實(shí)現(xiàn)聯(lián)合配送的效率優(yōu)化，擴(kuò)大配送地域范圍，提高配送時(shí)效性，未來或?qū)⒊蔀槌鞘鞋F(xiàn)代物流配送的主要發(fā)展趨勢。

經(jīng)典車輛路徑問題（Vehicle Routing Problem，VRP）問題屬于NP-hard。在數(shù)據(jù)建模型方面，多中心聯(lián)合配送同時(shí)具有MDVRP和OVRP特點(diǎn)，屬于帶時(shí)間窗的半開放式多中心車輛路徑問題HOMDVRPTW[2]。本文研究了基于GIS的多中心聯(lián)合配送問題，設(shè)計(jì)時(shí)空聚類算法，對(duì)該模式進(jìn)行分析，最后構(gòu)造算例分析驗(yàn)證了模型和算法的有效性和可靠性。

1? 算法設(shè)計(jì)

1.1? 時(shí)空距離計(jì)算。本文中時(shí)空路徑的概念來自時(shí)間地理學(xué)[3-5]，其最早被用來研究人類生命活動(dòng)地理特征，而后被引入日常行動(dòng)研究。時(shí)空路徑是由多個(gè)傾斜和垂直線段組成的集合，表示三維時(shí)空坐標(biāo)系內(nèi)的活動(dòng)軌跡，平面二維坐標(biāo)代表空間地理屬性，垂直坐標(biāo)代表空間活動(dòng)的時(shí)間屬性，其中，傾斜線段表示發(fā)生了空間移動(dòng)，傾斜的斜率表征車輛行駛速度，而垂直線段則表示停留在某地，時(shí)間進(jìn)展但空間位置無變化?；谏鲜鲈?，傳統(tǒng)VRP問題中的車輛路徑可以用時(shí)空路徑形式表示，如圖2所示，由配送中心DC出發(fā)遍歷所有需求點(diǎn)后返回DC的路徑：DC-A-B-C-D-DC和DC-D-E-DC。在多中心聯(lián)合配送模式下，如圖3所示，由DC1出發(fā)的車輛在完成D、E、C三點(diǎn)配送任務(wù)后，可就近前往DC2，而非返回出發(fā)點(diǎn)，可實(shí)現(xiàn)運(yùn)輸資源優(yōu)化配置，提高物流配送效率。

借助時(shí)間地理學(xué)理論框架，時(shí)間與空間兩類不同屬性可以在同一個(gè)三維坐標(biāo)系中表達(dá)，可采用一個(gè)具體數(shù)值衡量兩點(diǎn)之間的鄰近程度，即配送需求點(diǎn)的時(shí)空距離。當(dāng)兩點(diǎn)間的時(shí)空距離越小，說明配送中同一車輛從該點(diǎn)到另一點(diǎn)的可能性或可行性越大。計(jì)算兩點(diǎn)間的時(shí)間窗口距離，因時(shí)間屬性與空間屬性量綱并不一致，通?？蓪r(shí)間距離與空間距離進(jìn)行歸一化處理，再進(jìn)行加權(quán)計(jì)算，公式如下：

d=d+γ×d?????????????????????????????????????????????? （1）

d=T-T?????????????????????????????????????????????? （2）

式中：d表示i與j之間時(shí)空距離，d、d分別表示空間、時(shí)間距離，γ為時(shí)間距離換算系數(shù)，T表示時(shí)間窗起始點(diǎn)，d可利用GIS平臺(tái)沿著實(shí)際路網(wǎng)測量最短交通距離，相較歐氏距離更貼近交通運(yùn)行網(wǎng)絡(luò)真實(shí)情況。

另外，在計(jì)算時(shí)間距離時(shí)，需要整理所有配送中心的和需求點(diǎn)的時(shí)間窗，假設(shè)配送中心與需求點(diǎn)時(shí)間窗分別為10：00，14：00、11：00，14：00、11：30，16：00，時(shí)間窗起始點(diǎn)ET最小值為10：00，為配送中心最早服務(wù)時(shí)間，將10：00作為時(shí)間基準(zhǔn)，設(shè)為0時(shí)刻點(diǎn)，則兩個(gè)需求點(diǎn)的時(shí)間窗起始點(diǎn)可換算為60、90，11：00～10：00=1小時(shí)=60分，記為60，11：30～10：00

=1.5小時(shí)=90分，記為90，時(shí)間窗終止點(diǎn)LT換算同理，因此，上述舉例中的時(shí)間窗可換算成0，120、60，240、90，360。

1.2? 需求點(diǎn)時(shí)空聚類。聚類分析是對(duì)統(tǒng)計(jì)數(shù)據(jù)進(jìn)行分析的常用技術(shù)，在眾多領(lǐng)域受到廣泛應(yīng)用，聚類是將相似的對(duì)象分成不同組別，使組間差異盡可能大，組內(nèi)差異盡可能小，同一組內(nèi)的對(duì)象具備相似屬性。

車輛路徑優(yōu)化問題中需求點(diǎn)聚類多用于實(shí)現(xiàn)兩階段法優(yōu)化算法中的初始優(yōu)化，可有效降低計(jì)算復(fù)雜度，聚類對(duì)象通常為客戶點(diǎn)的地理空間位置。本文基于空間密度聚類算法（DBSCAN）思想，考慮配送服務(wù)時(shí)間窗口，設(shè)計(jì)真實(shí)道路網(wǎng)絡(luò)結(jié)構(gòu)下的配送需求點(diǎn)時(shí)空聚類算法。與K-means聚類算法需預(yù)先確定聚類數(shù)且僅適合凸集樣本有所不同，DBSCAN聚類依賴的是ε-鄰域半徑ε和ε-鄰域內(nèi)出現(xiàn)元素最少次數(shù)MinPts兩個(gè)重要參數(shù)，簇的定義是密度相連的點(diǎn)的最大集合，通過不停生長成足夠高密度區(qū)域從而完成聚類過程，可從含有噪聲的空間數(shù)據(jù)庫中生成任意形狀的聚類，DBSCAN方法適用于在車輛路徑問題中對(duì)不規(guī)則分布需求點(diǎn)的聚類分析[6-7]，一個(gè)簇包含的元素即為車輛一次配送的需求點(diǎn)集合。

基于GIS的需求點(diǎn)時(shí)空聚類算法具體流程設(shè)計(jì)如下：

Step 1：將各個(gè)需求點(diǎn)視為三維時(shí)空坐標(biāo)系中的要素對(duì)象，由需求點(diǎn)i地理坐標(biāo)和配送時(shí)間窗口起始點(diǎn)三者組成要素時(shí)空向量，導(dǎo)入相應(yīng)三維數(shù)據(jù)，生成數(shù)據(jù)向量矩陣;

Step 2：基于ArcGIS平臺(tái)，利用Network Analyst功能擴(kuò)展模塊獲取實(shí)際路網(wǎng)距離矩陣，按公式（1）和式（2）計(jì)算需求點(diǎn)的時(shí)空距離OD分布矩陣，以時(shí)空距離作為密度聚類值;

Step 3：標(biāo)定ε半徑參數(shù);首先計(jì)算所有需求點(diǎn)的k-距離（時(shí)空距離）差值，然后對(duì)k-距離進(jìn)行升序排列，輸出排序后的k-距離差;

Step 4：初始化所有需求點(diǎn)，標(biāo)記狀態(tài)為“未訪問”。

Step 5：隨機(jī)抽取一個(gè)配送中心點(diǎn)，判斷其是否為核心點(diǎn)，找到從該點(diǎn)出發(fā)密度可達(dá)對(duì)象集合，形成一個(gè)簇，簇的對(duì)象個(gè)數(shù)須大于MinPts，同時(shí)判斷是同一簇內(nèi)包含的配送需求量之和是否超過車輛載重量約束，標(biāo)記處理過的需求點(diǎn)為“訪問”狀態(tài)，配送中心點(diǎn)可多次被訪;

Step 6：返回Step 5，直到所有的需求點(diǎn)都被處理過，輸出簇。

最終，利用ArcGIS分別對(duì)每一個(gè)簇生成的聚類單元進(jìn)行路徑求解。

2? 問題描述

2.1? 擬解決問題。本文研究多中心聯(lián)合配送模式是在整合多家企業(yè)的物流配送中心及相關(guān)設(shè)備資源后進(jìn)行配送，配送中心可對(duì)所有車輛開放，接受車輛的終點(diǎn)停靠，需求點(diǎn)僅接受車輛的服務(wù)作業(yè)，不接受車輛的終點(diǎn)停靠，即車輛在需求點(diǎn)完成作業(yè)后必須離開，因此配送過程中車輛具有半開放式的特點(diǎn)。

2.2? 模型假設(shè)。模型基于如下假設(shè)：（1）配送中心、需求點(diǎn)地理空間位置已知，配送網(wǎng)絡(luò)中的各節(jié)點(diǎn)間具有可達(dá)性。（2）采用多中心聯(lián)合配送模式時(shí)，運(yùn)輸車輛車型相同，載重、行駛性能等屬性一致且已知。（3）每輛車行駛路線均從配送中心出發(fā)至配送中心結(jié)束，但不必返回出發(fā)時(shí)的原始配送中心。（4）每個(gè)需求點(diǎn)有且僅有一輛車進(jìn)行配送服務(wù)，需求訂單不可拆分，即一次性完成配送，不考慮單一需求超過車輛載重范圍的情況，不考慮貨物損壞。（5）僅考慮配送中心啟動(dòng)的固定成本，暫不考慮其建設(shè)、折舊成本等。

3? 算例分析

3.1? 算例描述。結(jié)合聯(lián)合配送特點(diǎn)，本文選擇遼寧省大連市瓦房店為實(shí)例研究區(qū)域，根據(jù)中國公路（OSM）數(shù)據(jù)為物流網(wǎng)絡(luò)底圖構(gòu)造算例，進(jìn)行仿真實(shí)驗(yàn)。假設(shè)多中心聯(lián)合配送模式下，F(xiàn)公司共有4個(gè)配送中心，計(jì)劃完成36個(gè)需求點(diǎn)的配送任務(wù)，配送車輛載重量為5t，平均行駛速度60km/h，配送成本6元/km，車輛固定成本200元/車，一個(gè)需求點(diǎn)作業(yè)時(shí)間為0.25h，時(shí)間窗起始時(shí)刻T在8：00～18：00之間隨機(jī)生成。

3.2? 結(jié)果分析。算例中需求點(diǎn)分散，每個(gè)DC規(guī)劃的配送覆蓋區(qū)域缺乏整體性、系統(tǒng)性，在地域空間上具有交叉性、重復(fù)性，在實(shí)際運(yùn)營中存在車輛使用數(shù)量多、返程空載率高、配送時(shí)效性低、配送費(fèi)用高等問題。

由表1數(shù)據(jù)可知，經(jīng)DBSCAN時(shí)空聚類后的路徑求解結(jié)果，明顯優(yōu)于ArcGIS平臺(tái)下網(wǎng)絡(luò)分析車輛配送（VRP）默認(rèn)程序分析得出的原始結(jié)果。經(jīng)過時(shí)空聚類后優(yōu)化求解，證明了基于GIS的時(shí)空聚類具有較好的優(yōu)化效果，也證明了多中心聯(lián)合配送模式可降低總配送成本，減少車輛使用數(shù)量，縮短車輛使用時(shí)間，具有可行性與合理性的實(shí)踐意義。

4? 結(jié)束語

本文針對(duì)多中心聯(lián)合配送模式的車輛路徑規(guī)劃問題，借鑒DBSCAN算法，設(shè)計(jì)了基于GIS的需求點(diǎn)時(shí)空聚類算法，考慮真實(shí)路網(wǎng)情況，并運(yùn)用GIS對(duì)聚類后的配送集合進(jìn)行路徑求解，為快速有效地解決此類問題提供了一種新的思路。此外，基于GIS空間技術(shù)的決策支持，進(jìn)行算例仿真研究，證明了多中心聯(lián)合配送的優(yōu)勢，可縮短作業(yè)時(shí)間，減少運(yùn)輸配送距離，優(yōu)化物流系統(tǒng)作業(yè)流程，實(shí)現(xiàn)物流行業(yè)降低成本、提質(zhì)增效的目標(biāo)。未來還可以考慮在車輛路徑問題中將DBSCAN時(shí)空聚類算法與智能優(yōu)化算法相結(jié)合，進(jìn)一步提高多中心車輛路徑模型和求解算法的準(zhǔn)確性和優(yōu)越性。

參考文獻(xiàn)：

[1] 范厚明，楊翔，李蕩，等. 基于生鮮品多中心聯(lián)合配送的半開放式車輛路徑問題[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2019，25（1）：256-266.

[2] 劉冉，江志斌，耿娜，等. 半開放式多車場車輛路徑問題[J]. 上海交通大學(xué)學(xué)報(bào)，2010，44（11）：1539-1545.

[3] 何保紅，梁麗婷，何明衛(wèi)，等. 基于時(shí)間地理學(xué)的居民活動(dòng)空間測度方法研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2020，20（4）：113-118.

[4] 李魯奇，孔翔. “雙十一”期間中國快遞流通的時(shí)空結(jié)構(gòu)與效率——基于時(shí)間地理學(xué)視角[J]. 地理研究，2019，38（8）：1891-1904.

[5] 戚銘堯，吳濤，張新. 車輛路徑問題：從時(shí)間地理學(xué)的視角[J]. 地球信息科學(xué)學(xué)報(bào)，2015（1）：22-30.

[6] 鄧天民，高超，朱杰，等. 基于DBSCAN算法的城市車輛出行次數(shù)建模及應(yīng)用[J]. 科學(xué)技術(shù)與工程，2018，18（35）：218-223.

[7] 丁喬，李旭，王建春. 結(jié)合DBSCAN聚類算法和粒子群算法的大規(guī)模路徑優(yōu)化方法研究[J]. 物流科技，2020，43（4）：10-15.

[8] 谷煒，張群，衛(wèi)李蓉. 基于GIS的物流配送中心末端大規(guī)模車輛路徑優(yōu)化問題研究[C] // 第十五屆中國管理科學(xué)學(xué)術(shù)年會(huì)論文集. 中國優(yōu)選法統(tǒng)籌法與經(jīng)濟(jì)數(shù)學(xué)研究會(huì)，2013：379-389.