徐松梅

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

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

中圖分類號(hào)：U116.2 文獻(xiàn)標(biāo)識(shí)碼：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 引 言

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

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

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

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

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

2 問(wèn)題描述及模型建立

2.1 問(wèn)題描述

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

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

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

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

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

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

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

時(shí)間懲罰成本遵循硬時(shí)間窗懲罰成本，如圖1所示，ES與KS分別代表著配送車輛早到時(shí)客戶能夠接受的最早送貨時(shí)間和配送車輛晚到時(shí)客戶能夠接受的最晚送貨時(shí)間，ES，KS為客戶可以接受的送貨時(shí)間，本文為方便計(jì)算以某一時(shí)間點(diǎn)為基準(zhǔn)，以分鐘為單位來(lái)進(jìn)行計(jì)時(shí)以及時(shí)間限制。當(dāng)配送車輛到達(dá)客戶j地的送貨時(shí)間t（即從客戶i到客戶j的送貨時(shí)間，包括在客戶j處的卸貨時(shí)間）少于客戶j的最早接貨時(shí)間ES時(shí)，其產(chǎn)生的懲罰費(fèi)用為M；當(dāng)配送車輛到達(dá)客戶j地的送貨時(shí)間t超過(guò)客戶j的最晚接貨時(shí)間KS時(shí)，其產(chǎn)生的懲罰費(fèi)用為M。在實(shí)際情況中，配送車輛早到所產(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ù)量不超過(guò)該公司擁有車數(shù)，約束（2）表示每一個(gè)出發(fā)地最多只有一個(gè)接受地，約束（3）表示每個(gè)客戶最多只被一輛車服務(wù)，約束（4）表示每個(gè)客戶最多接受一次配送服務(wù)，約束（5）所有客戶都要被服務(wù)，約束（6）每條配送路徑的車載量不得超過(guò)該車最大載重量。該模型共有三個(gè)0-1變量：

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

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

3.1 遺傳算法求解

求解步驟如圖2：

3.2 遺傳算法設(shè)計(jì)

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

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

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

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

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

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

3.3 算例求解

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

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

通過(guò)運(yùn)算得到配送方案如表5所示：

相比較原來(lái)配送方案，該配送方案少用了一輛運(yùn)輸車，總運(yùn)輸費(fèi)用下降到1 281.738元，說(shuō)明該模型有效。

4 結(jié) 論

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

參考文獻(xiàn)：

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

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

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

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

[5] 王曉寧. 農(nóng)超對(duì)接模式下生鮮農(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] 楊瑋，李國(guó)棟，張倩. 基于粒子群算法的農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[J]. 陜西科技大學(xué)學(xué)報(bào)，2013（3）：150-153.

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

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