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

李伯昊

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

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

李伯昊

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

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

冷鏈；車輛路徑優化；時間窗；貪婪算法

1 引言

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

2 文獻綜述

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

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

3 模型分析與建立

3.1 問題描述

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

3.2 假設與約束條件

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

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

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

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

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

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

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

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

（8）產品配送過程中車輛內外均保持恒定溫度。

約束條件：

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

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

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

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

3.3 決策變量定義：

Xijk：0-1變量，若車輛k由i經過 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需求量呈正相關；

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

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

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

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

Qi：需求點i的需求量；

Qo：車輛額定載重；

K：可用車輛；

Po：單位配送成本；

Lw：生鮮產品完好時物品的質量；

Li：生鮮產品到需求點i時物品的質量；

β：生鮮產品對時間的敏感系數；

W：產品在某一衡定溫度下變質的一個常速變化值；

P1：單位生鮮產品的損失價值。

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

λ：提前到達時的懲罰系數；

θ：晚點到達時的懲罰系數；

M：非常大的正數；

p：貨物的單位價值；

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

CHS：貨損成本；

CGD：固定成本；

CYS：運輸成本；

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

3.4 配送成本分析

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

貨損成本。考慮到生鮮產品運輸時其溫度往往為一已知值，尤其是經由冷鏈運輸時其溫度一般為一恒定值，為了簡化起見，本文假設生鮮產品在某一衡定溫度下，其變質速率為一常數W，而定義生鮮產品在其物流配送過程中隨時間變化的品質函數為：Li=LwWe-βt，其中，Lw為生鮮產品完好時物品的質量，t為產品經歷的物流時間，β為生鮮產品對時間的敏感系數，W是產品在某一衡定溫度下變質的一個常速變化值。在上述變質函數中，如果物品對時間非常敏感，β的取值相對小一些，反之取值則大一些。假定Lw=Qi，則整個配送過程中的貨損成本變為

其中Tki為車輛k到達需求點i的時間；Sk為車輛k從配送中心出發時的時間；Qi為需求點i的貨物需求量的質量；P1為單位生鮮產品的損失價值。

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

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

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

圖1 時間窗懲罰成本函數

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

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

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

4.1 算法選擇

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

4.2 算法設計

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

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

4.3 算法步驟

改進的算法分兩個階段：

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

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

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

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

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

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

Step5:計算該方案成本，設為W，若W小于目前最小成本，則更新最小成本為W，并保存當前方案，并轉到Step1，直到求解最小的方案成本W。

5 算例分析

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

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

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

利用C++語言編程，實現本文提出的改進算法，求解得到最終結果，見表3。

表3 計算最終結果

簡單總結如下：

第一輛車的出發時間為5：37，節點選擇為2—1—10—5；

第二輛車的出發時間為6：04，節點選擇為3—7—4；

第三輛車的出發時間為7：30，節點選擇為6—8—9。

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

通過算例結果可以看到，所有需求點的服務均在時間窗內，即企業配送的滿意度為100%，原因在于冷鏈的特殊性。相較于普通產品的物流配送，時間對于冷鏈運輸至關重要，對于時間的要求也是嚴格高于其他物流配送的。所以在節點選擇時，考慮的重點就變為時間而非距離。這種改進的算法，在最終求解時重點強調了時間因素，符合冷鏈企業在配送時的要求；同時也無需對參數進行調試，可操作性較強，容易推廣。

6 結語

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

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

[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]呂俊杰,孫雙雙.基于鮮活農產品冷鏈物流配送的車輛路徑優化研究[J].廣東農業科學,2013,40(9):178-181.

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

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

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

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

[8]任雪甜,朱曉敏,何中祥,等.基于改進CK節約算法的第三方冷鏈物流企業車輛調度(英文)[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

受“互聯網背景下的首都物流資源優化配置研究2015”資助（19008001078）

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