多目標(biāo)低碳冷鏈物流配送路徑優(yōu)化研究

張智勇 李小青 石永強(qiáng)

（華南理工大學(xué)，廣東 廣州 510006）

一、引言

隨著經(jīng)濟(jì)的發(fā)展，人民生活水平提高，人們對(duì)生鮮產(chǎn)品數(shù)量、品質(zhì)需求不斷增加，冷鏈物流的發(fā)展也十分迅速。為有效降低冷鏈物流成本，不少學(xué)者研究如何優(yōu)化冷鏈物流系統(tǒng)，而車(chē)輛路徑問(wèn)題是冷鏈物流體系優(yōu)化的重要環(huán)節(jié)。Hsu等[1]針對(duì)易腐食品配送過(guò)程的隨機(jī)性，提出帶時(shí)間窗的車(chē)輛路徑問(wèn)題（Vehicle Routing Problem with Time Windows， VRPTW），評(píng)估隨機(jī)交貨時(shí)間、食物變質(zhì)和時(shí)間窗對(duì)車(chē)輛路線(xiàn)與成本的影響，獲得最佳配送路線(xiàn)與調(diào)度決策。姚源果等[2]考慮交通、接駁方式對(duì)農(nóng)產(chǎn)品冷鏈物流配送優(yōu)化的影響，并利用蟻群算法對(duì)基于實(shí)時(shí)路況信息和接駁方式的優(yōu)化模型分別進(jìn)行實(shí)例求解，有效降低成本。

高速經(jīng)濟(jì)增長(zhǎng)的同時(shí)也帶來(lái)了高消耗與高排放。近年來(lái)，綠色低碳引起不少學(xué)者的關(guān)注與研究，冷鏈物流是高能源、高碳排放行業(yè)，節(jié)能減排勢(shì)在必行。Leng等[3]與陶帝豪等[4]分別針對(duì)選址-路徑問(wèn)題和車(chē)輛路徑問(wèn)題，考慮碳排放作為優(yōu)化目標(biāo)之一進(jìn)行優(yōu)化求解。實(shí)際中冷鏈物流配送優(yōu)化不僅需要考慮成本和碳排放，也需要考慮可以反映客戶(hù)對(duì)獲得產(chǎn)品和服務(wù)感受的客戶(hù)滿(mǎn)意度。任騰等[5]在低碳經(jīng)濟(jì)背景下考慮冷鏈配送的碳排放成本和客戶(hù)滿(mǎn)意度，建立包括滿(mǎn)意度在內(nèi)的總成本最小模型并對(duì)冷鏈配送企業(yè)提出建議。陶志文等[6]則提出保障客戶(hù)水平、降低碳排放和優(yōu)化配送成本的多目標(biāo)路徑優(yōu)化模型，采用粒子群算法求解，提升客戶(hù)滿(mǎn)意度。

本文綜合考慮環(huán)境、滿(mǎn)意度與經(jīng)濟(jì)效益三個(gè)因素，基于實(shí)時(shí)路況對(duì)行駛速度和時(shí)間變量進(jìn)行分析，以最小化配送總成本、最大化客戶(hù)滿(mǎn)意度為目標(biāo)，構(gòu)建考慮碳排放的多車(chē)型帶時(shí)間窗生鮮產(chǎn)品冷鏈配送路徑優(yōu)化模型，并設(shè)計(jì)改進(jìn)混合遺傳算法求解，尋找最優(yōu)配送路徑，降低生鮮產(chǎn)品的低碳冷鏈配送總成本，提升企業(yè)客戶(hù)滿(mǎn)意度同時(shí)降低能耗，實(shí)現(xiàn)企業(yè)的經(jīng)濟(jì)效益和社會(huì)效益。

二、問(wèn)題描述與模型構(gòu)建

1.問(wèn)題描述與參數(shù)說(shuō)明

已知某生鮮零售企業(yè)在某地有1配送中心，使用h種車(chē)型的電動(dòng)和燃油冷鏈車(chē)對(duì)零售點(diǎn)進(jìn)行生鮮配送服務(wù)，且車(chē)輛從配送中心出發(fā)，配送完成后返回配送中心。為保證模型可行性且不影響模型構(gòu)建和求解的前提下本文假設(shè)：（1）生鮮配送中心位置已知，產(chǎn)品存量滿(mǎn)足客戶(hù)點(diǎn)需求總和；（2）零售點(diǎn)的位置、需求量、時(shí)間窗一定且已知，且只允許一輛冷藏車(chē)對(duì)其進(jìn)行配送；（3）多種車(chē)輛型號(hào)已知，每條路線(xiàn)上客戶(hù)總需求量不超過(guò)車(chē)輛最大載重量；（4）冷鏈產(chǎn)品對(duì)溫度等要求一致；（5）配送時(shí)間窗內(nèi)不同時(shí)段的車(chē)輛行駛速度不同且不存在中途指派等偶然突發(fā)情況發(fā)生。

2.模型變量分析

（1）決策變量

3.目標(biāo)函數(shù)分析

（1）固定成本、違反時(shí)間窗的懲罰成本與制冷成本

（2）總貨損成本

（3）運(yùn)輸成本和碳排放成本

配送運(yùn)輸成本主要包括車(chē)輛運(yùn)輸和制冷過(guò)程中的燃油/電能消耗。記F1運(yùn)輸過(guò)程的消耗，采用綜合模式排放模型（Comprehensive Modal Emission Model，CMEM）計(jì)算車(chē)速和裝載量動(dòng)態(tài)變化情形下的車(chē)輛燃油消耗量[3][8]。燃油消耗量基礎(chǔ)模型為：

電動(dòng)汽車(chē)的電能消耗基礎(chǔ)模型表示為：

（4）客戶(hù)滿(mǎn)意度

客戶(hù)滿(mǎn)意度主要受送貨時(shí)間的準(zhǔn)時(shí)性等因素影響，本文使用模糊函數(shù)來(lái)衡量時(shí)間滿(mǎn)意度，如下。

4.目標(biāo)函數(shù)及模型建立

綜上所述，多車(chē)型低碳冷鏈配送路徑優(yōu)化模型為：

式（13）和（14）分別表示模型總成本與滿(mǎn)意度目標(biāo)；式（15）表示該運(yùn)輸路線(xiàn)上的總需求不超過(guò)車(chē)輛的最大載重；式（16）為車(chē)輛行駛最大里程約束；式（17）表示每個(gè)零售點(diǎn)只能被一輛車(chē)服務(wù)一次；式（18）表示每輛冷藏車(chē)從配送中心出發(fā)，配送任務(wù)結(jié)束后返回配送中心；式（19）為每個(gè)零售點(diǎn)進(jìn)入的車(chē)輛一定要離開(kāi)；式（20）為時(shí)間窗約束；式（21）和（22）代表決策變量的整數(shù)約束。

三、 模型求解

1.目標(biāo)函數(shù)的處理

2.改進(jìn)遺傳算法設(shè)計(jì)

考慮碳排放的生鮮產(chǎn)品配送路徑優(yōu)化問(wèn)題屬于NP-hard問(wèn)題，國(guó)內(nèi)外學(xué)者通常采用啟發(fā)式算法進(jìn)行求解。遺傳算法（Genetic Algorithms， GA）在大量同類(lèi)研究文獻(xiàn)中已被證明具有實(shí)行性，本文采取模擬退火算法（Simulated Annealing，SA）和大規(guī)模鄰域搜索算法（Large Neighborhood Search，LNS）對(duì)遺傳算法進(jìn)行改進(jìn)：GA在迭代過(guò)程中易陷入局部最優(yōu)，在最優(yōu)值多次保持不變后，對(duì)種群前10%進(jìn)行模擬退火操作，以一定概率接受較差解，使其跳出局部最優(yōu)得到新種群，實(shí)現(xiàn)全局最優(yōu)；使用高效尋優(yōu)的LNS產(chǎn)生鄰域解，根據(jù)相似性從當(dāng)前解中移除若干配送點(diǎn)，在滿(mǎn)足約束的前提下將被移除的顧客重新插回到破壞的解中，盡可能插回到使總目標(biāo)成本最小的位置，更新種群。主要步驟為：①參數(shù)初始化；②編碼、初始化種群，計(jì)算適應(yīng)度，記錄最優(yōu)解；③采用輪盤(pán)賭方法進(jìn)行個(gè)體選擇；④按照交叉概率，進(jìn)行OX交叉操作；⑤判斷迭代次數(shù)是否是鄰域搜索隔代數(shù)的倍數(shù)，即當(dāng)i%L=0時(shí)，對(duì)目前最優(yōu)解進(jìn)行鄰域搜索操作，以鄰域空間內(nèi)更優(yōu)解更新當(dāng)代種群；⑥按變異概率對(duì)i代種群進(jìn)行變異操作，比較最優(yōu)染色體，若子代更優(yōu)，則將最優(yōu)染色體替換；否則將i代種群最優(yōu)染色體替換掉i代子種群的最差個(gè)體；⑦執(zhí)行i=i+1，并更新溫度；⑧i與i-1代最優(yōu)染色體相同，則最優(yōu)解連續(xù)不變代數(shù) 1

A=A+，否則A=1，當(dāng)A＞A′，調(diào)用模擬退火算法更新種群，跳出最優(yōu)解；⑨重復(fù)步驟③到⑧，直到滿(mǎn)足最大迭代次數(shù)，選擇最后一代的最優(yōu)染色體作為最優(yōu)解。

四、算例與結(jié)果分析

1.數(shù)據(jù)處理與參數(shù)設(shè)置

2.運(yùn)算結(jié)果與結(jié)果分析

關(guān)于本文算法相關(guān)參數(shù)設(shè)置如下：size=200，代溝=0.9，pc=0.9，pm=0.01，L=30，T0=100℃，A′=50，r=0.9，MaxOutIter=300，MaxInIter=100，maxGEN=1000。在MATLAB R2019a上對(duì)文中實(shí)例與模型進(jìn)行求解，結(jié)果發(fā)現(xiàn)配送中心共安排13輛冷鏈車(chē)進(jìn)行配送，其中5輛電動(dòng)冷鏈車(chē)，其他為燃油車(chē)，總配送成本為24024.2元，客戶(hù)滿(mǎn)意度為79.23%。為驗(yàn)證模型有效性，探討模型的實(shí)際應(yīng)用意義，進(jìn)行不同模型的對(duì)比分析，與單車(chē)型相比，多車(chē)型減少1輛，總里程減少108.1km，客戶(hù)滿(mǎn)意度為提升6.85%，碳排放成本減少91.8元，總成本優(yōu)化2774.7元；不考慮碳排放模型時(shí)，總成本直觀上變低，但產(chǎn)生碳排放成本為3501.1元，該部分成本由社會(huì)負(fù)擔(dān)，綜合來(lái)看，考慮碳排放模型的總成本更低。不同模型結(jié)果如表1所示。

表1 不同模型對(duì)比結(jié)果分析

五、結(jié)語(yǔ)

針對(duì)冷鏈產(chǎn)品需求快速增長(zhǎng)、顧客滿(mǎn)意度重要性提升以及社會(huì)對(duì)綠色環(huán)保意識(shí)增強(qiáng)，為降低冷鏈配送總成本、減少碳排放量并提升客戶(hù)滿(mǎn)意度，本文建立了考慮客戶(hù)滿(mǎn)意度的多車(chē)型生鮮低碳冷鏈配送路徑優(yōu)化模型，并提出改進(jìn)混合遺傳算法求解所建立的模型。為驗(yàn)證模型與算法的有效性和實(shí)用性，進(jìn)行了不同模型與算法的對(duì)比分析，結(jié)果表明：①本文提出的算法能有效的解決求解模型，為企業(yè)實(shí)際中的路徑優(yōu)化等決策提供參考；②使用電動(dòng)車(chē)后比燃油車(chē)節(jié)約成本，并能減少污染，在實(shí)際允許的情況下可以多推行電動(dòng)車(chē)進(jìn)行配送服務(wù)；③所建立的考慮碳排放的模型，能降低總成本，提升客戶(hù)滿(mǎn)意度，減少碳排放，提升企業(yè)社會(huì)經(jīng)濟(jì)效益。