俞武揚(yáng)，楊沈記

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

帶軟時(shí)間窗的冷鏈物流配送路徑優(yōu)化研究

俞武揚(yáng)，楊沈記

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

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

冷鏈物流；路徑優(yōu)化；軟時(shí)間窗；遺傳算法

一、引言

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

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

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

二、問題描述與模型構(gòu)建

（一）問題描述

本文研究的帶軟時(shí)間窗冷鏈物流配送路徑優(yōu)化問題為：在給定區(qū)域內(nèi)，一個(gè)冷鏈配送中心給若干客戶進(jìn)行冷鏈產(chǎn)品的配送服務(wù)，配送中心和客戶的地理位置已知，不同客戶的需求量和可接受的服務(wù)時(shí)間段存在差異，要求合理安排冷鏈車的配送路徑使得貨物能在客戶可接受的時(shí)間段內(nèi)到達(dá)，并使總配送成本最小。

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

（二）模型構(gòu)建

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

表1 參數(shù)與變量說明

2.數(shù)學(xué)模型。根據(jù)問題的描述，帶軟時(shí)間窗的冷鏈物流配送路徑優(yōu)化的數(shù)學(xué)模型可表示為：

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

三、算法設(shè)計(jì)

遺傳算法是一種基于群體遺傳進(jìn)化機(jī)制的自適應(yīng)全局優(yōu)化算法。本文針對帶軟時(shí)間窗的冷鏈車輛配送問題特點(diǎn)設(shè)計(jì)了如下遺傳算法。

（一）染色體編碼

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

（二）初始化染色體

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

步驟1：染色體第一個(gè)基因位置設(shè)為配送中心1，然后給編號為2至N的N-1個(gè)客戶點(diǎn)隨機(jī)排序。

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

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

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

現(xiàn)有8個(gè)客戶點(diǎn)的隨機(jī)排序：“35786924”，如圖1所示可得到一條初始染色體：“135178619241”。

圖1 初始染色體生成示例

（三）交叉與變異算子

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

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

圖2 交叉算子示例

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

（四）其余條件

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

（2）選擇機(jī)制，根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照輪盤賭方法從第t代種群P（t）中選擇出優(yōu)良的個(gè)體遺傳到下一代種群P（t+1）中。

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

四、實(shí)驗(yàn)與仿真分析

（一）實(shí)例描述

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

表2 各客戶點(diǎn)配送相關(guān)信息（#表示編號）

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

（二）遺傳算法優(yōu)化方案

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

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

圖3 最優(yōu)配送路線方案

圖4 遺傳算法進(jìn)化圖

表3 最優(yōu)配送方案各子路徑數(shù)據(jù)

（三）掃描法優(yōu)化方案

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

圖5 配送中心利用掃描法進(jìn)行路線規(guī)劃的方案

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

表4 配送子路徑結(jié)果數(shù)據(jù)（掃描法）

（四）方案比較

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

表5 優(yōu)化結(jié)果比較

五、小結(jié)

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

[1]馬向國，劉同娟，楊平哲，等，2016.基于隨機(jī)需求的冷鏈物流車輛路徑優(yōu)化模型[J].系統(tǒng)仿真學(xué)報(bào)（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.鮮活農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[J].價(jià)值工程（31）：25-27.

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

[9]姚寶珍，楊成永，張強(qiáng)，等，2010蟻群算法在西餐連鎖店配送路徑中應(yīng)用[J].北京交通大學(xué)學(xué)報(bào)（6）：51-55.

[10]葛顯龍，孔陽，2016.帶有時(shí)間窗的生鮮物流配送路徑優(yōu)化研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識（12）：78-87.

（責(zé)任編輯：D 校對：R）

F252.8

A

1004-2768（2017）06-0067-04

2017-03-22

浙江省哲學(xué)社會(huì)科學(xué)規(guī)劃項(xiàng)目（17NDJC053YB）；教育部人文社會(huì)科學(xué)青年基金項(xiàng)目（13YJC630177）

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