徐賢浩, 沈夏嬋, 任欣欣

(華中科技大學(xué) 管理學(xué)院,湖北 武漢 430074)

0 引言

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)更新迭代和新零售業(yè)強(qiáng)勢崛起，人們對物流服務(wù)時(shí)間的要求越來越高，2021年中國同城快遞業(yè)務(wù)量超140億件，較上年增加19億件，同比增長15.99%，占當(dāng)年快遞業(yè)務(wù)總量近13%。

即時(shí)配送包括距離短、時(shí)效性強(qiáng)、地點(diǎn)分散等特點(diǎn)，用戶在下單時(shí)會(huì)附帶對商品種類、數(shù)量、送達(dá)期望時(shí)間等要求，平臺(tái)或商家需及時(shí)響應(yīng)，從用戶提出需求至商品送達(dá)，整個(gè)過程持續(xù)時(shí)間通常不超過一小時(shí)。在實(shí)際配送中，如何對眾多配送訂單進(jìn)行合理規(guī)劃及如何對車輛進(jìn)行合理運(yùn)力調(diào)度從而達(dá)到既提高配送服務(wù)質(zhì)量，同時(shí)又能控制配送總成本已成為當(dāng)前重要問題。

近年來越來越多的學(xué)者在研究即時(shí)配送車輛路徑問題會(huì)引入時(shí)間窗、道路交通狀況等實(shí)際因素。在對車輛路徑問題的數(shù)學(xué)模型研究上，陳萍等[1]建立了基于餐飲O2O配送的取送貨車輛路徑優(yōu)化模型；王帥等[2]研究了O2O平臺(tái)上食品提供商的車輛路徑問題；王征等[3]建立了基于即時(shí)響應(yīng)狀態(tài)下的配送訂單數(shù)學(xué)問題模型；柴獲等[4]設(shè)計(jì)了多重圖求解運(yùn)輸網(wǎng)絡(luò)的帶時(shí)間窗車輛路徑問題；慕靜等[5]將眾包配送運(yùn)力調(diào)度模型中的目標(biāo)函數(shù)改變?yōu)榕渌腿藛T收益激勵(lì)最大化；Huang et al.[6]研究了眾包配送交付中最后一公里問題；李桃迎等[7]引入了時(shí)間懲罰成本和K-means聚類算法來解決同時(shí)取送貨的VRP問題。

除此之外，還有許多研究聚焦在對求解算法的改進(jìn)上，孫小軍[8]設(shè)計(jì)了單親遺傳-布谷鳥搜索混合算法求解帶時(shí)間窗的配送問題。胡俊橋[9]使用遺傳-蟻群混合算法求解車輛路徑問題。孫小軍等[10]設(shè)計(jì)了一種基于交通擁堵和揮發(fā)因子兩個(gè)變量的改進(jìn)蟻群算法。Abidi et al.[11]使用改進(jìn)遺傳算法解決具有不確定性的RVRP問題。Kumar et al.[12]提出了基于Dijkstra的fast-clusiVAT算法。Ticha et al.[13]設(shè)計(jì)了一種基于多圖模型的自適應(yīng)大鄰域搜索啟發(fā)式方法。Lu et al.[14]使用分支定價(jià)切分算法研究具有不確定性需求的帶有時(shí)間窗的VRP問題。

上述研究為本文奠定了基礎(chǔ)，但仍然有進(jìn)一步研究的空間，具體體現(xiàn)如下：

第一，針對大規(guī)模即時(shí)配送的車輛路徑優(yōu)化問題仍有大量研究空間。在數(shù)據(jù)規(guī)模較大的條件下，現(xiàn)有數(shù)學(xué)模型無法較好解決，例如存在多門店、多客戶的“多對多”的情況。

第二，針對大規(guī)模車輛路徑問題求解使用的啟發(fā)式算法的路徑選擇策略仍需不斷改進(jìn)。當(dāng)前求解VRP問題所采用的單一或混合啟發(fā)式算法僅考慮了配送路徑長短對路徑選擇的影響，且均使用歐式距離即直線距離代表配送路徑的長度，與現(xiàn)實(shí)情況存在一定偏差，而在當(dāng)下“分鐘級”配送中，兩地點(diǎn)的實(shí)際距離(由于電動(dòng)車體積較小，本文使用步行路線近似代替電動(dòng)車行駛路線)與歐式距離的差值對路徑選擇和車輛行駛時(shí)間的影響較大。

1 模型構(gòu)建

1.1 帶時(shí)間窗的車輛路徑問題模型建立

1.1.1 問題描述與模型假設(shè)

同城即時(shí)配送作為新穎的第三方配送方式不具備配送中心，呈現(xiàn)出送貨點(diǎn)多分散和面廣的特點(diǎn)，且客戶有嚴(yán)格的時(shí)間窗要求，配送車輛完成后無需返回。模型基本假設(shè)為：

(1)整個(gè)配送網(wǎng)絡(luò)存在多配送中心，即為平臺(tái)商戶；

(2)所有配送任務(wù)均由多個(gè)同型號車輛完成；

(3)配送車輛從當(dāng)前位置出發(fā)，先取完所有商品后再開始配送，所有商品送貨完成才可視為當(dāng)前車輛全部配送任務(wù)完成，此時(shí)車輛無需返回初始位置；

(4)客戶均有假定的配送服務(wù)需求時(shí)間窗；

(5)單個(gè)客戶需求有且僅由單臺(tái)車輛滿足；

(6)本假設(shè)條件下配送商品的特點(diǎn)是體積小且不規(guī)則、車載容量靈活不固定等，因此暫不考慮配送配送車輛的商品數(shù)量約束；

(7)假定配送車輛均為小型電動(dòng)車，實(shí)際續(xù)航里程較短，因此需考慮配送車輛的最大里程限制；

(8)不考慮配送車輛到達(dá)客戶需求點(diǎn)的服務(wù)時(shí)間，即配送車輛到達(dá)客戶點(diǎn)便視為完成當(dāng)前客戶的配送任務(wù)；

(9)假定配送車輛全程勻速行駛，暫不考慮交通狀況變化、天氣或其他突發(fā)狀況等現(xiàn)實(shí)情況的影響。

1.1.2 模型建立

(1)符號說明

根據(jù)上述九個(gè)基本假設(shè)，本數(shù)學(xué)模型的各個(gè)參數(shù)、決策變量及函數(shù)定義如下：

①參數(shù)：

②決策變量：

(1)

(2)

③函數(shù)：

在實(shí)際的即時(shí)配送中，若配送商品晚于客戶要求時(shí)間送達(dá)便會(huì)極大影響客戶滿意度，最終會(huì)對企業(yè)造成一定損失。為簡化問題，假定時(shí)間懲罰成本隨時(shí)間呈線性變化，函數(shù)表達(dá)式如下:

(3)

(2)數(shù)學(xué)模型

通過上述描述與假設(shè)，建立帶用戶需求軟時(shí)間窗的車輛路徑問題數(shù)學(xué)模型，并將配送產(chǎn)生的總成本最小為目標(biāo)函數(shù)，具體如下:

(4)

(12)

對上述建立的數(shù)學(xué)模型中各表達(dá)式說明如下：

表達(dá)式(4)表示以配送產(chǎn)生的總成本最小為目標(biāo)函數(shù)，分別由車輛行駛成本、車輛固定成本、車輛取貨等待成本及車輛延誤的時(shí)間懲罰成本四項(xiàng)組成。

表達(dá)式(5)、(6)、(7)表示單個(gè)用戶的單個(gè)商品取送貨僅由一臺(tái)配送車輛完成；

表達(dá)式(8)表示單個(gè)車輛完成其全部配送任務(wù)的總耗時(shí)，分別由取貨等待時(shí)間、行駛時(shí)間兩部分組成；

表達(dá)式(9)表示單個(gè)車輛總行駛里程不得超過車輛最大行駛里程約束；

表達(dá)式(10)表示客戶理論等待時(shí)間須早于其能接受的最晚送達(dá)時(shí)間，否則因此產(chǎn)生的超時(shí)懲罰成本為無窮大；

表達(dá)式(12)表示各個(gè)參數(shù)、變量均大于零；

表達(dá)式(11)表示整數(shù)化約束，即xijk,yjk只能取0或1。

1.2 配送區(qū)域劃分研究

此前研究大規(guī)模車輛路徑問題時(shí)，考慮的是整個(gè)配送網(wǎng)絡(luò)中只存在單一門店的情況，此時(shí)只有客戶間的相對距離會(huì)影響配送區(qū)域劃分的結(jié)果。而配送網(wǎng)絡(luò)中存在多個(gè)門店時(shí)，門店距客戶的距離同樣也會(huì)影響配送區(qū)域劃分。將整個(gè)配送區(qū)域按照門店、車輛及客戶等地理位置數(shù)據(jù)劃分為若干個(gè)獨(dú)立子區(qū)域，各個(gè)獨(dú)立子區(qū)域分別尋找自己的最優(yōu)路徑，以此縮小優(yōu)化搜索范圍，提高算法求解效率。

本研究使用Voronoi劃分方法處理眾多客戶因地理位置不同而產(chǎn)生的分類問題，其主要思想是為多個(gè)門店點(diǎn)劃分獨(dú)立子區(qū)域，使其區(qū)域中的點(diǎn)只受離其最近的核心點(diǎn)影響。本研究中，多個(gè)客戶需求點(diǎn)中穿插分布著門店位置點(diǎn)，由車輛、客戶及門店組成的點(diǎn)均位于同一平面上，門店位置即是該平面上多個(gè)不重合節(jié)點(diǎn)，這些門店點(diǎn)將配送網(wǎng)絡(luò)分成了多個(gè)獨(dú)立子區(qū)域，每個(gè)獨(dú)立子區(qū)域內(nèi)包含的客戶點(diǎn)離該區(qū)域的門店點(diǎn)最近就由該門店負(fù)責(zé)配送。Voronoi算法具體實(shí)現(xiàn)如下：

(1)每個(gè)門店節(jié)點(diǎn)兩兩相連形成若干三角形；

(2)找出所有三角形外接圓圓心；

(3)遍歷三角形鏈表，尋找與三角形pT三邊共邊的相鄰三角形A、B、C；

(4)如果找到A、B和C，則連接其外心與pT外心，存入Voronoi邊鏈表中，否則尋找最外邊中垂線，也存入Voronoi邊鏈表中；

(5)遍歷結(jié)束，畫出Voronoi圖。

Voronoi劃分圖形成過程如圖1所示，本文選擇調(diào)用Python中的Voronoi函數(shù)。

圖1 Voronoi劃分示意圖

1.3 基礎(chǔ)蟻群算法的概述與改進(jìn)

1.3.1 基礎(chǔ)蟻群算法的概述

蟻群算法(Ant Colony Algorithm, ACA)誕生于1992年，算法模擬了蟻群協(xié)作覓食的過程，螞蟻較大概率會(huì)選擇信息素濃度高的路徑，并且路徑上的信息素濃度會(huì)隨時(shí)間推移而逐漸降低，最終螞蟻能夠找到一條距離食物的最佳路徑，即距離最短路徑。

(13)

其中，allowk為螞蟻k待訪問城市集合，α和β分別為信息素濃度和啟發(fā)函數(shù)的權(quán)重。

τij(t+1)=(1-ρ),τij(t)+Δτij(t)

(14)

(15)

(16)

其中，ρ為信息素?fù)]發(fā)系數(shù)，Q為常數(shù)，Lk為螞蟻k所走的路徑長度。

1.3.2 蟻群算法的三步改進(jìn)

(1)狀態(tài)轉(zhuǎn)移概率公式的優(yōu)化

傳統(tǒng)蟻群算法是使用狀態(tài)轉(zhuǎn)移概率公式計(jì)算出下一時(shí)刻待訪的最短路徑，即只考慮了距離長短因素對路徑選擇的影響。本文在此基礎(chǔ)上還考慮了超時(shí)懲罰成本，即添加時(shí)間窗因素到狀態(tài)轉(zhuǎn)移概率公式中，客戶期望商品送達(dá)時(shí)間窗為[0,tij]，tij越小表示客戶對商品送達(dá)的時(shí)間要求越嚴(yán)格，即優(yōu)先配送tij較小的客戶。時(shí)間窗因素φij表達(dá)式為:

(17)

加入時(shí)間窗因素φij后，改進(jìn)蟻群算法的狀態(tài)轉(zhuǎn)移概率計(jì)算公式如下:

(18)

(2)使用實(shí)際距離替代歐式距離

以往啟發(fā)式算法求解車輛路徑問題多使用歐氏距離度量兩點(diǎn)距離，但現(xiàn)實(shí)道路往往是不規(guī)則的曲線，因此歐式距離并不能反映車輛實(shí)際行駛距離，所求得的解也存在較大誤差。文中改進(jìn)蟻群算法所使用的實(shí)際距離是由百度地圖開發(fā)平臺(tái)JavaScript API v2.0求得。隨機(jī)選擇一組點(diǎn)(114.414694,30.51839)和(114.416259,30.521761)的經(jīng)緯度來說明歐式距離與實(shí)際距離的差別，計(jì)算得到兩點(diǎn)之間歐式距離為404米，實(shí)際距離為570米，差值為166米。

(3)改進(jìn)路徑選擇

為保證螞蟻在選擇下一步路徑時(shí)具有一定隨機(jī)性，即算法有一定概率選擇信息素剩余量少的路徑，此種做法在一定程度避免了局部最優(yōu)解。

本文改進(jìn)的蟻群算法將輪盤賭加入路徑選擇。將每條路徑的選擇概率看作輪盤扇面之一，指針停止時(shí)所在的扇面就選擇對應(yīng)概率的路徑，通過添加0-1之間的隨機(jī)數(shù)模擬指針停止時(shí)指向的扇面，以此增加螞蟻在選擇路徑時(shí)的多樣性。根據(jù)上述描述，本文改進(jìn)的蟻群算法求解步驟如下：

Step1iter→1(iter為迭代次數(shù))，將各參數(shù)初始化。

Step2構(gòu)建解空間將m只螞蟻隨機(jī)置于不同起點(diǎn)，對每只螞蟻按照公式(18)使用輪盤賭方法計(jì)算其下一個(gè)待訪問城市，直到所有螞蟻將所有城市訪問完成。

Step3計(jì)算每只螞蟻所走的路徑長度Lk，記錄當(dāng)前迭代次數(shù)的最優(yōu)解，同時(shí)根據(jù)公式(14)～(16)對各城市連接路徑上的信息素濃度進(jìn)行更新。

Step4判斷是否終止，若iter

2 算例驗(yàn)證及結(jié)果分析

2.1 背景描述

假設(shè)有如下場景：較短時(shí)間內(nèi)，門店收到了平臺(tái)一百個(gè)不同客戶的商品配送需求，平臺(tái)有十臺(tái)配送車輛位于該配送區(qū)域中。門店將任務(wù)分別分配給配送車輛，車輛在收到任務(wù)后先到門店取貨，門店優(yōu)先為先到達(dá)、客戶多的車輛準(zhǔn)備商品，車輛將需求商品全部取完后開始配送。

本文使用百度地圖選取了一百二十個(gè)實(shí)際地點(diǎn)，其中包括十臺(tái)配送車輛、十個(gè)門店及一百個(gè)客戶需求點(diǎn)。首先使用通過百度地圖開發(fā)者平臺(tái)提供的API接口獲取上述一百二十個(gè)真實(shí)地點(diǎn)的經(jīng)緯度數(shù)據(jù)，并對客戶點(diǎn)進(jìn)行Voronoi劃分，將一百個(gè)客戶分配給多個(gè)子配送區(qū)域；其次對劃分出的子配送區(qū)域，在已有各地址經(jīng)緯度數(shù)據(jù)的基礎(chǔ)上，計(jì)算各地點(diǎn)間的實(shí)際距離；最后進(jìn)行基礎(chǔ)蟻群算法和改進(jìn)蟻群算法算例對比實(shí)驗(yàn)。各點(diǎn)地理位置如圖2所示，其中藍(lán)點(diǎn)代表客戶所在點(diǎn)，紅點(diǎn)代表配送車輛所在點(diǎn)，白點(diǎn)代表門店所在點(diǎn)。

圖2 各點(diǎn)地理位置分布圖

為方便計(jì)算，假設(shè)配送車輛以V=300m/min勻速行駛，車輛最大里程約束L=50000m，門店出貨時(shí)間ti=0.1min/個(gè)，單臺(tái)車輛固定成本c1=5/臺(tái)，單位距離成本c2=0.001/m，單位時(shí)間占用成本c3=3/min，超時(shí)懲罰成本為λm=6/min、λn=3/min。從一百個(gè)客戶中隨機(jī)選擇七十個(gè)為普通客戶，理論等待時(shí)間窗為[0,20]，其余三十個(gè)為期望配送時(shí)間較短客戶，理論等待時(shí)間窗為[0,10]，所有客戶能接受的最晚配送時(shí)間均為60min。

實(shí)驗(yàn)仿真環(huán)境為操作系統(tǒng)Windows 10，處理器lntel(R)Core(TM) i5-7200U CPU @2.50GHz 2.71 GHz，使用MATLAB R2012a軟件實(shí)施編程，蟻群算法各參數(shù)設(shè)置如表1所示。

表1 蟻群算法的參數(shù)設(shè)置

2.2 數(shù)據(jù)收集

使用百度地圖開發(fā)者平臺(tái)處理包括門店、配送車輛、客戶在內(nèi)共一百二十個(gè)地點(diǎn)數(shù)據(jù)后，得到經(jīng)緯度數(shù)據(jù)，并對門店、配送車輛及客戶進(jìn)行單獨(dú)編號。

2.3 算例分析

以十個(gè)門店為核心點(diǎn)，Voronoi劃分結(jié)果如表2所示：

表2 Voronoi劃分結(jié)果

繪制Voronoi劃分效果圖如圖3所示，藍(lán)色點(diǎn)代表門店點(diǎn)，紅色×代表客戶點(diǎn)。

圖3 Voronoi劃分效果圖

使用基礎(chǔ)蟻群算法的求解結(jié)果如表3、4所示。

表3 基礎(chǔ)蟻群算法求解車輛路徑表

表4 基礎(chǔ)蟻群算法求解成本表

使用上述經(jīng)改進(jìn)后的蟻群算法求解結(jié)果如表5、6所示。

表5 改進(jìn)蟻群算法求解車輛路徑表

表6 改進(jìn)蟻群算法求解成本表

對比表4、6可以看出：(1)時(shí)間占用成本相同，原因是門店及客戶位置不變的情況下，Voronoi劃分結(jié)果是相同的，因此改進(jìn)蟻群算法不能減少占用時(shí)間和時(shí)間占用成本；(2)改進(jìn)蟻群算法相較基礎(chǔ)蟻群算法而言，六號配送車輛產(chǎn)生的超時(shí)懲罰成本占總超時(shí)懲罰成本的比例較大，分別為76%、92%，原因是六號配送車輛離門店距離最遠(yuǎn)。

兩種路徑規(guī)劃方案的行駛距離、各項(xiàng)時(shí)間以及各項(xiàng)成本如表7、8。

表7 兩種路徑規(guī)劃方案的行駛距離以及時(shí)間表

表8 改進(jìn)蟻群算法求解的成本表

對比表7和表8可以看出：(1)改進(jìn)蟻群算法求解的總超時(shí)時(shí)間(11分鐘)比基礎(chǔ)蟻群算法的總超時(shí)時(shí)間(17.1分鐘)低36%；改進(jìn)蟻群算法求解的超時(shí)懲罰成本比基礎(chǔ)蟻群算法低17%，是導(dǎo)致其總成本比基礎(chǔ)蟻群算法低17%的重要原因，說明使用改進(jìn)蟻群算法在降低總成本上更具優(yōu)勢。(2)改進(jìn)蟻群算法求解的車輛行駛總距離(35460米)比基礎(chǔ)蟻群算法的車輛行駛總距離(31410米)高13%，改進(jìn)蟻群算法求解的每輛車平均耗時(shí)(11.96分鐘)比基礎(chǔ)蟻群算法的每輛車平均耗時(shí)(10.6分鐘)長13%，原因是改進(jìn)蟻群算法的狀態(tài)轉(zhuǎn)移概率公式中加入了時(shí)間窗這一因素，使路徑尋優(yōu)搜索時(shí)需同時(shí)考慮客戶需求時(shí)間和行駛距離長短，這會(huì)犧牲了期望時(shí)間較長的用戶時(shí)間。

3 結(jié)論

本文研究了基于分鐘級的即時(shí)配送問題及其求解方法，文章結(jié)合了配送區(qū)域劃分問題和車輛路徑優(yōu)化問題，構(gòu)建以配送成本之和最小為目標(biāo)的物流配送路徑優(yōu)化模型，采用“門店-客戶”分配決策、改進(jìn)蟻群算法求解測試算例，驗(yàn)證了算法的有效性，并得出如下結(jié)論：

(1)根據(jù)大規(guī)模帶時(shí)間窗的車輛路徑問題特點(diǎn)及門店點(diǎn)和客戶點(diǎn)之間的相互關(guān)系，使用Voronoi劃分對門店-客戶進(jìn)行配送區(qū)域的分割和分配，創(chuàng)建分類內(nèi)部路徑，此方法有利于降低大規(guī)模車輛路徑問題的求解難度。

(2)針對本文的車輛路徑優(yōu)化模型特點(diǎn)，對比結(jié)果表明，采用Voronoi劃分-改進(jìn)蟻群算法的兩階段方法既能提升客戶的滿意度，同時(shí)又能顯著降低配送過程中產(chǎn)生的總成本。