基于雙層規劃模型的冷鏈物流網絡多目標優化

周梓渝，蔣惠園

（武漢理工大學 交通學院，湖北 武漢 430063）

1 引言

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

在現有研究基礎上，本文將綜合考慮配送中心建設及操作成本、車輛成本、懲罰成本及貨損成本，構建考慮時間窗的冷鏈物流配送中心選址及路徑優化的雙層規劃模型，并設計改進的遺傳算法，利用Matlab 軟件對實例進行運行求解，以得到最優解，為冷鏈物流網絡多目標優化問題提供理論依據。

2 模型構建

2.1 模型假設

本文研究的帶時間窗的冷鏈物流網絡多目標優化問題屬于NP-hard 問題，故為了研究方便，對模型做出如下假設：

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

（2）由于冷鏈食品的種類比較多且性質不同，為研究方便本文只選取單一品種。

（3）從供應商到配送中心過程中采用統一標準的車輛，供應商可由多輛車服務，但每輛車僅服務于一個配送中心。

（4）從配送中心到零售商過程中采用統一標準的車輛，每輛車只為一個配送中心服務，且在配送中心等候派遣的車輛數足夠多。

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

（6）各節點距離均已知。

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

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

（9）所研究的冷鏈產品貨損只與配送時間有關。

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

2.2 模型成本分析

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

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

2.2.2 車輛成本

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

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

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

供應商到配送中心之間的運輸成本Ctcp為：

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

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

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

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

因此，產生的懲罰成本為：

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

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

其中，Q0為冷鏈食品初始時的質量，t為時間，m是產品在某一恒定不變的溫度下變質的一個常速變化值，β 代表冷鏈產品對時間的敏感系數，產品對時間越敏感，β取值越小，反之β值越大。

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

從供應商到配送中心的貨損成本為：

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

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

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

2.3 模型構建

2.3.1 上層模型構建。上層模型目標函數如下：

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

2.3.2 下層模型構建。下層模型目標函數如下：

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

3 實例分析

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

3.1 數據描述

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

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

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

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

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

圖1 節點位置信息

表4 備選中心容量、與供應商間距離和建設及操作成本

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

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

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

表6 各參數數值

3.2 模型求解

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

（1）編碼與解碼操作。順序編碼的適用性較廣，用自然數的不同順序來編碼且不能重復，由于常見的二進制編碼具有雜亂無序性，所以在求解冷鏈物流網絡多目標優化問題時經常采用順序編碼。

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

步驟一：按照客戶所要求的最晚時間從小到大的順序將所有客戶依次排序，以此產生初始種群的首個染色體；

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

（3）適應度函數。本文中模型求解的最終目標是使得冷鏈物流配送中心選址及路徑優化的總成本達到最小，因此本文將適應度函數設定為：

其中，F表示適應度函數的初始值，F'表示經過變換后產生的新的適應度函數值。μ為一個隨機參數，取值范圍為（0,1）。

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

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

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

3.3 結果分析

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

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

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

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

表7 車輛最優行駛路徑

4 結語

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