考慮客戶滿意度的低碳冷鏈車輛路徑優(yōu)化

任 騰，陳 玥，向迎春，邢立寧+，李思迪

(1.中南林業(yè)科技大學(xué) 物流與交通學(xué)院，湖南 長沙 410004; 2.中南林業(yè)科技大學(xué) 旅游學(xué)院，湖南 長沙 410004)

0 引言

隨著社會經(jīng)濟(jì)的不斷發(fā)展，人們生活水平不斷提高，對于生鮮食品的需求量也逐漸增加，從而促進(jìn)了冷鏈產(chǎn)業(yè)的迅速發(fā)展。根據(jù)中國物流與采購聯(lián)合會發(fā)布的年度報告顯示，2018年我國冷鏈物流市場規(guī)模已達(dá)到3 035億元。在大規(guī)模冷鏈配送市場環(huán)境下，如何減縮冷鏈物流的配送距離、降低物流成本，成為至關(guān)重要的問題。

在冷鏈物流車輛配送問題上，國內(nèi)外已有部分學(xué)者對此進(jìn)行了研究，其中Pretorius等[1]基于聯(lián)合分布的思想，通過建立聯(lián)合分布節(jié)點來提高冷鏈物流終端配送能力；Zhang等[2]考慮到常見的冷鏈物流、第三方物流公司需要提供溫敏食品零售商節(jié)點時間窗和弧時間窗，研究了復(fù)雜車輛路徑問題(Vehicle Routing Problem, VRP)；Amorim等[3]考慮多個時間窗與多車型的約束，構(gòu)建了車輛配送路徑優(yōu)化模型。近年來，“節(jié)能減排，綠色發(fā)展”成為社會提倡的核心理念，關(guān)于車輛的低碳配送優(yōu)化問題也逐漸受到專家學(xué)者的廣泛關(guān)注。在油耗對車輛碳排放的影響方面，Suzuki[5]建立了以最小化油耗為目標(biāo)的車輛配送問題模型，并采用壓縮退火算法進(jìn)行求解；Kuo[6]以速度與載重量為約束，構(gòu)建了以油耗最小為目標(biāo)的模型，并與最短距離、最小運行時間目標(biāo)下的車輛路徑問題進(jìn)行了對比；Kopfer[7]在考慮距離與載重量的因素下，根據(jù)不同類型的車輛燃油量不同這一理論，對多車型低碳車輛路徑優(yōu)化模型進(jìn)行優(yōu)化；Harris等[8]研究了運輸耗電產(chǎn)生的二氧化碳排放與總物流成本之間的關(guān)系；肖超等[9]分析了冷鏈配送各環(huán)節(jié)的成本，考慮車輛載重、時間窗等約束，構(gòu)建了總成最小的VRP模型；肖建華等[10]考慮到城市道路限行的問題，將配送車輛分為多種類型進(jìn)行車輛路徑優(yōu)化。與此同時，顧客滿意度對于物流配送服務(wù)的重要性也促使各國學(xué)者開始對其進(jìn)行研究。受生鮮食品易腐性影響，冷鏈配送產(chǎn)品保質(zhì)期短、時效性強，通過維持良好的生鮮產(chǎn)品品質(zhì)，并在客戶允許的時間范圍內(nèi)完成物流配送，能大幅提高客戶滿意度[11]。在此方面，Moghaddam[12]通過對車輛配置與配送路線的整體規(guī)劃來提高不確定需求下物流配送的客戶滿意度；左文明等[13]通過構(gòu)建客戶滿意度動態(tài)測量模型，發(fā)現(xiàn)通過改善當(dāng)前B2C電子商務(wù)服務(wù)流程中的物流服務(wù)質(zhì)量可以顯著提升顧客滿意度；陳萍等[14]在分析餐飲O2O外賣客戶滿意度特點的基礎(chǔ)上，提出了適合餐飲O2O外賣配送的優(yōu)化模型。

現(xiàn)階段，學(xué)者們大多關(guān)注配送碳排放量的優(yōu)化，在理論上研究低碳等多種因素在冷鏈配送問題中的影響，并運用啟發(fā)式算法、精確算法等智能優(yōu)化算法[15-17]來解決同類VRP問題[18-19]，也有大量學(xué)者進(jìn)行了在普通配送、冷鏈配送、電商配送、外賣配送等多種情況下的客戶滿意度研究，但將兩因素結(jié)合，對低碳冷鏈配送中的客戶滿意度的研究卻較少。對于冷鏈物流企業(yè)而言，可通過對冷鏈車輛配送路徑進(jìn)行優(yōu)化來降低碳排放，從而實現(xiàn)物流配送環(huán)節(jié)的節(jié)能減排。在降低經(jīng)濟(jì)生產(chǎn)的環(huán)境代價的同時，企業(yè)經(jīng)濟(jì)效益的維護(hù)也不可忽視。因此，在降低冷鏈配送碳排放量的前提下，通過最大化提高客戶滿意度來實現(xiàn)企業(yè)經(jīng)濟(jì)效益的提升是有意義的。基于此，本文在分析了客戶允許時間、產(chǎn)品變質(zhì)率、距離、載重量等影響因素后，考慮車輛自身碳排放量與制冷設(shè)備碳排放量，建立了在客戶允許時間內(nèi)以總成本最小為目標(biāo)的低碳冷鏈車輛路徑優(yōu)化模型。同時，設(shè)計了改進(jìn)型蟻群算法，得到最優(yōu)的車輛配送路徑。

1 問題描述與假設(shè)

1.1 問題描述

本文研究單一配送中心、同車型、多車輛、多需求點的VRP，考慮車輛最大行駛距離、最大載重量等因素，在客戶允許服務(wù)時間范圍內(nèi)求配送總成本(碳排放成本、懲罰成本)最小時車輛的配送路徑。假設(shè)每一次配送車輛的起點均為配送中心，配送任務(wù)完成后返回配送中心；客戶時間窗、客戶服務(wù)時間、開關(guān)車門時冷鏈車輛內(nèi)部溫度、配送點地理位置和配送點需求量已知；車輛配送的貨物總量不超過每輛車的最大裝載量；每個配送點都能得到服務(wù)且只能由一輛冷藏車完成配送；配送過程中的車輛速度已知；車輛配送過程中貨物的總重量隨卸貨操作而變化；通過將客戶滿意度轉(zhuǎn)化為軟時間窗、貨物變質(zhì)率約束來體現(xiàn)物流配送時企業(yè)經(jīng)濟(jì)效益，達(dá)到冷鏈物流配送中企業(yè)環(huán)境成本與經(jīng)濟(jì)效益的綜合優(yōu)化。

1.2 符號和決策變量

本文出現(xiàn)符號和變量較多，模型符號如表1所示，部分變量在文中首次出現(xiàn)時進(jìn)行定義說明。

表1 符號和決策變量

續(xù)表1

2 模型構(gòu)建

2.1 車輛自身碳排放量

配送車輛行駛過程中，油耗與車速及載重存在著必然的關(guān)聯(lián)[20]，而車輛的碳排放主要來源于車輛行駛時的燃油廢氣排放，因此碳排放量與車速存在著不可忽視的聯(lián)系。車輛在行駛過程中碳排放量與車速的關(guān)系式為[21]：

(1)

車輛碳排放與車輛載重也存在密不可分的關(guān)系[22]，本文將車輛因載重所產(chǎn)生的碳排放表示為

(2)

2.2 車輛配送過程中制冷設(shè)備碳排放量

受技術(shù)條件影響，機(jī)械冷鏈車是國內(nèi)冷鏈車中的主要車型，機(jī)械鏈車的制冷系統(tǒng)由汽車發(fā)動機(jī)負(fù)責(zé)驅(qū)動，因此汽油為冷鏈車制冷設(shè)備所消耗的主要能源。而影響制冷油耗的因素除距離、需求量、儲存要求等因素外，還有外界溫度、車體的傳熱系數(shù)等次要因素。由于本文已假設(shè)車輛型號相同、行駛過程中車門關(guān)閉、車輛內(nèi)外部溫度穩(wěn)定不變，由溫度等因素引起的碳排放量本文不予考慮，配送中制冷設(shè)備的碳排放計算借鑒相關(guān)研究[23]，公式為：

(3)

2.3 客戶滿意度成本

冷鏈物流VRP模型中，客戶時間窗與產(chǎn)品質(zhì)量是影響顧客滿意度[24]的重要因素。通過對時間窗與產(chǎn)品質(zhì)量分別賦予權(quán)重后相加，便可求得本次配送的客戶總滿意度。

2.3.1 時間窗懲罰成本的計算

針對冷鏈配送產(chǎn)品時效性強、易腐性高的特點，本文采用帶軟時間窗約束及懲罰函數(shù)的VRP模型來描述客戶對于冷鏈車輛配送質(zhì)量的滿意度。在冷鏈配送中，企業(yè)需要在客戶規(guī)定的時間窗內(nèi)送達(dá)貨物，過早或者過晚送貨都會在一定程度上降低客戶的滿意度，只有在規(guī)定時間段內(nèi)送達(dá)才能保證客戶滿意度最高[25]。如圖1所示，車輛到達(dá)時間分為5種情況，分別表示不同含義的客戶滿意度?？蛻魸M意度最大在模型中轉(zhuǎn)換為利用懲罰成本最小[26]表示，轉(zhuǎn)化后懲罰成本函數(shù)示意圖如圖2所示。

對應(yīng)的懲罰函數(shù)表示如下：

(4)

在客戶規(guī)定的時間段[ei,li]內(nèi)，客戶滿意度最大，懲罰成本為0；在階段[Ei,ei]中，生鮮食品如果提前送達(dá)，車輛需要增加等待成本，提前時間越長，等待成本越大，u1為等待成本系數(shù)(單位：元/h)，此時懲罰成本隨時間向后推移而減小；[li,Li]階段，懲罰成本隨時間的向后推移逐漸增大，u2為遲到成本系數(shù)(單位：元/h)；在顧客允許范圍外的[0,Ei]和[Li,+∞]，懲罰成本為一個極大的實數(shù)M，目標(biāo)模型無解。該懲罰成本數(shù)學(xué)表達(dá)式為：

(5)

2.3.2 貨物變質(zhì)成本

冷鏈貨物儲存條件嚴(yán)格，對環(huán)境變化敏感，時間和溫度的變化對貨物變質(zhì)影響較大，配送時間的增加以及環(huán)境溫度的升高會導(dǎo)致變質(zhì)成本增加。變質(zhì)成本與兩者變化正相關(guān)。在物流配送中，卸貨環(huán)節(jié)是造成車廂內(nèi)溫度變化從而引起貨物變質(zhì)的主要環(huán)節(jié)。本文采用阿倫尼烏斯公式計算由于氣溫變化下生鮮貨物的變質(zhì)成本[27]，公式通常形式為：

(6)

式中：K為反應(yīng)速率常數(shù)；A為阿倫尼烏斯常數(shù)；Ea為活化能；T為絕對溫度；R為氣體常數(shù)。

運輸環(huán)節(jié)的變質(zhì)成本為：

lqm1×Wj(0)=[1-e-ψ1t1]×Wj(0);

(7)

(8)

其中Wj(t)為車輛在t時刻時從配送中心到配送點j整個過程中完好貨物的數(shù)量。

卸貨環(huán)節(jié)的變質(zhì)成本為：

lqm2×Wj(t1)=[1-e-ψ2(tj-t1)]×e-ψ1t1×Wj(0);

(9)

總變質(zhì)成本為：

(11)

2.4 模型建立

綜上所述，考慮顧客滿意度的低碳冷鏈車輛配送成本模型如下：

(12)

可簡化表示如下：

minC=W{P0+P1+P2}+PT+PQ。

(13)

(14)

qk≤Q，k∈K;

(15)

(16)

(17)

(18)

(19)

(20)

其中：式(14)表示車輛k從i點到j(luò)點的0-1變量；式(15)表示每個用戶的需求量小于每輛車的裝載量；式(16)和式(17)表示每個配送點都會被服務(wù)到，且每個配送點只能被服務(wù)一次；式(18)表示車輛配送的貨物總量以每輛車的最大裝載量為限；式(19)表示進(jìn)行服務(wù)的車輛數(shù)不得超過總車輛數(shù)；式(20)表示每輛車從配送中心出發(fā)、返回配送中心。

3 算法設(shè)計

本文研究以總成本最小為目標(biāo)的車輛路徑優(yōu)化問題，該問題屬于NP-hard問題，對于此類問題，啟發(fā)式算法[28-39]被廣泛地應(yīng)用，其中蟻群算法采用分布式并行計算機(jī)制，有自組織性、正反饋性與較強的魯棒性，可以使問題在較短的時間內(nèi)找到較為滿意的可行解。但其搜索時間長且算法容易早熟，從而導(dǎo)致結(jié)果陷入局部最優(yōu)。因此，本文設(shè)計改進(jìn)型蟻群算法，將傳統(tǒng)蟻群算法與局部搜索算法相結(jié)合進(jìn)行兩元素化(2-optimization, 2-opt)操作，并賦予信息素濃度上下限，以防止算法由于早熟影響優(yōu)化效果。

3.1 蟻群算法原理

蟻群算法是由意大利學(xué)者Dorigo[40]等于20世紀(jì)90年代初提出的一種模擬進(jìn)化算法，其真實地模擬了自然界螞蟻群體的覓食行為，基本蟻群算法流程如圖3所示。

3.2 算法改進(jìn)

基本蟻群算法存在搜索時間長、易陷入局部最優(yōu)和出現(xiàn)停滯現(xiàn)象等缺陷。在進(jìn)行全局信息素的更

新過程中，為避免搜索停滯和過早收斂于非全局最優(yōu)解，將每條邊的信息素濃度限制在[τmin,τmax]之內(nèi)。小于τmin的信息素值賦值為τmin，大于τmax的信息素值賦值為τmax，可以有效避免由于某條路徑的信息素濃度過大而吸引所有螞蟻迅速聚集導(dǎo)致搜索停滯，進(jìn)而提高搜索速度[41]，信息素上下限取值公式如下：

(21)

(22)

其中：σ為第t次迭代的最優(yōu)解個數(shù)，C(t)為第t次迭代所得最優(yōu)解的成本值。

對于所有螞蟻遍歷之后得到的單次最優(yōu)解，使用2-opt局部領(lǐng)域搜索[42]進(jìn)行調(diào)整優(yōu)化，進(jìn)一步優(yōu)化已求得的最優(yōu)解，擴(kuò)大解的搜索空間，改善種群信息結(jié)構(gòu)，幫助算法大概率跳出局部最優(yōu)解，提高算法搜索能力。改進(jìn)型蟻群算法流程如圖4所示。

基于此，本文在傳統(tǒng)蟻群算法中引入信息素上下限與鄰域搜索機(jī)制后，算法改進(jìn)步驟如下：

步驟1初始化參數(shù)。初始化客戶時間窗數(shù)據(jù)，客戶間距離dij，客戶需求量Qi。迭代次數(shù)Nc=0，最大迭代次數(shù)Ncmax，客戶數(shù)量n，確定螞蟻數(shù)量m，以及參數(shù)α、β、ρ的取值。

步驟2創(chuàng)建禁忌表，將m只螞蟻全部放置于配送中心。

步驟3在滿足車輛載重限制和時間窗約束的前提下，每只螞蟻根據(jù)以下公式計算的轉(zhuǎn)移概率與碳排放量來選擇下一個待訪問客戶，ηij=1/Z。Z為車輛的配送成本，包括車輛自身的碳排放成本、制冷設(shè)備的碳排放成本、違反客戶時間窗所造成的懲罰成本。

(23)

步驟4在根據(jù)轉(zhuǎn)移概率選擇下一個客戶點時采用輪盤賭選擇策略[43]，避免選取選擇概率最大客戶點，有效避免在概率相近時忽略可能的最優(yōu)解。引入隨機(jī)可能性，有效防止過早收斂。

步驟5更新禁忌表，重復(fù)該過程，直至所有螞蟻都遍歷所有客戶點并返回配送中心。禁忌表更新滿足時間窗限制與車輛載重限制。

步驟6對單次最優(yōu)路徑及其成本C(0)使用2-opt方法進(jìn)行鄰域搜索，交叉得出路徑所對應(yīng)的成本C(t)。

步驟7判定C(t)是否小于C(t-1)，是則輸出C(t)，否則輸出C(t-1)，當(dāng)t達(dá)到最大設(shè)定值時更新全局信息素，否則重回鄰域搜索循環(huán)，t=t+1。

步驟8所有螞蟻完成周轉(zhuǎn)后，對信息素進(jìn)行全局更新，同時為避免搜索停滯，把每條邊的信息素濃度限制在[τmin,τmax]之內(nèi)。信息素更新公式采用蟻周模型：

(24)

步驟9判斷是否滿足結(jié)束條件(連續(xù)5次不再產(chǎn)生更優(yōu)的解或已達(dá)到蟻群算法規(guī)定的迭代上限)；若不滿足，則返回步驟3開始新一輪循環(huán)，Nc=Nc+1。

步驟10收斂過程達(dá)到規(guī)定最大迭代次數(shù)后終止迭代，輸出最優(yōu)總成本及對應(yīng)配送路徑。

4 算例分析

4.1 已知條件

本文以長沙市某冷鏈中心作為配送中心，選取其10公里范圍內(nèi)的48個小區(qū)作為配送點。設(shè)配送中心編號為l0，48個配送點的編號分別為li，(i=1,2,…,48)。設(shè)定W為單位碳排放成本系數(shù)，W=0.04；固定值系數(shù)α0=1.576，α1=-17.6，α2=0.001 17，α3=36.067；β=0.075 1；θ=0.006 6；車輛行駛過程中車廂內(nèi)溫度為5℃，配送點進(jìn)行卸貨時車廂內(nèi)溫度升高0.7℃，利用公式T(K)=273.15+t(單位：℃)將攝氏溫度轉(zhuǎn)化為熱力學(xué)溫度，T1=278.15，T2=278.85；阿倫尼烏斯公式中Kmax=5×1 014(單位：s)，Ea=100(單位：kJ/mol)，R=8.314(單位：J/mol·K)。

如表2所示，選取其中10個配送點的坐標(biāo)(需求點1為配送中心)以及每個配送點的需求量、服務(wù)時間、客戶時間窗為例。每輛車的最大載重量為Q=15，車輛勻速行駛，速度為S=60 km/h。為了研究方便，本文以配送節(jié)點間的直線距離作為配送距離，并未考慮交通擁堵等路段實際因素。

表2 配送需求點及配送中心基本信息

4.2 運算結(jié)果

本文采用MATLAB R2014a編程軟件進(jìn)行求解，所用平臺基本信息如表3所示。

表3 實驗測試環(huán)境

編程語言為MATLAB語言。按照前文所描述的蟻群算法步驟進(jìn)行編程，以碳排放量成本及滿意度成本最低為目標(biāo)，將已知的需求點坐標(biāo)、需求量等代入程序，令信息素重要程度因子α=1，啟發(fā)函數(shù)重要程度因子β=3，信息素全局揮發(fā)因子ρ=0.4，螞蟻數(shù)量m=20，信息素釋放總量Q=15，最大迭代次數(shù)為200。進(jìn)行30次模擬仿真實驗后，最優(yōu)車輛路徑如圖5所示，總成本最優(yōu)值收斂情況如圖6所示。

傳統(tǒng)蟻群算法以最短距離為目標(biāo)輸出車輛最優(yōu)路徑，改進(jìn)型蟻群算法以碳排放成本與顧客滿意度成本最低為目標(biāo)輸出車輛最優(yōu)路徑。二者對比情況如表4所示。

表4 改進(jìn)前后路徑結(jié)果對比

改進(jìn)型蟻群算法下以最短距離為目標(biāo)的最終結(jié)果，改進(jìn)型蟻群算法下以考慮碳排放與顧客滿意度成本為目標(biāo)最終結(jié)果，橫向?qū)Ρ惹闆r如表5所示。傳統(tǒng)蟻群算法以考慮碳排放與顧客滿意度成本為目標(biāo)最終結(jié)果，改進(jìn)型蟻群算法下以考慮碳排放與顧客滿意度成本為目標(biāo)最終結(jié)果，縱向?qū)Ρ惹闆r如表6所示。

表5 模型改進(jìn)前后路程、成本、時間對比

表6 算法改進(jìn)前后路程、成本、時間對比

4.3 結(jié)果分析

從對比表4可以看出，改進(jìn)型蟻群算法下以考慮碳排放與顧客滿意度成本為目標(biāo)的車輛最優(yōu)路徑結(jié)果中，配送中心需要派遣7輛冷藏運輸車對48個需求點進(jìn)行配送，其路徑安排與傳統(tǒng)蟻群算法下以最短距離為目標(biāo)模型相比有很大差別。

從對比表5可以看出，以最短距離為目標(biāo)的模型與以考慮客戶滿意度時碳排放最低為目標(biāo)的模型的出車總數(shù)相同。與此同時，未考慮碳排放成本的配送路徑方案的總路程為103 250 m，考慮碳排放成本及滿意度成本方案的最優(yōu)車輛配送路徑所對應(yīng)的配送總路程為104 350 m，比未優(yōu)化前增加1.1%。最短距離目標(biāo)方案總路程并未明顯優(yōu)于考慮滿意度及碳排放成本方案的總路程。7輛冷鏈運輸車輛全勤時，以最小距離為目標(biāo)，總的碳排放量及滿意度相對成本為7 080 700，相比以碳排放成本最小為目標(biāo)時的總成本5 435 902增加了30.3%，后者明顯小于前者。最終方案總路程稍有增加，但配送總成本明顯下降。

從對比表6可以看出，在程序運行時間上，傳統(tǒng)蟻群算法耗時79.7 s，改進(jìn)型蟻群算法耗時76.2 s，算法收斂時間減少3.5 s?？偮烦碳疤寂欧艥M意度總成本都有所減少，2-opt幫助算法跳出局部最優(yōu)解，再次對解進(jìn)行了優(yōu)化。測試算例達(dá)到預(yù)期效果，優(yōu)化后的配送方案更符合低碳經(jīng)濟(jì)以及顧客滿意度的要求。

4 結(jié)束語

當(dāng)代社會低碳經(jīng)濟(jì)迅速發(fā)展，在物流企業(yè)降本增效的前提下，還需降低企業(yè)經(jīng)濟(jì)發(fā)展的環(huán)境代價，促進(jìn)物流與生態(tài)文明的協(xié)調(diào)發(fā)展。本文在考慮碳排放與客戶滿意度的前提下，針對當(dāng)前冷鏈配送過程中碳排放高而客戶滿意度低的問題，構(gòu)建了帶時間窗的冷鏈車輛配送模型，利用MATLAB編程求解模型?；趥鹘y(tǒng)蟻群算法收斂速度慢、易于早熟的特點，引入了信息素上下限與鄰域搜索操作，應(yīng)用改進(jìn)型蟻群算法對模型進(jìn)行求解優(yōu)化。實驗結(jié)果表明，改進(jìn)型蟻群算法具有更優(yōu)的運算效率與優(yōu)化效果。同時，以碳排放與客戶滿意度為目標(biāo)的車輛路徑優(yōu)化中，降低企業(yè)經(jīng)濟(jì)成本與節(jié)能減排并不沖突，所得配送方案更符合低碳經(jīng)濟(jì)以及企業(yè)發(fā)展的要求。本文研究為冷鏈物流配送企業(yè)在降能增效的要求下制定車輛配送路徑方案提供了參考，使得企業(yè)發(fā)展更符合打造綠色物流、發(fā)展綠色經(jīng)濟(jì)的要求。