車輛路徑問題研究綜述

吳姝雨

摘 要：作為現(xiàn)代物流領(lǐng)域的研究前沿，車輛路徑問題的求解算法及應(yīng)用領(lǐng)域一直是學(xué)者研究的重點。本文在研讀大量文獻(xiàn)的基礎(chǔ)上介紹了遺傳算法的研究現(xiàn)狀及其應(yīng)用情況，并對車輛路徑優(yōu)化在生鮮農(nóng)產(chǎn)品配送上的應(yīng)用進(jìn)行了簡單的綜述。

關(guān)鍵詞：車輛路徑問題；遺傳算法；生鮮農(nóng)場品；研究綜述

一、引言

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

二、遺傳算法

1.遺傳算法簡介

達(dá)爾文的生物進(jìn)化論自被提出以來就一直被科學(xué)家們廣泛應(yīng)用到各個領(lǐng)域。60年代時美國科學(xué)家結(jié)合進(jìn)化論，提出了遺傳算法。跟大自然中生物優(yōu)勝劣汰的進(jìn)化過程類似，遺傳算法在計算過程中模擬了自然界各種群由簡單到復(fù)雜，由低級到高級的進(jìn)化過程，不斷進(jìn)化種群，直至使種群達(dá)到包含最優(yōu)解或接近最優(yōu)解的狀態(tài)。

2.遺傳算法研究現(xiàn)狀

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

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

三、車輛路徑問題在生鮮農(nóng)產(chǎn)品配送中的應(yīng)用

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

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

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

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

四、總結(jié)

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

參考文獻(xiàn)：

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

[2]羅勇，陳治亞.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化[J].系統(tǒng)工程，2012，08：118-122.

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

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

[5]王紅玲，鄭綱，何劍鋒.基于改進(jìn)粒子群算法的生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化研究[J].安徽農(nóng)業(yè)科學(xué)，2010，（31）.

[6]邱榮祖，鐘聰兒，修曉虎.基于GIS和禁忌搜索集成技術(shù)的農(nóng)產(chǎn)品物流配送路徑優(yōu)化[J].數(shù)學(xué)的實踐與認(rèn)識，2011，（10）.

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

[8]曹倩，邵舉平，孫延安.基于改進(jìn)遺傳算法的生鮮農(nóng)產(chǎn)品多目標(biāo)配送路徑優(yōu)化[J].工業(yè)工程，2015，01：71-76.

[9]呂俊杰，孫雙雙.基于鮮活農(nóng)產(chǎn)品冷鏈物流配送的車輛路徑優(yōu)化研究[J].廣東農(nóng)業(yè)科學(xué)，2013，09：178-181.

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

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