錢 華 （上海瀟翔國(guó)際物流有限公司，上海 200090）

基于遺傳算法的農(nóng)產(chǎn)品物流車輛路徑問題決策研究

錢 華 （上海瀟翔國(guó)際物流有限公司，上海 200090）

我國(guó)農(nóng)產(chǎn)品物流成本較高的主要原因之一是缺乏科學(xué)的管理技術(shù)，尤其是基于定量分析的決策技術(shù)。對(duì)物流車輛路徑問題的優(yōu)化可以有效降低農(nóng)產(chǎn)品的物流成本。針對(duì)農(nóng)產(chǎn)品的時(shí)效性，對(duì)帶有時(shí)間窗的農(nóng)產(chǎn)品物流車輛路徑問題，引入客戶滿意度函數(shù)，建立實(shí)例決策模型，運(yùn)用遺傳算法工具箱進(jìn)行優(yōu)化求解。通過對(duì)優(yōu)化前后的數(shù)據(jù)進(jìn)行比較，驗(yàn)證決策模型的可行性和合理性。

農(nóng)產(chǎn)品物流；時(shí)間窗；車輛路徑問題；遺傳算法

1 VRP問題一般描述

車輛路徑問題 （Vehicle Routing Problem,VRP）是運(yùn)籌學(xué)與物流管理決策的一個(gè)重要問題。目前，一般意義上的物流，指物流中心按照不同客戶多頻度、小批量的訂貨要求進(jìn)行組織物流、其中主要內(nèi)容是根據(jù)確定的貨物量進(jìn)行車輛的分配和物流路線的生成，即廣受研究的車輛路徑問題，如圖1-1所示。

由于從事農(nóng)產(chǎn)品物流物流的汽車貨運(yùn)工作尤其是從事城市果蔬物流的汽車貨運(yùn)工作條件復(fù)雜，不僅貨運(yùn)點(diǎn)多、貨物種類繁多、道路網(wǎng)復(fù)雜、服務(wù)地區(qū)網(wǎng)點(diǎn)分布不均勻，最重要的是果蔬農(nóng)產(chǎn)品物流有一個(gè)嚴(yán)格的時(shí)間限制。因此，如何應(yīng)用計(jì)算機(jī)快速求解路線優(yōu)化方案是國(guó)內(nèi)外專家學(xué)者普遍探索的重要課題。

VRP問題需滿足以下條件：

（1）每條物流路徑上各客戶的需求量之和不超過貨車的最大載重量。

（2）每條物流路徑的長(zhǎng)度不超過貨車一次物流的最大行程。

（3）每個(gè)滿足每個(gè)客戶要求 （如時(shí)間要求），且只能由一輛貨車送貨。

（4）每輛貨車均從物流中心出發(fā)，完成任務(wù)后又全部返回物流中心。

2 VRP問題的一般數(shù)學(xué)模型

設(shè)物流中心為1個(gè)，貨車編號(hào)為k，客戶編號(hào)為1,2,…l，考慮車輛載重量約束、數(shù)量數(shù)目約束、時(shí)間約束等，可定義如下的基本數(shù)學(xué)模型：

定義變量：

目標(biāo)函數(shù)及約束條件：

3 VRP問題的分類及求解方法

VRP問題根據(jù)有無時(shí)間要求分為有時(shí)間窗VRP問題（TWVRP）和無時(shí)間窗 VRP問題。對(duì)有時(shí)間窗VRP的求解算法如圖3-1所示。

本文主要研究現(xiàn)代啟發(fā)式算法中的遺傳算法，其適合客戶達(dá)到一定數(shù)目時(shí)，并加入了時(shí)間因素和客戶滿意度等多目標(biāo)問題決策。

4 時(shí)間窗問題

農(nóng)產(chǎn)品如水果和蔬菜的保鮮時(shí)間各不相同，若每家門店對(duì)送貨時(shí)間有要求，則物流企業(yè)必須在規(guī)定的時(shí)間段內(nèi)將農(nóng)產(chǎn)品送貨上門，這就是帶有時(shí)間窗的VRP問題。

時(shí)間窗問題可以用不等式eTi≤ti≤lTi表示，eTi表示物流任務(wù)最早時(shí)間，lTi為物流任務(wù)最晚時(shí)間，ti為某物流任務(wù)需要的物流時(shí)間。時(shí)間窗限制可分為可調(diào)劑時(shí)間窗和不可調(diào)劑時(shí)間窗?？烧{(diào)劑時(shí)間窗表示如果貨車沒有按時(shí)送貨，則必須支付罰款；不可調(diào)劑時(shí)間窗表示每個(gè)物流任務(wù)必須在規(guī)定的一個(gè)時(shí)間段內(nèi)送到門店，無論早晚都完全被接受。很明顯，不可調(diào)劑的時(shí)間窗所產(chǎn)生了懲罰成本要大于可調(diào)劑的時(shí)間窗，且只有后者才有可行解。

由此產(chǎn)生客戶滿意度函數(shù) （CS Val），果蔬農(nóng)產(chǎn)品要在其有限的保鮮期限內(nèi)及時(shí)銷售，就必須做到及時(shí)物流，盡量縮短上架前流通時(shí)間。物流企業(yè)要實(shí)現(xiàn)農(nóng)產(chǎn)品利潤(rùn)最大化，就必須考慮農(nóng)產(chǎn)品的時(shí)間成本。這些成本包括由于延遲交貨而產(chǎn)生的罰款和最佳銷售時(shí)段的機(jī)會(huì)成本損失。我們可以用下圖4-1表示實(shí)際客戶滿意隨物流時(shí)間的長(zhǎng)短而變化。

工業(yè)品物流往往以降低總物流送成本或縮短物流時(shí)間為目標(biāo)，而沒有考慮將客戶滿意度和VRP問題的模型相互結(jié)合，使它成為可以1個(gè)約束變量。農(nóng)產(chǎn)品物流更注重客戶的滿意度，客戶滿意度可以通過如下時(shí)間函數(shù)表示：

如上例，當(dāng)貨車XY（第1類4噸車第1輛）在完成門店J的物流任務(wù)后駛向門店A時(shí)，如到達(dá)A的時(shí)間太早，那么貨車XY必須在A門店處等待，如圖4-2所示。

貨車XY在A門店的等待時(shí)間表示為：

式中：tij表示物流車輛從顧客i到顧客j的行使時(shí)間；uti為物流車輛在顧客i處的卸貨時(shí)間；wi（ti）表示當(dāng)顧客i的開始時(shí)間為ti時(shí)，物流車輛在顧客i處的等待時(shí)間。

5 EXCEL遺傳算法工具箱

利用EXCEL加載Evolutionary Solver，其基本原理是根據(jù)遺傳學(xué)、進(jìn)化論和適者生存原理建立的。EXCEL標(biāo)準(zhǔn)Solver是從單獨(dú)一個(gè)解 （初始點(diǎn)）開始，朝著優(yōu)化解的方向移動(dòng)。對(duì)所有點(diǎn)來說，標(biāo)準(zhǔn)solver只追蹤一個(gè)唯一的解 （目前為止找到的最好的解）。相反，evolutionary solver從隨機(jī)產(chǎn)生大量候選解開始，這些候選解被稱為 “群體”。在求解過程中，evolutionary solver追蹤候選解的整體群體。

在生成了群體之后，evolutionary solver接著對(duì)群體創(chuàng)造了新的一代。存在的候選解群體結(jié)對(duì)創(chuàng)造先下一代的子孫。借鑒遺傳學(xué)的原理，這些子孫后代結(jié)合了每對(duì)父母的一些因子。例如，一個(gè)后代可能兼有父母一方的一些可變單元格和另一方的一些值，而其他可變單元格可能只是在父母雙方之間均分。

在任何一代的解的群體中，有些解是好的 （或合適的），有些是不好的 （或不合適的）。我們通過計(jì)算群體中得候選解的目標(biāo)函數(shù)來確定解的適應(yīng)度。對(duì)那些不滿足一個(gè)或多個(gè)約束條件的解的懲罰就是將它們排除在外。接著，借鑒進(jìn)化論和適者生存的原理，群體中 “合適”的成員被允許頻繁地繁殖 （創(chuàng)造許多后代），而 “不適合”的成員不允許繁殖。如此下去，群體最終將變得越來越合適。

遺傳算法的另一個(gè)關(guān)鍵特征是突變。如同生物學(xué)中的基因突變一樣，evolutionary solver有時(shí)對(duì)群體中的成員進(jìn)行隨機(jī)的改變。例如，一個(gè)可變單元格的數(shù)值可能會(huì)被一個(gè)新的隨機(jī)值取代。這種突變可以創(chuàng)造與其余群體無關(guān)的后代。這是非常重要的，因?yàn)樗梢詭椭惴ㄔ诰植孔顑?yōu)值附近受到困擾時(shí)擺脫困擾。

Evolutionary solver不斷創(chuàng)造新一代的解，直到連續(xù)幾代都沒有改進(jìn)。然后算法就結(jié)束了，并報(bào)告目前為止找到的最佳解。

6 案例驗(yàn)證

6.1 案例背景

上海世紀(jì)聯(lián)華生鮮物流中心為全市13家主要門店物流農(nóng)產(chǎn)品。物流中心和13家門店實(shí)際地理位置如圖6-1所示。物流中心要在一天內(nèi)用一輛滿載的貨車將果蔬物流到各家門店，然后車輛返回物流中心，車輛出發(fā)點(diǎn)和返回點(diǎn)都是物流中心。我們將要物流的門店按字母順序列出，每家門店都標(biāo)上一個(gè)數(shù)字 （1～13之間的一個(gè)整數(shù)）和一個(gè)中文簡(jiǎn)稱，如表6-1中的B6：C18單元格和E3：Q4單元格所示。數(shù)據(jù)單元格是各點(diǎn)之間的物流距離 （D5：Q18），給出了每一家門店之間的物流距離。需要制定的決策是車輛返回到物流中心前均物流過每家門店。因此，相應(yīng)的可變單元格route（D22：P22）顯示出物流各階段物流的不同門店 （通過其數(shù)字標(biāo)號(hào)引用）。換句話說，在物流中心之后第一家門店的數(shù)字標(biāo)號(hào)將在單元格D22中顯示出來，第二家門店將在單元格E22中顯示出來，一次類推。表6-1所示的電子表格模型顯示了按字母順序物流各個(gè)門店的路徑。這條物流路線的總長(zhǎng)度為190公里。

6.2 案例求解

第23行顯示了根據(jù)第22行中各門店的數(shù)字編碼給出的中文簡(jiǎn)稱，使用了EXCEL的INDEX函數(shù)。第24行利用INDEX函數(shù)查詢出了物流路線中每個(gè)門店與前一個(gè)門店之間的距離。目標(biāo)單元格Total Miles Traveled（Q26）將路線中總物流距離加總一起。

圖6-1 上海世紀(jì)聯(lián)華生鮮物流網(wǎng)絡(luò)地理圖

表6-1 世紀(jì)華聯(lián)物流電子表格模型

由于各家門店只需要物流一次，這一模型中的一個(gè)約束條件是所有的可變單元格都必須是1～13中的一個(gè)整數(shù)，不能重復(fù)。這一約束條件很難利用標(biāo)準(zhǔn)的solver來實(shí)現(xiàn)。幸運(yùn)的是，premium solver包含了一個(gè)新的約束類型，成為alldifferent，它能滿足我們的要求。當(dāng)n個(gè)可變單元格選擇1～n的整數(shù)時(shí)，將這些可變單元格限制為alldifferent將迫使它們的取值為1～n之間整數(shù)且不重復(fù)。為了利用premium solver實(shí)現(xiàn)alldifferent這一約束條件，在solver中選擇add按鈕，彈出add constraint對(duì)話框。在對(duì)話框的左邊選擇可變單元格route（物流路線），在對(duì)話框中間的下拉菜單中選擇dif，如圖6-2所示。

由此得到的模型不是線性的，因?yàn)閕ndex函數(shù)用來計(jì)算距離和alldifferent約束。但是，evolutionary solver可以用來找到一個(gè)好的路徑。利用evolutionary solver求解后，得到的解顯示在表6-2中的D22：P22單元格和D23：P23單元格中。這條路徑比表6-1所示的路徑改善了很多，總物流距離為91公里，比原先190公里節(jié)約了99公里。物流優(yōu)化路線為物流中心→門店8→門店4→門店6→門店5→門店13→門店3→門店9→門店2→門店11→門店7→門店12→門店1→門店10。其中在運(yùn)用遺傳算法求解時(shí)個(gè)參數(shù)的設(shè)置如圖6-3所示。

圖6-2 顯示alldifferent約束的add constraint對(duì)話框

表6-2 世紀(jì)聯(lián)華物流路線優(yōu)化決策電子表格模型

Max time（最長(zhǎng)運(yùn)行時(shí)間）：100秒；

Interations （迭代次數(shù)）： 1000；

Precision （精度）： 1e-006；

圖6-3 遺傳算法參數(shù)設(shè)置

Convergence （收斂值）： 0.0001；

Population Size（種群數(shù)）：100;

Mutation Rate （突變率）： 0.075；

在 “變量的要求范圍”選項(xiàng)選中。這就將所有的可變單元格限制在上限和下限之間。這將大大縮小evolutionary solver需要搜索的范圍，并增加找到最優(yōu)解的機(jī)會(huì)。

在 “evolutionary solver”選項(xiàng)對(duì)話框中點(diǎn)擊 “限制” （limit）選項(xiàng)卡。這個(gè)對(duì)話框?qū)螘r(shí)終止搜索提供了額外的控制。在“最大子問題”、 “最大可行安全操作限制”中輸入較大的數(shù)值，可以使搜索持續(xù)很長(zhǎng)時(shí)間。 “偏差”為0.05， “最大無改善時(shí)間”為30，意味著evolutionary solver將繼續(xù)搜素直到在最后30秒內(nèi)解的改善不超過5%。減少 “偏差”，或增加 “最大無改善時(shí)間”通常會(huì)使搜索時(shí)間變得更長(zhǎng)。

7 總 結(jié)

本文主要研究了現(xiàn)代遺傳算法在解決帶時(shí)間窗的農(nóng)產(chǎn)品物流車輛路徑問題決策中的應(yīng)用，并結(jié)合了EXCEL遺傳算法工具箱，實(shí)現(xiàn)決策過程自動(dòng)化。在求解復(fù)雜的非線性規(guī)劃問題時(shí)，evolutionary solver顯示了兩個(gè)重要的優(yōu)點(diǎn)：第一，目標(biāo)函數(shù)的復(fù)雜性不會(huì)影響evolutionary solver。只要函數(shù)可以根據(jù)給定的候選解進(jìn)行計(jì)算 （為了確定適合的水平），那么函數(shù)是否有折點(diǎn)或者不連續(xù)或者許多局部最優(yōu)值都沒有關(guān)系。第二，通過計(jì)算不一定與當(dāng)前最優(yōu)解在同一領(lǐng)域內(nèi)的所有候選解群體，evolutionary solver不會(huì)受困于一個(gè)局部最優(yōu)值。另外，即使整個(gè)群體最終向只是局部最優(yōu)的解前進(jìn)，突變?nèi)匀豢梢员苊馑阉鞅焕г谝稽c(diǎn)上。事實(shí)上，由于隨機(jī)突變的存在，如果一直運(yùn)行下去，那么Evolutionaty Solver就可以保證找到任何一個(gè)最優(yōu)化問題的最優(yōu)解。但是，這當(dāng)然是不切實(shí)際的。

另一方面，我們必須指出，Evolutionaty Solver不是萬能的。首先，為了找到最優(yōu)解，計(jì)算花費(fèi)的時(shí)間要長(zhǎng)。選擇了某些限制性選項(xiàng)后，搜尋更優(yōu)解的過程可能會(huì)持續(xù)幾個(gè)小時(shí)甚至幾天。其次，Evolutionaty Solver對(duì)于有許多約束條件的模型的效果不是很好。例如，對(duì)于線性規(guī)劃問題的許多模型，標(biāo)準(zhǔn)Solver能夠即刻進(jìn)行求解，但evolutionary solver運(yùn)行通常會(huì)產(chǎn)生一個(gè)不同的最終解。最后，找到的最佳解不是最優(yōu)的 （雖然它可能非常接近最優(yōu)值）。Evolutionary solver作為最優(yōu)化工具的意義與標(biāo)準(zhǔn)solver是一個(gè)聰明的搜索引擎，嘗試不同的隨機(jī)解。它很可能在一個(gè)非常接近最優(yōu)值的解處結(jié)束，對(duì)于非線性規(guī)劃問題的大部分類型它幾乎不可能獲得精確的最優(yōu)解。因此，在evolutionary solver之后再運(yùn)行標(biāo)準(zhǔn)solver（GRG非線性）是有幫助的，從evolutionary solver找到的最優(yōu)解開始，通過在該解的領(lǐng)域內(nèi)進(jìn)行搜索，能改善這個(gè)解。

[1]李大衛(wèi)，王莉，王夢(mèng)光.遺傳算法在有時(shí)間窗車輛路徑問題上的應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐，1999(8)：32-33.

[2]汪祖柱，程家興，方宏兵,等.車輛路徑問題的混合優(yōu)化算法[J].運(yùn)籌與管理，2004(6)：42-43.

[3]劉誠(chéng)，陳治亞，封全喜.帶軟時(shí)間窗物流配送車輛路徑問題的并行遺傳算法[J].系統(tǒng)工程，2005(10)：13-14.

Research for the VRP in Agricultural Products Based on Genetic Algorithm

QIAN Hua(Shanghai Xiaoxiang International Logistics Company,Shanghai 200090,China)

One of the main reasons that cause the high cost of China agricultural products logistics is lacking of scientific technology of management,especially the decision making tech based on data analysis.One of the approaches can reduce the cost of agricultural products logistics is the optimizing vehicle route problem.The time windows VRP in agricultural products can be solved by bringing the function of customers satisfaction to the decision making model based on the company case and getting the result with the toolkits of genetic algorithm.To certifying the feasibility and reasonability of the DM model with the comparison the results.

agricultural products logistics;time windows;VRP;genetic algorithm

F506

A

1002-3100(2012)09-0106-05

2012-07-31

錢 華（1976-），男，上海人，上海瀟翔國(guó)際物流有限公司，工程師，碩士，研究方向：國(guó)際物流和供應(yīng)鏈。