強化學習理論下農村物流配送最優路徑規劃

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

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

1 引言

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

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

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

2 最優路徑規劃

2.1 農村物流配送路徑函數模型

2.1.1 問題描述

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

2.1.2 模型參數

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

農村物流以總配送總成本最小為目標,建立配送函數模型為:

(1)

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

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

(2)

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

(3)

(4)

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

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

(5)

(6)

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

(7)

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

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

(8)

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

(9)

(10)

2.2 強化學習環境設計

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

2.2.1 獎勵函數設計

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

(11)

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

2.2.2 狀態轉移函數

智能體經過強化學習,能夠根據目前狀態情況選取恰當的動作,強化學習環境更新智能體的下一個狀態,反復進行這個過程[12-13]。可發現狀態的更新與環境有關,經過模擬強化學習環境,即可獲得時間窗下農村物流配送車輛路徑的狀態轉移函數。

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

(12)

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

(13)

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

(14)

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

(15)

利用強化學習環境獲得的狀態轉換為St→Si+1,強化學習過程是通過不斷的測試、環境交互,從環境的獎懲中學習決策策略與狀態的價值,不斷迭代優化模型參數。

2.3 策略網絡訓練

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

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

(16)

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

(17)

經過蒙特卡洛計算策略的期望累計回報值,即

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

(18)

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

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

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

(19)

通過θ′分析e的難易程度,進而縮小訓練網絡時梯度方差。基準網絡按照回滾形式更新,每一次訓練結束后都會將θ與θ′對比分析,假設θ明顯優于θ′,就需要對θ′回滾更新,即θ′→θ。

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

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

1)貪婪動作選擇是根據策略網絡,每一步都是選取網絡輸出最大概率的動作;

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

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

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

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

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

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

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

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

(20)

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

3 實驗數據分析與研究

3.1 實驗環境

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

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

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

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

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

三種方法配送最優路徑如圖1所示。

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

3.3 配送車輛行駛成本對比

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

圖3 算法迭代對比分析

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

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

4 結論

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