基于多目標(biāo)和單配送中心的冷鏈物流配送路徑優(yōu)化研究
——以川渝地區(qū)某公司冷鏈物流配送為例

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

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

0 引言

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

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

1.1 研究?jī)?nèi)容

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

1.2 模型建立

1.2.1 基本假設(shè)

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

（1）所有配送點(diǎn)均由一個(gè)配送中心配送。

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

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

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

（5）每個(gè)配送點(diǎn)只能由一輛車完成配送。

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

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

1.2.2 參數(shù)描述

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

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

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

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

1.2.3 成本分析

（1） 固定成本

固定成本主要包括每輛車的購(gòu)置費(fèi)用，固定損耗以及員工工資等。固定成本以F1表示：

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

（2） 運(yùn)輸成本

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

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

（3） 制冷成本

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

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

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

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

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

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

主要目標(biāo)：

次要目標(biāo)：

約束函數(shù)為：

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

2 算法分析

2.1 遺傳算法的基本思想

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

2.2 遺傳算法流程

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

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

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

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

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

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

圖1 遺傳算法流程圖

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

2.3.1 編碼和解碼

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

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

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

（2）本次研究交叉算子采用部分匹配交叉法。部分匹配交叉法是隨機(jī)定義兩個(gè)交叉點(diǎn)之間的區(qū)域?yàn)槠ヅ鋮^(qū)域，交換兩個(gè)父代的匹配區(qū)域，從而得到交叉后的個(gè)體。交叉概率取0.5。

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

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

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

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

3 算例分析

3.1 樣本選擇

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

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

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

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

配送中心每?jī)商煜蚋髋渌忘c(diǎn)完成一次配送，配送出發(fā)時(shí)間在凌晨1：00～5：00，車輛出發(fā)時(shí)間與門(mén)店距配送中心距離有關(guān)，完成配送后返回配送中心。門(mén)店位置，需求量如表1所示：

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

4 結(jié)果分析

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

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

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

5.1 研究結(jié)論

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

5.2 研究的不足之處

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

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