基于改進遺傳算法的農(nóng)產(chǎn)品配送路徑優(yōu)化研究

周建國

[摘要]以第三方物流企業(yè)為視角，在保證配送質(zhì)量最高的情況下，將配送成本最低作為優(yōu)化目標，構(gòu)建多目標農(nóng)產(chǎn)品配送路徑優(yōu)化模型。針對此類NP問題，結(jié)合改進的遺傳算法，在Matlab2015環(huán)境下設計仿真實驗。結(jié)果表明，改進的遺傳算法在解決此類問題時，可行解能夠快速收斂到帕累托最優(yōu)，同時證明了模型和算法的科學性。

[關鍵詞]遺傳算法；農(nóng)產(chǎn)品物流；多目標優(yōu)化；VRP

[DOI]1013939/jcnkizgsc201801136

1引言

當前，我國農(nóng)產(chǎn)品流通過程中物流成本過高。一方面，在運輸過程中，由于農(nóng)產(chǎn)品自身的特點使得產(chǎn)品損失率較大，導致貨損成本過高；另一方面，由于農(nóng)產(chǎn)品呈現(xiàn)地域性特點，面對多網(wǎng)點的產(chǎn)地和銷售點，傳統(tǒng)的憑經(jīng)驗選擇配送路線顯得太不科學，造成了產(chǎn)品在途時間過長、迂回運輸?shù)痊F(xiàn)象?；谝陨媳尘?，文章以第三方物流企業(yè)為視角，在保證配送質(zhì)量最高的情況下，將配送成本最低作為優(yōu)化目標，構(gòu)建多目標農(nóng)產(chǎn)品配送路徑優(yōu)化模型。

文章研究的時間窗約束下的路徑優(yōu)化問題（VRP）屬于多目標優(yōu)化問題，對于這類問題很難用全局搜索法精確求解，目前解決這類問題大多數(shù)依靠啟發(fā)式算法。例如，遺傳算法、蟻群算法、粒子群算法、模擬退火算法等。[1]Feng Xu Li通過分析農(nóng)產(chǎn)品流通的現(xiàn)狀，提出一種軟時間窗約束下多類型車輛配送路徑優(yōu)化模型，創(chuàng)新性地考慮了在不同類型的車輛有不同的邊際和成本費用，通過遺傳算法解決；[2]王飛軍等人在分析農(nóng)產(chǎn)品配送車輛調(diào)度問題的基礎上，引入蟻群算法解決該問題。實驗證明，蟻群算法能夠快速收斂到帕累托最優(yōu)解，研究對于實現(xiàn)車輛合理調(diào)度、縮短運輸路程、降低運輸費用有較大意義。[3]張遜遜等人為了實現(xiàn)農(nóng)產(chǎn)品配送系統(tǒng)的節(jié)能減排，將碳排放量考慮到VRP問題中去，構(gòu)建碳排放量最低和最短路徑?jīng)Q策模型，提出了基于相似性選擇的演化算法，最后通過案例仿真驗證了所提出算法的科學性。[4]

2多目標VRP優(yōu)化問題數(shù)學模型構(gòu)建

21貨損成本

因為農(nóng)產(chǎn)品自身的特性，如易變質(zhì)性、地域性等特點，加上我國冷鏈不完善、溫度的波動以及流通環(huán)節(jié)中不專業(yè)操作等因素，從生產(chǎn)到銷售這段時間內(nèi)產(chǎn)生的貨損成本。

22物流滿意度

一般而言，將現(xiàn)實中貨物在途時間分為兩部分，第一部分是客戶期望收到貨物的時間，這段時間內(nèi)客戶的物流滿意度為100%；第二部分是客戶在可以接受的時間范圍內(nèi)接收貨物，假設在這段時間內(nèi)，客戶的物流滿意度與時間呈線性關系。

3VRP問題下改進的遺傳算法

GA主要依靠選擇、交叉、變異等遺傳算子實現(xiàn)種群的優(yōu)勝劣汰，對于二進制編碼的染色體而言，當種群不具多樣性，算法易陷入早熟、收斂；對于十進制編碼的染色體，面對組合優(yōu)化問題時，不能在任意基因位交叉染色體，交叉會使得新產(chǎn)生的染色體不是優(yōu)化問題的解。PGA的遺傳操作僅在兩條染色體上進行“交叉”為主，在一條染色體上進行變異操作為輔，即通過單個個體繁殖后代，所以稱為單親遺傳算法。PGA的選擇算子功能和GA無異；不同的是，PGA利用基因重組算子實現(xiàn)了GA的交叉和變異功能。

31基因換位操作[5]

GA主要通過交叉算子實現(xiàn)整個種群的迭代，但使用序數(shù)編碼時候個別問題不能進行交叉操作，必須使用PMX、OX和CX等特殊的交叉算子。這些特殊的交叉算子操作復雜，并且執(zhí)行效率不高。所以此處借助另一種遺傳算子實現(xiàn)種群的更迭—基因換位算子。PGA的基因換位算子是按一定概率p隨機交換染色體中基因位的過程?；驌Q位可以分為單點換位和多點換位，單點換位一次只交換一對基因位；多點換位是對于預先給定的正整數(shù)u，取隨機數(shù)i（1≤i≤u），一次交換i對基因位。當u取3，i取2，PGA的多點換位操作如下：

R=2 5 8 7 4 1 3 6 9

R′=2 7 8 5 4 9 3 6 1

32編碼及解碼方案

本文采用十進制編碼，0表示配送中心，1，2，3…表示目的地。首先，隨機產(chǎn)生一組排列。假設有9個目的地，隨機產(chǎn)生326481957的排列，具體編碼思路如下：

（1）從左向右依次累計目的地的需求量，一旦累計需求量超過貨車的載重量就停止計數(shù)，設經(jīng)過n次累計之后累積量超過貨車的載重，記錄此時的斷點1為n-1，累積量清零。

（2）從排列的第n位開始繼續(xù)重復第一步，假設再次超過貨車載重量時，此時的累計次數(shù)為m，記錄斷點2為n+m-1， 累積量清零。

（3）重復上述步驟直至排列的最后一位，生成斷點矩陣。

（4）依據(jù)斷點矩陣，在排列對應基因位和首末位加上0，編碼完成。

33適應度函數(shù)[6]

適應度函數(shù)（ft）用于評價解集中的個體對于目標函數(shù)的優(yōu)劣性，通常根據(jù)實際問題需要設定。在適應度函數(shù)的設計方面，常采用將目標函數(shù)映射成適應度函數(shù)的方法。本文選取（ft）=1/（Zmin+V·q）。V表示懲罰系數(shù)。

34算法流程

Step 1：確定編碼方案，將待優(yōu)化問題的潛在解表示成染色體。

Step 2：確定控制參數(shù)以及適應度函數(shù)。

Step 3：隨機產(chǎn)生初始種群。

Step 4：計算種群中個體的適應度值和遺傳概率。

Step 5：依據(jù)優(yōu)勝劣汰規(guī)則，保留適應值較大的個體，淘汰適應值低的個體。

Step 6：依據(jù)選擇概率復制最能適應環(huán)境的染色體，代替適應值較低的個體，保持種群規(guī)模基數(shù)不變。

Step 7：依據(jù)交叉概率和變異概率對種群重復Step 6。

Step 8：若滿足終止條件，輸出結(jié)果。若不滿足重復步驟Step 5～Step 7。

4案例仿真及結(jié)果分析endprint

41案例描述

現(xiàn)某第三方物流企業(yè)計劃從配送中心，坐標（00），向16個目的地配送農(nóng)產(chǎn)品，配送采用單一型號的貨車運輸，汽車裝載量為55噸，平均車速60km/h，車輛損失的機會成本為每小時15元，延遲費用80元。每天最早出發(fā)時間為6：00。單位路程運費率15，產(chǎn)品單位價值80，損失系數(shù)005。各網(wǎng)點的具體信息見上表。在Matlab2015程序下進行數(shù)值仿真，采用以下參數(shù)，選擇概率pc=015，改進遺傳算法的最大基因換位次數(shù)為6，初始種群個數(shù)20。

42結(jié)果分析

根據(jù)上述改進的遺傳算法編寫C語言程序，在Matlab2015環(huán)境下對該數(shù)學模型進行300次迭代尋優(yōu)。在第110代左右時候?qū)さ门晾弁凶顑?yōu)解。最終配送系統(tǒng)總成本2414575，目的地平均物流滿意度為804%。仿真求得6條使配送總成本最低的路徑（車輛從配送中心出發(fā)，完成對各個目的地的配送之后返回配送中心的過程），分別為，路徑一：0-15-14-4-0；路徑二：0-2-1-0；路徑三：0-16-6-8-0：路徑四：0-10-7-3-0；路徑五：0-9-13-11-5-0；路徑六：0-12-0。適應度函數(shù)變化趨勢見下圖，具體配送方案及時間見表2。

可行解的適應值隨迭代次數(shù)的進化過程

從種群的進化趨勢來看，適應度函數(shù)值從30代左右開始逐漸變大，種群中個體對于環(huán)境的適應性能力越來越強，每經(jīng)過一段時間種群的更迭，解集越接近帕累托最優(yōu)。從適應度的變化可知，曲線多處垂直上升，整體收斂速度較快。在經(jīng)過110次迭代之后，曲線變化趨于平緩，最終找到帕累托最優(yōu)解，證明了改進的遺傳算法良好的尋優(yōu)性能。

5結(jié)論

本文通過探討農(nóng)產(chǎn)品流通環(huán)節(jié)中的廣義物流成本，結(jié)合實際情況，采用單一的對農(nóng)產(chǎn)品配送路徑優(yōu)化從而控制流通成本，將農(nóng)產(chǎn)品在途時間作為評價第三方物流滿意度的標準，建立數(shù)學模型。針對多目標優(yōu)化問題，考慮到模型求解的復雜性，利用改進之后的遺傳算法在Matlab環(huán)境下對目標函數(shù)進行迭代尋優(yōu)。通過案例證明模型的科學性，同時從適應度函數(shù)的變化趨勢圖證明了算法的可行性。該研究能夠滿足一定階段下農(nóng)產(chǎn)品運輸中的路徑?jīng)Q策問題，對于降低流通成本具有較大意義。另外，本文的配送系統(tǒng)只考慮單一型號的車輛，有且只有一個配送中心問題，對于多種農(nóng)產(chǎn)品混合運輸問題沒有涉及，這都是今后需要研究的方向。

參考文獻：

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

[2]Feng Xu Li，Yue Fang Yang，F(xiàn)ei Wei，F(xiàn)eng WeiStudy on Multi-Vehicle Refrigerated Distribution of Agricultural Products with Soft Time Windows[J].Applied Mechanics and Materials，2013，2733（438）.

[3]王飛軍，呂建新，楊建偉基于蟻群算法的農(nóng)產(chǎn)品配送車輛調(diào)度問題研究[J].中國農(nóng)機化學報，2014（1）.

[4]張遜遜，許宏科，于加晴融合PM25排放量和運輸路程的區(qū)域農(nóng)產(chǎn)品配送路徑?jīng)Q策[J].長安大學學報：自然科學版，2017，37（2）：99-106

[5]李茂軍，童調(diào)生，羅隆福單親遺傳算法及其應用研究[J].湖南大學學報，1998（6）.

[6]雷英杰，張善文，李續(xù)武MATLAB遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社，2008endprint