基于雙層規(guī)劃模型的冷鏈物流網(wǎng)絡(luò)多目標(biāo)優(yōu)化

周梓渝，蔣惠園

（武漢理工大學(xué) 交通學(xué)院，湖北 武漢 430063）

1 引言

在冷鏈物流網(wǎng)絡(luò)優(yōu)化問題的現(xiàn)有研究中，陶帝豪[1]等分析了配送過程中的車輛固定成本、燃油成本、貨損成本及碳稅成本，并以上述總成本之和最小為目標(biāo)函數(shù)構(gòu)建數(shù)學(xué)模型，將全局人工魚群算法應(yīng)用到該模型中。運用Matlab 軟件對具體案例進(jìn)行求解。余寒[2]研究農(nóng)產(chǎn)品冷鏈總物流成本最小，采用非線性混合整數(shù)規(guī)劃模型對冷鏈物流網(wǎng)絡(luò)節(jié)點進(jìn)行優(yōu)化分析，并運用遺傳算法對算例求解。楊珺[3]等建立了整數(shù)規(guī)劃模型來解決電動汽車物流配送系統(tǒng)換電站的選址和路徑問題，并設(shè)計了兩階段啟發(fā)式算法來求解模型；周林[4]等研究了物流末端配送的個性化問題，考慮了送貨上門和客戶自取兩種方式，建立了多容量終端選址—多車型路徑多目標(biāo)優(yōu)化模型，并設(shè)計了一種兩階段模擬退火算法求解問題最優(yōu)解集。姚源果[5]等借助實時路況信息來分析農(nóng)產(chǎn)品冷鏈物流配送成本，建立總成本最小化的配送路徑優(yōu)化模型，并提出了在冷鏈配送中合理設(shè)置接駁點，建立了考慮實時路況和接駁點的冷鏈物流配送路徑優(yōu)化模型。運用蟻群算法進(jìn)行求解和實證分析。

在現(xiàn)有研究基礎(chǔ)上，本文將綜合考慮配送中心建設(shè)及操作成本、車輛成本、懲罰成本及貨損成本，構(gòu)建考慮時間窗的冷鏈物流配送中心選址及路徑優(yōu)化的雙層規(guī)劃模型，并設(shè)計改進(jìn)的遺傳算法，利用Matlab 軟件對實例進(jìn)行運行求解，以得到最優(yōu)解，為冷鏈物流網(wǎng)絡(luò)多目標(biāo)優(yōu)化問題提供理論依據(jù)。

2 模型構(gòu)建

2.1 模型假設(shè)

本文研究的帶時間窗的冷鏈物流網(wǎng)絡(luò)多目標(biāo)優(yōu)化問題屬于NP-hard 問題，故為了研究方便，對模型做出如下假設(shè)：

（1）本文只考慮一個供應(yīng)商，待選的配送中心數(shù)量不定，并給多個終端零售商提供服務(wù)。

（2）由于冷鏈?zhǔn)称返姆N類比較多且性質(zhì)不同，為研究方便本文只選取單一品種。

（3）從供應(yīng)商到配送中心過程中采用統(tǒng)一標(biāo)準(zhǔn)的車輛，供應(yīng)商可由多輛車服務(wù)，但每輛車僅服務(wù)于一個配送中心。

（4）從配送中心到零售商過程中采用統(tǒng)一標(biāo)準(zhǔn)的車輛，每輛車只為一個配送中心服務(wù)，且在配送中心等候派遣的車輛數(shù)足夠多。

（5）一輛車可以為一個及以上的零售商供貨，它從所屬配送中心出發(fā)，最后再返回到配送中心。

（6）各節(jié)點距離均已知。

（7）每個終端零售商只有一輛車配送，且只配送一次。

（8）車輛在運輸過程中速度不變。

（9）所研究的冷鏈產(chǎn)品貨損只與配送時間有關(guān)。

（10）終端零售商的位置、需求量等已知，且都有時間窗限制，懲罰成本與時間為線性函數(shù)關(guān)系。

2.2 模型成本分析

2.2.1 配送中心建設(shè)成本及操作成本。本文研究的是配送中心租賃的方式，即建設(shè)成本為租金；配送中心所需要的人力、支付給工人的工資，以及在運作過程中借助的工具都劃分到操作成本中，由于每天的貨物量相差較小，故操作成本變動幅度較小，則配送中心的建設(shè)成本Ccr和操作成本Copr為：

式中：Fr表示在r處建立配送中心的成本；Zr表示是否在r 處建立配送中心；Fop表示配送中心的操作成本。

2.2.2 車輛成本

（1）車輛固定成本。車輛固定成本指在服務(wù)過程中冷藏車輛產(chǎn)生的固定成本，包括車輛的固定損耗、制冷設(shè)備的固定成本及駕駛員的工資等。車輛固定成本Cfc為：

式中：Ck表示車輛k的固定使用成本；Xk表示車輛k是否被使用。

（2）車輛運輸成本。本文所研究的車輛運輸成本主要包括供應(yīng)商到配送中心之間的運輸成本和配送中心到終端零售商之間的運輸成本。

供應(yīng)商到配送中心之間的運輸成本Ctcp為：

式中：Cpr表示車輛從供應(yīng)商p到配送中心r的單位運輸成本；dpr表示供應(yīng)商p 到配送中心r 的距離；Zr表示是否在r處建立配送中心。

配送中心到終端零售商之間的運輸成本Ctc為：

式中：Csi表示車輛從配送中心（或零售商）到零售商之間的單位距離運輸成本；dsi表示配送中心（或零售商）到零售商的距離；表示車輛k是否從配送中心（或零售商）向零售商配送。

2.2.3 懲罰成本分析。本文采用軟時間窗來研究配送中心選址及車輛路徑優(yōu)化問題，假設(shè)懲罰成本具有線性趨勢。[ETi,LTi] 為配送中心將貨物運送至零售商i 的最佳服務(wù)時間窗，若產(chǎn)品在ETi之前或LTi之后送達(dá)，配送中心需支付一定的懲罰成本。運輸車輛的提前或延誤程度越大，懲罰成本將會呈直線性增大。將懲罰成本函數(shù)pi（si）定義為：

因此，產(chǎn)生的懲罰成本為：

式中：si表示車輛到達(dá)零售商i的時間；c1表示車輛提前到達(dá)零售商發(fā)生的單位時間的機(jī)會成本；c2表示車輛超出規(guī)定時間到達(dá)零售商發(fā)生的單位時間的懲罰成本。

2.2.4 貨損成本分析。根據(jù)傳統(tǒng)的T.T.T 理論，假設(shè)冷鏈易腐產(chǎn)品在某一恒溫下，其變質(zhì)速率為一常數(shù)m，其質(zhì)量隨時間變化的曲線呈現(xiàn)出指數(shù)速度的變質(zhì)，變質(zhì)函數(shù)Q(t)如下：

其中，Q0為冷鏈?zhǔn)称烦跏紩r的質(zhì)量，t為時間，m是產(chǎn)品在某一恒定不變的溫度下變質(zhì)的一個常速變化值，β 代表冷鏈產(chǎn)品對時間的敏感系數(shù)，產(chǎn)品對時間越敏感，β取值越小，反之β值越大。

本文所研究的貨損分為兩部分：從供應(yīng)商到配送中心運輸過程中發(fā)生的貨損、從配送中心到各個零售商之間運輸發(fā)生的貨損。

從供應(yīng)商到配送中心的貨損成本為：

式中：θ1表示從供應(yīng)商運到配送中心時冷鏈產(chǎn)品的單位損耗成本；qr表示一個周期內(nèi)配送中心的需求量，即配送路徑上零售商需求量之和；β表示冷鏈產(chǎn)品對時間的敏感系數(shù)；tpr表示從供應(yīng)商p運到配送中心r用的時間。

從配送中心到終端零售商的貨損成本為：

式中：θ2表示從配送中心到零售商配送時冷鏈產(chǎn)品的單位損耗成本；qi表示一個周期內(nèi)零售商的需求量；tsi表示從配送中心（或零售商）到零售商配送所用時間；表示第k輛車是否從配送中心（或零售商）向零售商配送；Yri表示零售商i 是否由配送中心r提供配送服務(wù)。

2.3 模型構(gòu)建

2.3.1 上層模型構(gòu)建。上層模型目標(biāo)函數(shù)如下：

式（11）表示目標(biāo)成本由運輸成本、配送中心建設(shè)成本、操作成本以及貨損成本組成；式（12）表示至少建立一個配送中心；式（13）表示配送中心的承載量要大于各個終端零售商的總需求量；式（14）表示條件的滿足狀態(tài)。

2.3.2 下層模型構(gòu)建。下層模型目標(biāo)函數(shù)如下：

式（15）表示目標(biāo)函數(shù)由車輛成本、貨損成本、違反時間窗產(chǎn)生的懲罰成本組成；式（16）表示一個零售商只由一輛車配送；式（17）表示運輸車輛的起止點均為配送中心；式（18）表示車輛的運輸量不得超過其承載量；式（19）表示每輛運輸車輛采用巡回配送方式，即到達(dá)某一零售商的車輛直接出發(fā)運往下一個零售商；式（20）表示每一運輸車輛最多只屬于一個配送中心；式（21）表示任意兩個配送中心之間不會有車輛運輸，即不存在配送關(guān)系；式（22）表示到達(dá)零售商的時間窗限制；式（23）-式（26）表示條件的滿足狀態(tài)。

3 實例分析

本文以長沙市杰杰生鮮食品有限公司作為實例，運用遺傳算法對模型進(jìn)行求解，給出杰杰生鮮食品有限公司的配送中心選址及路徑優(yōu)化方案，并對結(jié)果進(jìn)行分析。

3.1 數(shù)據(jù)描述

3.1.1 節(jié)點位置信息。將各節(jié)點分別進(jìn)行編號，其中O1-O5表示各備選配送中心，1-20 表示生鮮超市。利用百度地圖測量各生鮮超市、備選配送中心和供應(yīng)商間的距離，見表1-表3。供應(yīng)商、配送中心、生鮮超市的位置信息如圖1所示。

表1 各生鮮超市間距離（單位：km）

表2 各生鮮超市間距離（單位：km）

表3 配送中心至各超市間距離（單位：km）

3.1.2 備選配送中心的容量與成本。根據(jù)各備選配送中心的地理位置及土地面積，備選配送中心的容量和基礎(chǔ)建設(shè)成本值見表4。

圖1 節(jié)點位置信息

表4 備選中心容量、與供應(yīng)商間距離和建設(shè)及操作成本

3.1.3 時間窗的設(shè)定。將各終端零售商的需求量和服務(wù)時間進(jìn)行整理，并根據(jù)客戶群體的不同設(shè)定不同的時間窗，見表5。

表5 終端零售商需求量、時間窗限制、服務(wù)時間

3.1.4 參數(shù)值的確定。從供應(yīng)商到配送中心間的車輛行駛單位成本以及車輛的固定使用成本等參數(shù)值見表6。

表6 各參數(shù)數(shù)值

3.2 模型求解

遺傳算法的基本思想和自身特點決定了它是一種解決選址與路徑優(yōu)化問題行之有效的方法，因此本文設(shè)計改進(jìn)的遺傳算法，先對上層模型進(jìn)行求解，根據(jù)所得到的配送中心對下層模型進(jìn)行求解得到相應(yīng)的配送路徑，經(jīng)過不斷地迭代最終使得兩階段實現(xiàn)協(xié)調(diào)優(yōu)化，最終得到的最優(yōu)解為問題的最佳方案。具體計算步驟如下：

（1）編碼與解碼操作。順序編碼的適用性較廣，用自然數(shù)的不同順序來編碼且不能重復(fù)，由于常見的二進(jìn)制編碼具有雜亂無序性，所以在求解冷鏈物流網(wǎng)絡(luò)多目標(biāo)優(yōu)化問題時經(jīng)常采用順序編碼。

（2）種群初始化。在求解實際問題時，初始種群的一般規(guī)模為20～200 個，本文假定初始種群規(guī)模為M=100。雖然已有研究表明，初始種群的選擇對于最優(yōu)解的影響不是很大，但如果初始種群能夠在解空間內(nèi)均勻分布，那么在計算過程中就不易陷入局部最優(yōu)解。因此本文對完全隨機(jī)產(chǎn)生初始種群的傳統(tǒng)方法進(jìn)行了改進(jìn)，充分考慮模型中對客戶時間窗的要求，以此來確定生成初始種群的方法，這樣不僅能夠使初始種群盡可能的平均分布在解空間內(nèi)，也能夠使初始種群的優(yōu)越性有所提升。具體步驟如下：

步驟一：按照客戶所要求的最晚時間從小到大的順序?qū)⑺锌蛻粢来闻判?，以此產(chǎn)生初始種群的首個染色體；

步驟二：按照隨機(jī)排列客戶的方法產(chǎn)生其余的染色體，共產(chǎn)生100條染色體，即100種方案。

（3）適應(yīng)度函數(shù)。本文中模型求解的最終目標(biāo)是使得冷鏈物流配送中心選址及路徑優(yōu)化的總成本達(dá)到最小，因此本文將適應(yīng)度函數(shù)設(shè)定為：

其中，F(xiàn)表示適應(yīng)度函數(shù)的初始值，F(xiàn)'表示經(jīng)過變換后產(chǎn)生的新的適應(yīng)度函數(shù)值。μ為一個隨機(jī)參數(shù)，取值范圍為（0,1）。

（4）遺傳操作。依次進(jìn)行選擇操作、交叉操作、變異操作。設(shè)定變異概率為0.1%，交叉概率為0.7%。

（5）兩邊逐次糾正。在染色體i上隨機(jī)選擇一條子路徑xl，再隨機(jī)選擇出該路徑上的兩個客戶xi1和xi2，將位置進(jìn)行交換，產(chǎn)生新的子路徑；比較交換前后目標(biāo)函數(shù)的大小變化，保留比較小的目標(biāo)函數(shù)值時的路徑作為新的子路徑。反復(fù)進(jìn)行此操作過程，直到染色體i中的所有子路徑都被更新為止。

（6）算法終止。本文通過設(shè)定預(yù)先迭代次數(shù)來達(dá)到控制算法的運行時間和精度的目的，在迭代次數(shù)超過預(yù)先設(shè)定的迭代次數(shù)時，算法自動停止，迭代次數(shù)設(shè)為200。

3.3 結(jié)果分析

本文利用改進(jìn)的遺傳算法對模型進(jìn)行求解，通過Matlab軟件運行后的上下層模型迭代曲線如圖2、圖3 所示，得到結(jié)果：最佳的配送中心為O1，此時企業(yè)的運行總成本可以達(dá)到最小，干線的運輸成本為500 326.90 元，支線的運輸成本為5 342.09 元，配送中心的處理量為67.3t/周期。根據(jù)配送中心O1所確定的8條車輛行駛路徑具體見表7。

通過最終得到的結(jié)果可以發(fā)現(xiàn)，每條配送路徑上所配送的生鮮超市數(shù)量并不相同。這是由于在設(shè)計每條配送路徑時，不僅要滿足配送中心的車輛載重量和生鮮超市的需求量，同時還要滿足生鮮超市所設(shè)定的時間窗限制。因此出現(xiàn)每條配送路徑上生鮮超市數(shù)量不同且數(shù)目不多的情況。

圖2 遺傳算法上層模型迭代曲線

圖3 遺傳算法下層模型迭代曲線

表7 車輛最優(yōu)行駛路徑

4 結(jié)語

本文在總結(jié)現(xiàn)有研究成果的基礎(chǔ)上，通過對冷鏈物流選址及配送過程中的各組成成本進(jìn)行分析，包括配送中心選址及操作成本、運輸成本、針對客戶滿意度的懲罰成本及貨損成本，建立考慮時間窗的冷鏈物流配送中心選址及配送路徑優(yōu)化的雙層規(guī)劃模型，然后通過設(shè)計改進(jìn)的遺傳算法對模型求解，最后以實例驗證模型的可靠性。本文仍有需要繼續(xù)研究之處：（1）考慮碳排放成本情況下冷鏈物流選址及路徑的選擇；（2）配送車輛及配送種類不固定情況下冷鏈物流選址及路徑的選擇。