帶時間窗的冷鏈物流車輛路徑優(yōu)化問題研究

徐松梅

摘 要：文章研究了帶有硬時間窗限制的超市速凍食品冷鏈配送車輛路徑優(yōu)化問題，根據(jù)其配送批量小，配送地點分散，時間要求高的特點建立了配送成本最小的目標(biāo)函數(shù)，以降低物流的配送成本，提高其經(jīng)濟(jì)效益。該模型考慮了配送過程中的固定成本、運輸成本、時間懲罰成本以及制冷成本，其配送車數(shù)、每兩個客戶間的運輸量、配送時間以及卸貨時間相互作用，共同影響總成本，然后采用遺傳算法求解，最后以一個物流公司為算例，進(jìn)行求解證明該模型的可行性。

關(guān)鍵詞：路徑優(yōu)化；冷鏈物流；遺傳算法

中圖分類號：U116.2 文獻(xiàn)標(biāo)識碼：A

Abstract： In this paper， we study the optimization of the problem of the cold chain distribution of the frozen food in the supermarket with the hard time window. According to the characteristics of the small batch distribution， the scattered distribution time and the high time requirement， the objective function of the minimum distribution cost is established to reduce the distribution of the logistics cost， improve its economic efficiency. The model takes into account the fixed costs， transportation costs， time penalty costs and cooling costs in the distribution process， the number of dispatch vehicles， the amount of traffic between each two customers， the delivery time， and the time of unloading， which together affect the total cost and then using genetic algorithm to solve， and finally to a logistics company as an example， to prove the feasibility of the model.

Key words： path optimization； cold chain logistics； genetic algorithm

0 引 言

隨著人們對新鮮食品的需求不斷增多，冷鏈物流配送得到急速發(fā)展，現(xiàn)今我國很多中小城市的物流公司發(fā)展較落后，專門提供冷鏈配送的企業(yè)較少，大多物流企業(yè)將冷鏈配送作為副業(yè)，缺少對冷鏈配送的詳細(xì)規(guī)劃，因而冷鏈物流配送水平較低，降低配送成本與滿足客戶要求很難同時兼顧，尤其在滿足超市冷鮮產(chǎn)品供應(yīng)方面更加明顯。冷鏈物流的高成本源于運輸設(shè)備價格較高，制冷成本較高以及未按時到達(dá)產(chǎn)生的懲罰成本三部分組成，所以選擇合適的配送路徑可以滿足客戶的時間要求，最大限度地降低配送成本，提高企業(yè)的競爭力和經(jīng)濟(jì)效益。

1 國內(nèi)外研究綜述

目前國內(nèi)外冷鏈物流配送研究可分為對冷鏈物流的配送路徑的模型研究以及對冷鏈物流配送路徑算法研究。冷鏈物流配送路徑模型方面：王淑云、孫虹[1]探討了顧客需求變動下的冷鏈配送路徑模型。潘東靜[2]針對零售點農(nóng)產(chǎn)品需求模糊的情況進(jìn)行分析，建立了適用于模糊需求的冷鏈最小成本模型。石兆、符卓[3]結(jié)合了配送網(wǎng)絡(luò)時變特征對食品冷鏈配送的易腐性進(jìn)行行程時間分析，通過建立時變條件下的仿真模型來求解在配送網(wǎng)絡(luò)體系下的最優(yōu)路徑。于坤[4]研究了具有同時取送貨特征的典型城市冷鏈物流配送狀況。王曉寧[5]以冷鏈物流的高耗能和高排碳為研究的對象，主要研究了在農(nóng)產(chǎn)品的新型流通形式即農(nóng)超對接模式下的冷鏈物流碳排放。

冷鏈物流配送路徑優(yōu)化算法方面：繆小紅[6]運用了具有GIS功能的二次開發(fā)軟件——Map Objects控件和VB開發(fā)平臺來輔助解決路徑優(yōu)化問題。呂俊杰、孫雙雙[7]用蟻群算法和matlab工具對實例進(jìn)行求解分析。楊瑋等[8]用優(yōu)化的粒子群算法解決農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化問題。劉鎮(zhèn)等[9]構(gòu)建了冷鏈物流配送車輛路徑優(yōu)化模型，利用粗粒度并行遺傳算法，在云計算環(huán)境下對模型求解。邱榮祖等[10]應(yīng)用GIS與禁忌搜索法集成技術(shù)對帶時間窗的車輛路徑問題進(jìn)行求解。

目前對于冷鏈物流配送路徑優(yōu)化問題的研究大多是針對農(nóng)產(chǎn)品以及生鮮類食品長途跨市（省）運輸，并在建模中考慮到貨損成本，以一種農(nóng)產(chǎn)品（生鮮品）單價作為參考數(shù)據(jù)求解模型，很少有對市內(nèi)超市速凍食品配送路徑問題的研究，況且農(nóng)產(chǎn)品（生鮮品）的售價差距較大，易受貨損程度不一，以某種農(nóng)產(chǎn)品為例計算運輸成本以及貨損成本不盡合理，實際效用不高。本文研究了市內(nèi)超市速凍食品配送問題，由于配送一般要求當(dāng)日送達(dá)，基本不存在貨損成本，從而可以以均價參數(shù)，提高模型的精確度，具有較強(qiáng)實際應(yīng)用價值。

2 問題描述及模型建立

2.1 問題描述

城市冷鏈物流配送除了要考慮傳統(tǒng)配送中的顧客需求量、顧客時間要求、車輛限制以及車行駛里程外，還要考慮到溫度的控制，包括在運輸途中產(chǎn)生的制冷費用、在卸貨時由于溫差而產(chǎn)生的額外費用和制冷運輸車的成本。由于研究對象是市內(nèi)超市配送，超市營業(yè)時間相近，各超市的卸貨時間時長不同，導(dǎo)致在短時間內(nèi)完成多點配送較為困難，因而研究難點在于在降低配送里程的同時，盡量滿足顧客的時間要求，減少懲罰成本。endprint

本文研究一個配送中心，多配送地點的超市速凍食品冷鏈物流配送路徑優(yōu)化問題，客戶地址與需求量已知，同時考慮配送的時間懲罰成本并做出如下假設(shè)：（1）配送同一種飲料；（2）配送發(fā)生在早上，不會突然產(chǎn)生交通擁堵；（3）配送時路面狀況良好；（4）每輛冷藏運輸車只服務(wù)一條路徑；（5）每個客戶都只被服務(wù)一次。

2.2 數(shù)學(xué)模型

根據(jù)傳統(tǒng)的車輛路徑問題可設(shè)道路網(wǎng)絡(luò)圖GV，A為完全對稱網(wǎng)絡(luò)，其中集合V=v，v，…，v代表配送中心及其客戶地址，k=1，2，3，…，m表示某物流公司所擁有的車輛數(shù)目，d為包括配送中心在內(nèi)的配送節(jié)點間的距離，i，j=0…n。g為第k輛車從i地到j(luò)地的送貨量。則c為運輸成本，其單位為噸·公里。在時間窗限制條件下，冷鏈配送成本主要由車輛固定成本、運輸成本、時間懲罰成本以及制冷成本組成。其中固定成本是投入每輛車所需消耗的必須成本，包括車輛維修以及操作人員薪資等費用，該成本與運輸里程無關(guān)。運輸成本與車輛行駛里程有關(guān)，時間懲罰成本是當(dāng)車輛早到或遲到時作為未按規(guī)定時間到達(dá)所產(chǎn)生的費用。制冷成本發(fā)生在車輛配送時用于保持車廂內(nèi)食品所需溫度所花成本以及在卸貨過程中車廂內(nèi)外冷熱空氣交替所產(chǎn)生的額外制冷費用。

固定費用fk=1，2，…，m，其中k代表車輛，固定成本與配送車輛數(shù)目呈正相關(guān)，即若最終結(jié)果使得配送車輛減少則相應(yīng)的固定成本也會降低。

假設(shè)車輛k將貨物從i客戶配送至j客戶，其配送成本為d×c×g×y，其中y為0-1變量，當(dāng)?shù)趉輛車將貨物從i客戶運往j客戶時y=1，當(dāng)?shù)趉輛車沒有將貨物從客戶i送往客戶j時，y=0。由于本文為使計算精確并貼近實際單位運價采用噸·公里來度量，使得計算難度加大，即g表示的為從客戶i到客戶j時車上的總貨量，例如從配送中心出發(fā)到第一個客戶的貨運量是第k輛車服務(wù)的整條配送路徑上的貨運總量，當(dāng)?shù)竭_(dá)第一個客戶i并卸貨后，從客戶i到下一個客戶j的貨運總量為除去客戶i的需求量后余下的送貨量，以此類推遞減，直到送完最后一個客戶時，該車輛應(yīng)為空箱返回配送中心。即運輸費用與配送里程呈正相關(guān)，與配送量呈負(fù)相關(guān)。傳統(tǒng)的運輸成本計算往往固定了節(jié)點間的運輸成本，使其采用統(tǒng)一價格，在實際操作中并不可行，第一節(jié)點間的運輸費用是由車輛里程和運量共同決定的，隨著車輛的服務(wù)客戶的增加，該費用也會隨之變化，因而固定節(jié)點間的運費本身存在較大誤差。第二傳統(tǒng)的固定節(jié)點間費用忽略了空車返回的成本，本文的方法可以最大限度合理化配送次序，減少空車行駛里程。

對于速凍食品來說，車輛配送過程中車廂內(nèi)應(yīng)時刻保持低溫狀態(tài)，但在卸貨過程中由于車廂內(nèi)外存在溫差，為了維持車內(nèi)的平均溫度，會產(chǎn)生更高的制冷費用，當(dāng)車廂內(nèi)外的溫差越大所需的功率就越高，相應(yīng)的制冷費用就越大，為了簡便計算，將卸貨過程中的制冷成本分為兩部分：不考慮溫差時，為維持車內(nèi)的溫度所需的制冷費用以及由于車廂內(nèi)外溫差所導(dǎo)致的額外的制冷費用，總制冷成本不僅包括運輸途中的費用也包括裝卸時的費用。無冷熱空氣對流的制冷成本包括運輸過程中的制冷費用以及不考慮溫差的卸貨時產(chǎn)生的制冷成本，由如下公式表示：αd/s+g/？覣其中i≠j。在本公式中α為不考慮溫差的制冷系數(shù)，代表每單位時間內(nèi)所產(chǎn)生的制冷費用，s為冷藏車的運輸時速，g表示第j個客戶的需求量，？覣為在客戶j處的卸貨效率。運輸?shù)窖b卸地點后，冷藏車廂內(nèi)外溫差，打開冷藏車門后由于空氣對流會導(dǎo)致車廂內(nèi)的氣溫升高，所以為了保持車內(nèi)的溫度不變，需要增大功率，因增加的功率而產(chǎn)生的額外制冷成本計算公式為：θ·g/？覣·T，其中θ為卸貨時的氣溫每升高一度單位時間內(nèi)產(chǎn)生的成本，T為車廂內(nèi)外溫差。

時間懲罰成本遵循硬時間窗懲罰成本，如圖1所示，ES與KS分別代表著配送車輛早到時客戶能夠接受的最早送貨時間和配送車輛晚到時客戶能夠接受的最晚送貨時間，ES，KS為客戶可以接受的送貨時間，本文為方便計算以某一時間點為基準(zhǔn)，以分鐘為單位來進(jìn)行計時以及時間限制。當(dāng)配送車輛到達(dá)客戶j地的送貨時間t（即從客戶i到客戶j的送貨時間，包括在客戶j處的卸貨時間）少于客戶j的最早接貨時間ES時，其產(chǎn)生的懲罰費用為M；當(dāng)配送車輛到達(dá)客戶j地的送貨時間t超過客戶j的最晚接貨時間KS時，其產(chǎn)生的懲罰費用為M。在實際情況中，配送車輛早到所產(chǎn)生的懲罰成本小于配送車輛晚到所產(chǎn)生的懲罰成本，即M

綜上所述，超市冷鏈物流配送模型為：

minz=f+d×c×g×y+αd/s+g/？覣+θ×g/？覣×T+M×δ+M×

y≤5 i，j=0，1，2，…，n （1）

y≤1 j，k=1，2，3，…，n （2）

y≤1 i，j=0，1，2，…，n （3）

y≤1 i，k=1，2，3，…，n （4）

y=N k=1，2，…，m （5）

g≤Q k=1，2，…，m （6）

在上述模型中，約束（1）保證實際配送車數(shù)量不超過該公司擁有車數(shù)，約束（2）表示每一個出發(fā)地最多只有一個接受地，約束（3）表示每個客戶最多只被一輛車服務(wù)，約束（4）表示每個客戶最多接受一次配送服務(wù)，約束（5）所有客戶都要被服務(wù)，約束（6）每條配送路徑的車載量不得超過該車最大載重量。該模型共有三個0-1變量：

①y=代表車輛k是否服務(wù)點；②δ=代表車輛早于客戶j的要求時間到達(dá)；③=代表車輛晚于客戶j的要求時間到達(dá)。

3 物流配送模型算法以及案例求解

3.1 遺傳算法求解

求解步驟如圖2：

3.2 遺傳算法設(shè)計

（1）問題編碼。本文研究的問題是冷鏈物流配送，首先就要問題的配送中心和客戶點進(jìn)行編碼。編碼設(shè)計是采用客戶節(jié)點直接編碼，并不將配送中心編入其中，直接對n個客戶節(jié)點進(jìn)行全排列，每一種排列方式就是一種解，其中數(shù)列的順序就是配送車輛到達(dá)的順序，如：若隨機(jī)產(chǎn)生一個染色體為（3，4，2，5，8，9，7，1，6），則說明該路徑的配送順序為3—4—2—5—8—9—7—1—6，每一個染色體代表一個配送方案，再在每個染色體頭尾添加0元素。

（2）初始種群設(shè)定。初始化種群，隨機(jī)產(chǎn)生對33個客戶節(jié)點所進(jìn)行的全排列的染色體，這樣的染色體共有100個，會形成100行33列的二位矩陣。

（3）適應(yīng)度函數(shù)設(shè)定。適應(yīng)度函數(shù)為目標(biāo)函數(shù)。找出第i染色體，獲取其配送客戶順序，先對每個客戶的需求量進(jìn)行加總，使總重不超過車的載重能力，再針對第一個客戶的需求量進(jìn)行運輸費用求解，并算出運輸時間與裝卸時間，以便計算制冷費用以及時間懲罰費用，然后再計算下一個客戶的運輸費用，并在上一個客戶運輸時間和裝卸時間總和的基礎(chǔ)上計算本客戶的配送時間是否符合本客戶要求，從而判斷是否產(chǎn)生懲罰成本，但運輸?shù)闹评滟M用的時間為本段路的運輸時間和裝卸時間，并依此類推，完成配送。最后用for循環(huán)語句找出配送總成本最小的車，這樣一直重復(fù)找，直至再找不出更小的配送成本的車輛為止。

（4）選擇算子。本文采用的是輪盤賭法。將個體的適應(yīng)度值比上總?cè)旧w的適應(yīng)度值，作為該個體所占概率。隨機(jī)選擇輪盤旋轉(zhuǎn)圈數(shù)，令pick為隨機(jī)數(shù)，再讓pick減去第i個染色體所占概率，對初始種群中的染色體全部進(jìn)行該項循環(huán)操作，總共會有sizepop次循環(huán)，當(dāng)pick為負(fù)數(shù)時，循環(huán)才會終止。

（5）交叉算子。本文采用的是單點交叉的方法，即隨機(jī)選擇一個基因位置將兩個染色體的同基因位置上的基因進(jìn)行交換，以增加染色體的數(shù)目，增加種群規(guī)模。

（6）變異算子。本文采用的變異過程是將某一染色體的某兩個基因位做出交換，以改變其個體。隨機(jī)選擇一個數(shù)，若該數(shù)字小于變異概率則不進(jìn)行變異操作，若該數(shù)字大于變異概率則進(jìn)行變異。變異位置也是隨機(jī)選擇的。

3.3 算例求解

賽嘉物流公司以長途運輸大宗商品為主，超市配送業(yè)務(wù)為副業(yè)，該公司共有5輛冷藏配送車，配送網(wǎng)點18個，目前5輛車全部投入配送業(yè)務(wù)中，車速限定為40公里/小時，即0.75km/分。每臺配送車的最大車載量為5t。為方便計算本文以某天的氣溫為參考，車廂內(nèi)外溫差為10℃，速凍食品單價為6～10元，取均數(shù)8元。卸貨效率為45斤/min，不考慮車廂內(nèi)外溫差的制冷系數(shù)α為20元/時，額外制冷系數(shù)θ為5元/時，早到的時間懲罰系數(shù)M為50元，遲到的時間懲罰系數(shù)M為100元。每車的固定費用為120元/車。具體配送情況如表1至表4所示：

遺傳算法的參數(shù)為：染色體長度=33×2；種群規(guī)模=100；迭代次數(shù)=1 000；交叉概率=0.8；變異概率=0.2。運行結(jié)果為：2。運行圖如圖3所示：

通過運算得到配送方案如表5所示：

相比較原來配送方案，該配送方案少用了一輛運輸車，總運輸費用下降到1 281.738元，說明該模型有效。

4 結(jié) 論

本文針對帶時間窗的超市速凍品冷鏈配送問題進(jìn)行了研究，基于城市配送的批量小、地點分散、時間要求高的特點，建立了以最小配送成本為目標(biāo)函數(shù)的模型，從而進(jìn)行路徑的選擇，進(jìn)一步提高配送效率，降低配送能耗和最大化配送效益。本文的單位運輸成本取均值來計算，在實際生活中，每個路段的單位運輸成本不可能一成不變，因而可以考慮構(gòu)建物流配送系統(tǒng)，實時記錄配送的單位成本的變化，可以進(jìn)一步提高模型的精確度。

參考文獻(xiàn)：

[1] 王淑云，孫虹. 需求變動下的冷鏈品配送路徑規(guī)劃[J]. 公路交通科技，2014（8）：144-150.

[2] 潘東靜. 具有模糊需求的農(nóng)產(chǎn)品冷鏈物流車輛配送路徑優(yōu)化研究[J]. 安徽農(nóng)業(yè)科學(xué)，2015（5）：334-336.

[3] 石兆，符卓. 時變網(wǎng)絡(luò)條件下帶時間窗的食品冷鏈配送定位——運輸路徑優(yōu)化問題[J]. 計算機(jī)應(yīng)用研究，2013（1）：284-288.

[4] 于坤. 基于VRPSDP問題的城市冷鏈物流配送路徑優(yōu)化研究[D]. 大連：大連海事大學(xué)（碩士學(xué)位論文），2014：1-52.

[5] 王曉寧. 農(nóng)超對接模式下生鮮農(nóng)產(chǎn)品冷鏈物流車輛配送路徑研究——基于碳減排視角[D]. 南昌：華東交通大學(xué)（碩士學(xué)位論文），2014：1-60.

[6] 繆小紅. 基于GIS的生鮮食品冷鏈物流配送路徑優(yōu)化研究[D]. 福州：福建農(nóng)林大學(xué)（碩士學(xué)位論文），2010：1-77.

[7] 呂俊杰，孫雙雙. 基于鮮活農(nóng)產(chǎn)品冷鏈物流配送的車輛路徑優(yōu)化研究[J]. 廣東農(nóng)業(yè)科學(xué)，2013（9）：178-181.

[8] 楊瑋，李國棟，張倩. 基于粒子群算法的農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[J]. 陜西科技大學(xué)學(xué)報，2013（3）：150-153.

[9] 劉鎮(zhèn)，徐優(yōu)香，王譯. 基于云計算的冷鏈物流配送路徑優(yōu)化方法研究[J]. 電子設(shè)計工程，2013（17）：122-127.

[10] 邱榮祖，鐘聰兒，修曉虎. 基于GIS和禁忌搜索集成技術(shù)的農(nóng)產(chǎn)品物流配送路徑優(yōu)化[J]. 數(shù)學(xué)的實踐與認(rèn)識，2011（10）：145-152.endprint