基于遺傳算法的冷鏈物流配送路徑優(yōu)化研究

鄭義彬， 邱興宇， 孫源澤， 劉立博

(武漢理工大學(xué) 交通學(xué)院， 湖北 武漢 430063)

不少學(xué)者對(duì)冷鏈配送路徑問題進(jìn)行了研究。陳婧怡等針對(duì)多溫共配模式下生鮮農(nóng)產(chǎn)品冷鏈配送問題，采用多溫區(qū)冷藏車，構(gòu)建了考慮運(yùn)輸成本、貨損成本、制冷成本的路徑優(yōu)化模型,利用遺傳算法對(duì)算例進(jìn)行求解,借助ArcGIS規(guī)劃最短路徑。張?jiān)拼ǖ仍诘谌嚼滏溛锪髋渌吐窂絻?yōu)化研究的基礎(chǔ)上，考慮車輛行駛速度和載重量對(duì)運(yùn)輸能耗的影響，采用指數(shù)函數(shù)刻畫食品的變質(zhì)速率，運(yùn)用模擬退火算法對(duì)模型進(jìn)行優(yōu)化。邵舉平等引入生鮮度損耗系數(shù)反映產(chǎn)品質(zhì)量隨時(shí)間的變化，考慮配送總成本和顧客滿意度兩個(gè)目標(biāo),建立了生鮮農(nóng)產(chǎn)品配送路徑多目標(biāo)優(yōu)化模型，并對(duì)模型參數(shù)進(jìn)行了敏感性分析。陶志文等采用粒子群算法求解多目標(biāo)冷鏈配送優(yōu)化模型，同時(shí)對(duì)碳稅和冷藏車速度進(jìn)行了靈敏度分析。Xuping Wang等根據(jù)交付時(shí)裝置和車輛冷藏食品的特殊要求，以運(yùn)輸成本、配送中心建立成本、罰款成本和損壞成本等總成本最小為目標(biāo)，建立了不同運(yùn)輸方式下考慮冷藏食品時(shí)間窗的食品配送優(yōu)化模型。Y. Zhang等考慮與不同冷凍食品的單位體積相關(guān)的裝載量的限制，建立了多品種速凍食品配送中車輛路徑優(yōu)化模型，采用遺傳算法進(jìn)行求解，通過實(shí)際案例計(jì)算驗(yàn)證了模型的可行性和合理性，并顯示了遺傳算法參數(shù)值的有效組合。但現(xiàn)有研究考慮的環(huán)境變量不夠全面。該文建立較完善的綜合成本生鮮冷鏈路徑配送優(yōu)化模型，研究滿足客戶時(shí)間窗條件下總配送成本最小的最優(yōu)配送方案。

1 模型建立

1.1 模型假設(shè)

某配送中心對(duì)多個(gè)客戶進(jìn)行配送，配送產(chǎn)品單一，且滿足以下條件：1) 配送車輛有限且最大載重量固定,每輛車的最大容量滿足每條線路的需求量；2) 配送車輛都從配送中心出發(fā)，配送結(jié)束后返回配送中心；3) 每個(gè)客戶的需求已知，且均能被一輛車服務(wù)；4) 客戶有規(guī)定的時(shí)間窗，若配送到達(dá)時(shí)間不在客戶要求的配送時(shí)間窗內(nèi)，則產(chǎn)生相應(yīng)的懲罰成本；5) 每條配送線路長度均小于車輛最大行駛里程；6) 車輛勻速行駛，考慮在途目標(biāo)是使總配送費(fèi)用最小且客戶滿意度較高；7) 每個(gè)客戶的服務(wù)時(shí)間固定。

1.2 成本分析

根據(jù)假設(shè)的目標(biāo)，構(gòu)建以總成本最小為目標(biāo)的函數(shù)。總成本包含運(yùn)輸費(fèi)用、貨損費(fèi)用、懲罰成本。

參數(shù)描述：配送中心編號(hào)為0，各客戶位置編號(hào)為1～n。

車輛編號(hào)為1～k，車輛最大載重為Qm。變量xijk表示車輛k是否經(jīng)過線路i—j：當(dāng)車輛k經(jīng)過線路i—j時(shí)，xijk=1，否則xijk=0。若車輛k服務(wù)客戶i，則yik=1,否則yik=0。

冷鏈配送過程中固定成本與行駛里程無關(guān)，故只考慮與運(yùn)輸里程相關(guān)的變動(dòng)成本，如油耗、車輛保養(yǎng)和維修。配送車輛的變動(dòng)成本與行駛里程成正比。運(yùn)輸?shù)淖儎?dòng)成本由式(1)計(jì)算：

(1)

式中：C1為單位運(yùn)距的油耗成本(元/km)；dij為客戶i與j之間的距離。

為保持生鮮產(chǎn)品的質(zhì)量而產(chǎn)生的制冷費(fèi)用，只考慮行駛過程中產(chǎn)生的制冷成本，不考慮裝卸貨過程中產(chǎn)生的制冷費(fèi)用。計(jì)算公式如下：

(2)

式中：tk表示車輛的行駛時(shí)間；C2為單位制冷成本(元/kJ);G為制冷過程消耗的熱量，G=αRSΔT；α為常數(shù)；R為熱傳導(dǎo)系數(shù)；S為車廂受熱面積(m2)；ΔT為車輛內(nèi)外溫差(K)。

一般客戶要求的時(shí)間窗為軟時(shí)間窗，允許配送到達(dá)時(shí)間在客戶滿意時(shí)間之外的一定階段，在這一階段會(huì)產(chǎn)生相對(duì)應(yīng)的懲罰成本。設(shè)客戶n要求的時(shí)間窗為[En,Ln]，車輛k到達(dá)客戶i的時(shí)刻記為tik，eik表示在時(shí)間窗之前到達(dá)，lik表示在時(shí)間窗之后到達(dá)，則懲罰成本由下式計(jì)算：

F3=a(En-eik)+b(lik-Ln)

(3)

式中：a為提前到達(dá)的懲罰系數(shù)；b為延遲到達(dá)的懲罰系數(shù)。

1.3 數(shù)學(xué)模型構(gòu)建

冷鏈物流配送總費(fèi)用以F表示，目標(biāo)函數(shù)如下：

minF=F1+F2+F3

(4)

約束條件：

(5)

(6)

(7)

(8)

(9)

式(5)表示車輛的載重量不超過其滿載；式(6)表示一個(gè)客戶只被服務(wù)一次；式(7)表示每個(gè)客戶只被一輛車服務(wù)；式(8)表示車輛從配送中心出發(fā)，完成配送后返回配送中心；式(9)表示所有門店都能接受到配送服務(wù)。

2 算法設(shè)計(jì)

采用遺傳算法對(duì)冷鏈物流配送路徑優(yōu)化模型進(jìn)行求解(見圖1)。

(1) 變異。采用兩點(diǎn)互易進(jìn)行變異：1) 產(chǎn)生2個(gè)隨機(jī)自然數(shù)r1、r2；2) 交換第r1、r2位的基因。

(2) 交叉。采用兩點(diǎn)交叉：1) 隨機(jī)選擇2個(gè)染色體作為父本；2) 產(chǎn)生2個(gè)隨機(jī)自然數(shù)r1和r2；3) 將r1至r2之間的基因片段進(jìn)行交換,得到2個(gè)子代染色體,并進(jìn)行修訂處理,使其不發(fā)生沖突。

(3) 解碼。根據(jù)載重約束和時(shí)間窗約束對(duì)一個(gè)編碼S進(jìn)行劃分，步驟如下：1)i=1；2) 開始第i條路線Ri=[0]，0為配送中心；3) 嘗試將編碼S中的第1個(gè)點(diǎn)加入Ri，如果加入Ri后車輛載重滿足，則進(jìn)入下一步，否則i=i+1，轉(zhuǎn)入步驟2；4) 刪除S的第1位編碼，如果S空，則進(jìn)入下一步，否則轉(zhuǎn)入步驟3；5) 輸出各子路徑。

(4) 選擇。采用輪盤賭選擇，個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。

圖1 遺傳算法設(shè)計(jì)流程

3 算例分析

某配送中心以額定載重3 t的車輛給10個(gè)客戶配送貨物，各客戶的位置及需求量qi見表1，相關(guān)參數(shù)見表2。下面運(yùn)用上述優(yōu)化模型，通過合理安排車輛及配送路線使總配送成本最小。

表1 各客戶的位置及需求量

按照各節(jié)點(diǎn)坐標(biāo)計(jì)算配送中心及每個(gè)客戶之間的距離，兩點(diǎn)間的距離近似看作直線。計(jì)算結(jié)果見表3。

表2 相關(guān)參數(shù)設(shè)置

表3 客戶節(jié)點(diǎn)之間的距離 km

運(yùn)行遺傳算法進(jìn)行計(jì)算。運(yùn)行至50代時(shí)目標(biāo)函數(shù)值為435.95 元，對(duì)應(yīng)的最優(yōu)方案為配送中心選用3輛冷藏車進(jìn)行配送，配送線路分別為0—3—6—7—4—0、0—5—9—1—0、0—8—2—10—0。圖2為遺傳算法迭代曲線，圖3為遺傳算法求解的最優(yōu)路徑，圖4為經(jīng)驗(yàn)法得到的初始配送方案。

圖2 遺傳算法優(yōu)化迭代曲線

從圖2可看出：采用遺傳算法求解冷鏈物流配送路徑優(yōu)化模型，迭代超過50次后，曲線基于平穩(wěn)，逐漸收斂于最優(yōu)值435.95 元，相較于初始方案的總成本543.65 元，優(yōu)化模型的總成本降低較大。

圖3 遺傳算法優(yōu)化得到的配送路徑

圖4 根據(jù)經(jīng)驗(yàn)法得到的初始配送方案

4 結(jié)語

該文對(duì)冷鏈配送各部分成本進(jìn)行分析，以運(yùn)輸成本、貨損成本及針對(duì)客戶滿意度的懲罰成本最小為目標(biāo)建立考慮客戶時(shí)間窗的冷鏈配送路徑優(yōu)化模型，并設(shè)計(jì)遺傳算法對(duì)模型進(jìn)行求解。算例計(jì)算結(jié)果表明，該總費(fèi)用最小模型及算法有效，可為冷鏈配送路徑優(yōu)化決策提供理論依據(jù)。但需在以下兩方面進(jìn)行完善：1) 針對(duì)不確定環(huán)境下冷鏈物流配送方案的選擇；2) 配送車輛及配送種類不固定情形下的配送方案選擇。