吳姝雨

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

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

一、引言

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

二、遺傳算法

1.遺傳算法簡(jiǎn)介

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

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

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

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

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

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

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

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

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

四、總結(jié)

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

[4]李波，邱紅艷.基于雙層模糊聚類的多車場(chǎng)車輛路徑遺傳算法[J].計(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é)的實(shí)踐與認(rèn)識(shí)，2011，（10）.

[7]邵舉平，曹倩，沈敏燕，孫延安.生鮮農(nóng)產(chǎn)品配送中帶時(shí)窗的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]朱佳翔，江濤濤，蔡建飛，田剛，毛良虎.考慮市場(chǎng)時(shí)變需求的生鮮農(nóng)產(chǎn)品配送模糊多目標(biāo)決策研究[J].軟科學(xué)，2015，11：135-139.

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