丁 喬，李 旭，王建春 DING Qiao, LI Xu, WANG Jianchun

（山東科技大學(xué) 交通學(xué)院，山東 青島266590）

0 引 言

隨著電子商務(wù)的迅猛發(fā)展，物流行業(yè)迎來(lái)難得發(fā)展機(jī)遇的同時(shí)也面臨著巨大挑戰(zhàn)，現(xiàn)代物流業(yè)發(fā)展的目標(biāo)是在滿足客戶需求的同時(shí)降低運(yùn)作成本，但配送環(huán)節(jié)的成本占比最高且居高不下，成為阻礙物流發(fā)展的一個(gè)瓶頸。為了有效地組織配送業(yè)務(wù)，Dantzig 等[1]將配送過(guò)程抽象化，于1959年提出了車輛路徑問(wèn)題（Vehicle Routing Problems, VRPs）。從此大量的國(guó)內(nèi)外學(xué)者對(duì)車輛路徑問(wèn)題進(jìn)行了廣泛且深入的研究，并且取得了豐碩的成果。目前VRPs 問(wèn)題的求解規(guī)模一般為數(shù)百個(gè)客戶點(diǎn)，但在實(shí)際配送實(shí)例中該問(wèn)題的規(guī)模遠(yuǎn)不止如此，比如在上海，菜鳥(niǎo)驛站每天有大約30 萬(wàn)個(gè)包裹需要配送，這些問(wèn)題的規(guī)模往往成千上萬(wàn)。VRPs 問(wèn)題是一個(gè)典型的NP-hard 問(wèn)題，求解大規(guī)模的車輛路徑問(wèn)題具有很大的挑戰(zhàn)性。

車輛路徑優(yōu)化問(wèn)題屬于NP-Hard 問(wèn)題，一經(jīng)提出就引來(lái)大批國(guó)內(nèi)外研究人員的深入探索，如今對(duì)于此問(wèn)題的研究主要集中在車輛路徑優(yōu)化模型的建立[2-4]和車輛路徑優(yōu)化模型求解算法的研究[5-8]，通過(guò)對(duì)建立車輛優(yōu)化數(shù)學(xué)模型的深入研究使得車輛路徑優(yōu)化問(wèn)題越來(lái)越多樣化，越來(lái)越符合最后一公里的配送實(shí)際；通過(guò)對(duì)模型求解算法的研究，使得模型的求解速度和精度不斷提高，已達(dá)到能夠更好解決這個(gè)NP 難題的目的，但目前對(duì)于大規(guī)模的車輛路徑問(wèn)題研究相對(duì)較少，其中：王文蕊[9]通過(guò)地理信息的分級(jí)管理實(shí)現(xiàn)車輛路徑問(wèn)題規(guī)模的降低，最后通過(guò)濟(jì)南市區(qū)卷煙配送對(duì)提出方法進(jìn)行驗(yàn)證。冉崇善[10]將該問(wèn)題分為兩個(gè)階段進(jìn)行研究，分別為利用基于基地啟發(fā)式分區(qū)算法進(jìn)行區(qū)域劃分和利用改進(jìn)的遺傳算法來(lái)確定具體的一條配送線路的先后次序，完成配送路徑優(yōu)化任務(wù)。馬漢武[11]在大規(guī)模車輛路徑問(wèn)題引入裝卸頻率的概念后，建立優(yōu)化模型并設(shè)計(jì)改進(jìn)混合遺傳算法進(jìn)行求解。由上述文獻(xiàn)可知，廣大學(xué)者對(duì)于大規(guī)模車輛路徑問(wèn)題的研究主要是從如何將其規(guī)模降低的角度來(lái)進(jìn)行思考和解決的。本文提出一種結(jié)合自適應(yīng)DBSCAN 聚類算法的路徑優(yōu)化方法，通過(guò)DBSCAN 將客戶點(diǎn)形成若干個(gè)聚類簇，將大規(guī)模的城市果蔬配送路徑優(yōu)化問(wèn)題轉(zhuǎn)換成常規(guī)的路徑優(yōu)化問(wèn)題，然后通過(guò)粒子群算法進(jìn)行求解，完成路徑優(yōu)化。

1 自適應(yīng)DBSCAN 聚類算法

DBSCAN 是基于密度空間的聚類算法，與K-means 不同，它不需要確定聚類數(shù)量，由數(shù)據(jù)聚類結(jié)果顯示聚類數(shù)量，并且其可以用于凹數(shù)據(jù)集，適合用于不規(guī)則分布客戶點(diǎn)的聚類分析。DBSCAN 需要確定兩個(gè)參數(shù)：Eps為在一個(gè)點(diǎn)周圍鄰近區(qū)域的半徑；MinPts為鄰近區(qū)域內(nèi)至少包含點(diǎn)的個(gè)數(shù)。Eps的選擇根據(jù)實(shí)際問(wèn)題而定，MinPts的選擇通常采用k-距離圖像法來(lái)確定。本文采用一種自適應(yīng)DBSCAN 聚類分析方法，通過(guò)利用數(shù)據(jù)集自身分布特性生成候選Eps和MinPts，自動(dòng)尋找到聚類簇?cái)?shù)量變化的穩(wěn)定區(qū)間，此時(shí)對(duì)應(yīng)的參數(shù)即為要選擇的最優(yōu)參數(shù)。但是文獻(xiàn)[12]中的方法計(jì)算量巨大，適合用于樣本數(shù)量較少的情況，對(duì)于樣本數(shù)量巨大的情況該方法所需的計(jì)算時(shí)間會(huì)顯著增加。因此本文對(duì)該方法進(jìn)行了改進(jìn)，將Eps和MinPts候選參數(shù)的選擇由全局取期望值改成了抽樣取期望值，具體步驟如下：

步驟1：計(jì)算數(shù)據(jù)集D的距離分布矩陣[13]，n為樣本大小，即：

步驟2：對(duì)距離矩陣Dn×n的每一行元素進(jìn)行升序排列，則第i列的元素隨機(jī)取x個(gè)組成Di。

步驟3：對(duì)Di中的所有元素取平均數(shù)對(duì)所有的i值進(jìn)行計(jì)算，最終得到Eps參數(shù)候選列表DEps：

步驟4：生成MinPts參數(shù)候選列表DMinPts，在數(shù)據(jù)集D中隨機(jī)選取x個(gè)對(duì)象，對(duì)于步驟3 得到的Eps參數(shù)候選列表DEps，依次計(jì)算每一個(gè)DEps列表中的Eps候選值的領(lǐng)域?qū)ο髷?shù)量，并計(jì)算對(duì)象數(shù)量的數(shù)學(xué)期望，作為數(shù)據(jù)集D的鄰域密度閾值MinPts參數(shù)，即：

式中：Ni表示第i個(gè)對(duì)象的Eps鄰域?qū)ο髷?shù)量，x表示從數(shù)據(jù)集D中隨機(jī)抽取的對(duì)象數(shù)。

步驟5：依次選用DEps列表和DMinPts列表中的元素作為Eps和MinPts參數(shù)，輸入DBSCAN 算法中對(duì)數(shù)據(jù)集進(jìn)行聚類分析，分別得到不同輸入?yún)?shù)下對(duì)應(yīng)的聚類簇?cái)?shù)，當(dāng)聚類簇?cái)?shù)連續(xù)3 次相同時(shí)，認(rèn)為聚類結(jié)果趨于穩(wěn)定，記該聚類簇?cái)?shù)為最優(yōu)聚類簇?cái)?shù)M。

步驟6：繼續(xù)執(zhí)行步驟5，直到聚類簇?cái)?shù)不為M，則選擇最后一次聚類簇?cái)?shù)為M時(shí)對(duì)應(yīng)的Eps和MinPts為最優(yōu)參數(shù)。

2 路徑優(yōu)化模型及求解算法

2.1 路徑優(yōu)化問(wèn)題建模

本文所研究的城市生鮮配送車輛路徑優(yōu)化問(wèn)題，可以看做是帶時(shí)間窗的車輛路徑問(wèn)題（Vehicle Routing Problems with Time Windows，VRPTW），以車輛的最大載荷和客戶的時(shí)間窗為主要約束，目標(biāo)函數(shù)由固定成本、運(yùn)輸成本、制冷成本和懲罰成本四部分組成，如公式（4） 所示：

約束：

其中：式（5） 表示每個(gè)客戶點(diǎn)只能有一輛車為其服務(wù)；式（6） 表示每輛車的載重不能超過(guò)最大載荷；式（7） 表示到達(dá)客戶點(diǎn)的車和離開(kāi)客戶點(diǎn)的車數(shù)量相同。

其中參數(shù)和決策變量的含義如表1 所示。

2.2 粒子群算法

粒子群算法（Pariticle Swarm Optimization，PSO），PSO 的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)，同時(shí)又有深刻的智能背景，既適合科學(xué)研究，還特別適合工程應(yīng)用，并且易于實(shí)現(xiàn)、收斂速度快和沒(méi)有許多參數(shù)需要調(diào)整。一經(jīng)提出就被學(xué)術(shù)界廣泛關(guān)注，集中針對(duì)PSO 中的參數(shù)調(diào)整優(yōu)化和種群結(jié)構(gòu)改進(jìn)以及與其他職能算法相融合等方面進(jìn)行了深入的研究[14-17]，近些年粒子群算法也被廣泛的應(yīng)用于物流最后一公里的配送問(wèn)題中。

表1 參數(shù)及決策變量表

將PSO 應(yīng)用于物流最后一公里配送中，則問(wèn)題的求解目標(biāo)即為配送所產(chǎn)生的的成本最小，每一個(gè)粒子表示一種可行的配送方案，通過(guò)PSO 算法的迭代規(guī)則，最終找到配送成本最低的配送方案。粒子群算法的一般數(shù)學(xué)模型：假設(shè)在N 維空間進(jìn)行搜索，粒子i 的信息可用兩個(gè)N 維向量來(lái)表示：

式（8） 表示第i 個(gè)粒子的位置。

式（9） 表示第i 個(gè)粒子的速度。粒子通過(guò)以下式子來(lái)更新自己的速度和位置：

其中：

N 是粒子長(zhǎng)度，即解空間的維度；

i=1,2,3,…,M是種群大?。?/p>

c1和c2是學(xué)習(xí)因子，又稱加速系數(shù)；

rand1和rand2是介于［0,1 ］之間的隨機(jī)數(shù)；

Pbes是粒子i在第k次迭代中第d維的個(gè)體極值點(diǎn)位置；

Gbes是整個(gè)粒子群在d維的全局極值點(diǎn)的位置。

3 案例分析

本文選取了青島市黃島區(qū)1572 個(gè)餐飲店作為配送點(diǎn)，配送中心選擇當(dāng)?shù)匾延械纳r批發(fā)市場(chǎng)，通過(guò)本文的方法先對(duì)這些餐飲店進(jìn)行聚類分析，將大規(guī)模的路徑優(yōu)化問(wèn)題簡(jiǎn)化成正常規(guī)模的路徑優(yōu)化問(wèn)題，然后建立路徑優(yōu)化模型并利用粒子群算法完成對(duì)這1572 個(gè)客戶點(diǎn)的配送任務(wù)。

圖1 為餐飲店的分布圖，由圖1 可知餐飲店的分布具有一定的規(guī)律性，具有集中分布的特點(diǎn)，但是有一些分布區(qū)域集中的餐飲店數(shù)量巨大，不利于進(jìn)行路徑優(yōu)化計(jì)算，所以需要采用自適應(yīng)DBSCAN 算法對(duì)餐飲店進(jìn)行聚類分析，利用餐飲店之間的位置空間關(guān)系，將餐飲店進(jìn)行分類分區(qū)域。

圖1 餐飲店分布圖

圖2 參數(shù)序列與聚類簇?cái)?shù)折線圖

通過(guò)本文的自適應(yīng)DBSCAN 候選參數(shù)選擇方法，得到MinPts和Eps參數(shù)列表，將參數(shù)列表中的參數(shù)對(duì)逐個(gè)代入DBSCAN算法，得出對(duì)應(yīng)的聚類簇?cái)?shù)，如圖2 所示，由圖3 可知在第19、20、21 組參數(shù)得到的聚類簇?cái)?shù)連續(xù)3 次都為8 個(gè)，第22 組為6 個(gè)，依據(jù)本文的方法選出最優(yōu)MinPts為68，最優(yōu)Eps為1118.29m。聚類結(jié)果如圖3 所示。不同的顏色表示不同的聚類簇，其中會(huì)有少量的噪聲點(diǎn)，本文處理的方式是將噪聲點(diǎn)歸入就近的聚類簇。各個(gè)聚類簇成員數(shù)量如表2 所示。

圖3 聚類結(jié)果顯示

表2 各聚類簇成員數(shù)量表

為了驗(yàn)證該研究方法和數(shù)學(xué)模型的可行性，選擇當(dāng)?shù)氐难覎u農(nóng)貿(mào)批發(fā)市場(chǎng)為配送中心，以聚類簇1 的餐飲店為配送客戶點(diǎn)來(lái)完成配送任務(wù)。采用Matlab 編程實(shí)現(xiàn)粒子群算法，所建立的路徑優(yōu)化數(shù)學(xué)模型進(jìn)行仿真計(jì)算，仿真結(jié)果如圖4 所示，其中編號(hào)0 表示配送中心，其他客戶點(diǎn)編號(hào)為1-289，本次任務(wù)一共使用了14 輛配送車輛，總成本為2680.7562 元，計(jì)算所用時(shí)長(zhǎng)為16 秒，每輛車具體的配送路徑如表3 所示。

圖4 路徑優(yōu)化結(jié)果展示

表3 車輛配送路徑表

4 結(jié) 論

該研究將自適應(yīng)DBSCAN 聚類分析算法和粒子群聚類算法相結(jié)合，通過(guò)使用聚類分析算法將配送客戶點(diǎn)進(jìn)行分類，將大規(guī)模車輛路徑優(yōu)化問(wèn)題轉(zhuǎn)變?yōu)檎Ｒ?guī)模車輛路徑問(wèn)題，然后根據(jù)生鮮農(nóng)產(chǎn)品配送的實(shí)際情況建立生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化模型，使用粒子群算法對(duì)模型進(jìn)行求解，對(duì)解決大規(guī)模車輛路徑優(yōu)化問(wèn)題提供了新的解決方案，豐富了車輛路徑優(yōu)化問(wèn)題的解決理論。最后通過(guò)青島市黃島區(qū)1572 個(gè)餐飲店進(jìn)行實(shí)例驗(yàn)證，證明了本研究方法的可行性和合理性。