李伯昊

（北京工商大學(xué) 商學(xué)院，北京 100048）

基于改進(jìn)貪婪算法的冷鏈配送車輛路徑問題

李伯昊

（北京工商大學(xué) 商學(xué)院，北京 100048）

建立以配送總成本最小化為目標(biāo)的數(shù)學(xué)模型，研究在有時間窗的限制條件下，冷鏈物流配送路徑優(yōu)化問題，并基于貪婪思想改進(jìn)的傳統(tǒng)啟發(fā)式算法，對算例進(jìn)行求解分析。求得在最優(yōu)出發(fā)時間條件下，總成本最小的配送路線，使用該方法對求解具有指導(dǎo)意義。

冷鏈；車輛路徑優(yōu)化；時間窗；貪婪算法

1 引言

對于冷鏈企業(yè)來說，配送是整個物流系統(tǒng)的末端，配送的效率、成本、質(zhì)量將影響物流活動的整體成效，也影響著客戶對企業(yè)物流服務(wù)的滿意度。如果能在冷鏈配送環(huán)節(jié)中提高效率，不僅意味著減少了運輸過程中的損耗，為企業(yè)節(jié)約了大量成本，同時也保證了消費者在終端渠道購買時產(chǎn)品的完好性。影響冷鏈配送的成本因素有很多。第一，配送車輛運輸路線的安排，會直接影響行車線路的長短，行車路線的長短可以直觀地影響企業(yè)的物流運輸總成本，同時額外的行車距離還會帶來額外的人力成本、車輛損耗等成本。第二，冷鏈產(chǎn)品的易腐性特點，使得冷鏈物流對配送時間有著較為嚴(yán)格的要求。在流通過程中，冷鏈?zhǔn)称焚|(zhì)量下降的積累性是不可避免的，時間過長會引起產(chǎn)品質(zhì)量很大程度的損失。第三，隨著配送體系的不斷完善，客戶對配送時間的要求也越來越高，客戶在可接受的硬時間窗內(nèi)，提出了滿意度最高的軟時間窗。車輛的到達(dá)時間不僅影響產(chǎn)品在送達(dá)時的質(zhì)量，也影響了客戶的滿意程度。正是這些不確定的變量，產(chǎn)生了成本迥異的配送方案，使得企業(yè)的配送難度進(jìn)一步加大?？梢哉f，配送車輛路徑安排對于冷鏈企業(yè)是至關(guān)重要的。

2 文獻(xiàn)綜述

對于冷鏈車輛路徑問題的研究主要分為兩類。一類是根據(jù)冷鏈物流配送的特點，對流程中產(chǎn)生的成本因素、時間窗加以考慮。Chaug-Ing Hsu等在建模時，綜合考慮了易腐食品配送過程中交通堵塞、食品腐壞和設(shè)備能耗等隨機(jī)因素以及時間窗限制的影響，該模型表明庫存成本和能耗成本會顯著的影響總成本[1]。Ana Osvald和LidijaZadnikStim指出易腐食品花費在車上的時間長短是影響配送效率的關(guān)鍵，進(jìn)而提出帶時間窗的車輛路徑問題，并采用禁忌搜索的啟發(fā)式算法來求解，最后使用斯洛文尼亞食品市場的參數(shù)，使食品質(zhì)量的改善達(dá)到40%[2]。孫雙雙等在冷鏈總成本中考慮了冷藏車能耗因素，并構(gòu)建相關(guān)模型，應(yīng)用蟻群算法進(jìn)行求解，結(jié)果表明冷鏈物流配送最優(yōu)路徑的選擇中應(yīng)該考慮該因素[3]。鄭海娟建立了突發(fā)事件下冷鏈物流車輛路徑再規(guī)劃模型，考慮因素更加充分、細(xì)致[4]。

另一類研究是對求解算法進(jìn)行優(yōu)化?？娦〖t等利用改進(jìn)的遺傳算法求解冷鏈物流的數(shù)學(xué)模型。研究結(jié)果表明利用改進(jìn)的遺傳算法得到的最優(yōu)配送路線優(yōu)于標(biāo)準(zhǔn)遺傳算法求解結(jié)果[5]。潘立軍對帶時間窗車輛路徑問題的插入啟發(fā)式算法進(jìn)行了深入研究，提出了時差插入啟發(fā)式算法，確定其啟發(fā)規(guī)則、算法構(gòu)架，并仿真測試了該算法的最佳參數(shù)組合，比較該算法與三種經(jīng)典插入啟發(fā)式算法的求解質(zhì)量表明：該算法的求解質(zhì)量優(yōu)于Solomon的插入啟發(fā)式算法[6]。石兆等采用“預(yù)優(yōu)化階段+實時優(yōu)化階段”兩階段求解策略，通過分解法進(jìn)行問題分解，設(shè)計了最小包絡(luò)聚類分析方法與混合遺傳算法求解，此算法可以用較短的時間得到滿意解[7]。任雪甜等結(jié)合第三方物流企業(yè)多商品多零售商的特點，提出了單貨棧第三方冷鏈物流企業(yè)的車輛調(diào)度模型，并設(shè)計了一種改進(jìn)C-K節(jié)約算法，求解結(jié)果驗證了該模型的合理性[8]。

3 模型分析與建立

3.1 問題描述

假設(shè)現(xiàn)有一個冷鏈配送中心為n個需求點配送需要低溫的冷鮮肉。該配送中心需要向n個需求點進(jìn)行配送，每個需求點的配送需求量為Qi(i=1,2,...,n)，配送中心每輛車的額定載重統(tǒng)一為Q0，其中Qi(i=1,2,...,n)≤Q0。配送中心的位置、每個需求點的位置和配送量皆為己知；每個需求點的服務(wù)時間有一定限制，且每個需求點允許被服務(wù)的時間范圍為（時間窗），若車輛到達(dá)時間晚于LTi，則說明服務(wù)延遲，會拒絕接受貨物；最終車輛返回倉儲中心，最后求得滿足全部需求點需求配送的總成本最小的車輛行駛線路。

3.2 假設(shè)與約束條件

為了將問題抽象為數(shù)學(xué)模型，本文有如下假設(shè)：

（1）配送中心出發(fā)地理位置已知而且唯一；

（2）配送中心擁有一定數(shù)量的配送車輛，且配送車輛型號相同，車輛的額定裝載體積一定，且大于任一需求點的配送量；

（3）車輛由配送中心出發(fā)，將貨物配送至各需求點后，返回配送中心；

（4）每個需求點都有其接受服務(wù)的時間窗，其地理位置、配送量、時間窗均為已知；

（5）車輛按固定路徑行駛，經(jīng)過固定的節(jié)點順序，不會因突發(fā)情況而服務(wù)其他路線上的需求點；

（6）每個需求點由唯一車輛一次配送完成：每輛車可配送多個需求點，但每個需求點只能由一輛車服務(wù)；

（7）各需求點之間的運輸距離以直線距離計算；

（8）產(chǎn)品配送過程中車輛內(nèi)外均保持恒定溫度。

約束條件：

（1）送貨時間可以在需求點的最佳服務(wù)時間內(nèi)到達(dá)，如果不在需求點規(guī)定的時間窗體內(nèi)到達(dá)，會產(chǎn)生懲罰成本；

（2）每個需求點只能由一輛車服務(wù)一次，所有的需求點必須被服務(wù)；

（3）每條配送路徑上，各需求點的貨物總重量不得超過配送車輛的額定載重；

（4）每個需求點的要貨需求必須被滿足。

3.3 決策變量定義：

Xijk：0-1變量，若車輛k由i經(jīng)過 j，則其值為1，否則值為0；

Yki：0-1變量，若需求點i由車輛k服務(wù)，則其值為1，否則值為0；

Tki：車輛k到達(dá)需求點i的時間，Tki=Tk(i-1)+t(i-1)i+Sk(i-1)；

Ski：車輛k在需求點i的服務(wù)時間，即裝卸搬運時間，一般Ski與需求點i需求量呈正相關(guān)；

Cij：需求點i到需求點 j的運輸距離；

tij：從需求點i到需求點 j的行駛時間，設(shè)車輛勻速行駛速度為

ETi：需求點時間窗的上界；

LTi：需求點時間窗的下界；

Qi：需求點i的需求量；

Qo：車輛額定載重；

K：可用車輛；

Po：單位配送成本；

Lw：生鮮產(chǎn)品完好時物品的質(zhì)量；

Li：生鮮產(chǎn)品到需求點i時物品的質(zhì)量；

β：生鮮產(chǎn)品對時間的敏感系數(shù)；

W：產(chǎn)品在某一衡定溫度下變質(zhì)的一個常速變化值；

P1：單位生鮮產(chǎn)品的損失價值。

Sk：車輛k從配送中心出發(fā)時的時間；

λ：提前到達(dá)時的懲罰系數(shù)；

θ：晚點到達(dá)時的懲罰系數(shù)；

M：非常大的正數(shù)；

p：貨物的單位價值；

Cg：每輛車的固定運輸成本；

CHS：貨損成本；

CGD：固定成本；

CYS：運輸成本；

Cfi：客戶i對配送中心的時間窗懲罰成本。

3.4 配送成本分析

本文的目標(biāo)為尋找滿足顧客需求量、時間窗、求總成本最小的配送方案，其中，成本包括：生鮮產(chǎn)品的易腐性所造成的配送貨損成本、車輛固定成本、隨里程而遞增的運輸成本以及因配送不及時而產(chǎn)生的懲罰成本。

貨損成本?？紤]到生鮮產(chǎn)品運輸時其溫度往往為一已知值，尤其是經(jīng)由冷鏈運輸時其溫度一般為一恒定值，為了簡化起見，本文假設(shè)生鮮產(chǎn)品在某一衡定溫度下，其變質(zhì)速率為一常數(shù)W，而定義生鮮產(chǎn)品在其物流配送過程中隨時間變化的品質(zhì)函數(shù)為：Li=LwWe-βt，其中，Lw為生鮮產(chǎn)品完好時物品的質(zhì)量，t為產(chǎn)品經(jīng)歷的物流時間，β為生鮮產(chǎn)品對時間的敏感系數(shù)，W是產(chǎn)品在某一衡定溫度下變質(zhì)的一個常速變化值。在上述變質(zhì)函數(shù)中，如果物品對時間非常敏感，β的取值相對小一些，反之取值則大一些。假定Lw=Qi，則整個配送過程中的貨損成本變?yōu)?/p>

其中Tki為車輛k到達(dá)需求點i的時間；Sk為車輛k從配送中心出發(fā)時的時間；Qi為需求點i的貨物需求量的質(zhì)量；P1為單位生鮮產(chǎn)品的損失價值。

車輛固定成本。派遣每部車輛所需負(fù)擔(dān)的固定成本，包括駕駛員的工資或車輛固定損耗或租金等成本，則總固定成本CGD為：CGD=K×Cg。其中Cg表示每輛車的固定運輸成本。

車輛運輸成本。車輛運輸成本包括油耗、維修、保養(yǎng)等成本，大致上和車輛所行駛的里程數(shù)呈正比，則總的運輸成本CYS為其中Po表示單位配送成本，單位為元/km。

時間窗懲罰成本。本文采用有時間窗的限制條件，即允許配送車輛在需求點要求的時間外到達(dá)，但必須得到一定的懲罰，在借鑒了相關(guān)學(xué)者的研究成果后，構(gòu)建了冷鮮肉配送過程中的時間窗懲罰成本函數(shù)，如圖1所示。

圖1 時間窗懲罰成本函數(shù)

根據(jù)上述不同成本的分析，可得出最終目標(biāo)函數(shù)：

式（1）、式（2）表示保證訪問各需求點的車輛也從那個需求點離開；式（3）表示每個需求點i只被1輛車服務(wù)；式（4）表示每輛車所裝的重量不大于車的額定載重；式（5）表示混合時間窗約束。

4 基于貪婪思想改進(jìn)的算法求解

4.1 算法選擇

求解VRP的方法通常為傳統(tǒng)啟發(fā)式算法或現(xiàn)代啟發(fā)式算法。其中傳統(tǒng)啟發(fā)式算法采用局部搜索技術(shù)尋求滿意解，算法簡單，易于實現(xiàn)，但容易陷入局部最優(yōu)；現(xiàn)代啟發(fā)式算法集成了人工智能的思想，采用全局搜索技術(shù)尋求滿意解，能夠跳出局部最優(yōu)。然而現(xiàn)代啟發(fā)式算法技術(shù)要求較高，通常用于求解具體的問題，不同的原始數(shù)據(jù)和參數(shù)設(shè)置對算法的性能、結(jié)果影響較大，需要一些精心調(diào)試過的參數(shù)才能得到較好的解，這就有可能使其擴(kuò)展到其它情形帶來一定的困難。鑒于此，本文采用一種基于貪婪思想改進(jìn)的傳統(tǒng)啟發(fā)式算法，從另一個角度求解帶時間窗的冷鏈車輛路徑模型。

4.2 算法設(shè)計

針對本文所建立的模型，在求解基礎(chǔ)算子時，選用最近鄰域插入原則。這種規(guī)則的基本思想是：以最近插入的節(jié)點為當(dāng)前節(jié)點，選擇離當(dāng)前節(jié)點最近的未分配節(jié)點作為待插節(jié)點，并嘗試將其連接到當(dāng)前節(jié)點之后。

在得到基礎(chǔ)算子之后提出的算法改進(jìn)：把出發(fā)時間作為變量，車輛的出發(fā)時間的選擇不再是固定值，而是在某個區(qū)間段內(nèi)。通過改變不同的出發(fā)時間，使得第一個節(jié)點的選擇不再唯一，讓車輛可以在最優(yōu)出發(fā)時間的條件下，從配送中心出發(fā)。這樣構(gòu)造出來的可行解也大大增加，最終的結(jié)果也更接近最優(yōu)解。

4.3 算法步驟

改進(jìn)的算法分兩個階段：

第一階段：初始配送中心為當(dāng)前節(jié)點；每次從當(dāng)前節(jié)點開始搜索，從未分配路徑節(jié)點中，選擇離當(dāng)前節(jié)點總成本最少的，嘗試插入當(dāng)前路徑中。若約束條件可以滿足，則更新插入節(jié)點為當(dāng)前節(jié)點，繼續(xù)搜索、試插過程；若當(dāng)前路徑已插滿，則創(chuàng)建新的路徑。重復(fù)上述過程，直至所有節(jié)點均被分配完成為止。

第二階段：改變車輛出發(fā)時間，以1min為間隔，讓車輛在不同的時間出發(fā)，并仍按照第一階段的算法，重新求解。在求解的同時，更新路徑方案，將成本較高的剔除。最終得到在最佳出發(fā)時間的前提下，總成本最小的路線方案。具體算法步驟如下：

Step1:確定車輛k的出發(fā)時間區(qū)間。出發(fā)時間的上界為所有剩余需求點的ETi-t(i-1)i-Sk(i-1)，出發(fā)時間的下界為所有剩余需求點的LTi-t(i-1)i-Sk(i-1)，記為[T1,T2]。

Step2:車輛k從[T1,T2]區(qū)間內(nèi)出發(fā)，對車輛K的出發(fā)時間以 1min為分隔，考慮 T2-T1+1種情況，即 k分別從T1,T1+1,T1+2,…,T2時刻出發(fā)。假設(shè)從配送中心出發(fā)的時間為T，且T1≤T≤T2，從Step3中選取配送點。

Step3：以T時刻出發(fā)，從當(dāng)前未配送的需求點中選取配送成本最低的配送點作為下一步要到達(dá)的配送點。其中配送成本包括：（1）運輸成本；（2）時間窗懲罰成本；（3）貨損成本。保存當(dāng)前路徑、更新當(dāng)前時間、更新當(dāng)前未配送的需求點。

Step4:判斷當(dāng)前需求點剩余個數(shù)，若已經(jīng)全部配送完成，則執(zhí)行Step5。若仍有需求點未配送，判斷該車輛載重是否超額；若當(dāng)前載重不能滿足剩下所有配送點，則k=k+1；并轉(zhuǎn)到Step1；否則轉(zhuǎn)到Step3，繼續(xù)選擇車輛k的下一個到達(dá)配送點。

Step5:計算該方案成本，設(shè)為W，若W小于目前最小成本，則更新最小成本為W，并保存當(dāng)前方案，并轉(zhuǎn)到Step1，直到求解最小的方案成本W(wǎng)。

5 算例分析

本算例以A公司冷鮮肉配送的相關(guān)資料為基礎(chǔ)進(jìn)行合理假設(shè)，產(chǎn)品品質(zhì)隨配送時間變化的函數(shù)關(guān)系式為：Li=Lwe-t/600。該公司從配送中心向同城的10個需求點配送冷鮮肉。各需求點的需求量及時間窗限制見表1，各節(jié)點距離情況見表2。配送車最大載重為3t，車從車場口出發(fā)，以30km/h的速度勻速行駛，最后返回配送中心。配送車內(nèi)溫度為0℃，車外溫度為20℃，單位里程的運輸成本為4元/km，車輛固定成本約為200元/次，售價和安全損失價格均為20 000元/t。各需求點的停留時間（min）根據(jù)經(jīng)驗估計為需求量(t)乘以10。早到的懲罰系數(shù)為0.1%，晚到的懲罰系數(shù)為0.2%。

表1 配送中心不同需求點的需求量及時間窗

表2 配送中心不同需求點的配送距離（km）

利用C++語言編程，實現(xiàn)本文提出的改進(jìn)算法，求解得到最終結(jié)果，見表3。

表3 計算最終結(jié)果

簡單總結(jié)如下：

第一輛車的出發(fā)時間為5：37，節(jié)點選擇為2—1—10—5；

第二輛車的出發(fā)時間為6：04，節(jié)點選擇為3—7—4；

第三輛車的出發(fā)時間為7：30，節(jié)點選擇為6—8—9。

其中，貨損成本為：13 494.271元，固定成本為：600元，運輸成本為：496元；時間懲罰成本為：0元；總成本為：14 590.27元。

通過算例結(jié)果可以看到，所有需求點的服務(wù)均在時間窗內(nèi)，即企業(yè)配送的滿意度為100%，原因在于冷鏈的特殊性。相較于普通產(chǎn)品的物流配送，時間對于冷鏈運輸至關(guān)重要，對于時間的要求也是嚴(yán)格高于其他物流配送的。所以在節(jié)點選擇時，考慮的重點就變?yōu)闀r間而非距離。這種改進(jìn)的算法，在最終求解時重點強(qiáng)調(diào)了時間因素，符合冷鏈企業(yè)在配送時的要求；同時也無需對參數(shù)進(jìn)行調(diào)試，可操作性較強(qiáng)，容易推廣。

6 結(jié)語

本文在前人研究成果的基礎(chǔ)上，考慮了冷鏈物流運輸過程中的成本因素，設(shè)置了時間窗均有的限制條件，并通過基于貪婪思想改進(jìn)的傳統(tǒng)啟發(fā)式算法進(jìn)行算例求解，最后的結(jié)果輸出全部給出了車輛的最佳出發(fā)時間，達(dá)到了預(yù)期目標(biāo)。計算結(jié)果也表明，這種在最佳出發(fā)時間條件下確定總成本最小路線的求解方法具有一定的可操作性，為求解時間要求比較嚴(yán)格的VRP模型提供了新的思路。

本文沒有考慮路況的復(fù)雜性與不確定性，在實際操作的配送過程中，城市地區(qū)道路路段上的運行速度受到天氣、交通事故及許多其它因素的影響，使得配送車輛在城市道路上的行駛時間具有隨機(jī)性。以上不足將是下一步的研究方向。

[1]Chaug-Ing Hsu,Sheng-Feng Hung,Hui-Chieh Li.Vehicle routing problem with time-windows for perishable food delivery[J].Journal of Food Engineering,2007,(80):465-475.

[2]Ana Osvald,LidijaZadnikStim.A vehicle routing algorithm for the distributionof fresh vegetables and similar perishable food[J].Journal of Food Engineering,2008,(85):285-295.

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

[4]鄭海娟.突發(fā)事件下冷鏈物流車輛路徑再規(guī)劃研究[D].北京:北京交通大學(xué),2014.

[5]繆小紅,周新年,林森,等.第三方冷鏈物流配送路徑優(yōu)化研究[J].運籌與管理,2011,20(4):32-38.

[6]潘立軍.帶時間窗車輛路徑問題及其算法研究[D].長沙:中南大學(xué),2012.

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

[8]任雪甜,朱曉敏,何中祥,等.基于改進(jìn)CK節(jié)約算法的第三方冷鏈物流企業(yè)車輛調(diào)度(英文)[J].北京交通大學(xué)學(xué)報,2015,(4):21.

Study on Cold Chain Distribution Vehicle Routing Problem Based on Improved Greed Algorithm

Li Bohao
(Business School,Beijing Technology&Business University,Beijing 100048,China)

In this paper,we built a mathematical model aiming at the minimization of the total distribution cost,then studied the optimization of the cold chain distribution route under a time window constraint,and then applied the process in connection with a numerical case using the greed-improved heuristic algorithm.

cold chain;vehicle route optimization;time window;greed algorithm

F252.14

A

1005-152X(2015)11-0137-04

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

2015-09-26

受“互聯(lián)網(wǎng)背景下的首都物流資源優(yōu)化配置研究2015”資助（19008001078）

李伯昊（1991-），男，北京人，碩士研究生，研究方向：城市配送。