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

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

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

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

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

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

1 VRP問題一般描述

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

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

VRP問題需滿足以下條件：

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

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

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

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

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

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

定義變量：

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

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

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

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

4 時間窗問題

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

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

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

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

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

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

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

5 EXCEL遺傳算法工具箱

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

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

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

遺傳算法的另一個關(guān)鍵特征是突變。如同生物學(xué)中的基因突變一樣，evolutionary solver有時對群體中的成員進行隨機的改變。例如，一個可變單元格的數(shù)值可能會被一個新的隨機值取代。這種突變可以創(chuàng)造與其余群體無關(guān)的后代。這是非常重要的，因為它可以幫助算法在局部最優(yōu)值附近受到困擾時擺脫困擾。

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

6 案例驗證

6.1 案例背景

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

6.2 案例求解

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

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

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

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

由此得到的模型不是線性的，因為index函數(shù)用來計算距離和alldifferent約束。但是，evolutionary solver可以用來找到一個好的路徑。利用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。其中在運用遺傳算法求解時個參數(shù)的設(shè)置如圖6-3所示。

圖6-2 顯示alldifferent約束的add constraint對話框

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

Max time（最長運行時間）：100秒；

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

Precision （精度）： 1e-006；

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

Convergence （收斂值）： 0.0001；

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

Mutation Rate （突變率）： 0.075；

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

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

7 總 結(jié)

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

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

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

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

[3]劉誠，陳治亞，封全喜.帶軟時間窗物流配送車輛路徑問題的并行遺傳算法[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-），男，上海人，上海瀟翔國際物流有限公司，工程師，碩士，研究方向：國際物流和供應(yīng)鏈。