張亞明，李艷明，劉海鷗

（燕山大學(xué) 經(jīng)濟(jì)管理學(xué)院，河北 秦皇島 066004）

0 引言

目前,針對冷鏈物流VRP調(diào)度優(yōu)化方面的研究[1-9]仍然處于初級階段，主要集中在優(yōu)化VRP模型或改進(jìn)求解算法方面。在優(yōu)化模型上：一方面，關(guān)于多車型冷鏈VRP模型目標(biāo)成本構(gòu)成分析不夠全面，少有文獻(xiàn)考慮多車型冷鏈VRP問題；另一方面，基于冷鏈物流特性，顧客滿意度主要由配送時間及品質(zhì)兩因素約束，而文獻(xiàn)大多集中在時間窗的考慮，少有文獻(xiàn)在構(gòu)建多車型模型時將時間與品質(zhì)同時考慮進(jìn)顧客滿意度約束中。在改進(jìn)算法上，傳統(tǒng)遺傳算法的尋優(yōu)效率也劣于單親遺傳算法。因此，本文在模型上，根據(jù)阿倫尼烏斯方程推導(dǎo)貨損成本，利用冷藏車制冷及操作原理計算能源成本，運用投入產(chǎn)出法計算碳排放成本，并得到時間及品質(zhì)的滿意度函數(shù)作為約束條件之一，建立更加貼近實際的多車型冷鏈VRP模型；在算法優(yōu)化上，采用改進(jìn)的基于局部精英保留策略的單親遺傳算法進(jìn)行求解，量化分析單車型配送和多車型配送時的成本差異，以探究多車型在冷鏈調(diào)度中的優(yōu)勢，同時得到顧客滿意度在成本優(yōu)化過程中的變化趨勢，為企業(yè)尋求成本和滿意度均衡提供理論參考。

1 滿意度約束冷鏈物流VRP模型構(gòu)建

1.1 問題描述及假設(shè)

首先，滿意度約束冷鏈物流VRP問題旨在保證顧客滿意度不低于一定水平的情況下，尋求最優(yōu)綜合成本，允許犧牲一定的成本來提高滿意度。VRP問題中影響顧客滿意度的主要因素是配送準(zhǔn)時性與產(chǎn)品品質(zhì)；其次，顧客對生鮮品的需求差異較大（如對瓜果、蔬菜的需求量較大，而對肉、蛋、奶、海鮮的需求量較小），若運用單一車型完成配送，極有可能使其非滿載運行，導(dǎo)致配送成本上升[10]。因此，模型選擇多車型配送模式是可行的；最后，冷鏈物流是整個物流系統(tǒng)中能源消耗與碳排放量都極高的產(chǎn)業(yè)，這與當(dāng)前主張“低碳經(jīng)濟(jì)”的宗旨發(fā)生沖突。因此，在模型中加入低碳因素是大勢所趨。綜上所述，模型構(gòu)建需要解決的問題是：如何在多車型模式中合理調(diào)度車輛，規(guī)劃路徑，在最大程度滿足顧客情況下，使總配送成本最低。問題假設(shè)如下：

（1）一個配送中心且貨源足夠，多輛不同型號的冷藏車；

（2）顧客需求量總和不超出車載容量限制；

（3）冷藏車行駛速度均為勻速；

（4）配送任務(wù)只涉及貨物的配送，即單向流向；

（5）配送車輛要求必須從配送中心發(fā)出并返回；

（6）客戶均被服務(wù)且僅接受一次服務(wù)，已知所有客戶的地理位置、需求量、接受服務(wù)時間范圍并固定不變；

（7）冷藏貨物的品質(zhì)僅與溫度及配送時間有關(guān)；

（8）員工工資計入調(diào)用每輛冷藏車的固定費用中；

（9）卸貨速度均相同且為勻速。

1.2 符號描述

（1）標(biāo)號

N{n|n=1,2,…,N}為顧客集合；K{k|k=1,2,…,K}為配送車輛集合；L{l|l=1,2,…,L}為配送車型集合。

（2）參數(shù)

Q為車輛最大載重；qi為顧客的需求量；v為車輛平均行駛速度；dij為顧客i到j(luò)之間的距離；pf為每輛車的固定費用；pc為車輛每公里運輸費用；c1、c2分別為單位時間車輛等待和遲到產(chǎn)生的成本；[EETi,LETi]為顧客最大接受服務(wù)的時間范圍；[ETi,LTi]為顧客期望被服務(wù)的時間范圍；Hti為車輛在顧客i的卸貨時間；ce為單位制冷成本；C為消耗每單位CO2排放量的環(huán)境成本；u為柴油的CO2排放系數(shù)；f為每公里燃油消耗量；P為損失貨物的單位懲罰成本；ω1、ω2分別為時間滿意度和品質(zhì)滿意度的權(quán)重；l為顧客滿意度的最低值；m為l型車輛為l型車輛的第m輛服務(wù)的顧客數(shù)量為l型車輛的第m輛服務(wù)的第j個顧客。

（3）變量

ti為車輛到達(dá)顧客i的時間；L(tj)為顧客j對送貨時間的滿意度；Dtj、Htj、Wtj分別表示車輛到達(dá)客戶 j時的累積運輸時間、處理時間、等待時間；s1、s2表示顧客的平均時間滿意度和平均品質(zhì)滿意度；s表示顧客總體滿意度。

1.3 冷鏈物流成本

總成本包括車輛固定、運輸、時間、貨損、能源與碳排放成本，此處只分析貨損、能源與碳排放成本。

1.3.1 貨損成本

冷鏈物流的貨損成本主要受時間和溫度兩個因素影響。一方面，生鮮品隨時間積累而腐壞變質(zhì)；另一方面，由于對溫度的高度敏感，裝卸過程中的溫度變化，使得生鮮品腐壞變質(zhì)。

根據(jù)化學(xué)家阿倫尼烏斯提出的反應(yīng)速率常數(shù)與溫度之間關(guān)系的方程推導(dǎo)得出未變質(zhì)率貨損成本DC可表示為：

1.3.2 能源成本

能耗成本主要指制冷機組工作所需的油耗及其在正常工作中的不可逆損失。卸貨過程中，根據(jù)冷藏車運輸操作流程，以及呂寧等人的研究結(jié)論（開門過程中，制冷機組對冷藏車內(nèi)空氣溫升的抑制作用不大[12]）可知，制冷機組需關(guān)閉，因此卸貨過程不計能耗；運輸過程中，為保持車廂內(nèi)適宜溫度，制冷機組開啟，產(chǎn)生能耗成本。本文研究中長距離運輸，宜使用獨立式制冷機組，即等待過程雖然冷藏車發(fā)動機熄火但制冷機組仍保持工作，產(chǎn)生能耗。綜上，能源成本EC可表示為：

1.3.3 碳排放成本

計算溫室氣體排放首要指標(biāo)即對CO2排放量進(jìn)行計算，這一指標(biāo)即為冷鏈物流配送過程中的平均溫室氣體排放量。CO2排放量計算基本原理是按照生命周期定義進(jìn)行演變，本文根據(jù)冷鏈物流VRP模型的特點，由劉宇等人的研究方法（投入產(chǎn)出法計算CO2排放量[13］），CEC計算公式為：

1.4 滿意度分析

顧客滿意度的限制約束有兩個，即時間滿意度和品質(zhì)滿意度。首先，建立時間滿意度函數(shù)。車輛須在顧客期望時間范圍內(nèi)進(jìn)行配送任務(wù)；超出期望時間且在最大接收服務(wù)時間范圍內(nèi)進(jìn)行配送任務(wù)時，時間滿意度與時間呈負(fù)相關(guān)；超出最大接收服務(wù)時間時，顧客拒絕服務(wù)?；诨旌蠒r間窗的時間滿意度（見圖1）。品質(zhì)滿意度影響因素主要由變質(zhì)率決定。顧客的總體滿意度是對兩個約束因素賦予一定權(quán)重相加得到。

圖1 基于混合時間窗的時間滿意度

則顧客滿意度可表示為：

2 單車型與多車型冷鏈VRP模型構(gòu)建

2.1 單車型

由以上分析可得單車型冷鏈VRP模型：

其中：式（5）表示冷鏈VRP總成本，各項分別為冷藏車調(diào)度成本、運輸成本、貨損成本、能源成本、碳排放成本、早到的等待成本與晚到的懲罰成本；式（6）為車輛載重限制；式（7）為配送中心車輛數(shù)限制；式（8）為前序節(jié)點唯一；式（9）為后序節(jié)點唯一；式（10）為顧客僅由一輛車服務(wù)一次；式（11）為每個顧客均被服務(wù)；式（12）為配送車輛只能在最大接受服務(wù)時間段內(nèi)到達(dá)；式（13）為抵達(dá)客戶i的時間即抵達(dá)i時的累積行駛與累積等待和累積卸貨三個時間之和；式（14）表示客戶對時間和品質(zhì)的整體滿意度不低于λ。

2.2 多車型

多車型配送成本與單車型的成本構(gòu)成相同，模型表示為：

模型除需滿足式（12）至式（14）外，還需滿足：

其中：式（15）表示冷鏈多車型VRP總成本，為目標(biāo)函數(shù)表示總成本最??；式（16）為車輛載重限制；式（17）確保車輛從配送點發(fā)出并返回；式（18）為每個顧客均被某種車型的車服務(wù)；式（19）為車流量守恒式，即對于每個顧客點進(jìn)入的車輛一定要離開。

3 改進(jìn)單親遺傳算法求解模型

在傳統(tǒng)遺傳算法TGA（Traditional Genetic Algorithm）中，其交叉算子為雙親，求解復(fù)雜模型時效率較低，并且具有“早熟收斂”的特點。單親遺傳算法PGA（Partheno Genetic Algorithm）是傳統(tǒng)遺傳算法的變形，在繁殖方式上為單親繁殖，即在單條染色體上進(jìn)行繁殖，改變了傳統(tǒng)遺傳算法的雙親式繁殖，采用自身內(nèi)部進(jìn)行染色體進(jìn)化的方式，初始群體質(zhì)量要求降低，較易生成初始解，不再采用交叉算子，優(yōu)化了傳統(tǒng)GA的弊端，加快了運行速度。

求解單車型VRP模型的遺傳算法設(shè)計同文獻(xiàn)[9]。多車型VRP求解涉及車型載重限制，問題復(fù)雜，進(jìn)行染色體編碼及種群初始化需考慮車型最大載重約束及顧客時間窗約束。

3.1 染色體編碼

本文選用“先路徑，后客戶”原理進(jìn)行染色體編碼，即以第一條路徑的首個訪問顧客點作為染色體的首個基因，之后對所有染色體編碼X=(x1,x2,…,xn)，均按照顧客訪問順序執(zhí)行。多車型冷鏈VRP模型單親遺傳算法染色體編碼的具體操作步驟為：

第一步：隨機選取一個顧客作為第k條染色體X的首個基因，X每更新一次，k+1。標(biāo)記車輛抵達(dá)第一個顧客時的時間以及所載貨物重量，從左向右依次將符合車載約束、顧客接受配送時間窗約束的顧客添加到當(dāng)前染色體中，并同步更新冷藏車的載重量及行駛時間；

第二步：對所有客戶按照上述約束條件進(jìn)行添加，構(gòu)成一條完整的滿足車載容量限制及時間窗約束的路徑k；

第三步：染色體X的顧客訪問順序保持不變，去除顧客點對應(yīng)基因，得到新的基因排列串Y，命為X；

第四步：對新的染色體X執(zhí)行第一步，產(chǎn)生第k+1條染色體。經(jīng)過多次循環(huán)操作，直到全部顧客點基因安排完畢，產(chǎn)生全部路徑。

3.2 種群初始化

初始種群作為種群進(jìn)化的初始步驟，是關(guān)鍵環(huán)節(jié)，選擇恰當(dāng)?shù)姆N群初始化方法有助于完成高速度收斂、高效率運行的算法操作。針對多車型VRP模型，算法的種群初始化具體如下：

第一步：根據(jù)車型匹配約束對全部顧客進(jìn)行分類排列。例如顧客點2、顧客點4均可由車型A完成配送任務(wù)，則將顧客點2及顧客點4排列一隊；當(dāng)顧客點能夠同時由多車型完成配送，則將該顧客點隨機分配在其所匹配車型隊列中；

第二步：生成初始種群首條染色體。按照時間窗下界的早晚順序依次排列，當(dāng)兩個顧客[EETi,ELTi]下界ELTi相同，則對其按照EETi早晚次序依次排序；

第三步：隨機生成剩余染色體。即顧客點隨機排列。

通過車型、顧客需求及時間窗的約束對顧客進(jìn)行訪問順序排列，從而得到一條較好的染色體，有助于算法在進(jìn)化初始有一個良好的起點。且剩余染色體采用隨機生成的方法能夠使初始種群的基因分布較為均勻，避免了解的偶然性。

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

在GA求解中，適應(yīng)度f越大的染色體，保留的可能性越大，目標(biāo)函數(shù)值Z則應(yīng)越小，因此適應(yīng)度f和總成本Z的關(guān)系呈負(fù)相關(guān)。本文將Zi代表第i條子路徑所產(chǎn)生的總成本，用fi=1/Zi作為適應(yīng)度。

3.4 遺傳算子設(shè)計

本文采用局部精英策略的單親遺傳算法算子設(shè)計，操作步驟同單車型。不涉及交叉算子及變異算子的概率，并且交叉和變異的基因位置為隨機抽取。操作流程為將局部最優(yōu)染色體先后分別進(jìn)行三種雙基因段交叉操作、單基因段變異操作、變異與交叉操作，從而得到7個子代。

4 實證分析

4.1 基本數(shù)據(jù)

設(shè)有30個客戶信息如表1所示，3種車型基本信息見表2。假設(shè)配送路程均使用直線距離，模型中參數(shù)設(shè)置為：v=60km/h，柴油價格為6.48元/升。u=2.68，C=0.25元。ce=50元/h；P=2000元/t。λ=0.6，ω1=ω2=0.5，c1=100元/h，c2=400元/h。

4.2 單車型冷鏈VRP求解

選用車型B完成配送服務(wù)。顧客總需求量為29.7噸，由于裝卸貨物復(fù)雜程度較高，取α=0.5，初始車輛k=11。經(jīng)試驗，融合概率merging_prob=0.4，種群規(guī)模pop_size=400，最大進(jìn)化代數(shù)num_iter=400時達(dá)到最優(yōu)，超載懲罰系數(shù)為1000，滿意度懲罰系數(shù)為10。

算法運行總時間為253.74s，最優(yōu)解首次出現(xiàn)在178代，平均滿意度為0.77。結(jié)果見圖2至圖4。

圖2 單車型冷鏈VRP結(jié)果圖

圖3 冷鏈VRP染色體進(jìn)化圖

表1 客戶信息

表2 3種冷藏車車型參數(shù)

圖4 冷鏈VRP滿意度曲線

4.3 多車型冷鏈VRP求解

由于車型由單車型增加到3種車型，種群規(guī)模也要隨之增加，經(jīng)試驗，融合概率merging_prob=0.4，種群規(guī)模pop_size=600，最大迭代次數(shù)num_iter=600時達(dá)到最優(yōu)。算法運行總時間為295.63s，最優(yōu)解首次出現(xiàn)在186代，平均滿意度為0.72。結(jié)果見下頁圖5至圖7。

圖5 多車型冷鏈VRP結(jié)果圖

圖6 多車型VRP染色體進(jìn)化圖

圖7 多車型VRP滿意度曲線

4.4 結(jié)果分析

由圖2及圖3看出，算法取得了較為滿意解，且收斂速度較快。圖4顯示，顧客滿意度總體趨勢為先升后降最終趨于較優(yōu)而非最優(yōu)，意味著企業(yè)在實際冷鏈配送過程中不能一味追求低成本而忽略顧客滿意度。

由圖5和圖6看出，算法在求解多車型冷鏈VRP也取得了較為滿意的結(jié)果，并具有較好的收斂性。圖7顧客滿意度曲線變化趨勢符合算法優(yōu)化過程。通過對比單車型和多車型求解結(jié)果（見表3），可以看出多車型目標(biāo)成本更低，雖然滿意度稍低，但已達(dá)到約束要求，且結(jié)果更加穩(wěn)定。由單車型和多車型各項成本對比發(fā)現(xiàn)，多車型較單車型除運輸成本稍高外，其他各項成本均明顯低于單車型，尤其是占據(jù)總成本比例最高的貨損和能源成本明顯有較大程度降低，建議企業(yè)面對大規(guī)模配送問題采用多車型配送模式。

5 結(jié)論

針對冷鏈配送特殊性，本文考慮基于時間和品質(zhì)因素的滿意度函數(shù)的約束條件以及選擇混合時間窗和具有多車型VRP問題進(jìn)行研究，建立了更加符合冷鏈物流特性的VRP模型，詳細(xì)分析了貨損成本、能源成本和碳排放成本。設(shè)計局部精英單親遺傳算法求解，驗證了該算法在求解VRP問題上具有一定的優(yōu)越性，量化分析了多車型冷鏈配送成本的優(yōu)勢，為企業(yè)在多車型配送模式的決策提供理論參考。同時，揭示了顧客滿意度在成本優(yōu)化過程中的變化趨勢，啟示企業(yè)在實際冷鏈配送過程中不能盲目追求低成本而忽略顧客滿意度，為后續(xù)深入研究成本與顧客滿意度的權(quán)衡提供參考價值。

表3 單車型和多車型結(jié)果對比