1、物流配送車輛優化調度的一種神經網絡算法摘要：本文討論了物流配送車輛優化調度問題的分類，建立了解決非滿載車輛卸貨路線優化的神經網絡模型，提出了解決配送車輛優化調度問題的步驟，并進行了具體的調度試驗，驗證了算法的可行性。關鍵詞：配送，調度，神經網絡0 引言據統計，美國2000年的運輸費用為5900億美元，占當年GDP總值99600億美元的5.92%，可見，減少運輸費用是有效減少物流成本的重要方面。對于物流中心和第三方物流企業的貨物配送，運輸車輛的調度是工作的重點，正確合理的調度可以有效減少車輛的空駛率，實現合理路徑運輸，從而有效減少運輸成本，節約運輸時間，提高經濟效益。1 配送車輛調度優化問題分類

2、運輸車輛的優化調度問題由Dantzig和Ramser于1959年首次提出，由于該問題在交通運輸、工業生產管理等領域具有廣泛而重要的應用，因此30多年來其研究得到很大重視，國外的Bodlin，Christofider，Golden，Assad, Ball 等人對該問題進行了較為深入的研究1 2 3。 總體上看，車輛的優化調度問題一般可根據時間特性和空間特性分為車輛路徑規劃問題和車輛調度問題。當不考慮時間要求，僅根據空間位置安排車輛的線路時稱為車輛路徑規劃問題（VRP-Vehicle Routing Problem）；考慮時間要求安排運輸線路時稱為車輛調度問題VSP（Vehicle Schedul

3、ing Problem）。某些學者將有時間要求的車輛調度問題稱為Vehicle Routing Problem with Time Windows。車輛優化調度問題可根據不同性質具體分為以下幾類。按照運輸任務分為純裝問題、純卸問題以及裝卸混合問題，所謂的裝卸混合問題就是車輛在運輸途中既有裝貨又有卸貨。按照車輛載貨狀況分為滿載問題和非滿載問題，滿載問題是指貨運量多于一輛車的容量，完成所有任務需要多輛運輸車輛。非滿載問題是指車的容量大于貨運量，一輛車即可滿足貨運要求。按照車輛類型分為單車型問題和多車型問題。按照車輛是否返回車場劃分為車輛開放問題和車輛封閉問題，車輛開放問題是指車輛不返回其出發地，車

4、輛封閉問題是指車輛必須返回其發出車場。按照優化的目標可分為單目標優化問題和多目標優化問題，單目標優化是指某一項指標最優或較優，如運輸路徑最短。多目標優化則是指同時要求多個指標最優或較優。如同時要求運輸路徑最短和費用最省。 按照貨物的種類要求可分為同種貨物優化調度和多種貨物優化調度。多種貨物優化調度問題是指運輸貨物的種類多于一種，車輛調度時可能要考慮某些種類的貨物不能同時裝配運輸的要求，如滅害靈等殺蟲劑和食品等不能混裝運輸等。 按照有無休息時間要求可分為有休息時間的優化調度和無休息時間優化調度問題。 實際中的車輛優化調度問題可能是以上分類中的一種或幾種的綜合，如某配送中心向其多個客戶配送貨物需要

5、多輛車，這些車的類型不一樣，運輸的貨物種類包括食品、日用品和蔬菜等多類，調度優化時希望運輸費用最省，同時也希望運輸時間最短，這樣問題變為一個多車型多貨種的送貨滿載車輛的多目標優化調度問題。 車輛的優化調度問題是一個有約束的組合優化問題，屬于NP難題（Nondeterministic Polynomial Problem），是一個非確定型的多項式問題。NP問題的解有多個，隨著其輸入規模的擴大，問題的求解難度大大增加，求解的時間呈幾何級數上升。目前，尚無有效的多項式時間算法來求解NP難題。 在求解車輛優化調度問題時，常常將問題分解或轉化為一個或幾個已經研究過的基本問題，如旅行商問題，最短路徑問題，

6、最小費用流問題，中國郵遞員問題等。再用比較成熟的理論和方法進行求解，以得到原車輛調度問題的最優解或滿意解。常用的方法可以分為精確算法、啟發算法和智能算法。精確算法主要有分支界定法，割平面方法，線性規劃法，動態規劃法等，啟發式算法主要有構造算法、兩階段法、不完全優化法等，智能算法分為神經網絡方法、遺傳算法和模擬退火算法等。精確算法的計算量隨著車輛優化問題規模的增大呈指數增長，如當停車卸貨點的數目超過20個時，采用一般的精確算法求解最短運輸路徑的時間在幾個小時以上。精確算法不適合于求解大規模的車輛優化調度問題。2 配送車輛優化調度的神經網絡算法2.1 算法概述人工神經網絡是對人腦功能的簡單和近似模

7、擬，它由大量具有某種傳遞函數的神經元相互連接而成。人們經常采用Hopfield網絡和自組織特征映射神經網絡來解決車輛的優化調度問題。在Hopfield網絡中，系統能夠從初始狀態，經過一系列的狀態轉移而逐漸收斂于平衡狀態，此平衡狀態是局部極小點。采用神經網絡來求解車輛調度問題時一般按下列步驟進行4：(1). 產生鄰接矩陣將車輛的源點、所經過的各個匯點和停點抽象成網絡的結點，它們之間的有向路徑抽象成網絡的邊，由此構成一個有向圖G=(N,L,D)，其中N表示結點數，L表示邊數，D為N×N的矩陣，可根據優化的目標分別是邊（i,j）對應的長度、費用或時間，這樣可定義距離鄰接矩陣、費用鄰接矩陣和

8、時間鄰接矩陣。如果兩個結點間存在路徑，則相應矩陣元素的值為路徑的長度或運費或運時；如果兩個結點間不存在路徑，則相應矩陣元素的值為。(2). 約束的處理對于車輛調度中的約束，將其作為神經網絡的一個能量項來處理，將其施加一個懲罰項后加入到網絡的能量方程式中，這樣隨著網絡的收斂，約束的能量也逐漸趨于穩態，使約束得到體現。(3). 神經網絡計算設鄰接矩陣中的每個元素對應著一個神經元，定義位于位置(x,i)的神經元的輸出為Vxi。首先確定網絡的能量函數，該能量函數包括網絡的輸出能量函數和各個約束轉化的能量函數， 進而，確定神經元的傳遞函數和狀態轉移方程，經過網絡的反復演化，直至收斂。當網絡經過演化最終收

9、斂時，可形成一個由0和1組成的換位陣，陣中的1所在位置即表示所經過的結點，這些結點間的距離、費用和運時之和即為最短距離、最少運費和最小運時。(4)調度方案的形成根據換位陣所形成的最短距離、最小運費和最小運時路徑，最終來確定車輛調度的方案。2.2 非滿載配送車輛優化路徑的Hopfield網絡求解算法2.2.1 約束條件為確保網絡穩態時的輸出能量是一個有效的換位陣，網絡必須同時滿足以下約束條件(1) 有效路徑約束為防止不存在的路徑被選中，設定如下的約束函數：式中：u1為懲罰系數(2) 輸入輸出路徑約束為保證網絡的結點有輸入路徑，必有輸出路徑，設定如下的約束函數：式中：u2為懲罰系數(3) 為保證網

10、絡的狀態收斂到超立方體2n(n-1)中的一個，設定如下的約束函數：式中：u3為懲罰系數(4) 為保證最短路徑源于規定的起點s，終止于規定的終點d，約束函數設定如下： (4)式中：u4為懲罰系數2.2.2 能量方程網絡的目標函數設定為： (5)式中：u5為懲罰系數 網絡的能量函數為：(6)各神經元的輸出為： (7)模型的運動方程為： (8) (9)將式（6）帶入式（9）得到神經網絡的運動方程： (10)式中規定為： (11)比較式(8)和式(10)中的系數，可以得到如下的連接權重和偏置電流為：(12)(13)將式(12)和式(13)中的Txi,yiIxi代入式(8),然后交替求解網絡的運動方程式

11、(8)和代數方程式(7)，當神經網絡趨于穩態時，就可得到一個優化解，即最短路徑。4 試驗 深圳市科技園的實際部分路網如圖1所示，針對此路網，設定由沃爾瑪商場先向華潤超市后向清華深圳研究生院配送商品，運輸車輛為一輛小型皮卡車，要求運輸路徑最短。假設先送華潤超市，后送清華研究生院，以沃爾瑪商場為起點，以華潤超市為終點，將其間所有路網點編號，如圖1所示。采用Hopofield網絡來1點到12點之間求最短路徑。首先，生成的距離矩陣：用Hopfild神經網絡對以上的有向圖進行計算，選取各懲罰系數如下：51000；14000；21500，31000；4550。網絡的時間常數=1，并假定每個神經元的具有相同的傳遞函數，即gxig;xi=；網絡的初始電壓Uxi=0。對圖的網絡圖進行計算，其神經網絡的最終輸出的換位陣如下所示根據換位陣，得到的最短路徑為：1 4 7 12同理，在求由華潤超市到清華深圳研究生院時的最短路徑時，以華潤超市為起點1，清華研究生院為終點12，對其中的路網進