滿意度約束多車型冷鏈物流VRP優(yōu)化研究

張亞明，李艷明，劉海鷗

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

0 引言

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

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

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

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

（1）一個(gè)配送中心且貨源足夠，多輛不同型號(hào)的冷藏車；

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

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

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

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

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

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

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

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

1.2 符號(hào)描述

（1）標(biāo)號(hà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為每輛車的固定費(fèi)用；pc為車輛每公里運(yùn)輸費(fèi)用；c1、c2分別為單位時(shí)間車輛等待和遲到產(chǎn)生的成本；[EETi,LETi]為顧客最大接受服務(wù)的時(shí)間范圍；[ETi,LTi]為顧客期望被服務(wù)的時(shí)間范圍；Hti為車輛在顧客i的卸貨時(shí)間；ce為單位制冷成本；C為消耗每單位CO2排放量的環(huán)境成本；u為柴油的CO2排放系數(shù)；f為每公里燃油消耗量；P為損失貨物的單位懲罰成本；ω1、ω2分別為時(shí)間滿意度和品質(zhì)滿意度的權(quán)重；l為顧客滿意度的最低值；m為l型車輛為l型車輛的第m輛服務(wù)的顧客數(shù)量為l型車輛的第m輛服務(wù)的第j個(gè)顧客。

（3）變量

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

1.3 冷鏈物流成本

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

1.3.1 貨損成本

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

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

1.3.2 能源成本

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

1.3.3 碳排放成本

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

1.4 滿意度分析

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

圖1 基于混合時(shí)間窗的時(shí)間滿意度

則顧客滿意度可表示為：

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

2.1 單車型

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

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

2.2 多車型

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

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

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

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

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

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

3.1 染色體編碼

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

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

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

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

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

3.2 種群初始化

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

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

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

第三步：隨機(jī)生成剩余染色體。即顧客點(diǎn)隨機(jī)排列。

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

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è)計(jì)

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

4 實(shí)證分析

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

設(shè)有30個(gè)客戶信息如表1所示，3種車型基本信息見表2。假設(shè)配送路程均使用直線距離，模型中參數(shù)設(shè)置為：v=60km/h，柴油價(jià)格為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)試驗(yàn)，融合概率merging_prob=0.4，種群規(guī)模pop_size=400，最大進(jìn)化代數(shù)num_iter=400時(shí)達(dá)到最優(yōu)，超載懲罰系數(shù)為1000，滿意度懲罰系數(shù)為10。

算法運(yùn)行總時(shí)間為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)試驗(yàn)，融合概率merging_prob=0.4，種群規(guī)模pop_size=600，最大迭代次數(shù)num_iter=600時(shí)達(dá)到最優(yōu)。算法運(yùn)行總時(shí)間為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顯示，顧客滿意度總體趨勢(shì)為先升后降最終趨于較優(yōu)而非最優(yōu)，意味著企業(yè)在實(shí)際冷鏈配送過程中不能一味追求低成本而忽略顧客滿意度。

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

5 結(jié)論

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

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