車輛路徑問題研究綜述

吳姝雨

摘 要：作為現代物流領域的研究前沿，車輛路徑問題的求解算法及應用領域一直是學者研究的重點。本文在研讀大量文獻的基礎上介紹了遺傳算法的研究現狀及其應用情況，并對車輛路徑優化在生鮮農產品配送上的應用進行了簡單的綜述。

關鍵詞：車輛路徑問題；遺傳算法；生鮮農場品；研究綜述

一、引言

車輛路徑問題最早在60年代被提出，Dantzig和Ramser首次在交通領域提出該問題就立即引起了社會的廣泛關注。發展到現如今，車輛路徑問題的應用已經跳出了交通領域，在別的很多領域被使用，如：通訊、工業管理、航空等。

二、遺傳算法

1.遺傳算法簡介

達爾文的生物進化論自被提出以來就一直被科學家們廣泛應用到各個領域。60年代時美國科學家結合進化論，提出了遺傳算法。跟大自然中生物優勝劣汰的進化過程類似，遺傳算法在計算過程中模擬了自然界各種群由簡單到復雜，由低級到高級的進化過程，不斷進化種群，直至使種群達到包含最優解或接近最優解的狀態。

2.遺傳算法研究現狀

遺傳算法作為一種群體隨機搜索方法，在車輛路徑問題研究中運用很多。很多國內外的研究學者對基礎的遺傳算法進行了改良，以期達到求解不同約束條件下車輛路徑優化問題的目的。通過研究撰寫遺傳算法的文獻發現，研究學者們分別用各種改進遺傳算法對車輛路徑問題進行了求解，如：免疫遺傳算法、小生境遺傳算法，以及遺傳算法與爬山算法、禁忌搜索算法、蟻群算法相結合的混合算法。

將基礎的遺傳算法與改進的遺傳算法進行對比仿真實驗，可以發現經過改良的遺傳算法，其各方面能力都更優。羅勇等為了求解更優的物流配送路線，就采用了針對性改進的遺傳算法。通過研究發現，改良后的算法不僅收斂速度變快，而且全方位尋優的能力也有很大提高。由此可見改進的遺傳算法是能更好的處理物流配送路徑問題。基礎的遺傳算法有容易陷入局部最優和早熟的缺點，為了解決這個問題，周艷聰等設計了基于小生境技術的改進遺傳算法，還在改進的遺傳算法的基礎上求解了物流配送路徑的優化問題。不僅如此，還通過對物流配送過程的研究，建立了不帶時間窗約束的物流配送優化模型。大規模車場的車輛路徑問題是車輛路徑優化問題中的一個難點，一直是學者們研究的重點。李波等引入了雙層模糊聚類方法，針對基礎的遺傳算法進行了改進，得到了求解該問題的基本框架。通過隨機的實驗算例證明，所提出的方法是有效可行的。

三、車輛路徑問題在生鮮農產品配送中的應用

對近年來，針對生鮮農產品配送路徑問題的研究已經越來越多，人們對綠色食品的質量要求不斷提高，是導致該問題備受關注的根本原因。容易腐爛變質，存放不易是大多數生鮮農產品的特點。而在整個銷售過程中，生鮮農產品需要經歷從農戶手中到經銷商手中這樣一個配送過程，盡可能在配送過程中選擇合適的路徑，節約時間，保證生鮮農產品的質量，從而保證農戶、經銷商、消費者的利益就變得越來越重要。

為了保證生鮮農產品的質量、安全，生鮮農產品配送過程中的時效性一直是各個學者研究的關注點，大多數相關文獻的模型建立都是以配送時間最短和配送成本最低為目標。王紅玲等學者的研究考慮了生鮮農產品的特點構建了以生鮮農產品在途時間最短、配送成本最低為優化目標的農產品配送模型，并采用經過改進后的粒子群算法進行求解。由于生鮮農產品的時效性強的特點，對帶時間窗的車輛路徑問題的研究也相當多。邱榮祖等在分析了農產品的物流配送模式的基礎上，建立了有時限的物流配送路徑優化模型，并應用GIS于禁忌搜索算法集成技術進行求解。文獻中還選用了具體的數據進行了實驗的驗證，進行了初步的應用研究。

生鮮農產品作為日常生活的必須品，在運輸的過程中需要考慮時效性和顧客的滿意度情況。顧客的滿意度是一個軟時間窗，可以應用模糊隸屬度函數來表示。邵舉平等考慮了生鮮農產品時效性強的特點，以顧客滿意度和配送總成本為目標，建立了路徑優化模型，選用符合研究問題的智能算法，并用改算法對算例進行驗證。生鮮農產品的配送大多具有三層配送網絡結構，為了提高在此網絡配送中的配送效率，曹倩等以成本最小和顧客滿意度最大為目標建立了數學模型，而且利用懲罰函數對模型進行約束，針對遺傳算法進行改進，并使用改進后的遺傳算法對模型進行求解。

除了考慮生鮮農產品的時效性特點以外，一些學者還從很多其他方面對其進行了研究。生鮮農產品的易腐特性就是學者們比較關注的而一個點。呂俊杰等針對生鮮農產品在冷鏈物流中配送的問題進行了研究。該研究是站在物流配送商的角度，考慮冷鏈配送車輛的成本，建立了物流配送車輛的路徑優化模型，采用MATLAB工具和啟發式算法對算例進行驗證，驗證的結果說明考慮冷鏈配送車輛成本的路徑模型能找到更優的配送路徑。除了易腐性以外，生鮮農產品還具有市場需求的模糊不確定性、時變性。朱佳翔等考慮了農產品的這些性質，以“最早出發”與“多供應點選擇”為目標建立了優化模型。還以現實案例進行了模型的驗證分析，結果表明所建立的生鮮農產品配送模型具有可行性和科學性。食品安全問題是人們關注的焦點，針對這個問題張瑜等從生鮮食品物流配送模式出發，以上海聯華超市股份有限公司為例，根據聯華超市現有的生鮮食品物流配送模式，分析其問題，從供應鏈角度提出優化模式及實施建議。

四、總結

通過對上述車輛路徑問題的研究，本文得出以下幾點總結：（1）國內外對于車輛路徑問題的研究比較多，但是對于動態車輛路徑問題的研究仍屬于起步階段。求解車輛路徑問題單單使用一種算法不容易得出最優解，可以考慮多種算法想結合的方式求解問題。（2）針對動態車輛路徑問題的研究，雖然已有很多文獻考慮了時變網絡下車輛速度等因素的變化，但大多數沒有結合實際交通路網，盡管引入了實時路線更新的概念，但未考慮車輛在行駛過程中經過的每條路段和每個路網節點。（3）生鮮農產品運輸的車輛路徑研究大多是在靜態網絡的狀態下進行的，可見，目前對生鮮農產品運輸的車輛路徑問題研究主要局限在靜態網絡中，時變網絡條件下的VRP研究比較少。針對上述情況，結合實際的城市配送體系，本文認為可以研究生鮮農產品在時變網絡條件下的車輛運輸路徑問題。

參考文獻：

[1]Dantzig G B. Ramser J H. The truck dispatching problem[J]. Management science， 1959， 6（1）： 80-91.

[2]羅勇，陳治亞.基于改進遺傳算法的物流配送路徑優化[J].系統工程，2012，08：118-122.

[3]周艷聰，孫曉晨，余偉翔.基于改進遺傳算法的物流配送路徑優化研究[J].計算機工程與科學，2012，10：118-122.

[4]李波，邱紅艷.基于雙層模糊聚類的多車場車輛路徑遺傳算法[J].計算機工程與應用，2014，05：261-264+270.

[5]王紅玲，鄭綱，何劍鋒.基于改進粒子群算法的生鮮農產品配送路徑優化研究[J].安徽農業科學，2010，（31）.

[6]邱榮祖，鐘聰兒，修曉虎.基于GIS和禁忌搜索集成技術的農產品物流配送路徑優化[J].數學的實踐與認識，2011，（10）.

[7]邵舉平，曹倩，沈敏燕，孫延安.生鮮農產品配送中帶時窗的VRP模型與算法[J].工業工程與管理，2015，01：122-127+134.

[8]曹倩，邵舉平，孫延安.基于改進遺傳算法的生鮮農產品多目標配送路徑優化[J].工業工程，2015，01：71-76.

[9]呂俊杰，孫雙雙.基于鮮活農產品冷鏈物流配送的車輛路徑優化研究[J].廣東農業科學，2013，09：178-181.

[10]朱佳翔，江濤濤，蔡建飛，田剛，毛良虎.考慮市場時變需求的生鮮農產品配送模糊多目標決策研究[J].軟科學，2015，11：135-139.

[11]張瑜，陳華艷.生鮮食品物流配送模式的問題及優化研究--以上海聯華超市股份有限公司為例[J].中國商論，2015，11：81-84.