王　咪，楊孔雨

（北京信息科技大學　信息管理學院，北京　100192）

?

基于2-Opt免疫遺傳算法的冷鏈配送路徑優(yōu)化問題研究

王咪，楊孔雨

（北京信息科技大學信息管理學院，北京100192）

分析了生鮮產品冷鏈配送的現(xiàn)狀，并指出了研究生鮮產品冷鏈配送路徑優(yōu)化問題的重要意義?？紤]配送過程中道路顛簸對于生鮮產品配送成本的影響，同時結合車輛固定成本、運輸成本、能源成本、懲罰成本、貨損成本等建立冷鏈物流車輛配送路徑優(yōu)化模型，并將2-Opt算法與免疫遺傳算法相結合對該模型進行求解，最后通過實例分析，證明該模型有效實用，為相關行業(yè)的發(fā)展和企業(yè)運營提供參考。

冷鏈；2-Opt；免疫遺傳算法；配送路徑優(yōu)化

1　引言

隨著生鮮電商如雨后春筍般崛起，生鮮電商的“O2B+O2O”時代已經到來，冷鏈物流成本越來越受到食品企業(yè)、快遞企業(yè)和電商企業(yè)的關注［1］。生鮮產品集易腐性、季節(jié)性、地域性、儲存保鮮條件要求高等特點于一身，造成其配送成本極其高昂，大約占到產品整體成本的70%［2］。這已經成為了冷鏈物流的短板之一，嚴重制約著生鮮電商的發(fā)展。影響冷鏈配送成本的因素主要有配送路線設計、配送時間、客戶對時間的要求等，正是這些不確定的因素，形成了成本迥異的配送方案，可見，車輛配送路徑的選擇對冷鏈成本的影響是重大的，對它的研究具有應用的廣泛性和經濟上的重大價值，受到國內外學者的廣泛關注。李宏研究城市冷鏈物流配送車輛運行時間和一天之中溫度變化的依時特性，對傳統(tǒng)冷鏈配送路徑模型進行改進，并運用時間導向最近鄰點法進行演算、求解并進行主要參數(shù)的敏感度分析［3］。何琴飛考慮道路暢通狀況，基于道路阻抗函數(shù)的相關理論，建立冷鏈配送路徑優(yōu)化的數(shù)學模型，分析比較得出道路暢通狀況對于冷鏈配送有重大影響的結論［4］；李亞男、劉聯(lián)輝等基于城市發(fā)展理念，以碳排放為約束條件，構建冷鏈物流配送網絡優(yōu)化模型，并根據配送運輸網絡模型求解的復雜性，使用遺傳算法得出優(yōu)化模型的最優(yōu)解［5］。

2　模型分析與建立

2.1問題描述

由于冷鏈物流車輛配送路徑中涉及到的因素比較多，配送中心需對配送車輛、路徑選擇、配送時間等作出合理安排，才能達到既使配送成本最小，又能使客戶滿意度最大化的目的。本文所描述的配送中心有K輛冷藏車，每輛冷藏車的固定成本Ck、耗油量、使用年限、載重、極限行駛里程Dis等相同。配送的貨物為單一類型，配送中心的缺貨率為零，時刻能夠滿足客戶的需求。假設該配送中心有n個客戶，且每一位客戶的需求量、地理位置、到貨時間窗要求等基本信息已知，配送中心安排冷藏車和裝卸人員為客戶配送，每輛冷藏車對應一條配送路徑，每輛車可服務多個客戶，每個客戶只能由一輛車服務，裝卸人員的裝卸貨速率一致。冷藏車從配送中心出發(fā)，最后返回配送中心。

2.2模型建立

2.2.1目標函數(shù)

（1）固定成本。通常要完成一次配送任務需要預計使用多少輛冷藏車，這樣做一是可以盡可能的節(jié)約成本，二是減少問題的約束，使組織路線更容易，更有彈性。一般來說，可以使用以下公式來確定車輛數(shù)：

Qi是客戶i本次配送的需求量；α是對裝（卸）車復雜度及約束的多少的估計參數(shù)（0＜α＜1），一般來講，裝（卸）車越復雜，約束越多，α應越小，表示一輛車所能容納的貨物量越少；Cap是冷藏車額定載重量。

那么，配送過程中使用K輛冷藏車的配送成本為：

Ck表示第k輛程中使用K輛冷藏車的固定成本。

（2）運輸成本。冷藏車在配送過程中的運輸成本是與行駛里程成正比的。但是生鮮產品在配送過程中的腐損程度與受到的顛簸有很大的關系，從而影響到配送中心的配送成本。配送過程中生鮮產品受到的顛簸少，產品損壞程度就小，配送中心的配送成本也會相應減少。我國道路收費的標準是按照路面好壞程度來收費的。高速公路路面平整、顛簸少、速度快，因此收費最高，其次是國道、省道等［6］。因此，要保證生鮮產品的新鮮度和客戶的滿意度，配送中心在選擇配送路徑時需要充分考慮道路質量的問題，確定這批生鮮產品在哪種道路上配送才能保證供應商與消費者的雙贏。本文提出一個帶道路等級評估系數(shù)的模型，表1所示是不同路面質量的道路等級分類以及它的道路等級評估系數(shù)μij。

表1　道路分類與評價系數(shù)表

配送過程中的運輸成本可表示為：

s表示單位距離運輸成本；disij表示客戶i和客戶j之間的距離；Xij表示配送車輛是否經過（i，j）路段，若經過，則Xij=1；否則，Xij=0。

（3）能源成本。冷藏車通過制冷裝置維持車內的溫度，以保證生鮮食品保持適宜的溫度，減少腐損。生鮮成品配送過程中的能源成本主要來源于以下兩個方面［7］：

①由于冷藏車內外溫度之差而通過車廂隔熱壁傳入車廂內的熱負荷為：

那么，在冷藏車在配送過程中通過隔熱壁消耗的制冷成本為：

②冷藏車在服務顧客時，由于車廂門開啟，也會造成一定的熱負荷，產生制冷成本：

那么，冷藏車在服務客戶時消耗的制冷成本為：

V表示冷藏車的體積；τ表示車廂傳熱系數(shù)（W m2·°C）；S表示車廂外表面積；φ表示車廂門開啟程度系數(shù)；ΔT表示車廂內外溫度之差；tij表示配送冷藏車從客戶i行駛到客戶j的用時；ρ表示氮液熱量轉化系數(shù)；Pref表示制冷劑成本。

（4）違反時間窗的懲罰成本。若配送車輛在與客戶預定的時間窗ei之前，晚于客戶可接受的時間窗Ei到達，則配送公司可以立即交貨，但是需要承擔約定的懲罰費用；若配送車輛在與客戶約定的時間窗之內到達，則沒有懲罰費用；若配送車輛在與客戶預定的時間窗l(fā)i之后，早于客戶可接受的時間窗Li到達，則配送公司也要承擔一定的懲罰費用，若配送車輛沒有在客戶可接受的時間窗之內到達，此時客戶會拒絕接受貨物［9］。

綜上所述，冷藏車k在服務客戶i時的懲罰成本為：

則冷藏車在配送一批貨物時總的懲罰成本為：

（5）貨損成本。考慮到生鮮產品在冷鏈運輸過程中的溫度一般為定值，故假設其變質速率為一常數(shù)R，并定義生鮮產品在配送過程中其品質隨時間變化呈指數(shù)形式。函數(shù)如下：

?是生鮮產品的質量對時間的敏感度，若產品對時間的敏感度強，該值相對小些，反之則大些；sk為冷藏車K從配送中心出發(fā)的時間。

整個配送過程中的貨損成本為：

2.2.2約束條件

目標函數(shù)

上述約束條件中，式（1）表示配送過程中冷藏車的載重量不得超過它的額定載重量；式（2）表示閉環(huán)配送；式（3）和式（4）表示一個客戶只能由一輛冷藏車配送，且只能被配送一次；式（5）表示冷藏車到達客戶的時間不得超過客戶可接受的時間窗范圍。

3　基于2-opt的免疫遺傳算法

目前學者們在解決冷鏈物流車輛配送路徑優(yōu)化問題時多采用模擬退火算法、禁忌搜索算法、遺傳算法、改進遺傳算法等。這些算法各有優(yōu)勢，也存在其弊端。模擬退火算法具有一定的容錯機制，但是無法確保優(yōu)化結果最優(yōu)；禁忌搜索算法能夠通過調整禁忌規(guī)模來提高搜索速度，但是容易陷入局部最優(yōu)；遺傳算法是一種全局收斂方法，但是不可避免的會產生退化現(xiàn)象。

本文采用免疫遺傳算法解決冷鏈物流車輛配送優(yōu)化問題，該算法使遺傳算法具有免疫功能，有效抑制退化現(xiàn)象，提高全局搜索速度。同時使用2-opt算法作為變異算子，提高免疫遺傳算法的局部搜索能力。2-opt鄰域搜索算法是求解TSP問題的常用啟發(fā)式算法，對于優(yōu)化Hamilton回路有很大的優(yōu)勢，在冷鏈物流車輛路徑優(yōu)化問題中，單輛車配送的客戶數(shù)量并不多，因此不適合使用3-opt、or-opt這樣復雜的算法。并且使用2-opt算法能彌補免疫遺傳算法易陷入局部最優(yōu)的缺點。

免疫遺傳算法的流程如下：

（1）抗體編碼。將待求解的實際問題轉化為免疫系統(tǒng)能夠處理的抗原形式，抗體則對應問題的解?，F(xiàn)在使用最多的編碼方式有自然數(shù)編碼、二進制編碼和字符編碼。本文采用自然數(shù)編碼中的配送中心和客戶共同編碼。

并定義免疫系統(tǒng)由N個抗體組成，即群體規(guī)模為N，M表示抗體的基因數(shù)。

（2）產生初始抗體。

（3）計算抗體與抗體間的親和力。在進化過程中免疫系統(tǒng)是一個不確定系統(tǒng)，其多樣性由Shannon的平均信息熵來表示。定義pij是第i個等位基因在j基因座上出現(xiàn)的頻率。

則處于j位置的基因信息熵為：

整個群體的基因信息熵為：

那么根據熵的定義，得到抗體v和w的親和力：

（4）排除相似抗體。如果ayv，w＞ω，則淘汰一條抗體。

ω為濃度閾值；v為相同等位基因段的數(shù)量。

（5）計算抗原與抗體的親和度。計算抗原與抗體的親和度axv，排除親合力小于上一代親和度最小值的抗體：

（6）選擇優(yōu)良抗體加入記憶庫。在傳統(tǒng)適應度選擇比例的基礎上增加基于濃度的調節(jié)概率因子。抗體v的濃度計算公式為：

個體的選擇概率pc由適應度概率pf和濃度抑制概率pd兩部分組成：

（7）交叉、變異、隨機產生新抗體。交叉操作采用順序交叉。在雙親1中隨機選擇一個匹配區(qū)域，產生原始后代，將雙親2中與匹配區(qū)域不同的部分按照原來的順序插入到原始后代，組成子代1。按照同樣的方法組成子代2。

變異操作采用2-opt算法。2-opt算法在改進車輛路徑優(yōu)化問題中的單條路線上有獨特的優(yōu)勢。其基本思想是取路線上的兩條線段（i，i+1）和（j，j+1），斷開這兩條線段，將點i與j+1相連，j與i+1相連，同時將線路反轉，形成新的線路。如果變化后的線路里程比原路徑短，則此線路為優(yōu)化解。否則保留原路線。

（8）如果迭代次數(shù)超過預先的設定，則輸出最優(yōu)解。否則返回第3步。

4　算例分析

本文以J公司鮮奶配送的相關資料為基礎進行合理假設，該公司冷藏車從配送中心出發(fā)，向同城的10個需求點配送鮮奶。冷藏車額定載重量是3t，配送一次的固定成本為200元，配送過程中車廂內的溫度是0℃，車廂外的溫度是20℃，單位里程的運輸成本是4元，道路顛簸系數(shù)為1.12。冷藏車在預定時間窗之前到達的懲罰系數(shù)為0.1%，在預定時間窗之后到達的懲罰系數(shù)為0.2%。各需求點的需求量及時間窗限制見表2，各節(jié)點距離情況見表3。

表2　各需求點的需求量及時間窗

表3　配送中心與各需求點間的距離（km）

利用本文提出的基于2opt的免疫遺傳算法求得最終結果：使用3輛冷藏車配送此次貨物。第1輛冷藏車的配送路線是2-3-5-10，第2輛冷藏車的配送路線是1-8-4，第3輛冷藏車的配送路線是6-7-9。

5　結束語

本文分析了冷鏈物流配送的現(xiàn)狀，重點分析冷鏈配送過程中的固定成本、運輸成本、能源成本、時間窗懲罰成本和貨損成本，建立冷鏈物流車輛配送路徑優(yōu)化問題的數(shù)學模型，并提出將2-opt算法與免疫遺傳算法相結合來求解該模型。但是在實際配送過程中，可能會遇到因天氣狀況、交通事故等因素造成的時間的不確定性，這是本文沒有考慮到的，還需要繼續(xù)研究。

［1］韓春陽，伍景瓊，賀瑞.國內外冷鏈物流發(fā)展歷程綜述［J］.中國物流與采購，2015，（15）：54-55.

［2］李宏.城市冷鏈物流配送車輛路徑問題的研究［D］.長沙：長沙理工大學，2006.

［3］何琴飛.考慮道路暢通狀況的冷鏈物流配送優(yōu)化問題［D］.大連：大連海事大學，2015.

［4］李亞男，劉聯(lián)輝，李小曼，等.低碳約束下城市冷鏈物流配送系統(tǒng)優(yōu)化研究［J］.中國市場，2016，（10）：36-39.

［5］Peiqing Li，Jie He，Dunyong Zheng，etc.Vehicle Routing Problem with Soft Time Windows Based on Improved Genetic Alogrithm for Fruits and Vegetables Distribution［J］.Discrete Dynamics in Nature and Society，2015，（48）：30-38.

［6］章鏞初.冷藏汽車熱負荷計算［J］.專用汽車，1988，（2）：12-15.

［7］張金鳳.帶模糊時間窗的冷鏈物流車輛路徑優(yōu)化［D］.武漢：武漢理工大學，2013.

［8］苑立杰.免疫遺傳算法在車輛路徑問題中的應用研究［D］.大連：大連海事大學，2013.

Study on Cold Chain Distribution Route Optimization Based on 2-Opt Immunity Genetic Algorithm

Wang Mi，Yang Kongyu
（School of Information Management， Beijing Information Science Technology University， Beijing 100192， China）

In this paper， we analyzed the current status of the fresh product cold chain distribution industry， pointed out the significanceof route optimization therein， then considering the impact of bumping on the distribution cost of the fresh products and in connection with thefixed vehicle cost， transportation cost， energy cost， penalty cost， and cargo loss cost， etc.， established the cold chain logistics vehicledistribution route optimization model， combined the 2-Opt algorithm and the immunity genetic algorithm to solve it， and at the end， throughan empirical case， demonstrated the validity and practicality of the model.

cold chain； 2-Opt； immunity genetic algorithm； distribution route optimization

F224；F252.14

A

1005-152X（2016）07-0072-04

10.3969/j.issn.1005-152X.2016.07.016

2016-06-07

北京市自然科學基金項目（4132024）；北京市社會科學基金重點項目（15ZHA004）

王咪（1991-），女，山東濟寧人，北京信息科技大學研究生，研究方向：物流系統(tǒng)規(guī)劃與設計；楊孔雨（1967-），男，山東巨野人，北京信息科技大學教授，研究生導師，研究方向：智能決策和優(yōu)化計算的理論應用研究。