周建國(guó)

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

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

[DOI]1013939/jcnkizgsc201801136

1引言

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

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

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

21貨損成本

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

22物流滿意度

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

3VRP問題下改進(jìn)的遺傳算法

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

31基因換位操作[5]

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

R=2 5 8 7 4 1 3 6 9

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

32編碼及解碼方案

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

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

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

（3）重復(fù)上述步驟直至排列的最后一位，生成斷點(diǎn)矩陣。

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

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

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

34算法流程

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

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

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

Step 4：計(jì)算種群中個(gè)體的適應(yīng)度值和遺傳概率。

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

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

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

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

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

41案例描述

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

42結(jié)果分析

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

可行解的適應(yīng)值隨迭代次數(shù)的進(jìn)化過程

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

5結(jié)論

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

參考文獻(xiàn)：

[1]羅勇，陳治亞基于改進(jìn)遺傳算法的物流配送路徑優(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].中國(guó)農(nóng)機(jī)化學(xué)報(bào)，2014（1）.

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

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

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