基于遺傳算法的農產品物流車輛路徑問題決策研究

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

基于遺傳算法的農產品物流車輛路徑問題決策研究

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

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

農產品物流；時間窗；車輛路徑問題；遺傳算法

1 VRP問題一般描述

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

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

VRP問題需滿足以下條件：

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

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

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

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

2 VRP問題的一般數學模型

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

定義變量：

目標函數及約束條件：

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

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

本文主要研究現代啟發式算法中的遺傳算法，其適合客戶達到一定數目時，并加入了時間因素和客戶滿意度等多目標問題決策。

4 時間窗問題

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

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

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

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

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

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

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

5 EXCEL遺傳算法工具箱

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

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

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

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

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

6 案例驗證

6.1 案例背景

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

6.2 案例求解

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

圖6-1 上海世紀聯華生鮮物流網絡地理圖

表6-1 世紀華聯物流電子表格模型

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

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

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

表6-2 世紀聯華物流路線優化決策電子表格模型

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

Interations （迭代次數）： 1000；

Precision （精度）： 1e-006；

圖6-3 遺傳算法參數設置

Convergence （收斂值）： 0.0001；

Population Size（種群數）：100;

Mutation Rate （突變率）： 0.075；

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

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

7 總 結

本文主要研究了現代遺傳算法在解決帶時間窗的農產品物流車輛路徑問題決策中的應用，并結合了EXCEL遺傳算法工具箱，實現決策過程自動化。在求解復雜的非線性規劃問題時，evolutionary solver顯示了兩個重要的優點：第一，目標函數的復雜性不會影響evolutionary solver。只要函數可以根據給定的候選解進行計算 （為了確定適合的水平），那么函數是否有折點或者不連續或者許多局部最優值都沒有關系。第二，通過計算不一定與當前最優解在同一領域內的所有候選解群體，evolutionary solver不會受困于一個局部最優值。另外，即使整個群體最終向只是局部最優的解前進，突變仍然可以避免搜索被困在一點上。事實上，由于隨機突變的存在，如果一直運行下去，那么Evolutionaty Solver就可以保證找到任何一個最優化問題的最優解。但是，這當然是不切實際的。

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

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

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

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