多點物流配送車輛路徑問題（VRP）優化與實證分析

摘要：本文應用掃描算法對多點物流配送車輛路徑問題進行優化，借助計算機編程實現多目標、動態車輛調度和線路優化。以河北快運為例進行實證分析，結合實例進行測試和結果分析，證明其可行性，使該算法設計更好地適應實際的需要。

關鍵詞：多點物流配送；車輛路徑問題；優化

基金項目：廣東省高等教育教學研究和改革項目：物流專業產教融合協同育人平臺建設研究

在配送線路優化設計中，通常有兩類問題：一類是尋求兩點之間最短路徑，此類問題一般采用圖論中求解最短路問題最好的算法Dijkatra算法進行優化。另一類是尋求從某一點到其余各點的最短路徑，即物流配送網絡中有一個配送中心和n個節點，車輛由配送中心出發，服務完n個節點再返回配送中心。這類問題就是多點物流配送車輛路徑問題。該問題的研究目標就是對一系列客戶需求點設計適當的配送線路，并在滿足一定約束條件（如供應量、需求量、車載限制、時間限制等）的基礎上，實現優化目標（如里程最短、費用最省、時間最少等）。本文筆者重點討論由一個配送中心向多個客戶進行共同配送的車輛路徑問題。

1.模型的建立

多點物流配送車輛路徑問題（Vehicle Routing Problem ，VRP）最早是由Dantzig和Ramser于1959年首次提出的，后被證明屬于NP難題行列。

一般車輛路徑問題描述為：某配送中心有[M]輛車，需對[N]個節點（客戶）進行運輸配送，每個節點的需求量為[gi]（[i=1，2，...，N]），每輛配送車輛的最大載重量為[q]。設[cij]表示節點[i]到節點[j]的運輸成本，如時間、費用等。為構建數學模型的方便，將配送起點編號為0，各個配送任務節點標號為1，2，… N，配送中心以及貨運節點統一用點i（i=0，1，2，…N）來表示。變量定義如下：

[yki=1 節點i的任務由車輛k完成0 否則xijk=1 車輛k從節點i行駛至節點j0 否則]

建立VRP數學模型：

[minz=ijkcijxijkigiyki≤q ?k式（1）kyki=1M i=1，2，…，Ni=0式（2）ixijk=ykj j=1，…，N；?k式（3）jxijk=yki i=0，1，…，N；?k式（4）]

其中，式（1）為車載容量約束；式（2）保證每個節點的運輸任務僅由1輛成完成，且所有任務則由M輛車協同完成；式（3）和式（4）限制到達和離開某一客戶的車輛僅有1輛。

2 .模型的求解思路 （用VRP 掃描法）

2.1 VRP 掃描算法基本思想

掃描法（Sweep Algorithm） 目的在于求解車輛調度問題，并針對幾個求解相似問題的算法進行比較，證明該算法所求得的解較優于其他的方法，此方法屬于先分群再排路線的方法，此方法分為兩階段：

第一階段：用坐標表示各需求點的區位，然后任取一需求點為起點，以車輛容量為分群的約束，再以該需求點為零度按順時針或逆時針的方向，進行顧客的掃描分群；

第二階段：依據求解旅行商問題（TSP）的算法，求解各顧客群的排程。

2.2 VRP掃描算法求解步驟

2.2.1確定配送中心和各個節點的位置和需求量；

2.2.2以配送中心為原點，確定一尚未使用車輛，從最小角度且尚未指派的節點開始，沿著順時針或逆時針方向掃描，當該車輛容量超限時，結束該條線路；

2.2.3重復上述步驟，生成新的線路，直至所有節點都被排入線路；

2.2.4依據TSP算法，求解出各站點在各線路上排定的順序，使行駛路線最短，成本最低。

3.算例分析

3.1問題描述

本文以“邯運杯”全國大學生物流設計大賽案例中的河北快運公司為例進行分析研究，本文中的數據都來源于大賽案例。河北快運下設四個子公司分別為天恒、天昊、天誠以及天信。河北快運的總分撥點設在廊坊。河北快運2006年及2007年業務量如圖1和圖2所示。

由圖1和圖2知，河北快運下設的四個貨運子公司每年貨運量差距大，每月總貨運周轉波動幅度大，且各子公司之間存在著相互競爭的局勢，不利于創造雙贏。從中總結得出河北快運需在車輛調度和配送線路選擇方面進行綜合優化。

3.2問題求解

為了研究的需要，對模型進行一些假設：①河北快運子公司間的競爭可協調，實現資源的統一調配；②假設所有車輛具有相同容量，車載限額40噸；③暫不考慮貨物的缺失成本。④利用計算機進行求解，詳細計算過程略，直接得出優化結果。

具體步驟：

①利用VB編程，創建運輸配套程序窗口（與總公司的SQL數據庫相連），結合算法構建一個比較完善的運輸調度系統。

②通過運輸配套程序窗口，獲取多目標配送相關的信息，其中包括貨物種類、數量、所需到達時間及回程貨源等信息。

③在相關約束條件下，執行VRP掃描法，得出最終配送優化線路和確定調配車輛數。

結束語

本文針對多點物流配送車輛路徑問題，建立數學模型，根據企業實際數據、借助計算機軟件進行算例分析，為企業的車輛路徑問題進行優化。本文借助計算機編程實現快捷、動態的多點物流配送車輛路徑問題優化，具有一定的理論價值和實際應用價值。在實際應用中，多點物流配送車輛路徑問題的優化需要考慮的因素很多，為了求解的方便，筆者在求解過程中作出一些假設，使本文的算法的應用具有一定的差距。所以，如何尋找一種綜合考慮多因素影響的模型和算法，是今后還需進一步努力研究的方向。另外，VRP屬于NP難題行列，所以VRP目前仍是一個困難的組合優化問題，理論上，僅能保證一些相對小規模的VRP可求得最優解。

參考文獻：

[1]方金城，張岐山.物流配送車輛路徑問題（VRP）算法研究[J].徐州工程學院學報，2007，22（2）：84-88.

[2]洪江濤，陳誠.物流企業車輛調度的優化模型研究[J].軟科學，2011，25（3）：126-129.

作者簡介：

王榮花（1977- ），女，山西臨汾，碩士研究生，講師，研究方向：物流管理。