王有鴻

(運(yùn)城學(xué)院經(jīng)濟(jì)管理系，山西運(yùn)城 044000)

隨著國(guó)民經(jīng)濟(jì)的飛速發(fā)展，國(guó)內(nèi)居民的生活品質(zhì)不斷提升，當(dāng)前國(guó)內(nèi)居民的膳食模式逐步由過去的溫飽型向營(yíng)養(yǎng)養(yǎng)生型轉(zhuǎn)換。膳食模式是衡量國(guó)家和區(qū)域居民生活水準(zhǔn)的重要指標(biāo)，且對(duì)增強(qiáng)各年齡段人們的身體素質(zhì)具有重要意義。生鮮農(nóng)產(chǎn)品存在季節(jié)特征、地域特征和易腐敗特征，這些特征給貯藏、運(yùn)輸、銷售帶來了挑戰(zhàn)，并易于引發(fā)淡季食品供給不足、商品單調(diào)，旺季食品物流輸送不順暢等狀況。為改變生鮮農(nóng)產(chǎn)品的供需狀況，須要最大化地滿足居民對(duì)新鮮食物的需求。

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

國(guó)內(nèi)外科研人員針對(duì)車輛配送路徑的研究較多，但結(jié)合生鮮農(nóng)產(chǎn)品提升農(nóng)業(yè)物流效率的研究較少。本研究探討基于遺傳算法的生鮮農(nóng)產(chǎn)品物流配送路徑的聚類優(yōu)化，以期實(shí)現(xiàn)高效和低成本物流。

1 生鮮農(nóng)產(chǎn)品配送線路優(yōu)化模型設(shè)立

1.1 生鮮農(nóng)產(chǎn)品配送的車輛路徑問題結(jié)構(gòu)模型

車輛路徑問題即針對(duì)各個(gè)需求配送點(diǎn)選取科學(xué)的車輛運(yùn)輸線路，從生鮮農(nóng)產(chǎn)品配送核心起始，有序地通過需求配送點(diǎn)，并最終返回配送核心，其中貨物的需求狀況、車輛的限定、運(yùn)行里程的限定以及時(shí)間限定等須達(dá)到相應(yīng)的標(biāo)準(zhǔn)，如里程最小、開銷最少、采用的車輛數(shù)目最少等。圖1給出傳統(tǒng)配送VRP模型。

1.2 帶時(shí)間窗口的車輛路徑模式

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

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

在硬時(shí)間窗體運(yùn)輸路徑模式的配送過程中，生鮮運(yùn)輸車應(yīng)當(dāng)在恰當(dāng)?shù)臅r(shí)間點(diǎn)內(nèi)達(dá)到配送點(diǎn)，若生鮮運(yùn)輸車在最早服務(wù)時(shí)間之前或最晚服務(wù)時(shí)間之后到達(dá)使用者所在地點(diǎn)，則會(huì)出現(xiàn)整體生產(chǎn)模式的延遲與空置，出現(xiàn)時(shí)間開銷大而效率低的狀況，并產(chǎn)生很大的懲罰值。

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

本研究結(jié)合數(shù)學(xué)建模方法對(duì)生鮮農(nóng)產(chǎn)品物流配送路徑進(jìn)行優(yōu)化設(shè)計(jì)，采用生鮮運(yùn)輸車完成生鮮農(nóng)產(chǎn)品配送核心與幾個(gè)配送點(diǎn)之間的n個(gè)運(yùn)輸動(dòng)作，假定現(xiàn)有生鮮運(yùn)輸車的容量為Q，生鮮運(yùn)輸車的固有車輛成本為h(h>0)，各個(gè)配送點(diǎn)的需求量為qi，令qi小于Q，此外規(guī)定任務(wù)起始的執(zhí)行時(shí)間區(qū)，整個(gè)任務(wù)的需求時(shí)間為si，路段(vi，vj)對(duì)應(yīng)的時(shí)間成本、運(yùn)輸時(shí)間分別為cij、tij。

時(shí)間窗體的設(shè)計(jì)準(zhǔn)則是通過數(shù)學(xué)模型優(yōu)化生鮮運(yùn)輸車的行駛路線，且在給定時(shí)間內(nèi)開始操作并完成輸送，從而使生鮮農(nóng)產(chǎn)品派送的花銷較少。

(1)

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

(2)

tij+cij≤si。

(3)

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

2 生鮮農(nóng)產(chǎn)品物流配送路徑遺傳算法聚類優(yōu)化設(shè)計(jì)

2.1 生鮮農(nóng)產(chǎn)品物流配送路徑遺傳算法

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

遺傳算法同時(shí)檢索上一層的多個(gè)種群個(gè)體，并將初始染色體種群用作遺傳，從而構(gòu)建初始化種群的起點(diǎn)。各個(gè)個(gè)體將1～n之間的自然數(shù)排列形成一個(gè)序列，本試驗(yàn)采用初始化種群的模式獲取popsize模式的初始種群，其中n為各個(gè)生鮮農(nóng)產(chǎn)品的需求網(wǎng)點(diǎn)數(shù)目，popsize為整個(gè)種群的規(guī)模。

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

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

本研究依照VRPTW方式構(gòu)建改進(jìn)交叉方法的遺傳策略，其算法的基本策略見圖5。

2.2 生鮮農(nóng)產(chǎn)品物流配送路徑遺傳算法聚類優(yōu)化

若所需求的生鮮農(nóng)產(chǎn)品量高于車輛單次運(yùn)載的容量Q，則

(4)

式中：x為各個(gè)需求網(wǎng)點(diǎn)的生鮮農(nóng)產(chǎn)品需求量。

測(cè)算步驟為：(1)設(shè)定初始循環(huán)次數(shù)為1，由于模糊聚類[11]陣列F為一個(gè)對(duì)稱陣列，本研究選取三角陣列實(shí)現(xiàn)測(cè)算，并得到簡(jiǎn)化步驟；(2)針對(duì)模糊聚類陣列F，選最大部分進(jìn)行循環(huán)，并將F設(shè)定為目標(biāo)，進(jìn)而給出三角陣列的測(cè)算實(shí)例(圖6)。

本研究綜合遺傳算法，并結(jié)合聚類方法，對(duì)簡(jiǎn)化的VRPTW模式實(shí)現(xiàn)優(yōu)化求取，其測(cè)算步驟為：(1)選取自然數(shù)編碼模式構(gòu)建可行的生鮮農(nóng)產(chǎn)品運(yùn)輸線路染色體；(2)設(shè)定測(cè)控參量，其中設(shè)定交叉率為pc，變異狀況為pm，群體規(guī)模為N；將遺傳代數(shù)gen設(shè)定為0，即隨機(jī)獲取的初始種群p(0)中包含Num個(gè)染色體部分；(3)構(gòu)建生鮮農(nóng)產(chǎn)品運(yùn)輸?shù)男熊嚲€路；(4)設(shè)定i的初始值為1，測(cè)算種群中第i個(gè)染色體的線路距離和適應(yīng)程度，若達(dá)到算法的終止標(biāo)準(zhǔn)則停止，否則繼續(xù)；(5)i進(jìn)行自增加，若i小于n則返回步驟(2)，否則進(jìn)行下個(gè)步驟；(6)依照使用層級(jí)復(fù)制下一代染色體，實(shí)現(xiàn)最大交叉保留狀況，并且交換變異模式，進(jìn)行g(shù)en的自增加，若滿足終止標(biāo)準(zhǔn)則終止，否則轉(zhuǎn)至步驟(3)。

3 生鮮農(nóng)產(chǎn)品物流配送路徑遺傳算法聚類優(yōu)化和分析

3.1 實(shí)例設(shè)計(jì)

本研究假定須配送19個(gè)生鮮農(nóng)產(chǎn)品需求配送點(diǎn)(圖7)，并將生鮮農(nóng)產(chǎn)品配送核心的位置設(shè)置為(0，0)，圓圈表述各個(gè)需求配送點(diǎn)，編號(hào)間的距離表示網(wǎng)點(diǎn)之間的間隔距離。表1 為生鮮農(nóng)產(chǎn)品需求配送點(diǎn)網(wǎng)點(diǎn)坐標(biāo)以及需求數(shù)目，通過Matlab程序完成需求配送點(diǎn)在遺傳算法聚類優(yōu)化下的仿真。

3.2 生鮮農(nóng)產(chǎn)品運(yùn)輸外部相似性測(cè)算

本研究進(jìn)一步測(cè)算各需求配送點(diǎn)期待服務(wù)質(zhì)量和生鮮農(nóng)產(chǎn)品外部相似特點(diǎn)，并評(píng)判各需求配送點(diǎn)的期望服務(wù)質(zhì)量和所運(yùn)輸商品的外部相似特性。生鮮農(nóng)產(chǎn)品運(yùn)輸外部相似性見表2。

3.3 生鮮農(nóng)產(chǎn)品物流配送聚類結(jié)果

聚類分類停止標(biāo)準(zhǔn)依照生鮮農(nóng)產(chǎn)品關(guān)聯(lián)性質(zhì)和各需求配送點(diǎn)的貨物運(yùn)載狀況設(shè)置，此處設(shè)定權(quán)值為0.6，生鮮農(nóng)產(chǎn)品運(yùn)輸車的運(yùn)載量為2 t，然后根據(jù)客戶需求完成聚類測(cè)算。M為懲罰值，Q為生鮮運(yùn)輸車的容量。

從表3、表4可以看出，改變聚類方法的權(quán)重并結(jié)合Matlab實(shí)現(xiàn)編碼，能夠得到各種聚類結(jié)果，從而得到各種生鮮農(nóng)產(chǎn)品的配送方式。

設(shè)定本研究中的遺傳算法參量最大進(jìn)化代數(shù)為100，種群的大小為52，交叉率為0.92，變異率為0.81，軟時(shí)間窗體之下的待懲罰參量為2，延遲懲罰數(shù)據(jù)為3；在電腦上運(yùn)行得到，最優(yōu)配送間距為108 km，所采用的生鮮農(nóng)產(chǎn)品運(yùn)載工具數(shù)目最少為3輛，其所對(duì)應(yīng)的最優(yōu)化配送線路為路徑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為生鮮農(nóng)產(chǎn)品配送方法的聚類優(yōu)化結(jié)果。

3.4 組內(nèi)路徑求取結(jié)果

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

表1 生鮮農(nóng)產(chǎn)品配送網(wǎng)點(diǎn)坐標(biāo)以及需求數(shù)目

表2 生鮮農(nóng)產(chǎn)品運(yùn)輸外部相似性

表3 權(quán)重結(jié)果為W1狀況時(shí)的聚類值

表4 權(quán)重結(jié)果為W2狀況時(shí)的聚類值

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

表5 生鮮農(nóng)產(chǎn)品配送方法的聚類優(yōu)化結(jié)果

依照各個(gè)車間對(duì)應(yīng)配送核心(0，0)的坐標(biāo)方位，以需求配送點(diǎn)7、10、8、9、19、17獲取的最優(yōu)線路模式0—7—10—8—9—19—17—0為例作圖。

圖8為遺傳算法經(jīng)過198次迭代之后獲取的最優(yōu)結(jié)果以及效能的追蹤結(jié)果。因此在現(xiàn)實(shí)的操作中，應(yīng)當(dāng)適當(dāng)削減終止的最大迭代數(shù)目。

3.5 本研究方法性能測(cè)試

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

表6 實(shí)現(xiàn)一次運(yùn)行的模式

表7 組內(nèi)的最優(yōu)線路

以需求配送點(diǎn)7、10、8、9、19、17組成的路徑0—7—10—8—9—19—17—0為例，對(duì)比分析本研究生鮮農(nóng)產(chǎn)品配送方法和傳統(tǒng)生鮮農(nóng)產(chǎn)品配送方法的結(jié)果。

由表8可見，本研究路徑0—7—10—8—9—19—17—0測(cè)算方法的結(jié)果，不論為11次求解的平均結(jié)果還是最優(yōu)測(cè)算結(jié)果均優(yōu)于傳統(tǒng)方法，本測(cè)算方法的最優(yōu)間距為8.48 km，平均測(cè)算距離為 8.55 km，本方法選取的生鮮農(nóng)產(chǎn)品運(yùn)輸工具平均為3輛；而傳統(tǒng)方法的最優(yōu)間距為10.3 km，平均測(cè)算距離為11.1 km，配送生鮮農(nóng)產(chǎn)品的車輛恒定為4輛。此外，本方法能夠動(dòng)態(tài)決定選取生鮮農(nóng)產(chǎn)品運(yùn)輸工具的數(shù)目，說明本方法具有優(yōu)秀的特性，因而測(cè)算所得解的質(zhì)量較高。

4 結(jié)論

在市場(chǎng)經(jīng)濟(jì)的大環(huán)境下，生鮮農(nóng)產(chǎn)品的競(jìng)爭(zhēng)尤為激烈，而生鮮農(nóng)產(chǎn)品物流的中心環(huán)節(jié)在于配送，當(dāng)前生鮮農(nóng)產(chǎn)品的物流配送過程繁雜，貨運(yùn)種類和需求配送點(diǎn)多，交通路線復(fù)雜，在整個(gè)配送服務(wù)區(qū)域內(nèi)所分布的配送網(wǎng)點(diǎn)不均衡。顧客對(duì)生鮮農(nóng)產(chǎn)品的品質(zhì)需求日益增加，而生鮮農(nóng)產(chǎn)品配送企業(yè)仍采用以往的經(jīng)營(yíng)模式，使得農(nóng)產(chǎn)品運(yùn)輸效率低。因而科學(xué)地規(guī)劃輸送路線完成生鮮農(nóng)產(chǎn)品配送已成為社會(huì)和相關(guān)企業(yè)關(guān)注的重點(diǎn)。

表8 本研究與傳統(tǒng)生鮮農(nóng)產(chǎn)品配送方法的結(jié)果比較

本研究對(duì)生鮮農(nóng)產(chǎn)品物流配送路徑進(jìn)行優(yōu)化設(shè)計(jì)，并給出生鮮農(nóng)產(chǎn)品配送VRP模式和帶時(shí)間窗口的車輛路徑模式，進(jìn)而完成生鮮農(nóng)產(chǎn)品物流配送路徑遺傳算法聚類優(yōu)化，給出生鮮農(nóng)產(chǎn)品物流配送路徑遺傳算法步驟和聚類優(yōu)化方法，即首先設(shè)定初始循環(huán)數(shù)目，并通過模糊聚類陣列給出對(duì)稱陣列，結(jié)合三角陣列測(cè)算得到簡(jiǎn)化步驟；在模糊聚類陣列中，選最大部分完成循環(huán)，并采用Matlab完成生鮮農(nóng)產(chǎn)品物流配送路徑遺傳算法聚類優(yōu)化試驗(yàn)設(shè)計(jì)。假定有19個(gè)生鮮農(nóng)產(chǎn)品需求配送點(diǎn)應(yīng)配送，通過生鮮農(nóng)產(chǎn)品運(yùn)輸外部相似性測(cè)算生鮮農(nóng)產(chǎn)品物流配送聚類結(jié)果、組內(nèi)路徑求取結(jié)果，并對(duì)本方法進(jìn)行性能測(cè)試，結(jié)果表明，本方法明顯優(yōu)于傳統(tǒng)配送方法。