付秋睿，蒲 忠，魏 卓 FU Qiurui,PU Zhong,WEI Zhuo

（1.西南石油大學(xué) 經(jīng)濟與管理學(xué)院，四川 成都 610500；2.中國石油吉林油田分公司物資供應(yīng)處，吉林 松原 138000）

0 引言

隨著國民經(jīng)濟的持續(xù)增長，人民生活水平的不斷提高，居民對食品品質(zhì)的要求逐漸增加，冷鏈?zhǔn)袌鲂枨蟛粩鄶U大。在這樣的背景下，冷藏設(shè)備和運輸設(shè)備不斷完善，冷鏈物流行業(yè)進(jìn)入了高速發(fā)展時期。但是當(dāng)前我國制冷技術(shù)仍有缺陷，單位時間制冷成本很高。不合理的線路使得配送時間長，車輛空載率高，從而導(dǎo)致冷鏈物流環(huán)節(jié)配送效率低成本高，因此，優(yōu)化配送線路是提高效率降低成本的關(guān)鍵。

1 川渝地區(qū)冷鏈物流配送路徑優(yōu)化模型

1.1 研究內(nèi)容

針對川渝地區(qū)某公司易腐食品冷鏈物流配送成本過高，效率很低的問題進(jìn)行研究。因為冷鏈物流具有時效性，運輸時間長短顯著影響著冷鏈的質(zhì)量。而降低成本是公司運營考慮的重要條件，所有以時間為主要目標(biāo)，成本為次要目標(biāo)，建立優(yōu)化模型。因該公司實際情況限制，此次研究是多車輛，單配送中心的車輛運輸問題。

1.2 模型建立

1.2.1 基本假設(shè)

本次研究是車輛路徑問題，根據(jù)實際需要，提出如下假設(shè)：

（1）所有配送點均由一個配送中心配送。

（2）所有配送車輛型號一致，制冷設(shè)備一樣，折舊年限相同。

（3）配送中心和配送點地理坐標(biāo)已知。

（4）每輛車所負(fù)責(zé)配送的線路上總貨物需求不超過其最大載重。

（5）每個配送點只能由一輛車完成配送。

（6）車輛配送產(chǎn)品為單一品種，且運輸途中外部溫度不變。

（7）車輛勻速，路況良好，不考慮擁堵情況。

1.2.2 參數(shù)描述

根據(jù)假設(shè)定義如下變量：

配送點數(shù)設(shè)為M，配送中心編號是0，配送點依次為：1,2,3,4,…,M。

車輛編號為k，車輛數(shù)為n，最大載重為Q，配送點i需求量為qi。

對于兩配送點之間組成的直線段（i,j）和車輛k有決策變量xijk。當(dāng)xijk等于1，車輛k從配送點i行駛到配送點j，當(dāng)xijk等于0，車輛k不從配送點i行駛到配送點j。

1.2.3 成本分析

（1） 固定成本

固定成本主要包括每輛車的購置費用，固定損耗以及員工工資等。固定成本以F1表示：

C1為車輛固定成本，單位為萬元；n為配送中心自有的車輛數(shù)。

（2） 運輸成本

運輸成本主要為載貨汽車燃料消耗成本。載貨汽車燃料消耗成本與其行駛里程數(shù)成正比關(guān)系。載貨汽車油耗成本以F2表示：

C2為車輛單位距離油耗成本，單位元/KM；dij為節(jié)點i與節(jié)點j之間的距離；為所有車輛行駛總距離。

（3） 制冷成本

制冷成本是指冷藏車行駛過程中由于需要保持低溫而消耗制冷劑產(chǎn)生的成本。通過計算太陽輻射和車廂內(nèi)外部溫差產(chǎn)生的熱負(fù)荷來確定消耗的制冷劑量。第k輛車產(chǎn)生的熱負(fù)荷以Gk表示：

Β為車廂劣化程度；R為傳熱率；S為車輛受太陽輻射面積；Tw為外界溫度；Tf為車廂內(nèi)部溫度。

因此，冷藏車在行駛過程中產(chǎn)生的制冷成本F3為：

C3為單位能量制冷成本，單位元/KJ；tk為車輛k行駛時間。

1.2.4 目標(biāo)函數(shù)

基于以上分析，得出區(qū)域冷鏈物流配送模型目標(biāo)函數(shù)為：

主要目標(biāo)：

次要目標(biāo)：

約束函數(shù)為：

區(qū)域冷鏈物流配送模型中，公式（7）表示每個客戶點只能接受一次配送服務(wù)；公式（8）表示載貨汽車完成客戶服務(wù)后必須離開；公式（9）表示載貨汽車完成任務(wù)后必須返回配送中心；公式（10）表示某路徑上客戶需求總量不超過裝載汽車最大載量限制；公式（11）為決策變量，當(dāng)車輛k從i前往j時取值1，反之取0。

2 算法分析

2.1 遺傳算法的基本思想

遺傳算法是借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。它是遵循生存競爭，適者生存的原則，模擬一個人工種群的進(jìn)化過程。通過選擇、交叉以及變異等機制，在每次迭代中都保留一組候選個體，重復(fù)此過程，種群經(jīng)過若干代進(jìn)化后，理想情況下其適應(yīng)度達(dá)到近似最優(yōu)。

2.2 遺傳算法流程

（1） 確定種群規(guī)模M，隨機生成M個個體作為初始種群X（0 ），設(shè)t=0；

（2） 計算X（t）中個體的適應(yīng)值；

（3） 根據(jù)適應(yīng)值的大小從X（t）中選擇若干個個體作為進(jìn)化群體X "（t）；

（4） 在群體X "（t）上按給定的概率進(jìn)行交叉進(jìn)化和變異進(jìn)化，按給定的規(guī)則選擇N個個體作為下一代種群X（t）；

（5）是否滿足終止準(zhǔn)則，如果滿足，停止計算，否則，返回（2）。

遺傳算法流程，如圖1所示：

圖1 遺傳算法流程圖

2.3 模型的遺傳算法設(shè)計

2.3.1 編碼和解碼

冷鏈物流配送路徑問題是特殊的車倆路徑問題，是一種基于優(yōu)化排序的組合問題。一般的編碼方法為二進(jìn)制編碼或十進(jìn)制編碼。本次研究采用十進(jìn)制編碼。具體方法為：對m個配送點依次進(jìn)行編號，用i1a,i2b,…,ikc表示，k代表車輛，a、b、c代表該輛車所途徑配送點個數(shù)，配送中心用0表示。染色體編碼串為： （0,i11,i12,…,i1a,0,i21,i22,…,i2b,0…0,ik1,ik2,…,ikc,0）。

其中，染色體長度為m+k+1。0為配送中心，編碼串中兩個0之間的數(shù)字表示一條配送路徑。例如有15個配送點和4輛車配送的染色體編碼串為（0→5→2→14→13→0→3→6→8→9→10→0→11→12→1→0→4→7→15→0），表示由4輛車對15個配送點完成配送服務(wù)，共有4條子路經(jīng)。其對應(yīng)的4條子路經(jīng)為：

子路經(jīng)1：5→2→14→13

子路經(jīng) 2：3→6→8→9→10

子路經(jīng)3：11→12→1

子路經(jīng)4：4→7→15

2.3.2 遺傳算子的設(shè)計

（1）本次研究采用比例選擇法確定選擇算子。比例選擇法又稱輪盤賭選擇策略，是最基本的選擇策略之一。將種群中所有個體的適應(yīng)度值進(jìn)行累加然后歸一化，最終通過隨機數(shù)對隨機數(shù)落在的區(qū)域?qū)?yīng)的個體進(jìn)行選取，類似賭場里面的旋轉(zhuǎn)的輪盤，例如種群大小為m，個體i的適應(yīng)度為Fi，則個體i被選中遺傳到下一代群體的概率Pi為：

（2）本次研究交叉算子采用部分匹配交叉法。部分匹配交叉法是隨機定義兩個交叉點之間的區(qū)域為匹配區(qū)域，交換兩個父代的匹配區(qū)域，從而得到交叉后的個體。交叉概率取0.5。

（3）本次研究變異算子選擇倒位變異算子。倒位變異算子是隨機選擇一條子路徑，將這條子路徑倒序排列成新的子路徑，由此實現(xiàn)變異思想。因為變異在進(jìn)化過程中發(fā)生的概率很小，所以變異概率取0.005。

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

由于川渝地區(qū)冷鏈物流優(yōu)化模型目標(biāo)函數(shù)是總時間最短和總成本最低，是求解最小值函數(shù)，因此采用倒數(shù)的方式將目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù)：

其中，F(xiàn)i代表第i個染色體的適應(yīng)度值，Ai為配送總成本值。目標(biāo)函數(shù)越小，則適應(yīng)度函數(shù)值越大，越符合模型優(yōu)化目標(biāo)。

3 算例分析

3.1 樣本選擇

x超市是川渝地區(qū)著名大型國有零售企業(yè)，目前已擁83家連鎖超市，遍布川渝各個區(qū)縣。現(xiàn)排除掉相對位置接近的13家門店，選取其中70家門店進(jìn)行冷鏈配送路徑優(yōu)化研究，驗證模型和算法的有效性。

3.2 相關(guān)數(shù)據(jù)

冷藏車從渝北配送中心出發(fā)向70家門店進(jìn)行配送服務(wù)。配送產(chǎn)品為酸奶，運輸過程中溫度控制在4度，車輛內(nèi)外溫差為26度，車輛型號、車況、車速均一致，車輛載重為5噸，行駛速度為80公里/小時。

3.3 配送點相關(guān)信息

配送中心每兩天向各配送點完成一次配送，配送出發(fā)時間在凌晨1：00～5：00，車輛出發(fā)時間與門店距配送中心距離有關(guān)，完成配送后返回配送中心。門店位置，需求量如表1所示：

表1 配送點極坐標(biāo)表

4 結(jié)果分析

根據(jù)遺傳算法的設(shè)計思路，采用Matlab2014b設(shè)計多目標(biāo)區(qū)域冷鏈物流配送路徑優(yōu)化程序。根據(jù)上述分析，在CPU為Intel Core i5 5200U、內(nèi)存為4GB、操作系統(tǒng)為Windows 7的計算機上運行 Matlab 2014b，求解上述模型。所得優(yōu)化路徑如表2所示：

最優(yōu)計算結(jié)果表明，算例最優(yōu)解為94.31小時，總成本為86 807.32元，完成一次配送所需6 807.32元。在第83次迭代時生成最優(yōu)解，一共10條路徑為最優(yōu)路徑組合。與原路徑相比，優(yōu)化路徑時間更短，成本更低。經(jīng)過驗算，所有路徑模型全部符合模型容量約束以及返回配送中心的要求。

5 研究結(jié)論與不足

5.1 研究結(jié)論

本次研究針對冷鏈物流的時效性，設(shè)計以總時間最短為主要目標(biāo)，總成本最低為次要目標(biāo)的路徑優(yōu)化模型，并通過遺傳算法對模型進(jìn)行求解。在求解過程中采用十進(jìn)制編碼確定運輸路徑，采用部分匹配交叉法確定交叉算子，采用倒位變異法選擇變異算子，并用倒數(shù)的方式確定適應(yīng)度函數(shù)。通過Matlab進(jìn)行編程求解，在迭代83次后得出優(yōu)化路徑，與原路徑相比，優(yōu)化路徑時間更短，成本更低。

5.2 研究的不足之處

由于此次研究考慮的僅僅是確定車型，確定車輛，單車場的路徑問題，因此對多配送中心的車輛路徑問題還有待進(jìn)一步深入研究。在算法上，交叉算子變異算子的選擇還有進(jìn)一步提升空間，同時運用遺傳算法和其他優(yōu)化算法結(jié)合進(jìn)行優(yōu)化，或許能得到更優(yōu)結(jié)果。

表2 優(yōu)化路徑表