基于遺傳算法的生鮮農產品物流配送路徑聚類優化

王有鴻

(運城學院經濟管理系，山西運城 044000)

隨著國民經濟的飛速發展，國內居民的生活品質不斷提升，當前國內居民的膳食模式逐步由過去的溫飽型向營養養生型轉換。膳食模式是衡量國家和區域居民生活水準的重要指標，且對增強各年齡段人們的身體素質具有重要意義。生鮮農產品存在季節特征、地域特征和易腐敗特征，這些特征給貯藏、運輸、銷售帶來了挑戰，并易于引發淡季食品供給不足、商品單調，旺季食品物流輸送不順暢等狀況。為改變生鮮農產品的供需狀況，須要最大化地滿足居民對新鮮食物的需求。

目前我國的農業物流配送存在諸多問題，如配送渠道雜亂，配送過程開銷大、時間長，且很多生鮮農產品配送企業往往采用傳統的經營與輸送方式，農產品物流輸送效率低，運輸過程消耗大，無法與當前的市場需求相適應。因而采用先進的科學技術組織生鮮農產品配送、規范車輛配送路徑具有重要意義。對生鮮農產品企業來說，改進配送線路可提升配送效率，減少運輸開銷，并可迅速將農產品配送到顧客手中，提升顧客滿意度，且能夠節約配送車輛數目，緩和交通情況，保證生態平衡。車輛路徑問題(vehicle routing problem，簡稱VRP)[1]對于生鮮農產品能否被準確運送具有重要作用，好的配送模式對于生產效率的提升具有重要意義，國內外研究者針對生鮮農產品的配送進行了大量解析和調研。Christiansen等對車輛路徑狀況進行了專門探索[2]；Santini等選取人工神經網絡模式來實現車輛路徑優化[3]；Paraskevopoulos等給出5種模式的車輛路徑優化策略，分別為帶時間約束的VRP模式、帶能力限定的VRP模式、多配送核心的VRP模式、分批次配送的VRP模式以及開放性的VRP模式[4]；李軍針對有時間窗的車輛路徑優化狀況提出一種利用旅行商問題的 C-W 算法來安排路線的啟發式算法，并得到較好的效果[5]；郭森等把使用者分配在相同的車輛中，進而選取一種基于動態學習和突變因子的粒子群算法實現車輛分配，最后依照現有需要實現仿真測試[6]；殷亞等依照路徑優化特性，利用遺傳算法特點，構建出3種混合蝙蝠算法，能提升優化效能[7]。

國內外科研人員針對車輛配送路徑的研究較多，但結合生鮮農產品提升農業物流效率的研究較少。本研究探討基于遺傳算法的生鮮農產品物流配送路徑的聚類優化，以期實現高效和低成本物流。

1 生鮮農產品配送線路優化模型設立

1.1 生鮮農產品配送的車輛路徑問題結構模型

車輛路徑問題即針對各個需求配送點選取科學的車輛運輸線路，從生鮮農產品配送核心起始，有序地通過需求配送點，并最終返回配送核心，其中貨物的需求狀況、車輛的限定、運行里程的限定以及時間限定等須達到相應的標準，如里程最小、開銷最少、采用的車輛數目最少等。圖1給出傳統配送VRP模型。

1.2 帶時間窗口的車輛路徑模式

在VRP的基礎上加入時間窗體限定，即將VRP拓展為有時間窗車輛路徑問題(vehicle routing problems with time windows，簡稱VRPTW)。依據用戶的滿意程度可將時間窗體劃分為硬時間窗體和軟時間窗體[8]。

硬時間窗體即生鮮農產品配送車輛應在給定時間段內把配送物品運送至使用者所在地，如果使用者拒絕接受時間段之外的相關服務，則擬定相應的懲罰函數，若配送生鮮農產品在指定的時間內超出懲罰值，則超出硬時間窗體限定(圖2)。

在硬時間窗體運輸路徑模式的配送過程中，生鮮運輸車應當在恰當的時間點內達到配送點，若生鮮運輸車在最早服務時間之前或最晚服務時間之后到達使用者所在地點，則會出現整體生產模式的延遲與空置，出現時間開銷大而效率低的狀況，并產生很大的懲罰值。

軟時間窗體指配送車輛若不能把生鮮農產品在給定的時間內運達，則應對相應環節進行處罰[9](圖3)。與硬時間窗體的車輛路徑問題(vehicle routing problem with hard time window，簡稱VRPHTW)相比，軟時間的路徑窗體路徑問題放棄了時間窗體限定，在現實中，由于路面交通流量、車輛的運轉速度和使用者需要時間等不確定原因使得車間存儲的生鮮農產品沒有在給定的時間內到達使用者所在地，若采用硬時間窗體限定模式優化，則使開銷增大。

本研究結合數學建模方法對生鮮農產品物流配送路徑進行優化設計，采用生鮮運輸車完成生鮮農產品配送核心與幾個配送點之間的n個運輸動作，假定現有生鮮運輸車的容量為Q，生鮮運輸車的固有車輛成本為h(h>0)，各個配送點的需求量為qi，令qi小于Q，此外規定任務起始的執行時間區，整個任務的需求時間為si，路段(vi，vj)對應的時間成本、運輸時間分別為cij、tij。

時間窗體的設計準則是通過數學模型優化生鮮運輸車的行駛路線，且在給定時間內開始操作并完成輸送，從而使生鮮農產品派送的花銷較少。

(1)

qi≤yipi≤Q,i=1,…,n；

(2)

tij+cij≤si。

(3)

式中：若選取特定路線(vi，vj)，則權值xij為1，否則為0；lj表示配送核心到車間距離；pi表示生鮮運輸車的數量；yi表示生鮮運輸車離開車間的運載量。

2 生鮮農產品物流配送路徑遺傳算法聚類優化設計

2.1 生鮮農產品物流配送路徑遺傳算法

遺傳算法[10]的優勢在于其中的群體搜索功能能夠使種群中的各個個體之間進行數據傳送，其模擬策略主要是由個體構建的群體學習策略，并且把與每個個體相關的研究狀況形成解。該算法的步驟為：(1)對染色體進行編碼，構建符合約束標準的染色體，進而獲取相關初始種群并測算種群中各個染色體的適應模式，適應模式主要反饋染色體的優劣狀況，遺傳算法能夠獲取適應度較強的染色體；(2)對染色體進行選擇，完成交叉和變異，并采用相關基準算子得到下一代種群；(3)重復步驟(1)、(2)直至達到終止條件。

遺傳算法同時檢索上一層的多個種群個體，并將初始染色體種群用作遺傳，從而構建初始化種群的起點。各個個體將1～n之間的自然數排列形成一個序列，本試驗采用初始化種群的模式獲取popsize模式的初始種群，其中n為各個生鮮農產品的需求網點數目，popsize為整個種群的規模。

圖4為一個賭局模型，整個賭局被分割為大小存在差別的扇面區域，指針能夠轉向各個區域，且指針停留在各區域的概率和各區域圓心角存在一定的比例，若圓心角較大則停留在該區域的概率較大，若圓心角較小則停留在該區域的概率也較小。

假設種群的規模為N，父輩種群Z={a1，a2，…，aN}，其中各個部分的適應程度為f，子群體的初始狀況為X={}，并且給定各個部分的具體操作模式：把全部個體依照適應程度從大到小進行排列，則排序之后的種群為Z={b1，b2，…，bN}，且f(b0)>f(b1)>f(b2)>…>f(bN)，基于該模式測算得到父輩種群模式的適應層級；計算種群中全部適應層級的總和，得到各個個體被選取的概率；累積各個個體的概率得到累積值，完成輪盤的轉動。

本研究依照VRPTW方式構建改進交叉方法的遺傳策略，其算法的基本策略見圖5。

2.2 生鮮農產品物流配送路徑遺傳算法聚類優化

若所需求的生鮮農產品量高于車輛單次運載的容量Q，則

(4)

式中：x為各個需求網點的生鮮農產品需求量。

測算步驟為：(1)設定初始循環次數為1，由于模糊聚類[11]陣列F為一個對稱陣列，本研究選取三角陣列實現測算，并得到簡化步驟；(2)針對模糊聚類陣列F，選最大部分進行循環，并將F設定為目標，進而給出三角陣列的測算實例(圖6)。

本研究綜合遺傳算法，并結合聚類方法，對簡化的VRPTW模式實現優化求取，其測算步驟為：(1)選取自然數編碼模式構建可行的生鮮農產品運輸線路染色體；(2)設定測控參量，其中設定交叉率為pc，變異狀況為pm，群體規模為N；將遺傳代數gen設定為0，即隨機獲取的初始種群p(0)中包含Num個染色體部分；(3)構建生鮮農產品運輸的行車線路；(4)設定i的初始值為1，測算種群中第i個染色體的線路距離和適應程度，若達到算法的終止標準則停止，否則繼續；(5)i進行自增加，若i小于n則返回步驟(2)，否則進行下個步驟；(6)依照使用層級復制下一代染色體，實現最大交叉保留狀況，并且交換變異模式，進行gen的自增加，若滿足終止標準則終止，否則轉至步驟(3)。

3 生鮮農產品物流配送路徑遺傳算法聚類優化和分析

3.1 實例設計

本研究假定須配送19個生鮮農產品需求配送點(圖7)，并將生鮮農產品配送核心的位置設置為(0，0)，圓圈表述各個需求配送點，編號間的距離表示網點之間的間隔距離。表1 為生鮮農產品需求配送點網點坐標以及需求數目，通過Matlab程序完成需求配送點在遺傳算法聚類優化下的仿真。

3.2 生鮮農產品運輸外部相似性測算

本研究進一步測算各需求配送點期待服務質量和生鮮農產品外部相似特點，并評判各需求配送點的期望服務質量和所運輸商品的外部相似特性。生鮮農產品運輸外部相似性見表2。

3.3 生鮮農產品物流配送聚類結果

聚類分類停止標準依照生鮮農產品關聯性質和各需求配送點的貨物運載狀況設置，此處設定權值為0.6，生鮮農產品運輸車的運載量為2 t，然后根據客戶需求完成聚類測算。M為懲罰值，Q為生鮮運輸車的容量。

從表3、表4可以看出，改變聚類方法的權重并結合Matlab實現編碼，能夠得到各種聚類結果，從而得到各種生鮮農產品的配送方式。

設定本研究中的遺傳算法參量最大進化代數為100，種群的大小為52，交叉率為0.92，變異率為0.81，軟時間窗體之下的待懲罰參量為2，延遲懲罰數據為3；在電腦上運行得到，最優配送間距為108 km，所采用的生鮮農產品運載工具數目最少為3輛，其所對應的最優化配送線路為路徑1：0—13—14—7—1—19—6—0；路徑2：0—7—15—8—2—25—6—0；路徑3：0—10—11—3—1—5—6—0。表5為生鮮農產品配送方法的聚類優化結果。

3.4 組內路徑求取結果

在整個算法中，遺傳算法給定的參量設定模式：種群規模(N)為100個，最大迭代次數(C)為200次，交叉率(pc)為 0.89，變異率(pm)為0.03，懲罰參量為3。

表1 生鮮農產品配送網點坐標以及需求數目

表2 生鮮農產品運輸外部相似性

表3 權重結果為W1狀況時的聚類值

表4 權重結果為W2狀況時的聚類值

本研究首先采用模糊聚類方法對客戶進行分類，即對需求配送點1～19進行分類，共分為5類，其中需求配送點7、10、8、9、19、17為一類，需求配送點2、12、6、5、3為一類，需求配送點10、15、16、5為一類，需求配送點18、4、11為一類，需求配送點13、1、14為一類，然后采用遺傳算法規劃生鮮農產品運輸線路。遺傳算法得到的結果為近似的最優結果，不是最優結果，但能夠通過選取多次執行代碼得到較好的近似最優值。由表6可知，5類需求配送點得到的最優線路模式分別為：0—7—10—8—9—19—17—0，目標解析式數據為 9.121 km；0—2—12—6—5—3—0，目標解析式數據為 8.983 km；0—10—15—16—5—0，目標解析式數據為 8.512 km；0—18—4—11—0，目標解析式數據為8.892 km；0—13—1—14—0，目標解析式數據為9.053 km。

表5 生鮮農產品配送方法的聚類優化結果

依照各個車間對應配送核心(0，0)的坐標方位，以需求配送點7、10、8、9、19、17獲取的最優線路模式0—7—10—8—9—19—17—0為例作圖。

圖8為遺傳算法經過198次迭代之后獲取的最優結果以及效能的追蹤結果。因此在現實的操作中，應當適當削減終止的最大迭代數目。

3.5 本研究方法性能測試

由表7可知，本研究中的5條最優生鮮農產品配送路線的配送間距分別為9.120、8.984、8.512、8.891、9.050 km，它們采用的平均生鮮農產品運載工具數目均為3輛，平均滿載率分別92.1%、93.1%、87.6%、91.1%、87.6%。

表6 實現一次運行的模式

表7 組內的最優線路

以需求配送點7、10、8、9、19、17組成的路徑0—7—10—8—9—19—17—0為例，對比分析本研究生鮮農產品配送方法和傳統生鮮農產品配送方法的結果。

由表8可見，本研究路徑0—7—10—8—9—19—17—0測算方法的結果，不論為11次求解的平均結果還是最優測算結果均優于傳統方法，本測算方法的最優間距為8.48 km，平均測算距離為 8.55 km，本方法選取的生鮮農產品運輸工具平均為3輛；而傳統方法的最優間距為10.3 km，平均測算距離為11.1 km，配送生鮮農產品的車輛恒定為4輛。此外，本方法能夠動態決定選取生鮮農產品運輸工具的數目，說明本方法具有優秀的特性，因而測算所得解的質量較高。

4 結論

在市場經濟的大環境下，生鮮農產品的競爭尤為激烈，而生鮮農產品物流的中心環節在于配送，當前生鮮農產品的物流配送過程繁雜，貨運種類和需求配送點多，交通路線復雜，在整個配送服務區域內所分布的配送網點不均衡。顧客對生鮮農產品的品質需求日益增加，而生鮮農產品配送企業仍采用以往的經營模式，使得農產品運輸效率低。因而科學地規劃輸送路線完成生鮮農產品配送已成為社會和相關企業關注的重點。

表8 本研究與傳統生鮮農產品配送方法的結果比較

本研究對生鮮農產品物流配送路徑進行優化設計，并給出生鮮農產品配送VRP模式和帶時間窗口的車輛路徑模式，進而完成生鮮農產品物流配送路徑遺傳算法聚類優化，給出生鮮農產品物流配送路徑遺傳算法步驟和聚類優化方法，即首先設定初始循環數目，并通過模糊聚類陣列給出對稱陣列，結合三角陣列測算得到簡化步驟；在模糊聚類陣列中，選最大部分完成循環，并采用Matlab完成生鮮農產品物流配送路徑遺傳算法聚類優化試驗設計。假定有19個生鮮農產品需求配送點應配送，通過生鮮農產品運輸外部相似性測算生鮮農產品物流配送聚類結果、組內路徑求取結果，并對本方法進行性能測試，結果表明，本方法明顯優于傳統配送方法。