基于混合遺傳算法的農(nóng)產(chǎn)品物流配送路徑優(yōu)化

羅慶+周軍

摘要：農(nóng)業(yè)生產(chǎn)及農(nóng)業(yè)生產(chǎn)資料供應(yīng)和農(nóng)產(chǎn)品的合理配送，除了應(yīng)選擇合適的運(yùn)輸方式外，還要確定合理的配送路線和貨物的運(yùn)輸量，對(duì)于不同的運(yùn)輸條件、組織方法，車輛可以按照不同的配送路線完成農(nóng)產(chǎn)品及其相關(guān)生產(chǎn)資料的配送任務(wù)。在構(gòu)建了農(nóng)產(chǎn)品及其生產(chǎn)資料的物流配送路徑優(yōu)化數(shù)學(xué)模型的基礎(chǔ)上，提出了基于局部競(jìng)爭(zhēng)機(jī)制的選擇小生境技術(shù)和自適應(yīng)調(diào)節(jié)交叉變異參數(shù)方法提高全局收斂性能，然后將帶有記憶功能的模擬退火算法與上述改進(jìn)遺傳算法相結(jié)合，以提高局部搜索能力，從而構(gòu)造出一種新的混合遺傳算法。經(jīng)過計(jì)算證明，這種混合算法可以在很大程度上解決上述問題，并得到最優(yōu)解或者近似最優(yōu)解。

關(guān)鍵詞：農(nóng)業(yè)生產(chǎn)；混合遺傳算法；小生境技術(shù)；模擬退火算法；路徑優(yōu)化；農(nóng)產(chǎn)品物流配送路線；最短路徑；實(shí)例驗(yàn)證

中圖分類號(hào)： TP301.6；F252.14文獻(xiàn)標(biāo)志碼： A文章編號(hào)：1002-1302（2017）12-0174-04

農(nóng)產(chǎn)品物流要求高，一是由于農(nóng)產(chǎn)品與工業(yè)品不同，它是有生命的動(dòng)物性與植物性產(chǎn)品，所以，農(nóng)產(chǎn)品的物流特別要求“綠色物流”，在物流過程中做到不污染、不變質(zhì)；二是由于農(nóng)產(chǎn)品價(jià)格較低，一定要做到低成本運(yùn)行；三是農(nóng)產(chǎn)品流通涉及到保證與提高農(nóng)民的收入。因此，農(nóng)業(yè)現(xiàn)代生產(chǎn)和消費(fèi)是靠物流運(yùn)輸業(yè)的發(fā)展來實(shí)現(xiàn)的，高效、廉價(jià)的農(nóng)業(yè)物流配送系統(tǒng)能促使市場(chǎng)競(jìng)爭(zhēng)加劇，帶來生產(chǎn)經(jīng)營(yíng)中更多的規(guī)模經(jīng)濟(jì)效益及產(chǎn)品價(jià)格的下降。而農(nóng)產(chǎn)品運(yùn)輸成本在物流總成本中所占比例非常大，是成本消耗最大的物流活動(dòng)，約占物流總成本的1/3～2/3。在通常情況下，單位農(nóng)產(chǎn)品的物流運(yùn)輸成本與運(yùn)輸距離成正比，故農(nóng)產(chǎn)品配送路線的選擇會(huì)直接影響運(yùn)輸成本的大小，在農(nóng)產(chǎn)品配送的過程中盡量避免同一貨物在同一路線上的往返，即對(duì)流現(xiàn)象的發(fā)生，同時(shí)也要防止運(yùn)輸迂回的出現(xiàn)。

由于在組織車輛完成農(nóng)產(chǎn)品配送任務(wù)時(shí)，通常會(huì)存在多種可以選擇的配送路線方案，而車輛按不同的運(yùn)輸路線完成同樣的運(yùn)輸任務(wù)時(shí)，其利用效果是不一樣的。因此，在滿足農(nóng)產(chǎn)品配送任務(wù)要求的前提下，要選擇最經(jīng)濟(jì)的配送線路。所謂最經(jīng)濟(jì)的配送路線，就是在保證配送安全、滿足配送服務(wù)要求的前提下，運(yùn)輸時(shí)間、運(yùn)輸費(fèi)用最省的路線。由于在一般情況下車輛的行駛時(shí)間和運(yùn)輸費(fèi)用均與配送路程成正比，因此在忽略車輛行駛速度、不同道路條件下車輛運(yùn)行費(fèi)用差別的前提下，可以認(rèn)為配送路徑最短的路線是最經(jīng)濟(jì)的物流配送線路。

在物流領(lǐng)域中，物流配送的路徑優(yōu)化實(shí)際上是一個(gè)多項(xiàng)式復(fù)雜程度的非確定性（NP）問題，傳統(tǒng)的算法在解決這類問題時(shí)特別是在配送節(jié)點(diǎn)較多的情況下，求解的結(jié)果在滿意程度上存在一定的不足。而遺傳算法作為仿生智能方法，是一種較為有效的全局搜索算法，且具有運(yùn)算簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn)，可以獲得物流配送路徑的近似最優(yōu)解或滿意解[1-2]，但是由于遺傳算法的局部搜索能力不強(qiáng)，最終獲取的解的質(zhì)量并不是很高。為此本研究嘗試結(jié)合多種算法來彌補(bǔ)遺傳算法在這方面的不足，最后給出了實(shí)例驗(yàn)證和性能分析，用以證明混合遺傳算法的可行性。

1物流配送路徑優(yōu)化數(shù)學(xué)模型的建立

物流配送路徑是指各送貨車輛向各個(gè)用戶送貨時(shí)所要經(jīng)過的線路，配送路徑合理與否對(duì)運(yùn)輸速度、車輛的合理利用和運(yùn)輸費(fèi)用都有直接的影響。因此，采用科學(xué)合理的方法來確定配送路徑，是物流管理中非常重要的工作。配送路徑的優(yōu)化目標(biāo)可以是多種選擇的，如果成本與路程相關(guān)性較強(qiáng)，而與其他因素的相關(guān)性較弱時(shí)，可以選擇以路程最短為目標(biāo)。本研究假設(shè)只有1個(gè)農(nóng)產(chǎn)品配送中心，多輛汽車向多個(gè)農(nóng)產(chǎn)品配送點(diǎn)送貨，每個(gè)配送點(diǎn)的坐標(biāo)和配送量一定，每輛配送車的載質(zhì)量也是一定的，要求合理安排配送車輛的運(yùn)行路線，使總運(yùn)輸線路距離最短，根據(jù)長(zhǎng)期實(shí)際工作經(jīng)驗(yàn)為實(shí)現(xiàn)滿意的運(yùn)行路線作出以下設(shè)計(jì)：

（1）將相互接近的農(nóng)產(chǎn)品配送點(diǎn)的貨物裝載在1輛配送車上，且配送路徑上的配送點(diǎn)需要量之和不能大于配送車輛的載質(zhì)量；（2）配送路線從離農(nóng)產(chǎn)品配送中心最遠(yuǎn)的停留點(diǎn)開始，一旦確認(rèn)了最遠(yuǎn)的停留點(diǎn)之后，配送車輛應(yīng)一并載上與這個(gè)關(guān)鍵停留點(diǎn)相鄰的其他配送點(diǎn)的貨物，因此要求配送路徑不能超過配送車輛的最大行駛距離；（3）每個(gè)農(nóng)產(chǎn)品配送點(diǎn)原則上只能由1輛配送車輛配送，且滿足配送點(diǎn)的需求。

假設(shè)農(nóng)產(chǎn)品配送中心有m輛汽車，每輛汽車的載質(zhì)量為qi（i=1，2，…，m），最大行駛距離為Dm，向N個(gè)配送點(diǎn)配送，每個(gè)配送點(diǎn)需要貨物量為Qi（i=1，2，…，N），且Qi

根據(jù)以上假設(shè)得如下模型[3-5]：

minZ=∑Ni=0∑Nj=0∑Ml=0cijdijl；（1）

受約束于：

h=<∑Qi/aq>；（2）

∑Ni=0Qiyil≤qil=1，2，…，h；（3）

∑hl=0yil=1，i=1，2，…，N

h，i=0；（4）

∑Ni=0dijl=yjl，j=1，2，…，N，l=1，2，…，h；（5）

∑Nj=1dijl=yjl，i=1，2，…，N，l=1，2，…，h。（6）

式（2）中：h為所需車輛數(shù)，輛；<>為上型取整；a為系數(shù)，0

由于物流配送的車輛不止1輛，但是在做配送計(jì)劃時(shí)，可以按照區(qū)域分解為1輛汽車的配送路徑，再將每輛汽車的最優(yōu)配送路徑按區(qū)域匯總，即可獲得整個(gè)物流中心配送的方案。因此，為方便配送路徑的優(yōu)化，本研究主要針對(duì)單輛汽車的配送路徑進(jìn)行優(yōu)化。

2遺傳算法概述

遺傳算法由美國(guó)Michigan大學(xué)Holland教授提出，按照“優(yōu)勝劣汰，適者生存”的原則對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化，其本質(zhì)是一種高效、并行的全局搜索的方法。

2.1染色體編碼

對(duì)于路徑優(yōu)化的遺傳算法一般采用的是自然數(shù)編碼[6-7]，實(shí)際操作時(shí)可以隨機(jī)生成1組<1的小數(shù)，例如采用隨機(jī)生成函數(shù)產(chǎn)生10個(gè)小于1的1組染色體：

[0.156 5，0.977 6，0.953 2，0.486 4，0.805 3，0.142 2，0423 3，0.912 2，0.792 5，0.957 8]，再對(duì)染色體里的各個(gè)基因從小到大或者從大到小進(jìn)行排列，獲取其在數(shù)組中的位置數(shù)值體，例如上個(gè)染色體的信息就變?yōu)閇6，1，7，4，9，5，8，3，10，2]，筆者可以將數(shù)組中的基因個(gè)體看作配送點(diǎn)，正好對(duì)應(yīng)10個(gè)配送點(diǎn)，可以非常清晰地得到1組解，即1個(gè)染色體[8]。

假設(shè)用3輛車對(duì)10個(gè)配送點(diǎn)進(jìn)行配送，則可以將上述染色體加上4個(gè)0作為本研究的路徑配送方案，0代表的是物流配送中心。例如染色體為[0，6，1，7，0，4，9，5，0，8，3，10，2，0]表示的配送路徑方案：路徑1，0—6—1—7—0；路徑2，0—4—9—5—0；路徑3，0—8—3—10—2—0。共3條配送路徑。

2.2適應(yīng)度函數(shù)

在本研究中路徑優(yōu)化目標(biāo)是配送路徑成本最小值，因此將運(yùn)輸成本作為本研究的目標(biāo)，結(jié)合考慮式（3）的約束條件作為運(yùn)輸成本的一部分，即[9]：

Z=∑Ni=0∑Nj=0∑Ml=0cijdijl+H∑hlmax（∑Ni=0Qiyil-qt，0）。（7）

當(dāng)配送點(diǎn)的需求量大于配送車輛的最大載質(zhì)量時(shí)，H作為懲罰系數(shù)，應(yīng)趨于無窮大，使式（7）成本Z趨于無窮大，表示無解。為了方便計(jì)算，本研究設(shè)H=2 000 000，再將種群中的個(gè)體按照從小到大的順序排列，最后進(jìn)入選擇操作。

2.3交叉算子

將“2.2”節(jié)中的種群按照最佳保留和一定概率進(jìn)行保留相結(jié)合產(chǎn)生新的種群，種群中個(gè)體被選中的概率：

ps=b（1-b）u-11-（1-q）T。（8）

式中：b為系數(shù)范圍≥0～≤0.15；u為第s個(gè)個(gè)體的排序序號(hào)；T為種群大小。

本研究對(duì)種群中的個(gè)體交叉采用隨機(jī)交叉方式。例如假設(shè)有10個(gè)配送點(diǎn)，有2個(gè)染色體，其中A為0123045607890，B為0987065403210。先將物流配送中心0去掉，A′=123456789，B′=987654321；再隨機(jī)產(chǎn)生交叉位置，將父代中間部分放在對(duì)方的前面，如果有重復(fù)的基因，則刪除本身重復(fù)的數(shù)字，從而產(chǎn)生2個(gè)新的染色體[10-11]。例如選擇第3位、第7位為交叉點(diǎn)A″=123|4567|89，B″=987|6543|21，修正后，A=6543|123456789，B=4567|987654321；去掉后面相同的數(shù)字得到，A=654312789，B=456798321；最終在原有位置重新加載4個(gè)0，即最后得到A=06543031207890，B=0456079803210。由此看出，此辦法在父代相同的情況下，仍可以產(chǎn)生新的子代。

2.4變異算子

為了保持種群的多樣性，避免過早陷入早熟，可以按照一定概率（一般為0～0.001）進(jìn)行變異操作，實(shí)際上是隨意交換個(gè)體中的2個(gè)位置，得到新的染色體C1，具體如下：

C=123|4567|89C1=127452389。

2.5進(jìn)化結(jié)束

判斷迭代次數(shù)達(dá)到預(yù)設(shè)的代數(shù)時(shí)，進(jìn)化結(jié)束；否則，將迭代次數(shù)加1繼續(xù)迭代。

2.6算法步驟

步驟1：輸入配送點(diǎn)的位置數(shù)據(jù)，設(shè)置種群規(guī)模和迭代次數(shù)G；

步驟2：生成配送點(diǎn)之間的距離二維矩陣dm×n；

步驟3：隨機(jī)生成n個(gè)染色體，分別為C1{s1′s2′s3′s4′s5′…sn′} 、C2{s1″s2″s3″s4″s5″…sn″}、C3{s1s2s3s4s5…sn}。計(jì)算各個(gè)染色體的適應(yīng)度值，再將染色體按照適應(yīng)度值降序排列[8-9]，此時(shí)迭代次數(shù)為0；

步驟4：根據(jù)交叉概率進(jìn)行交叉操作；

步驟5：根據(jù)變異概率進(jìn)行隨機(jī)變異操作；

步驟6：將新一代種群按照適應(yīng)度值進(jìn)行升序排序，再選取n個(gè)最優(yōu)個(gè)體組成下一代種群；

步驟7：判斷迭代次數(shù)是否達(dá)到G，否則迭代次數(shù)加1，轉(zhuǎn)到步驟4；

步驟8：計(jì)算結(jié)束，得到最優(yōu)解。

3改進(jìn)的遺傳算法

針對(duì)早熟收斂現(xiàn)象，采用基于局部競(jìng)爭(zhēng)選擇的小生境技術(shù)，通過自適應(yīng)調(diào)節(jié)交叉變異參數(shù)，將具有共同特性的基因個(gè)體進(jìn)行交叉，避免了交叉隨機(jī)性。小生境技術(shù)就是將每代個(gè)體劃分為若干類，從每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為1個(gè)類的優(yōu)秀代表，從而組成1個(gè)群[12]，其中選擇二進(jìn)制編碼策略如下：

若變量xi∈[uv]，則：

xi=ai+（bi-ai）·∑Lj≠1（gij·2i）/（2L+1-1）。

式中：L為變量xi對(duì)應(yīng)串的長(zhǎng)度；gij為第i個(gè)變量xi的第j個(gè)基因，與n個(gè)變量x1→xn相對(duì)應(yīng)的基因串giL構(gòu)成了1個(gè)長(zhǎng)串gnL…gnlgn-1L…gn-1l…glL…gll，染色體長(zhǎng)度為n·L，按照個(gè)體適應(yīng)度生成m個(gè)小生境，在進(jìn)化過程中，采用評(píng)價(jià)種群早熟的新指標(biāo)α，根據(jù)以下公式實(shí)現(xiàn)自適應(yīng)調(diào)整[13]：

Pc=11+exp（-k1·α）；（9）

Pm=11+exp（-k2·α）+1.0。（10）

式中：k1、k2>0，由于α始終≥0，故Pc的取值范圍為0.5～10，Pm的取值范圍為0～0.5。

可以看出，在進(jìn)化過程中交叉變異參數(shù)會(huì)動(dòng)態(tài)地進(jìn)行調(diào)整，當(dāng)種群個(gè)體有離散趨勢(shì)時(shí)，α變大，則Pc增大，Pm減??；反之，種群個(gè)體增強(qiáng)時(shí)，α變小，則Pc減小，Pm增大。endprint

4模擬退火操作

為了利于遺傳模擬退火混合算法的實(shí)現(xiàn)，本研究提出將帶有記憶功能的模擬退火算法置于遺傳算法中，作為1個(gè)獨(dú)立的算子，對(duì)遺傳算法經(jīng)過選擇、交叉、變異等步驟產(chǎn)生的新染色體進(jìn)行模擬退火操作，并記住算法中的最優(yōu)解，同時(shí)，將遺傳算法的迭代次數(shù)作為模擬退火算法的退火時(shí)間。交叉、變異得到新的種群后，在新的種群中每個(gè)染色體i的鄰域中隨機(jī)挑選1個(gè)染色體模擬退火的概率：

Aij（te）=min1，exp-fj（te）-fi（te）te。（11）

根據(jù)模擬退火的概率接受或者拒絕j，其中fj（te）、fi（te）分別為個(gè)體i、j的目標(biāo)函數(shù)值。對(duì)得到的種群計(jì)算目標(biāo)函數(shù)值，找出最小函數(shù)值minfi（te）和它對(duì)應(yīng)的最優(yōu)解f*。

5仿真驗(yàn)證與性能分析

本研究假設(shè)有30個(gè)農(nóng)產(chǎn)品配送點(diǎn)需要配送，配送點(diǎn)坐標(biāo)如圖1、表1所示。配送中心坐標(biāo)為（0，0）。對(duì)普通遺傳算法、改進(jìn)遺傳算法都取迭代次數(shù)為300次，種群大小為100個(gè)，按其普通遺傳算法交叉概率與變異概率（表2）進(jìn)行試驗(yàn)。

5.1改進(jìn)遺傳算法比較

根據(jù)表2所示參數(shù)，種群大小為100個(gè)，迭代次數(shù)為300

利用普通遺傳算法所得最優(yōu)路徑為0—22—21—23—20—28—29—30—28—26—18—13—11—10—12—8—14—

15—16—17—24—25—19—9—1—3—7—6—0，總路程為222 km。

利用改進(jìn)后的遺傳算法所得最優(yōu)路徑為0—2—8—14—19—25—27—20—13—7—4—5—6—16—17—15—18—24—26—28—29—30—23—21—22—11—12—10—9—3—1—0，總路程為190 km。

通過圖4、圖5可以看出算法迭代的過程，普通的遺傳算法一直迭代到250次左右，而改進(jìn)的遺傳算法迭代到80次左右，說明采用基于局部競(jìng)爭(zhēng)機(jī)制的選擇小生境技術(shù)和自適應(yīng)調(diào)節(jié)交叉變異參數(shù)方法相結(jié)合的遺傳算法進(jìn)化過程比一般遺傳算法的進(jìn)化速度要快170次，而最終的路徑優(yōu)化也比一般遺傳算法的要減少32 km配送距離。

5.2模擬退火的混合遺傳算法比較

在基于局部競(jìng)爭(zhēng)機(jī)制的選擇小生境技術(shù)和自適應(yīng)調(diào)節(jié)交叉變異參數(shù)方法相結(jié)合的遺傳算法上，加入模擬退火算法進(jìn)行仿真，初始溫度為10 ℃，衰減系數(shù)為0.8，得到配送路徑如圖6所示。

在加入模擬退火后的改進(jìn)遺傳算法基礎(chǔ)上得到的最優(yōu)路徑為0—9—10—11—22—21—23—20—27—29—30—28—

26—24—25—19—12—8—7—13—14—15—18—17—16—

6—5—2—4—3—1—0?？偮烦虨?84 km，減少配送距離 6 km。從圖7可以看出，其迭代次數(shù)為35次，比改進(jìn)的遺傳算法減少45次，比普通遺傳算法減少215次，大大提高了收斂速度。

6結(jié)論

本研究提出了在基于局部競(jìng)爭(zhēng)機(jī)制的選擇小生境技術(shù)和自適應(yīng)調(diào)節(jié)交叉變異參數(shù)方法相結(jié)合的改進(jìn)遺傳算法上，加入模擬退火算法用于優(yōu)化農(nóng)產(chǎn)品物流配送路徑，并從組合優(yōu)化的角度對(duì)農(nóng)產(chǎn)品物流路徑優(yōu)化問題提出解決方案，減少了搜索時(shí)間，提高了解空間質(zhì)量，使混合算法的功效得到了極大提高。

參考文獻(xiàn)：

[1]梅家斌. 遺傳算法在神經(jīng)網(wǎng)絡(luò)權(quán)值優(yōu)化中的應(yīng)用[J]. 武漢科技學(xué)院學(xué)報(bào)，2001，14（3）：23-25.

[2]Ghoseiri K，Nadjari B. An ant colony optimaztion algorithm for the bi-objective shortest path problem[J]. Applied Soft Computing，2010，10（4）： 1237-1246.

[3]閻慶，鮑遠(yuǎn)律. 新型遺傳模擬退火算法求解物流配送路徑問題[J]. 計(jì)算機(jī)應(yīng)用，2004，24（增刊1）：261-263.

[4]Pijls W，Post H. A new bidirectional search algorithm with shortened postprocessing[J]. European Journal of Operational Research，2009，198（2）： 363-369.

[5]姜大立，楊西龍，杜文，等.車輛路徑問題的遺傳算法研究[J]. 系統(tǒng)工程理論與實(shí)踐，1999，19（6）：40-45.

[6]Amir G S，Ali N M，Saeed P，et al. Application of genetic algorithmfor solving multi-objective optimization problems in robust control of distillation column[J]. International Journal of Advancements in Computing Technology，2011，3（1）： 32-43.

[7]張波，葉家瑋，胡郁蔥. 模擬退火算法在路徑優(yōu)化問題中的應(yīng)用[J]. 中國(guó)公路學(xué)報(bào)，2004，17（1）：79-81.

[8]Funke B，Grünert T，Irnich S. Local search for vehicle routing and scheduling problems： review and conceptual integration[J]. Journal of Heuristics，2005，11（4）： 267-306.

[9]劉巖. 帶同時(shí)取貨和送貨的車輛路徑優(yōu)化問題研究[D]. 北京：北京交通大學(xué)，2009：15-17.

[10]Montemanni R，Gambardella L M，Rizzoli A E，et al. Ant colony system for a dynamic vehicle routing problem[J]. Journal of Combinatorial Optimization，2005（4）： 327-343.

[11]唐坤.車輛路徑問題中的遺傳算法設(shè)計(jì)[J]. 東華大學(xué)學(xué)報(bào)（自然科學(xué)版），2002，28（1）：66-70.

[12]林焰，郝聚民，紀(jì)卓尚，等. 隔離小生境遺傳算法研究[J]. 系統(tǒng)工程學(xué)報(bào)，2000，15（1）：86-91.

[13]孫建永，申建中，徐宗本. 一類自適應(yīng)遺傳算法[J]. 西安交通大學(xué)學(xué)報(bào)，2000，34（10）：84-88.朱振偉，張開飛，李赫，等. 玉米秸稈力學(xué)特性的研究[J]. 江蘇農(nóng)業(yè)科學(xué)，2017，45（12）：178-181.endprint