強化學習理論下農(nóng)村物流配送最優(yōu)路徑規(guī)劃

韓翔宇,李 慧,梁 碩,王書強

(1. 邯鄲學院河北省光纖生物傳感與通信器件重點實驗室,河北 邯鄲 056005;2. 邯鄲學院信息工程學院,河北 邯鄲 056005;3. 河北工程大學,河北 邯鄲 056038)

1 引言

隨著農(nóng)產(chǎn)品進城與農(nóng)用品下鄉(xiāng)的數(shù)量增多,進而增加物流的訂單量。但這些訂單較為分散,同時合作的物流公司較少,車輛配送時會出現(xiàn)單程、倒流與迂回等運輸情況,這大大增加配送貨車行駛距離,進而增加運輸成本[1-2]。假設(shè)在配送前獲得最優(yōu)路徑,可以縮短物流配送路程,節(jié)省大量配送時長時間,降低物流總成本,提高物流配送效率[3-4]。

為此,關(guān)于配送最優(yōu)路徑的問題,諸多學者提出各自的解決辦法。如李學現(xiàn)等人[5]提出考慮能耗動態(tài)變化的露天礦卡車運輸最優(yōu)路徑規(guī)劃方法,根據(jù)路段運輸功率,得出路徑各節(jié)點間的轉(zhuǎn)移概率,并通過自適應(yīng)動態(tài)因子調(diào)整蟻群信息,結(jié)合交叉算子與變異算子增加種群類別,進而提升該算法的局部收斂能力,最終選出最優(yōu)路徑。王雷等人[6]提出智能網(wǎng)聯(lián)下無人駕駛汽車配送路徑優(yōu)化方法以配送車輛最小成本為目標,運輸時長為限定條件,建立配送車輛行駛路徑模型,并采用多種群遺傳算出路徑規(guī)劃最優(yōu)解,進而得出最優(yōu)路徑策略。

通過綜合上述優(yōu)勢,采用強化學習規(guī)劃農(nóng)村物流配送最優(yōu)路徑,該方法能夠進一步縮短物流運輸時長,減少物流配送路徑總長度,進而降低配送車輛的總成本。

2 最優(yōu)路徑規(guī)劃

2.1 農(nóng)村物流配送路徑函數(shù)模型

2.1.1 問題描述

假設(shè)有a個配送中心A,b個顧客,配送車輛根據(jù)配送中心指令完成各自任務(wù),并不會產(chǎn)額外費用。若配送車輛過早與過晚到達目顧客所在地,就會產(chǎn)生額外成本。為此,增加1個虛擬配送中心o,o產(chǎn)生不需要任何費用。物流配送車輛從o出發(fā),經(jīng)過A,再到達顧客所在位置,進行取貨與送貨服務(wù),再從A回到o[7]。

2.1.2 模型參數(shù)

設(shè)定o描述為虛擬配送中心;B={1,2,…,b}描述為顧客點集合;C={1,2,…,c}為農(nóng)村物流配送中心車輛;集合N=A∪B為全部點的集合;Q描述為配送車輛極限滿載量;sb′與pb′分別代表顧客b′的送貨與取貨的需求量;Sb″b′k與Pb″b′k分別代表配送車輛k從顧客b′到b″的車輛取貨與送貨的總質(zhì)量;db′b″代表b′到b″之間的距離;[tb″e,tb″,i]描述為b″的配送使用時間;?1與?2分別代表配送車輛早到與晚到的懲罰系數(shù);e1是配送車輛出行一次固定行駛成本;e2是車輛單位行駛成本。

農(nóng)村物流以總配送總成本最小為目標,建立配送函數(shù)模型為:

(1)

其中,minZ表示車輛配送最小總成本;xb″b′k表示配送車輛k從顧客b′到b″的服務(wù)次數(shù)。

各顧客點只可進行一次服務(wù),其表達式如式(2)所示:

(2)

顧客點需要送貨與取貨的量分別用式(3)與式(4)表示。

(3)

(4)

式中,V表示總配送車輛。

在配送車輛滿載極限之內(nèi),顧客點取貨與送貨的量分別用式(5)與式(6)描述。

(5)

(6)

配送車輛載貨極限值表達式如式(7)所示。

(7)

配送車輛行駛狀態(tài),即每一臺配送車輛都是從虛擬配送中心駛出,并駛回該中心,其表達式為:

Sb″b′k+Pb″b′k≤Qxb″b′k,?b″,b′∈N,k∈V

(8)

式(9)與式(10)描述為決策兩個變量公式。

(9)

(10)

2.2 強化學習環(huán)境設(shè)計

在物流配送函數(shù)模型基礎(chǔ)上,結(jié)合強化學習規(guī)劃農(nóng)村物流配送路徑[8-9]。如果配送系統(tǒng)中存在一個智能體,經(jīng)過一系列運作,給出配送路徑的解決策略。在每一個環(huán)節(jié)中,智能體都能實時收到系統(tǒng)狀態(tài)數(shù)據(jù),并根據(jù)已知信息與策略,指導其作出相應(yīng)動作。該過程就是通過強化學習給出智能體的獎懲與狀態(tài)變化。通過車輛路徑實例來訓練智能體,并根據(jù)獎懲函數(shù)評估智能體給出的解決方案,并對其狀態(tài)相應(yīng)改進。

2.2.1 獎勵函數(shù)設(shè)計

獎勵函數(shù)設(shè)計是智能體訓練核心的部分。其不是為了得到某一時刻的最大化獎勵,而是為了獲得長期最大化的累計獎懲。通常在計算農(nóng)村物流配送最優(yōu)路徑時,易陷入局部最優(yōu)解,無法保證配送路徑最短,增加配送車輛行駛的成本,為此基于強化學習設(shè)計一種獎懲函數(shù),通過不斷動態(tài)調(diào)整獎懲函數(shù),使訓練模型達到最佳效果[10]。

(11)

當中,α1與α2均為負的常數(shù);ηt表示t時刻的狀態(tài)。強化學習與其它學習方法不同,其是根據(jù)估計數(shù)值的情況來改進模型參數(shù),獎勵函數(shù)更新強化學習策略網(wǎng)絡(luò)與價值網(wǎng)絡(luò),智能體按照這些獎勵信號不斷更新,進而得到期望結(jié)果。

2.2.2 狀態(tài)轉(zhuǎn)移函數(shù)

智能體經(jīng)過強化學習,能夠根據(jù)目前狀態(tài)情況選取恰當?shù)膭幼?強化學習環(huán)境更新智能體的下一個狀態(tài),反復進行這個過程[12-13]?？砂l(fā)現(xiàn)狀態(tài)的更新與環(huán)境有關(guān),經(jīng)過模擬強化學習環(huán)境,即可獲得時間窗下農(nóng)村物流配送車輛路徑的狀態(tài)轉(zhuǎn)移函數(shù)。

假設(shè)Xt與Gt表示配送車輛路徑強化學習的系統(tǒng)的兩個狀態(tài)。強化學習的動作就是在序列的末尾增添一個客戶點,b′作為在t時截取序列的頂點,Bt描述在t以前客戶的序列。如果該過程在tm時停止,代表該時刻沒有需求的顧客,即全部顧客點的需求為0。在t時刻智能體會獲得來自局部信息與全局信息,也就是Xt,Gt,Bt。當中Bt為歷史軌跡,通過模型即可獲得各客戶點的條件概率分布,即P(b″=i|Xt,Gt,Bt)。再利用概率分布策略選取b″客戶點加入當前序列的末端,并更新系統(tǒng)的狀態(tài),即

(12)

當中,w(b′,b″)描述為b′到b″的配送車輛行駛所用的時間。利用歐式距離算出配送車輛距離與車速,即:

(13)

配送車輛裝載容量更新過程為

(14)

無需考慮w(b′,b″)是否為負,因為系統(tǒng)會屏蔽需求超過該配送車輛的裝載極限容量的客戶點。則需求更新過程為:

(15)

利用強化學習環(huán)境獲得的狀態(tài)轉(zhuǎn)換為St→Si+1,強化學習過程是通過不斷的測試、環(huán)境交互,從環(huán)境的獎懲中學習決策策略與狀態(tài)的價值,不斷迭代優(yōu)化模型參數(shù)。

2.3 策略網(wǎng)絡(luò)訓練

采用帶有回滾基準訓練策略網(wǎng)絡(luò),可以得出各智能體的累計回報率,并根據(jù)該結(jié)果預測策略的梯度,完成各智能體策略的訓練[14]。設(shè)定e表示農(nóng)村物流配送的1個實例;θ表示實例策略網(wǎng)絡(luò);pθ(πt|e)描述為θ輸出個智能體各動作概率矢量總和,并經(jīng)過采樣選取輸出的聯(lián)合策略,即

πt=sample(pθ(πt|e))

(16)

基準網(wǎng)絡(luò)θ′是根據(jù)其輸出的動作概率向量pθ′(πt|e),并以貪婪選取形式得出聯(lián)合策略,即:

(17)

經(jīng)過蒙特卡洛計算策略的期望累計回報值,即

L(θ|e)=Epθ(e)[R(π)]

(18)

當中,Epθ(e)表示期望概率矢量;R(π)表示策略π={π1,π2,…,πT}的累計回報。根據(jù)帶有回滾基準求解策略的梯度,并結(jié)合梯度下降的算法更新策略網(wǎng)絡(luò)相關(guān)參數(shù),計算過程為:

ΔθL(θ|e)=-Epθ(π|e)[(R(π)-R(π)′))×Δθlgpθ(π|e)],

θ=Adam(θ,ΔθL(θ|e))

(19)

通過θ′分析e的難易程度,進而縮小訓練網(wǎng)絡(luò)時梯度方差?；鶞示W(wǎng)絡(luò)按照回滾形式更新,每一次訓練結(jié)束后都會將θ與θ′對比分析,假設(shè)θ明顯優(yōu)于θ′,就需要對θ′回滾更新,即θ′→θ。

2.4 動作選擇與全局搜索策略

通過多次強化學習的策略網(wǎng)絡(luò)已具有良好的決策能力,動作選取策略按照網(wǎng)絡(luò)輸出的概率矢量,選出最佳動作[15]。選用貪婪與采樣兩種方式選取最佳的動作,即:

1)貪婪動作選擇是根據(jù)策略網(wǎng)絡(luò),每一步都是選取網(wǎng)絡(luò)輸出最大概率的動作;

2)采樣動作選取策略依舊以策略網(wǎng)絡(luò)輸出概率當做采樣概率分布,在該分部上進行動作采樣的選取,但該方法不是按照貪婪動作選取方式,而是根據(jù)不同概率選擇適合的動作。

網(wǎng)絡(luò)訓練時,θ′當做每一次訓練實例難度程度的評估標準,可看做是評價者的身份,通過貪婪動作選取方法,能夠迅速得出正確的評估指標。而θ可視為執(zhí)行者,即策略能力的評價。使用采樣動作選取策略,能夠預測出動作期望值,也就是執(zhí)行者的決策的能力。實例策略網(wǎng)絡(luò)與基準網(wǎng)絡(luò)都是經(jīng)過不同的動作選取恰當?shù)膭幼?進而有效提升學習效率與模型性能。

模型訓練結(jié)束后,按照貪婪動作選取策略,能夠在最短時間內(nèi)算出配送車輛路徑,但會出現(xiàn)回路中線路交叉問題或者貪婪動作選取策略自負的行為,進而選取概率動作不是最大的概率動作。為了避免發(fā)生這兩種問題,使用2-opt尋優(yōu)方案,詳細過程如下:

1)任意選取子回路γ上的兩個點,同時將這兩個點間的路徑做翻轉(zhuǎn)處理,進而生成新的子回路γ′;

2)假設(shè)γ′優(yōu)于γ,就需要更新目前子回路γ=γ′,之后把迭代次數(shù)I重置,即次數(shù)設(shè)置為0,回到1),否則迭代系數(shù)設(shè)定為I=I+1,再回到1);

3)假設(shè)最大迭代次數(shù)依舊沒有改進子回路,就需要通過2-opt全局尋找,并把γ當做最優(yōu)子回路送回。

采樣查找。該模型運用采樣查找方式找出策略重復計算相同的實例,得到相同實例有多個解,選取當中最優(yōu)的解。假設(shè)n描述采樣的數(shù)量,則最優(yōu)解計算過程如式(20)所示。

π′=arg min{L(π1),L(π2),…,L(πn)}

(20)

經(jīng)過式(20)計算,可有效解決自負行為。由于本模型能夠在最短時間內(nèi)算出最優(yōu)解,并能保證解的質(zhì)量,進而有效保證農(nóng)村物流配送路徑成本最小。

3 實驗數(shù)據(jù)分析與研究

3.1 實驗環(huán)境

某鄉(xiāng)縣物流配送中心負責15個顧客點,有4臺配送車輛,每臺車裝載量極限為6噸,每次配送路徑最大距離為60m。物流配送中心空間坐標為(11.9km,19.9km),15個顧客空間坐標與需要配送貨物情況如表1所示。

表1 顧客點空間坐標與需求情況

為了證實強化學習下最優(yōu)配送路徑規(guī)劃效果良好,選取蟻群算法與多種群遺傳算法作為對比方法,并求解配送最優(yōu)路徑,如圖1-3所示。

圖1 各方法下配送路徑示意圖

3.2 配送路徑的距離對比分析

三種方法配送最優(yōu)路徑如圖1所示。

通過圖1可顯著看出強化學習最優(yōu)路徑行駛最短,且沒有出現(xiàn)重復路徑,而蟻群算法與多種群遺傳算法的路徑距離較長,且存在重復路徑。這是因為所提方法通過獎勵函數(shù)與狀態(tài)轉(zhuǎn)移函數(shù),不斷調(diào)整配送車輛行駛狀態(tài),有效避免配送路徑出現(xiàn)重復、交叉等問題。

3.3 配送車輛行駛成本對比

為了進一步證實強化學習方法的有效性,從物流配送中心歷史數(shù)據(jù)庫中,隨機選取8次車輛行駛路徑事件作為實驗研究對象,以物流配送行駛成本與迭代計算次數(shù)作為評估指標對比分析,實驗結(jié)果如圖2、圖3所示。

圖3 算法迭代對比分析

從圖2可知, 所提方法每次配送路徑行駛的成本均小于對比方法, 因所提方法運用帶有回滾基準求解策略的梯度, 并根據(jù)梯度下降更新策略網(wǎng)絡(luò),時刻調(diào)整配送路徑策略,為此所提方法物流成本最小。

從圖3可看出,所提方法找到最優(yōu)解的最大迭代次數(shù)始終小于對比方法的迭代次數(shù),且最大迭代次數(shù)小于60次,提高了配送效率。這是因為所提方法采用貪婪與采樣兩種全局搜索方式,能夠有效提升最優(yōu)解搜索的速度,為此在較少迭代次數(shù)就能找到最優(yōu)解,證實所提方法方法性能良好。

4 結(jié)論

由于農(nóng)村物流配送存在時效性差,運輸成本高,為此,通過強化學習得到農(nóng)村物流配送最優(yōu)路徑規(guī)劃。以配送成本最小為目的,建立物流配送路徑函數(shù)模型。采用獎勵函數(shù)與狀態(tài)轉(zhuǎn)移函數(shù)設(shè)計策略網(wǎng)絡(luò),根據(jù)帶有回滾基準訓練策略網(wǎng)絡(luò)。通過貪婪與采樣計算得出配送路徑的最優(yōu)解,最終完成配送最優(yōu)路徑的規(guī)劃。實驗證實了所提方法能夠有效降低物流運輸成本,并能在迭代次數(shù)較低的情況下算出路徑規(guī)劃最優(yōu)解。