基于神經網絡的煙草物流配送路徑優化研究

萬貴華，陳昌明，徐 方，高向東，武長征，曾 蕾， 甘 露，李小峰，許軍華，鄧 敏 ，徐 瓊

(1. 湖北省煙草公司孝感市公司 物流中心，湖北 孝感 432000； 2. 湖北工程學院 計算機與信息科學學院，湖北 孝感 432000)

隨著我國煙草物流的不斷發展，其規模逐年遞增，物流建設也越來越受到行業的重視，對煙草物流也有了更多的投資。當今煙草物流的建設工作按照“由小到大、由內到外、由商流到物流”的原則逐步開展[1]。影響煙草行業經濟效益的因素眾多，其中，煙草物流這一因素對煙草行業總體經濟效益影響最為顯著。近年來，國家越來越重視煙草物流的建設工作，煙草物流的信息化和智能化有了長足的進展。同時，國家政策也給行業物流提供了大力支持，使得煙草商業交易的網絡化、智能化不斷完善[2]。

然而，國內煙草物流行業仍存在許多不足。首先，物流環節獨立管理和運作無法形成大規模的統一管理模式，從而不能獲得大規模物流效益，因此難以由量到質的改變。其次，物流基礎設施總體布局不科學、不統一，影響物流效率[3]。最后，長遠規劃不足，缺少科學的管理，需要有合理的系統管理軟件來搭配硬件設施進行高效管理。

物流配送路徑優化是國內外學者競相研究的熱點問題。基于最短路徑的迪杰斯特拉(Dijkstra)算法是較早提出的著名路徑優化算法[4]，該算法是求解圖中的一個頂點到圖中其他各點的最短路徑，使用貪心算法策略最終解決有權圖的路徑優化問題[5]。基于蟻群的優化算法是模仿螞蟻尋找食物時進行路徑發現的方法[6]，是一種概率型路徑優化算法。基于遺傳算法[7]的多目標路徑優化方法根據生物在自然界中的進化規律而設計[8]，通過模擬自然選擇和生物進化的過程搜尋最優路徑。基于動態規劃思想的Floyd算法可以在加權圖中搜尋給定節點到多源點之間的最短路徑[9]。但是上述算法都有各自的不足之處，存在學習效率低、收斂速度慢，或者容易陷入局部最優解等問題。為了在煙草物流配送路徑規劃中克服上述不足，尋找最優配送路徑，本文提出了改進的神經網絡路徑優化算法，提高優化效率，避免算法陷入局部最優解。

1 煙草物流配送概述

煙草物流中最重要的是配送路徑的優化問題。主要存在車輛路徑問題、旅行商問題、路徑優化問題，還需要考慮貨物量、車輛的裝載量、車輛行駛時間等因素。

1.1 車輛路徑問題

車輛路徑問題通常是指貨物由一個點或者配送中心的一輛或多輛運輸車分配到多個需求點的過程(如圖1所示)。此過程可能存在時間窗口、負載限制等制約因素。經過合理規劃車輛后，能使整個配送過程滿足一些目標，例如成本最少或者時間最少等。近年來，車輛路徑的優化是各國研究者競相研究的熱點問題，其研究成果有著廣泛的應用領域，適用于許多行業的車輛路徑規劃。該研究成果可以有效降低企業的運輸成本，提高運行效率和經濟效益，具有較高的研究價值和很好的經濟效益。

圖1 車輛路徑問題示意圖

1.2 旅行商問題

旅行商問題的定義可描述為一個商人需要前往多個目的地，其中每個目的地都必須且只能路過一次，當該商人最終返回出發點時，本次旅行結束。而待解決的問題便是如何使該商人的旅行總路徑最少，或者花費的時間最短，或者是產生的費用開銷最少。

下面對這一問題進行數學建模，商人要去的地點集合可以記為C={C1，C2，…，Cn}，地點Ci與地點Cj之間的距離可以表示為d(Ci，Cj)∈Z+，要求集合C中的每個地點被經過一次，則路徑可以表示為(Ck1，Ck2，…，Ckn)，該路徑要滿足如下表達式的值最小，表達式如下：

(1)

式中：k1，k2，…，kn是1，2，…，n的一個置換。

1.3 路徑優化問題

目前的車輛路徑優化算法可分為兩類，分別是精確算法和啟發式算法。啟發式算法是目前研究的熱點，它又可以細分為傳統啟發式算法和現代啟發式算法。對于精確算法來說，它的主要優點在于，處理較小規模問題，能較快獲得最優解。然而在處理大規模問題時，這種類型的算法需要大量的運算時間，不能應用于實時性要求高的場景。這種類型的算法主要有切平面法、Dijkstra算法、動態規劃法和和分支定界法。

啟發式算法是相對于精確算法而提出的，是根據工作經驗的積累或受到自然現象的啟發來尋求解決方案，采用全局概率搜索法求解問題。傳統啟發式算法的主要特點是更傾向于在可接受范圍內尋求最優解。這些算法主要有：兩階段法、插入算法、節約算法、掃描算法等。然而，現代啟發式算法在階段計算的結果中允許次優解。這方面的典型算法有遺傳算法[10]、模擬退火算法[11]、蟻群算法[12]、禁忌搜索算法[13]和比較流行的神經網絡算法。啟發式算法雖然不能保證問題的最優解，但在大規模問題的場景求解時可以快速找到較好的解。

2 神經網絡路徑優化算法

人工神經網絡采用許多電子元器件模擬生物神經網絡中的神經元，這些電子元器件進行大規模的連接以適應于并行處理模式，并組建神經網絡模擬人腦的運行方式，實現人腦的部分功能。由于它可以通過大量樣本的學習訓練來處理復雜事物關系，特別適合解決各類預測、分類、評估匹配、識別等問題，因此在金融、 航空、醫學、環保等領域都有應用的前景。

2.1 Hopfield神經網絡

在上世紀80年代，美國科學家霍普菲爾德將能量函數相關的內容引入到對稱網絡的研究中，進而研究出了Hopfield模型。這種方式對網絡的穩定性有較大的改善，對于當前神經網絡的發展有非常大的促進作用。下面的圖2為離散Hopfield神經網絡結構圖。

圖2 三層離散Hopfield神經網絡結構圖

圖2中的第0層是網絡的輸入，并非神經元，因此不參與計算；真實的神經元是從圖中第1層開始，因此從該層開始根據第0層的輸入信息執行函數處理產生輸出。該模型將會比較其輸出結果與閾值函數f，如果輸出結果大于閾值θ，則模型輸出值等于1；否則，模型輸出值等于0。

對于二值神經元，它的計算公式如下

(2)

式中：Xj為外部輸入，且

(3)

2.2 神經網絡與路徑優化

區域物流網絡與神經網絡有著許多相同之處，在神經網絡模型中，神經元是區域物流網絡中的節點，而神經網絡中的邊則是各節點之間的關系，輸入是商戶地理位置信息和車輛信息，輸出則是配送路徑和時間預測信息。因此，本文利用神經網絡的高容錯性和智能處理能力，采用改進的人工神經網絡模型來推理優化物流配送路徑，將有效提高物流配送效率，帶來更大的經濟效益。

當前已有一些神經網絡模型被應用于物流配送路徑優化中，Caulfield等學者成功的將脈沖耦合神經網絡模型應用于解決迷宮中的最短路徑問題，但這種求解方式需要每個節點都與神經元一一對應，但是神經元數量龐大；為了克服這一問題，提出了時延脈沖耦合神經網絡[14]，它既保持了脈沖耦合神經元的優點，又能減少神經元數量；多輸出脈沖耦合神經網絡[15]采取線性閾值和多輸出，有效減少了迭代頻率，從而降低計算復雜度，使它僅僅和最短路徑的長度有關；三態級聯脈沖耦合神經網絡[16]通過并行方式且有效的處理了信號在神經元之間的傳輸方向，增加了神經網絡的計算速度[17]。上述方法都不太適合于煙草物流的特定場景，但受上述研究基礎的啟發，本文提出了改進的神經網絡的路徑優化算法。

2.3 改進的神經網絡路徑優化算法

圖3 神經網絡模型基本結構

在該神經網絡模型中，網絡的輸入為：

x(k-1)=[x1(k-1)，…，xn(k-1)，xn+1(k-1)，…，xni(k-1)]Tni=n+m+1

(4)

輸出為：

(5)

式中：N1，N2是第1、2層神經元數；wij為第一層到第二層的權值系數，w1j1是第2層到第3層的權值系數；θij和θ2是偏置值。

神經網絡根據樣本的輸入來調節權值，使輸出值更接近期望值，以此獲得最優路徑。實驗結果表明該算法在優化性能方面取得了較好的預測效果，具有一定的有效性和實用性。在上世紀50年代，研究者提出了模擬退火算法。在組合優化領域，后來的研究者引入了模擬退火算法，并成功進行應用。模擬退火算法是一種基于迭代求解策略的、有效的隨機尋優算法。它利用了物理中固體物質的退火過程和一般組合優化問題之間具有的某種相似性特征，能夠使用求解過程大概率的跳出局部最優解，盡可能地向全局最優解趨近。模擬退火算法可以作為一種通用的優化算法，具有較高的實用價值，目前已經廣泛的應用于工業控制和工程技術領域。

本文結合神經網絡和經典的模擬退火算法的優勢，提出了一種改進的神經網絡算法，用于進行煙草物流中的路徑規劃，優化原有煙草物流配送路徑。

本文在傳統的神經網絡算法中引入模擬退火算法的思想形成了一種改進的神經網絡算法。模擬退火算法思想有利于改進算法結果的反饋方式。另一方面，利用Hopfield的能量函數來優化原模擬退火算法的初始值，將兩種算法的優勢加以融合來彌補各自的缺點。相比于傳統神經網絡，該算法具有較高的收斂速度和求解速度。其改進的神經網絡流程圖如圖4所示，其中Ek為退火算法的初始值，Ek退火算法得了的另一計算值，p為程序設定的概率閾值，Tk為k時刻的溫度，exp表達式為模擬退火算法中的經典表達式。

圖4 改進的神經網絡算法流程圖

改進的神經網絡算法在自學習和自適應方面有著較強的能力。因此，在非可控因素(例如路段、車流量、送貨時限等)對物流配送造成影響的問題上能進行自我調節。該算法的實現降低物流配送成本、提高效率，從而獲得更高的經濟效益。

3 實驗分析

本文以湖北省煙草公司孝感市公司與湖北工程學院合作的研發項目為實例進行研究。通過對湖北省煙草公司孝感市公司煙草物流中心的配送路徑進行研究，充分了解現有車輛信息、配送路徑、送貨時長等情況，對目前煙草物流中的安排調度和配送路徑進行了研究，最終應用在項目組開發的煙草物流配送路徑優化系統上。該系統實現了煙草物流配送的智能優化，可根據當前客戶的訂貨量和客戶的地理位置分布動態生成最優配送路徑。該項目改變了原先利用經驗的人工線路規劃，利用計算機輔助，使得煙草物流路徑規劃更加科學合理，從而起到提高效率、減低成本、方便配送的作用。

下面以孝感市孝昌縣的煙草物流配送為例。研究者組織人員對該縣的煙草物流進行調研。首先，了解現有物流配送的運行情況以及存在的問題；其次，采集每個客戶的地理位置，記錄其對應的經度和緯度；最后，調研進行路徑優化時的約束條件，如對配送時間的要求、線路條數的要求、配送車輛的數量和裝載量，等等。通過前期大量的調研，研究者采集到了進行路徑優化的所有數據。最后將客戶位置信息映射到地理信息系統中，為算法的研究做好準備。將本文提出的算法應用于物流配送的前后進行對比，具體數據如表1所示。

表1 算法應用前后的相關數據對比

從表1中的數據可以看出，在配送客戶數和配送周期相同的情況下，在使用本文提出的算法后，孝昌縣煙草物流配送的車輛數、配送里程、線路條數都有所減少，其中車輛數減少了25%，配送里程減少了31.8%，線路條數減少了25%。從總體上看，基于本文所提出的路徑優化算法開發的系統達到了預期的目的，能為企業降低成本，增加效益。在系統中提供了相關參數的修改模塊，以適應不同應用場景的要求，提供系統的可維護性和使用范圍。

4 小結

本文首先分析了煙草物流行業的發展背景和趨勢，然后描述了煙草物流配送中的三個關鍵問題，分別是車輛路徑問題、旅行商問題和路徑優化問題。接著利用神經網絡建立了煙草物流路徑優化的模型，并引入模擬退火算法對其進行了改進。改進的算法能夠避免陷入局部最優解，具有很好的全局收斂性。本文以煙草配送為應用場景，每個配送點都是固定的，線路的起點和終點也都是固定的，在路徑生成中使用初始點采用固定值，初始點不參加路徑的交換活動。這樣使得算法具有較好的可用性。目前算法中的一些參數主要是根據經驗進行確定，下一步將利用相關理論和實驗分析進行參數的調優，使算法能夠輸出更好的結果。