張湘博，李文敬，周杰，李松釗

（廣西師范學院計算機與信息工程學院，南寧 530023）

基于深度學習的物流配送路徑優(yōu)化算法的研究

張湘博，李文敬，周杰，李松釗

（廣西師范學院計算機與信息工程學院，南寧 530023）

針對物流配送過程，傳統(tǒng)路徑優(yōu)化算法對交通擁堵、天氣狀況、環(huán)境因素不敏感，導致車輛在物流配送中效率低下、意外狀況多的問題，提出基于深度學習的物流配送路徑優(yōu)化算法。首先構建基于自編碼網(wǎng)絡的模型，依據(jù)樣本數(shù)據(jù)對模型進行訓練，預測路段代價值ω，然后與城市干道網(wǎng)絡相結合，建立帶權重交通網(wǎng)絡。最后，通過與禁忌搜索物流配送路徑優(yōu)化算法對比實驗，該算法在實際配送中配送速度、物流成本與經(jīng)濟效益明顯優(yōu)于禁忌搜索路徑優(yōu)化算法。因此，該算法是物流配送路徑優(yōu)化的一種有效方法。

深度學習；物流配送；路徑優(yōu)化；自編碼網(wǎng)絡；優(yōu)化算法

0 引言

物流配送目的是把物資分發(fā)給相應的客戶手中。在運輸過程中，如何在最短時間，最低花銷完成配送是物流配送主要研究的問題。物流配送成本在整個環(huán)節(jié)中占了最大的比例。配送線路安排的合理與否，對配送速度、成本、效益影響很大,特別是在當今道路交通擁堵，車輛增多的情況下，科學地規(guī)劃物流配送，能很好地提高物流效益，增進經(jīng)濟的發(fā)展。

在實際生活中，物流配送活動的關鍵是物流配送的路徑優(yōu)化,與電子商務的發(fā)展也是密切相關的。對貨運車輛進行路徑優(yōu)化，可以提高經(jīng)濟效益，實現(xiàn)合理高效物流。對物流配送路徑優(yōu)化的研究，是研發(fā)智慧物流、開展現(xiàn)代電子商務、智能調(diào)控交通運輸?shù)幕A。同時路徑優(yōu)化對城市合理的交通指導，因而改善城市的交通環(huán)境。因此，對配送路徑優(yōu)化問題進行研究具有重要的科學意義和應用價值。為此，我們運用人工智能的深度學習技術，對物流配送路徑人優(yōu)化算法進行研究，具有非常重要的意義。

1 相關研究工作

物流配送路徑優(yōu)化的研究二十世紀六十年代開始，經(jīng)歷了簡單的啟發(fā)式算法，啟發(fā)式算法的設計和當前的人工智能算法三個階段[1]。使用較多的算法有蟻群算法和遺傳算法，其中模擬退火算法、粒子群算法和禁忌搜索算法等。

國內(nèi)，統(tǒng)計最近三年有關物流路徑優(yōu)化的文獻，發(fā)現(xiàn)使用最多的是蟻群算法，主要原因是蟻群算法原理簡單，易于實現(xiàn)，且尋優(yōu)能力較強[2]，實際應用效果明顯，許星[3]在蟻群算法中引入遺傳操作、修改信息素更新策略。其次使用較多的是遺傳算法，遺傳算法有良好的高柔性和魯棒性[4]，在初始種群的劃分和交叉變異環(huán)節(jié)上易于提出改進，顧志康[5]基于遺傳算法特性，設計了新的染色體結構，并運用混合交叉法進行基因重組進行算法改進。傅成紅[6]針對一種典型的車輛路徑問題禁忌搜索算法，提出用毗鄰信息指導的動態(tài)候選集規(guī)模改進禁忌搜索算法，國外Schmitt[7]解決帶時間限制的CVRP（帶裝載力限制車輛路徑問題）利用了交換變異算子和交叉算子的遺傳算法，并在以后的研究中做了改進;Ombukib[8]等設計了多目標遺傳算法求解帶VRPTW（帶時間窗約束車輛路徑問題）問題;William[9]提出兩種混合遺傳算法解決VRP（車輛路徑問題）。Montane[10]使用分區(qū)-路徑規(guī)劃法構造啟發(fā)式算法產(chǎn)生初始解，然后通過鄰域操作設計構造求解VRPPD的禁忌搜索算法;Ho[11]通過節(jié)點再分配、節(jié)點分裂、節(jié)點交換和2-opt等四種鄰域設計構造算法求解VRP，根據(jù)以往文獻分析，總體而言，禁忌搜索在求解VRP方面最為有效，能在最短時間得到最優(yōu)解，其缺點在于難以確定適當禁忌期限；模擬退火算法競爭力相對較弱，存在方法過于復雜，運算量大，涉及復雜的求解策略等問題，若是允許較長的計算時間，模擬退火是最好的選擇；遺傳算法性能優(yōu)良，目標函數(shù)值相對變化很小，然而產(chǎn)生初始種群的隨機數(shù)選擇、交叉和變異過程對求解有很大影響;蟻群算法[12]則存在搜索速度較慢、較易早熟等問題，雖經(jīng)多次改進，但綜合比對，其求解速度和解質量仍難讓研究者滿意;在某些情況下，結合各種算法特點設計的混合算法[13]能取得較好的求解效果，神經(jīng)網(wǎng)絡的發(fā)展，深度學習對解決物流配送路徑優(yōu)化問題提供了一種更好的方法。

2 深度學習基本原理與物流路徑問題

2.1 深度學習

最近，隨著Master在圍棋上的不斷連勝，深度學習也變得廣為人知，深度學習本質[14]上就是多層神經(jīng)網(wǎng)絡，常用來解決分類、回歸、關聯(lián)規(guī)則挖掘、動態(tài)系統(tǒng)應用等問題。深度學習常用的模型[15]有：限制玻爾茲曼機模型是個二部圖，模型的的隱藏節(jié)點條件獨立；自動編碼器模型，它的輸出值設定為輸入值，這樣訓練得到的參數(shù)可以最大程度提取數(shù)據(jù)的共性特征。;深信度網(wǎng)絡（DBN）有多個限制玻爾茲曼機組成，先預訓練得到權值，訓練時間有效的減少；卷積神經(jīng)網(wǎng)絡（CNN），它的原理是實現(xiàn)數(shù)據(jù)在空間上變換，從而減少維數(shù)，降低訓練時間。在圖形識別應用上，不用復雜的特征提取和重建數(shù)據(jù)，直接作為網(wǎng)絡模型的輸入。

考慮到每天都有大量的交通監(jiān)控數(shù)據(jù)生成，道路的交通狀況會周期性的重復，在龐大交通數(shù)據(jù)里面，必然存在著一定的共性特征。自編碼網(wǎng)絡與DBN和CNN模型相比，結構簡單，且訓練時間短。自編碼網(wǎng)絡訓練的原理是依據(jù)相同的輸入輸出節(jié)點，因此在交通數(shù)據(jù)訓練上，可以有效的提取共性特征，在道路交通預測中采用自編碼網(wǎng)絡的方法可以快速有效的訓練模型。

2.2 物流配送難點

物流配送是依據(jù)客戶指定的目的地和貨物，在規(guī)定的時間內(nèi)送達，中間過程是在配送中心分貨、轉運。在眾多研究中[16-18]，大家把物流配送路徑選擇作為旅行商問題來解決，但以前的研究基于一個靜態(tài)的交通網(wǎng)絡，但現(xiàn)在我國物流業(yè)高速發(fā)展，交通壓力變大，必須要考慮道路交通狀況對物流配送路徑選擇的影響。

配送的難點：傳統(tǒng)配送中，司機在物流配送過程中，路徑的選擇主要依靠過往的經(jīng)驗或者同事的建議，可以快速有效地將貨物送達，如果在一個新的配送區(qū)域，可能要花很多的時間去熟悉道路；在預警天氣面前，有些路段受影響嚴重，既定路線無法通行，運輸時間無法保證；上下班高峰時，部分路段擁堵嚴重，道路施工時，路段封閉等意外情況都會造成配送的困難。

例如；大家在使用百度地圖或高德地圖時，經(jīng)常遇到導航的路線無法通行，因為城市每天都有大量的道路施工，影響著路段的交通。

2.3 路徑優(yōu)化模型

解決2.2節(jié)中物流配送問題，關鍵在于準確預測當前時間段，物流配送經(jīng)過路段的道路交通情況，依據(jù)預測的道路狀況選擇合理的物流配送路徑。物流配送路徑優(yōu)化模型如下圖:

圖1

交通數(shù)據(jù)按時段分為多個樣本組，其中白天5-22點交通數(shù)據(jù)具有研究價值，因此把樣本按時刻劃分為17組，道路交通網(wǎng)絡主要考慮其拓撲結構。配送信息需要出發(fā)時間、配送地點。道路的拓撲結構附加上預測的各時刻路段通行代價權重，就構成了分時帶權交通網(wǎng)絡模型。這時的物流配送路徑優(yōu)化問題就轉化成了旅行商問題，根據(jù)網(wǎng)絡模型的復雜程度，選擇合適的算法，最后求解最優(yōu)配送路徑。

交通狀況的預測需要考慮天氣、道路施工、節(jié)假日和上下班高峰等，考慮到同樣的天氣情況下，路段的道路交通受影響程度不同。例如在下中雨的時候，有的路段地勢高，道路寬敞，交通受影響較輕。有的路段地勢低，且道路狹窄，道路交通受影響嚴重。因此，如果對天氣氣象設定通用的影響值，是不妥當?shù)摹Ｐ枰致范卧O置天氣影響值。

新版氣象災害預警信號從五個等級改成了四個等級，分別用藍色、黃色、橙色和紅色來表示，表示一般、較重、嚴重和特別嚴重，同時以中英文標識，與國家的所有應急處置等級和顏色保持一致。因此我們把天氣影響值Ti依照預警等級分為四個值，設定工作日正常天氣交通代價值為標準值T0、預警天氣代價值為Tq，天氣影響值為預警天氣時路段代價值與正常天氣時代價值之比。公式如下：

道路施工可能造成路段擁堵，甚至路段封閉。例如，最近眾多城市都在修地鐵和高架，對城市道路交通影響非常嚴重，依靠導航經(jīng)常遇到無法通行的情況。因此，對路段狀態(tài)值的判斷也是很重要的，路段狀態(tài)判斷在交通樣本數(shù)據(jù)分組時進行，如果發(fā)現(xiàn)在該路段中一天內(nèi)都無車輛經(jīng)過信息，即判定道路封閉。

國家交通有關法規(guī)規(guī)定:城市無中心線道路限速30公里每小時，公路為40公里每小時，為了方便自編碼網(wǎng)絡模型的訓練和道路狀況的區(qū)分，按最高速40公里每小時，最低速為0，平均劃分十等分，設定道路狀態(tài)值為RbR，具體數(shù)據(jù)通過對關注區(qū)域的路段固定周期測得。

因為數(shù)據(jù)的訓練是按小時劃分的，因此不需要再考慮上下班高峰的問題，周末和節(jié)假日，人們出行情況變動較大，道路狀態(tài)值受影響情況明顯。節(jié)假日影響值Ji，影響值即與正常天氣路段代價值之比，故公式如下：

3 物流路徑的優(yōu)化

3.1 深度學習與物流配送的結合

本文采用了基于自編碼網(wǎng)絡的深度學習模型[19]，模型只計算隱藏層的權重參數(shù)，不進行分類操作，用合適的函數(shù)來分類，這樣很大程度上提高了分類的精度，但是文獻19中的模型數(shù)據(jù)分組不夠精細，對天氣因素的處理不夠合理，因此我們對數(shù)據(jù)按時段分組，使得預測更為精準，對天氣因素處理先按天氣分組，對比訓練后計算出天氣影響值，同理求解出周末和節(jié)日影響值。訓練流程如圖2所示。

圖2

自編碼模型如圖3所示。

圖3

模型權重參數(shù)求解采用常見的梯度下降法，通過迭代逼近求取隱層權重ω，輸入特征向量V與輸出節(jié)點一一對應，因此采用Sigmoid函數(shù)為隱藏層的變換核函數(shù)[19]，輸入特征向量v與權重ω計算后加上偏置數(shù)b得到輸出特征值，求解過程歸結如下：

在分類問題上，采用基于Softmax的預測模型[19]，設定類標簽y（i）∈{1，2，…，10}，分類標簽代表預測模型要輸出的10個路段代價值，估算概率值p=（y=j|x），于是假設函數(shù)hθ（x）如下：

其中：θ1，θ2，…，θk為要求取的模型參數(shù)，同理，代價函數(shù)則為：

求取最小j（θ）時參數(shù)值θj的值，通過迭代的方法算出模型參數(shù)θk。求解出最終的路段預測器。

3.2 交通網(wǎng)絡權重

物流配送最優(yōu)路線應該是：路途最近，即經(jīng)過路段長度最短；時間最短，最短時間內(nèi)把物品送到目的地；路線可行，即選擇的路線沒有路段封閉或者嚴重擁堵。由此定義路段權重式子如下：

W=S×Ti×Ji×j（θ）σ（6）

S為路段長度，σ為固定系數(shù)，經(jīng)學習可以獲得。路段權重為標準路段代價值、影響值和路段長度系數(shù)的積。

3.3 算法選擇

城市內(nèi)的交通網(wǎng)絡規(guī)模相對較小，運算量較少，采用禁忌算法最為合適。如果在多個城市之間物流中轉時，可以采用混合算法求解。

3.4 優(yōu)化算法描述

基于帶權重交通網(wǎng)絡的物流配送路徑優(yōu)化算法如下：

輸入：配送貨物要到達的地點，所在地的最近時期道路交通信息和路段長度，配送出發(fā)時間。

輸出：當前時段最合適的物流配送路線。

Step1首先對數(shù)據(jù)樣本進行有效數(shù)據(jù)篩選和按時段分組，按正常天氣工作日（標準）、預警天氣工作日、正常天氣節(jié)假日進行分類。

Step2用標準組數(shù)據(jù)對自編碼網(wǎng)絡模型進行訓練，由公式（3）確定輸出特征，完成模型的預訓練。依據(jù)公式（4）（5）預測得到標準路段代價值T0。

Step3然后按照圖2的方式再進行分類數(shù)據(jù)的訓練，求解各個預測代價值，分別代入公式（1）（2）中求出天氣影響值Ti和節(jié)假日影響值Zi、Ji。

Step4按照標準分時數(shù)據(jù)，對自編碼模型監(jiān)督學習，求解出各時段路段代價值T0，和系數(shù)σ的值。

Step5依據(jù)配送信息，選擇對應的時刻路段代價值T0（Step4）和影響值（Step3），代入公式（6）中求得路段權重W，結合交通網(wǎng)絡的拓撲結構，構建帶權重交通網(wǎng)絡。

Step6在帶權重交通網(wǎng)絡中，采用禁忌搜索算法求解最優(yōu)路線。

Step7輸出配送路線

交通信息樣本的分組，依據(jù)節(jié)假日，上下班高峰期，天氣信息分組訓練，使得預測的代價函數(shù)值更為準確、可靠。依據(jù)獲得的最新的交通數(shù)據(jù)樣本，更新自編碼網(wǎng)絡的參數(shù)值，使得對當前路段交通狀況預測更加準確、可靠，為物流配送路徑的選擇提供依據(jù)。

4 實驗結果與分析

實驗環(huán)境是：Win7操作系統(tǒng)個人版，CPU為Intel i7 4790，內(nèi)存為金士頓16G×2的計算機，編程工具用MATLAB。網(wǎng)絡模型為三層結構，如圖4所示。

圖4

4.2 模型的訓練和測試

模型的訓練與測試基于南寧市30條主干道路的某局部區(qū)域監(jiān)控數(shù)據(jù)。交通數(shù)據(jù)采樣主要依據(jù)該區(qū)域的道路監(jiān)控數(shù)據(jù)，氣象數(shù)據(jù)和城市道路拓撲結構來自網(wǎng)絡收集。數(shù)據(jù)首先進行分類和篩選，篩選是選出錯誤數(shù)據(jù)和異常數(shù)據(jù)，異常數(shù)據(jù)比如車輛信息無，該路段1天內(nèi)無車輛通行，即可判斷該道路封閉。分類如3.1節(jié)所示，分為兩個對比組，一個標準組。每組數(shù)據(jù)均為10000個樣本進行訓練。得出特征信息，然后預測權值，再計算出天氣、周末和節(jié)日影響因子。最后進行測試，檢驗預測權值與實際權值的差距。流程如下：

預測準確率如圖5所示。

T0是工作日正常天氣下的道路代價值，Ti為預警天氣下的道路代價值，Zi為周末道路代價值。從圖5可以觀察到正常天氣情況下，準確率較低，預警天氣下準確率最高，分析其原因，正常情況下，道路的交通狀況隨機性較強，當出現(xiàn)預警天氣時，道路交通受影響明顯，預測變得簡單。分析其內(nèi)在原因，很大的可能是因為學習集包含了較多的擁堵時段數(shù)據(jù)，因此系統(tǒng)在預測真實擁堵時，準確率偏高?？偟膩碚f，路段交通狀況的預測是成功的，所以說，應用自編碼網(wǎng)絡的特征學習在對交通數(shù)據(jù)認知層次確實具有可挖掘的深度辨識能力。

圖5

4.3 配送仿真與驗證

為了驗證本文算法在實際物流配送中的效果，在南寧市隨機設置6組配送任務樣本，在各個時段執(zhí)行配送任務，分別用本文算法和禁忌搜索算法[12]求解配送路徑，最后與測試結果相對比、驗證。

表1

任務樣本選取如表1所示，任務樣本分為兩組，一組為城區(qū)內(nèi)配送，一組為不同城區(qū)間配送，周一為小雨，周三晴天，周末部分道路施工。在仿真測試中，不考慮貨物的裝卸時間。時間單位為分鐘，兩種算法物流所用平均時間如下圖：

圖6

4.4 實驗分析

通過圖4看以發(fā)現(xiàn)自編碼網(wǎng)絡模型對擁堵和突發(fā)狀況比較敏感，表1中可以發(fā)現(xiàn)在上下班高峰時段，傳統(tǒng)的TS算法所選擇的路徑時間大大地增加了，原因有高峰期擁堵和一些主干道的施工影響。周一和周三的物流配送時間相似度較高，明顯可以觀察到天氣對道路交通影響，在周日，物流配送時間規(guī)律與工作日浮動明顯。施工影響道路交通，物流配送時間增長明顯。

對于整個交通道路狀況來說，此次訓練的數(shù)據(jù)量還是較為偏少，但在訓練結果上，該算法顯示了在擁堵、天氣、意外狀況下路況預測上的巨大優(yōu)勢。隨著未來的經(jīng)濟發(fā)展，道路狀況在很長的一段時間內(nèi)都處于高壓狀態(tài)，通過深度學習的方法，對大量的交通信息進行分析，預測道路交通狀況，為物流配送選擇合適的行程路線，因此對深度學習在交通運輸?shù)膽醚芯渴呛苡斜匾陀幸饬x的。

5 結語

針對城市的快速發(fā)展，車流量的快速增長，城市的擁堵時常發(fā)生，通過對過往車流量的數(shù)據(jù)分析，準確預測主要干道的道路交通狀況，依據(jù)路段狀況合理選擇行駛路線，為城市交通帶來幫助。深度學習現(xiàn)在仍處于研究階段，但在很多行業(yè)都顯示了極大的潛力。相信未來它對交通運輸?shù)膸椭佑辛Α?/p>

[1]ChaoWang Mohammed A Quddus*，GIson.Impact of Traffc Congestion on Road Accidents:A Spatial Analysis of the M25 Motorway in England[J].Accident Analysis and Prevention，2009，41（4）:798-808.

[2]陳迎欣.基于改進蟻群算法的車輛路徑優(yōu)化問題研究[J].計算機應用研究，2012，29（6）:2031-2034.

[3]許星.物流配送路徑優(yōu)化問題的研究[D].杭州:浙江大學，2006.

[4]王輝.基于改進遺傳算法的物流配送路徑優(yōu)化研究田[D].青島：山東科技大學，2010.

[5]顧志康，李旭宏，徐家兵.一種改進遺傳算法在物流配送車輛調(diào)度中的應用研究[J].公路交通科技，2004，21（11）:118-120.

[6]袁慶達，杜文，周再玲.帶軟時間窗的混合車隊車輛路線問題的模型和算法研究田.西南交通大學學報，2000，36（4）:401-406.

[7]L.J.Schm itt.An Evaluation of a Genetic A lgorithmic Approach to the Vehicle Routing Problem[R].Working Paper，Department of Information Techonogy Management，Christian Brothers University，Memphis，TN，1995.

[8]Ombukib，et al.Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows[J].Applied Intelligence，2006，24（1）:17-30.

[9]William Ho，George T.S.Ho，Ping Ji.A Hybrid Genetic Algorithm for the Multi-Depot Vehicle Routing Problem[J].Engineering Applications of Artificial Intelligence，2008，21（4）:548-557.

[10]Montane F A T，Galvao R D.A Tabuproblem with Simultaneous Pick-up and Delivery Research，2006，33（3）:595-619.Algorithm for the Vehicle Routing Service[J].Computers&Operations

[11]Ho SC，D.Haugland.A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows and Split Deliveries[J].Computers&Operations Research，2004，31（12）:1947-1964.

[12]彭碧濤，周永務.多時間窗車輛路徑問題的混合蟻群算法[[J].計算機工程與應用，2010，46（31）:28-31.

[13]Thangiah SR，Osman IH，Sun T.Hybrid Genetic Algorithm，Simulated and Tabu Search Methods for Vehicle Problems with Time Annealing Windows[R].Technical Report SRU 2CpSc2TR294227.Computer Science Department，Slippery Rock University，1994.

[14]毛勇華，桂小林，李前，賀興時.深度學習應用技術研究[J].計算機應用研究，2016（06）.

[15]Zouxy，Deep Learning（深度學習）學習筆記整理系列[EB/OL].http://blog.csdn.net/zouxy09.

[16]羅慶，周軍.基于混合遺傳算法的物流配送路徑優(yōu)化分析[J].中央民族大學學報，2016（08）.

[17]李君，梁昔明，張克.改進的粒子群優(yōu)化算法在物流配送中的應用[J].北京建筑大學學報，2016（12）.

[18]李靜.一種基于蟻群改進算法的單向物流配送路徑優(yōu)化[J].電子設計工程，2016（5）.

[19]譚娟，王勝春.基于深度學習的交通擁堵預測模型研究[J].計算機應用研究，2015（10）.

Research on Optim ization Algorithm of Logistics Distribution Routing Based on Depth Learning

ZHANG Xiang-bo，LIWen-jing

（School of Computer and Information Engineering，Guangxi Teachers Education University，Nanning 530023）

Aiming at the problem of logistics distribution process,traditional path optimization algorithm is not sensitive to traffic congestion,weather conditions and environmental factors,which leads to the problem of low efficiency and unexpected situation in logistics distribution,proposes a logistics optim ization algorithm based on depth learning.Firstly,constructs amodel based on self-coding network.The model is trained according to the sample data,and predicts the expected value of the road segment.Then,the weighted traffic network is established by combining with the urban trunk network.Finally,through the comparison experimentwith the tabu search logistics route optimization algorithm,the distribution speed,logistics cost and economic benefit of the algorithm are better than that of tabu search.Therefore,the algorithm is an effective way to optimize the logistics distribution path.

張湘博（1987-），男，河南許昌人，碩士研究生，研究方向為深度學習、物流配送

李文敬（1964-），男，廣西邕寧，教授，碩士，研究方向為并行計算、智能物流

周杰（1992-），男，廣西恭城人，碩士研究生，研究方向為并行計算、圖像處理

李松釗（1994-），男，廣西靈山，碩士研究生，研究方向為深度學習

2017-03-09

2017-05-04

國家自然科學基金（No.61363074、No.61163012）、廣西自然科學基金（No.2016GXNSFAA380243）

1007-1423（2017）14-0014-07

10.3969/j.issn.1007-1423.2017.14.003

Depth Learning;Logistics Distribution;Path Optimization;Self-Coding Network;Optimization A lgorithm