帶軟時間窗的冷鏈物流配送路徑優化研究

俞武揚，楊沈記

（杭州電子科技大學 管理學院，浙江 杭州 310018）

帶軟時間窗的冷鏈物流配送路徑優化研究

俞武揚，楊沈記

（杭州電子科技大學 管理學院，浙江 杭州 310018）

消費者對生鮮產品的需求不斷增加，促進了城市冷鏈物流的快速發展。文章分析了冷鏈車的能耗成本和貨損成本，并將運輸過程和卸貨過程分開進行考慮，以總成本最低為目標建立了帶軟時間窗的優化模型。針對具體模型特點設計遺傳算法進行求解，最后結合具體實例進行仿真試驗，遺傳算法所得配送線路方案比原有掃描法配送方案成本明顯更低，從而驗證了模型和算法的有效性。

冷鏈物流；路徑優化；軟時間窗；遺傳算法

一、引言

消費者對生鮮產品的需求不斷增加，促進了城市冷鏈物流的快速發展。據《2015中國冷鏈物流發展報告》所述，我國冷鏈物流總需求量已經連續三年超過15%的增長率，按此趨勢估計，城市冷鏈物流發展空間巨大。冷鏈物流是指冷藏冷凍類生鮮產品在物流過程（包括生產、存儲與運輸配送等環節）中始終處于規定低溫環境，從而保證產品品質的特殊物流[1]。冷鏈物流配送問題是在著名學者Dantzig和Rasmer[2]提出的車輛路徑問題（Vehicle Routing Problem，VRP）的基礎之上，結合時間窗約束、能耗成本和貨損成本等因素構建而成。

本文研究的就是冷鏈物流的路徑優化問題，目前對該方面的研究，國內外諸多學者已取得了一系列相應成果：在國外，Lidija Zadnik等[3]研究了帶時間窗約束的農產品冷鏈配送優化問題；Pedro Amorim等[4]研究了葡萄牙食品配送VRP問題，但是研究過程中沒有考慮貨損的因素；J Brito等[5]研究了在不確定時間分布情況下冷凍食品的模糊車輛路徑問題，通過軟計算方法得到最優解；近年來，由于城市交通狀況復雜度越來越高，城市生鮮食品配送運輸條件越發嚴峻，導致末端各種問題不斷顯現，Song BD，Ko YD等[6]研究了城市易腐食品的末端配送問題，在配送需求位置與數量已知，配送供應中車輛的數量與規格確定的情況下，以最優服務效率為目標研究了普通貨車與冷藏車混合配送優化問題。在國內，李雅萍[7]研究了帶時間窗的鮮活農產品冷鏈物流VRP成本模型；邵舉平、曹倩等[8]為提高生鮮農產品物流配送效率，建立了最大化顧客滿意度以及最小化配送成本的多目標優化模型，并設計了基于遺傳算法的求解方法；姚寶珍等[9]在研究西餐廳連鎖店的路徑優化路線時，為滿足各連鎖店時間窗的約束建立了帶時間窗的VRP模型，然后運用啟發式算法對模型進行求解，并且用經典案例檢驗了算法性能，最后將文章提出的算法求解實際的大連市連鎖西餐廳配送路線；葛顯龍等[10]在VRP的基礎上充分考慮配送損耗等因素建立帶時間窗的生鮮損耗配送模型，針對模型的特征設計自適應的遺傳算法對模型求解。

從目前的研究來看，學者們在生鮮農產品配送與車輛路徑問題的結合進行了較多的研究，但對冷鏈物流的研究相對還不夠完善；由于冷鏈物流配送所配送貨物具有較強的易腐性，因而在配送的時效性方面要求比較高，并且還需要配備特殊的冷藏保鮮設備，因此決策過程所涉及的因素更加復雜多樣，模型求解難度更大。本文將軟時間窗加入到冷鏈物流配送中，考慮冷鏈車的能耗成本和貨損成本，并將運輸過程和卸貨過程分開進行考慮，以總成本最低為目標建立數學模型，針對具體模型特點設計自適應遺傳算法進行求解，最后結合具體實例進行仿真試驗，并將優化后的冷鏈配送中心的配送線路方案與傳統掃描法所得方案進行對比，從而驗證算法和模型的有效性。

二、問題描述與模型構建

（一）問題描述

本文研究的帶軟時間窗冷鏈物流配送路徑優化問題為：在給定區域內，一個冷鏈配送中心給若干客戶進行冷鏈產品的配送服務，配送中心和客戶的地理位置已知，不同客戶的需求量和可接受的服務時間段存在差異，要求合理安排冷鏈車的配送路徑使得貨物能在客戶可接受的時間段內到達，并使總配送成本最小。

為了簡化研究問題，這里認為配送的冷鏈貨品腐敗率一致并且問題需滿足以下約束假設：（1）配送中心擁有固定數量的冷鏈車，車輛車型一致；（2）所有的冷鏈車必須從配送中心發出并最終回到配送中心；（3）每位客戶的需求量大于零且小于冷鏈車最大載重；（4）每位客戶的需求必須得到滿足且只能由同一輛車進行配送服務；（5）配送任務需要在客戶指定時間段內完成；（6）客戶點和配送中心的位置距離滿足三角不等式；（7）不考慮交通擁堵等情況，配送過程中冷鏈車勻速行使；（8）配送中心貨物充足，車輛每次配送任務不會出現超載情況；（9）配送過程中冷鏈車能夠始終保持貨品所需溫度，車內溫度不變；（10）不考慮貨品在配送中心的裝貨時間及貨損。

（二）模型構建

1.參數與變量設置。模型所需的參數與變量說明如表1所示：

表1 參數與變量說明

2.數學模型。根據問題的描述，帶軟時間窗的冷鏈物流配送路徑優化的數學模型可表示為：

模型中的目標函數（1）表示的是：冷鏈車的固定成本、車輛行使的運輸成本、超載懲罰成本、早到等待成本、晚到懲罰成本、運輸過程中的能耗成本與貨損成本、卸貨過程的能耗成本與貨損成本；約束（2）表示每個客戶只能由一輛車配送；約束（3）確保配送任務覆蓋所有客戶；約束（4）、（5）表示變量之間的關系；約束（6）表示配送時間數量關系；約束（7）、（8）表示變量的定義。

三、算法設計

遺傳算法是一種基于群體遺傳進化機制的自適應全局優化算法。本文針對帶軟時間窗的冷鏈車輛配送問題特點設計了如下遺傳算法。

（一）染色體編碼

本文采用的是自然數編碼方式進行編碼，配送中心編號為1，冷鏈配送中心同時使用M輛冷鏈車給多個客戶點（編號為2，3，…，N）進行冷藏商品配送，最后又回到配送中心。染色體長度為N+M+1，一條染色體表示一種配送方案，如染色體“128415631791”表示3輛冷鏈車給8個客戶點（編號為 2，3，…，9）配送。路徑 1：配送中心 1→客戶2→客戶8→客戶4→配送中心1；路徑2：配送中心1→客戶5→客戶6→客戶 3→配送中心1；路徑3：配送中心1→客戶7→客戶9→配送中心1。

（二）初始化染色體

本文設計了一種考慮每條路徑中冷鏈車最大載重量限制的初始化染色體方法：

步驟1：染色體第一個基因位置設為配送中心1，然后給編號為2至N的N-1個客戶點隨機排序。

步驟2：從染色體基因1后的客戶點開始遍歷，對客戶點需求量進行累計求和，如果冷鏈車的最大承載重量Q大于前s個客戶點需求量之和且小于前s+1個客戶點需求量之和，則在第s個客戶點后插入配送中心基因1，并記錄插入次數num。

步驟3：遍歷染色體新插入基因1后面的客戶點。也就是從第s+1個客戶點起重新進行遍歷操作，重復步驟2以獲得第2條路徑配送的客戶點；如此反復安排所有客戶點的配送路徑。

步驟4：如果步驟3中新遍歷的客戶點總需求量小于最大承載重量Q，則直接在最后插入配送中心1，此時可得到一條初始染色體。

現有8個客戶點的隨機排序：“35786924”，如圖1所示可得到一條初始染色體：“135178619241”。

圖1 初始染色體生成示例

（三）交叉與變異算子

遺傳算法中最具特色的機制即其中的交叉算子和變異算子，通過這兩種算子實現了對生物進化的模擬。由于設計的編碼含有多個配送中心基因“1”以及客戶為自然數編碼，普通的交叉及變異方式易產生不可行解，因此本文設計了如下保證可行性的兩種算子：

（1）交叉算子：對于所選中的兩個父代染色體，去除表示配送中心的基因項“1”后將它們還原成為關于客戶2至N的兩個排列，隨機選中兩個點位，由兩個父代染色體生成兩個子代染色體，各自繼承父代中兩點位之間的基因不變，而兩點位外的基因則由另一個父代染色體排除已繼承基因后依次填入空位即得，然后再利用初始化染色體的方法重新插入配送中心基因項“1”生成兩個可行的子代染色體。該交叉過程示例如圖2所示。

圖2 交叉算子示例

（2）變異算子：對于選中的父代染色體，同樣先去除表示配送中心的基因項“1”后還原成關于客戶2至N的一個排列，然后隨機選擇其中兩個基因進行互換，再利用初始化染色體的方法重新插入配送中心基因項“1”生成可行的子代染色體。

（四）其余條件

（1）適應度函數，適應度用于評價配送方案的好壞程度，染色體（即表示配送方案）適應度值越大，該配送方案保留下來的概率也越大。由于目標函數是求解總成本最小的配送方案，因此設定適應度函數f為目標函數Z的倒數，f=1/Z。

（2）選擇機制，根據各個個體的適應度，按照輪盤賭方法從第t代種群P（t）中選擇出優良的個體遺傳到下一代種群P（t+1）中。

（3）算法終止條件，以事先給定的最大迭代次數作為算法終止條件。

四、實驗與仿真分析

（一）實例描述

杭州某冷鏈配送中心擁有同一車型冷鏈車6輛，車輛最大載重為3.6噸，需要向周邊區縣的14個大型超市配送某種冷藏商品，根據前面建模數據，配送中心標號為1，其余14個客戶點標號為2至15，配送中心和各客戶點的位置坐標、客戶點的需求信息、服務時間和時間窗約束均如表2所示。

表2 各客戶點配送相關信息（#表示編號）

根據一般冷鏈配送標準，每輛冷鏈車完成一次配送任務平均固定成本C1為300元；冷鏈車行駛速度平均為50 km/h，每公里的運輸成本為C2為3元/km；車門不開和車門打開時單位溫差時單位時間發生的熱負荷為 H1、H2分別為 60 kCal/h和80 kCal/h，單位熱負荷產生的成本P1為0.4元/kCal；冷藏商品價格 P2為 12 000元 /t，車門關閉和車門開啟時貨損率分別為σ1=0.3%，σ2=0.5%。配送中心每天早上5點統一發貨，從發貨時間開始計算，冷鏈車從配送中心出發，最后又回到配送中心，選擇使得總成本最小的配送路線方案。

（二）遺傳算法優化方案

針對上面的實例數據，設定種群規模為NIND=100，算法迭代終止代數為MAXGEN=300，自適應交叉概率 Pc=0.7，變異概率 Pm=0.3，代溝 GGAP=0.9；超載懲罰系數設為δ=10000；提前到達等待成本系數為θe=400，遲到的懲罰成本系數為θl=500。根據算法結合MatlabR2014a編制程序共運行10次，其中有9次得到最優配送方案，平均配送距離為1 071.56 km，平均配送總成本為6 836.94元，平均計算時間為7.30秒。最優配送方案如下：使用5輛冷鏈車進行配送，總行駛距離為1 059.18 km，最優配送總成本為6 785.7元，求得最優配送路線方案如圖3所示。

每個配送環路表示由一輛冷鏈車進行配送，最優方案有5條子路徑，各子路徑配送數據見表3。算法中染色體種群進化過程如圖4所示，從圖中曲線可知，在算法運行開始曲線下降速度較快表明算法尋優速度較快；隨后曲線變化趨于緩和，種群中個體值逐漸開始收斂，最后在接近70代左右收斂到問題的最優解。

圖3 最優配送路線方案

圖4 遺傳算法進化圖

表3 最優配送方案各子路徑數據

（三）掃描法優化方案

目前該冷鏈配送中心主要采用掃描法再結合客戶點時間窗要求進行冷鏈車路徑規劃。具體操作方式如下：以冷鏈配送中心為中心點，再選取任意一個最早需配送的客戶點為起始點，這里選取的是客戶點9；沿這兩點畫一條射線順時針方向旋轉，以車輛容量為分群約束進行客戶點的掃描分群，然后在每個分群考慮客戶點的時間窗要求安排車輛配送的先后順序，直到將所有客戶點安排好路線。利用掃描法結合客戶點時間窗要求，配送中心使用6輛冷鏈車進行任務配送，路線安排如圖5所示。

圖5 配送中心利用掃描法進行路線規劃的方案

掃描法所得配送方案總行駛距離為1 115.57 km，方案總成本為9 060.8元，各配送子路徑數據如表4所示。

表4 配送子路徑結果數據（掃描法）

（四）方案比較

目前大部分中小型配送企業主要是采用掃描法對配送路線進行安排規劃，這種方法主要是注重對配送距離的考慮，對于有時間窗的配送任務很難考慮全面，如表5用掃描法安排帶時間窗的配送任務往往會使得時間窗懲罰成本很高，最終總成本增加。本文設計的遺傳算法在求解帶軟時間窗的冷鏈物流路徑優化問題時能夠同時考慮時間窗約束、運輸總距離、冷鏈車能耗成本和貨損成本，能夠找到總配送成本最優的冷鏈車配送方案。兩種方法相比較而言，遺傳算法具有明顯優勢總成本節約了2 275.1元，從而驗證了本文算法的有效性。

表5 優化結果比較

五、小結

本文研究了帶軟時間窗的冷鏈物流路徑優化問題，在帶時間窗VRP問題基礎上考慮了冷鏈車的能耗成本和貨損成本，并將運輸過程和卸貨過程分開進行考慮，建立了以總成本最低為目標的數學模型，針對具體模型特點設計了遺傳算法進行求解，最后結合實例進行仿真試驗。仿真結果表明，本文設計的算法在求解冷鏈物流路徑優化問題時比掃描法具有明顯優勢，能夠有效解決冷鏈物流路徑優化問題。

[1]馬向國，劉同娟，楊平哲，等，2016.基于隨機需求的冷鏈物流車輛路徑優化模型[J].系統仿真學報（8）：1824-1832.

[2]DantzigGB，Ramser J H.The Truck DispatchingProblem[J].Management Science，1959，6（1）：80-91.

[3]Osvald A，Stirn L Z.A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food[J].Journal of Food Engineering，2008，85（2）：285-295.

[4]Amorim P，Parragh S N，Sperandio F，et al.A rich vehicle routing problem dealing with perishable food：a case study[J].TOP，2014，22（2）：489-508.

[5]Brito J，Martinez F J，Moreno J A，et al.Fuzzy optimization for distribution of frozen food with imprecise times[J].Fuzzy Optimization and Decision Making，2012，11（3）：337-349.

[6]Song B D，Ko Y D.A vehicle routing problem of both refrigeratedand general-type vehicles for perishable food products delivery[J].Journal of Food Engineering，2016，169：61-71.

[7]李雅萍，2013.鮮活農產品冷鏈物流配送路徑優化研究[J].價值工程（31）：25-27.

[8]邵舉平，曹倩，沈敏燕，等，2015.生鮮農產品配送中帶時窗的VRP模型與算法[J].工業工程與管理（1）：122-127.

[9]姚寶珍，楊成永，張強，等，2010蟻群算法在西餐連鎖店配送路徑中應用[J].北京交通大學學報（6）：51-55.

[10]葛顯龍，孔陽，2016.帶有時間窗的生鮮物流配送路徑優化研究[J].數學的實踐與認識（12）：78-87.

（責任編輯：D 校對：R）

F252.8

A

1004-2768（2017）06-0067-04

2017-03-22

浙江省哲學社會科學規劃項目（17NDJC053YB）；教育部人文社會科學青年基金項目（13YJC630177）

俞武揚（1974-），男，博士，杭州電子科技大學管理學院副教授，研究方向：物流建模與優化計算、應急管理等；楊沈記（1992-），男，杭州電子科技大學管理學院碩士研究生，研究方向：物流配送優化。