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

羅慶+周軍

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

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

中圖分類號： TP301.6；F252.14文獻標志碼： A文章編號：1002-1302（2017）12-0174-04

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

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

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

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

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

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

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

根據(jù)以上假設得如下模型[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輛，但是在做配送計劃時，可以按照區(qū)域分解為1輛汽車的配送路徑，再將每輛汽車的最優(yōu)配送路徑按區(qū)域匯總，即可獲得整個物流中心配送的方案。因此，為方便配送路徑的優(yōu)化，本研究主要針對單輛汽車的配送路徑進行優(yōu)化。

2遺傳算法概述

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

2.1染色體編碼

對于路徑優(yōu)化的遺傳算法一般采用的是自然數(shù)編碼[6-7]，實際操作時可以隨機生成1組<1的小數(shù)，例如采用隨機生成函數(shù)產(chǎn)生10個小于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]，再對染色體里的各個基因從小到大或者從大到小進行排列，獲取其在數(shù)組中的位置數(shù)值體，例如上個染色體的信息就變?yōu)閇6，1，7，4，9，5，8，3，10，2]，筆者可以將數(shù)組中的基因個體看作配送點，正好對應10個配送點，可以非常清晰地得到1組解，即1個染色體[8]。

假設用3輛車對10個配送點進行配送，則可以將上述染色體加上4個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適應度函數(shù)

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

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

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

2.3交叉算子

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

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

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

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

2.4變異算子

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

C=123|4567|89C1=127452389。

2.5進化結束

判斷迭代次數(shù)達到預設的代數(shù)時，進化結束；否則，將迭代次數(shù)加1繼續(xù)迭代。

2.6算法步驟

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

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

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

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

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

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

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

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

3改進的遺傳算法

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

若變量xi∈[uv]，則：

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

式中：L為變量xi對應串的長度；gij為第i個變量xi的第j個基因，與n個變量x1→xn相對應的基因串giL構成了1個長串gnL…gnlgn-1L…gn-1l…glL…gll，染色體長度為n·L，按照個體適應度生成m個小生境，在進化過程中，采用評價種群早熟的新指標α，根據(jù)以下公式實現(xiàn)自適應調整[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。

可以看出，在進化過程中交叉變異參數(shù)會動態(tài)地進行調整，當種群個體有離散趨勢時，α變大，則Pc增大，Pm減小；反之，種群個體增強時，α變小，則Pc減小，Pm增大。endprint

4模擬退火操作

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

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

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

5仿真驗證與性能分析

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

5.1改進遺傳算法比較

根據(jù)表2所示參數(shù)，種群大小為100個，迭代次數(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。

利用改進后的遺傳算法所得最優(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次左右，而改進的遺傳算法迭代到80次左右，說明采用基于局部競爭機制的選擇小生境技術和自適應調節(jié)交叉變異參數(shù)方法相結合的遺傳算法進化過程比一般遺傳算法的進化速度要快170次，而最終的路徑優(yōu)化也比一般遺傳算法的要減少32 km配送距離。

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

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

在加入模擬退火后的改進遺傳算法基礎上得到的最優(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。總路程為184 km，減少配送距離 6 km。從圖7可以看出，其迭代次數(shù)為35次，比改進的遺傳算法減少45次，比普通遺傳算法減少215次，大大提高了收斂速度。

6結論

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

參考文獻：

[1]梅家斌. 遺傳算法在神經(jīng)網(wǎng)絡權值優(yōu)化中的應用[J]. 武漢科技學院學報，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]閻慶，鮑遠律. 新型遺傳模擬退火算法求解物流配送路徑問題[J]. 計算機應用，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)工程理論與實踐，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)化問題中的應用[J]. 中國公路學報，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]劉巖. 帶同時取貨和送貨的車輛路徑優(yōu)化問題研究[D]. 北京：北京交通大學，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]唐坤.車輛路徑問題中的遺傳算法設計[J]. 東華大學學報（自然科學版），2002，28（1）：66-70.

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

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