李伯昊

（北京工商大學 商學院，北京 100048）

基于改進貪婪算法的冷鏈配送車輛路徑問題

李伯昊

（北京工商大學 商學院，北京 100048）

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

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

1 引言

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

2 文獻綜述

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

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

3 模型分析與建立

3.1 問題描述

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

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

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

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

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

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

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

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

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

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

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

約束條件：

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

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

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

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

3.3 決策變量定義：

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

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

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

Ski：車輛k在需求點i的服務時間，即裝卸搬運時間，一般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ā)時的時間；

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

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

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

p：貨物的單位價值；

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

CHS：貨損成本；

CGD：固定成本；

CYS：運輸成本；

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

3.4 配送成本分析

本文的目標為尋找滿足顧客需求量、時間窗、求總成本最小的配送方案，其中，成本包括：生鮮產(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到達需求點i的時間；Sk為車輛k從配送中心出發(fā)時的時間；Qi為需求點i的貨物需求量的質(zhì)量；P1為單位生鮮產(chǎn)品的損失價值。

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

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

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

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

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

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

4 基于貪婪思想改進的算法求解

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ù)才能得到較好的解，這就有可能使其擴展到其它情形帶來一定的困難。鑒于此，本文采用一種基于貪婪思想改進的傳統(tǒng)啟發(fā)式算法，從另一個角度求解帶時間窗的冷鏈車輛路徑模型。

4.2 算法設(shè)計

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

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

4.3 算法步驟

改進的算法分兩個階段：

第一階段：初始配送中心為當前節(jié)點；每次從當前節(jié)點開始搜索，從未分配路徑節(jié)點中，選擇離當前節(jié)點總成本最少的，嘗試插入當前路徑中。若約束條件可以滿足，則更新插入節(jié)點為當前節(jié)點，繼續(xù)搜索、試插過程；若當前路徑已插滿，則創(chuàng)建新的路徑。重復上述過程，直至所有節(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ā)，從當前未配送的需求點中選取配送成本最低的配送點作為下一步要到達的配送點。其中配送成本包括：（1）運輸成本；（2）時間窗懲罰成本；（3）貨損成本。保存當前路徑、更新當前時間、更新當前未配送的需求點。

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

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

5 算例分析

本算例以A公司冷鮮肉配送的相關(guān)資料為基礎(chǔ)進行合理假設(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)本文提出的改進算法，求解得到最終結(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é)果可以看到，所有需求點的服務均在時間窗內(nèi)，即企業(yè)配送的滿意度為100%，原因在于冷鏈的特殊性。相較于普通產(chǎn)品的物流配送，時間對于冷鏈運輸至關(guān)重要，對于時間的要求也是嚴格高于其他物流配送的。所以在節(jié)點選擇時，考慮的重點就變?yōu)闀r間而非距離。這種改進的算法，在最終求解時重點強調(diào)了時間因素，符合冷鏈企業(yè)在配送時的要求；同時也無需對參數(shù)進行調(diào)試，可操作性較強，容易推廣。

6 結(jié)語

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

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

[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è)科學,2013,40(9):178-181.

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

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

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

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

[8]任雪甜,朱曉敏,何中祥,等.基于改進CK節(jié)約算法的第三方冷鏈物流企業(yè)車輛調(diào)度(英文)[J].北京交通大學學報,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-），男，北京人，碩士研究生，研究方向：城市配送。