基于遺傳算法并考慮時間窗的冷鏈產品配送路徑優化

侯 玲，張治國，徐英展

（1.四川大學錦城學院，四川 成都 611731；2.成都信息工程大學 物流學院，四川 成都 610103）

1 引言

隨著經濟發展和生活水平的逐漸提高，人們對生鮮產品的需求逐年增加，冷鏈配送得到高速發展。冷鏈物流需要在整個供應鏈環節對溫度進行控制，以保證配送產品的質量，因此冷鏈配送有較強的時效性和質量要求。如何在降低物流成本的情況下優化配送車輛路徑，實現快速準時配送，受到廣泛關注。

Dantzig和Ramser[1]在1959年率先提出了車輛路徑問題的數學模型，并對模型進行求解分析；Pedro Amorim[2]等研究了葡萄牙產品配送車輛路徑優化問題，但沒有涉及貨物在運輸中的損耗問題。我國對生鮮物流配送車輛路徑的研究要滯后于國外，但仍然有很多學者取得了相應的成果：如李雅萍[3]研究了鮮活農產品的冷鏈物流車輛路徑問題，將固定成本、運輸成本和時間窗約束進行整合處理；潘璠，等[4]將物流及時性和客戶配送與客戶服務公平性考慮到生鮮產品配送車輛路徑問題中，但是并沒有引入時間窗等針對生鮮特殊屬性的約束要求；葛顯龍，等[5]提出帶有時間窗的生鮮物流配送車輛路徑問題，并設計自適應遺傳算法求解了該模型。

通過以上分析總結可以看到，國內外學者們對VRP問題進行了許多探討，由于生鮮產品的特有屬性，其配送問題涉及到運輸方案、模型目標等不同，因此在建模和求解算法上存在很大區別，已有文獻多是沿用傳統VRP問題的研究方法，沒有充分考慮生鮮物流配送的損耗、客戶的時間窗要求和需求動態性。

本文對冷鏈配送進行分析，充分考慮配送成本最小化和客戶滿意度最大化，在配送路徑優化模型基礎上為每個客戶設置時間窗，在模型中加入時間窗約束，規定配送車輛必須在時間窗范圍內到達客戶位置并對其進行服務，若超過時間窗規定則會舍棄掉該規劃方案；同時引用冷鏈產品腐蝕模型來評價配送產品的新鮮程度，在提高客戶滿意度的同時，優化后的路徑使配送成本最小。在模型求解過程中，設計自適應遺傳算法，通過MATLAB編程運算，得到全局最優解，并通過算例進行驗證。

2 問題描述

本文所描述的冷鏈配送車輛路徑優化問題是指一個配送中心有若干冷藏車，已知多個冷鏈配送需求點，且冷藏車能滿足多個配送點的需求。冷藏車從配送中心出發，按照規劃的配送順序，將貨品依次送至客戶手中。其中，配送的貨物為冷鏈生鮮產品，配送中心與各需求點以及各需求點之間的距離已知，配送中心的貨物容量能滿足所有需求點的貨量需求，冷藏車的容量、運輸費率、冷藏費率已知，生鮮產品的損耗系數已知，各冷藏車的載貨量及費用相同，客戶的需求量、要求運達時間窗已知。在上述條件已知的情況下，科學合理的對配送車輛進行路徑優化，合理規劃派送順序，在產品配送滿足所有客戶時間窗要求的前提下，使配送總成本達到最小。

3 模型建立

3.1 建模思路

本文以配送總成本最小為前提，在總成本的計算中加入產品腐敗成本和時間窗限制。不同客戶有不同的時間窗要求，當一種配送方案的配送到達時間無法滿足所有客戶的時間窗要求時，將這種配送方案舍去。在客戶滿意度達到最大的情況下，得到最優的配送方案。

該冷鏈配送車輛路徑優化模型主要考慮以下幾點：

（1）冷鏈產品因其易腐特性，無法長時間保鮮，因產品腐敗產生的費用是配送總成本的重要組成。本模型加入貨損成本，更具現實意義。

（2）由于冷鏈產品易變質的特性，客戶對配送時間都會有較嚴格的要求，而且貨品配送至客戶位置后，一般都會進行二次加工，不能在規定時間內將貨物配送至客戶手中就會大大降低客戶滿意度。本文路徑優化模型加入客戶時間窗要求，滿足不同客戶的時間要求，提升了客戶滿意度。

（3）模型以總成本最小化為目標函數，其中總成本包括車輛的派遣成本、運輸成本、制冷成本以及冷鏈產品的變質損耗成本。在合理前提以及約束限制下，通過合理規劃車輛配送順序，使得在配送總成本最小的同時滿足所有客戶的時間窗要求。

（4）合理使用車輛資源。盡量以較少的冷藏車輛滿足所有客戶需求，減少車輛派遣費用，同時要求一輛冷藏車服務的客戶不能過多，防止車輛超載和因服務時間過長而造成超時配送。

（5）減少單個客戶的被服務次數。指一個客戶僅由一輛冷藏車進行配送，避免客戶的貨品需求被分割，減少客戶操作次數的同時降低配送環節總成本。

3.2 模型的一般假設

在冷鏈配送環節中存在很多不可避免的復雜因素，如道路狀況、車輛狀況、天氣等復雜因素，這些因素無法避免并會導致計算結果存在一些細微誤差，但不影響優化合理性。因此，本文進行以下合理假設：

（1）假設配送道路均為暢通，冷藏車在配送中視為勻速運動；

（2）冷藏車的載重量可以滿足若干個需求點的需求量；

（3）冷藏車載重量等參數均相同且狀況良好；

（4）客戶的需求量、位置、時間要求等參數已知；

（5）配送中心的容量可以滿足所有需求；

（6）所運載貨品為單一類型的貨品；

（7）在配送過程中，冷藏車車廂內外的溫度保持恒定不變。

3.3 模型的約束條件

本文配送路徑優化模型必須在滿足一定約束條件下進行，在約束條件的限制下求得總成本最低方案。根據冷鏈配送的實際情況，針對模型的基本條件，提出約束條件如下：

（1）冷藏車配送路徑起點和終點均為冷藏庫；

（2）規劃方案要滿足所有需求點的需求量；

（3）冷藏車的裝載量必須小于冷藏車的額定裝載量；

（4）一輛冷藏車可以負責多個配送點的配送任務；

（5）每個配送點只能由一輛冷藏車一次性完成配送；

（6）車輛必須在需求點的時間窗內送達。

3.4 模型的參數設置

O表示冷鏈配送中心；

M={i=1,2,...,M0}表示配送需求點即客戶的集合；

N={n=1,2,…,N0}表示冷藏車的集合；

P表示冷藏車的最大容量；

Fn表示第n臺冷藏車的派遣成本，Cp為總派遣成本；

c0為冷藏車每公里運輸成本，C0為冷藏車總運輸成本；

α為制冷劑單價,β為單位時間制冷劑消耗量，Cf表示配送過程總制冷成本；

price為配送貨品單價，η為冷鏈配送中貨品的

U=O?M表示所有節點的集合，包括冷鏈配送中心和需求點；

Qi表示第i個客戶的冷藏品配送量；損耗系數；

dij表示從需求點i到需求點j的路程長度；

tij表示從需求點i到需求點j的運輸時長，其中i,j∈U；

ti1表示客戶的時間窗上限，ti2表示客戶的時間窗下限，其中i∈U；

V為冷藏車行駛的平均速度；

Ctotal表示冷鏈物流配送總成本。

決策變量：

Xijn表示第n(n ∈N )輛冷藏車是否從需求點i到需求點j(i ,j∈M )間進行派送，值為1時表示是，值為0時表示否；

Yin表示第i(i∈M)個需求點是否由第n輛冷藏車進行派送，值為1時表示是，值為0時表示否；

3.5 冷鏈產品物流配送成本分析

（1）車輛派遣費用。車輛派遣費用主要包括車輛保養、維護以及人力資本費用等，包含哪些費用及如何計算費用視具體情況而定，為方便計算，不進行展開細化，車輛派遣成本可以表示為：

（2）運輸成本。運輸成本指在配送環節中，因車輛行駛而產生的費用，一般指油耗費用。總運輸成本C0可表示為：

（3）制冷成本。冷鏈配送環節中，冷藏車通過一些措施來控制車內溫度，使貨品一直保存在低溫環境中。在配送過程中，一直會有制冷費用的產生，制冷費用與運輸時間有關，本文用β表示制冷劑單位時間的消耗量，冷鏈配送運輸過程中制冷成本費用可表示為：

（4）冷鏈產品損耗成本。由于冷鏈產品的易腐敗特性，在低溫配送過程中，雖然處于相對低溫的狀態，但仍然存在腐蝕變質過程。本文在冷鏈產品配送環節成本中增加了因冷鏈產品腐敗而帶來的腐敗損耗成本。

因本文討論的冷鏈產品配送一般為市內配送，配送時間相對較短，并且冷藏車車廂內部處于相對低溫環境，冷鏈產品的腐敗速率大大減小，運用簡單的常速連續型質變曲線來描述冷鏈產品配送過程中的品質變化情況，如圖1所示。

圖1 常速質變連續型質變曲線

運輸過程中貨品的損耗系數為η，冷鏈產品單價為price，則運輸過程中冷鏈產品的損耗成本Cs可以表示為：

因冷鏈產品品類眾多，大多數包裝良好，如紅酒、牛奶等生鮮產品，在配送環節中基本不會發生腐敗情況，所以損耗成本計算要根據實際情況而定。

3.6 模型建立

模型中各表達式含義如下：

目標函數（5）為冷鏈配送的總成本，包括車輛派遣成本、運輸成本、制冷成本與貨品損耗成本，模型以總成本最小化為決策目標；式（6）限制冷藏車不能超載；式（7）表示出發冷藏車總數不得大于最大車輛數N0；式（8）表示配送起點和終點均為配送中心；式（9）表示一個需求點只能由一輛冷藏車完成配送；式（10）為流量守恒限制，即到達需求點的車輛必須離開需求點；式（11）為各需求點間行駛時間的計算公式；式（12）表示冷藏車需要在規定時間內到達客戶位置；式（13）、式（14）為決策變量。

4 基于遺傳算法的模型求解

由于問題的復雜性，本文采用遺傳算法求解，具體算法流程如圖2所示。

4.1 染色體編碼

進行染色體編碼時，需要將所有車輛的線路選擇情況轉化為遺傳算法的染色體集合，每條染色體代表著不同的車輛路徑選擇方案，通過對每條染色體的適應度評價和遺傳操作，篩選出較優的線路方案。

本文采用實數編碼的方法，以需求點的個數即客戶數量M0作為基因長度，第M個基因位即代表第M個需求點。用車輛數量N0作為基因位的基因值，即1到N0的隨機整數，代表每個需求點被分配到的配送車輛。如染色體4242113表示第5、6個需求點由車輛1配送，第2、4個需求點由車輛2進行配送，第7個需求點由車輛3進行配送，第1、3個需求點由車輛4進行配送。

這種編碼方式只體現了冷藏車需要對哪幾個配送需求點進行配送，而沒有將具體的配送順序體現出來，所以在后續的適應度計算中，會將不同車輛的需求點按時間窗排序，以時間窗排序的結果進行適應度計算。

圖2 遺傳算法流程圖

4.2 種群初始化

種群初始化是遺傳操作的開始，初始種群由一定規模的不同個體組成，通過適應度的計算、選擇、交叉、變異等操作生成子代群體，之后不斷進行迭代計算，直到達到模型算法的終止條件。所以，初始種群的個體數量影響著后續遺傳操作過程，由于模型程序的特殊性，當初始種群過小時，可能出現種群中無可適應環境的個體的情況，無法進行后續的遺傳操作；當初始種群過大時，則會導致運算時間過長，降低計算效率。

本文討論的冷鏈產品配送，一般為市內短途配送，所涉及需求點較少，不需要很大的初始種群規模，因此，初始群體中的染色體數定為100個，運用MATLAB程序生成100行、M0列的矩陣，使用實數編碼生成初始種群。

4.3 適應度函數處理

適應度用來表示每條染色體的生存概率，用適應度函數求出每一代種群中所有染色體的生存概率，從而根據每條染色體的生存概率進行比較和篩選。由于本文的目標函數為配送總成本最小，因此，在目標函數的處理上以總成本的倒數作為適應度函數，即f=1/Ctotal。如果染色體所對應的配送方案違反了模型的約束條件，則將該方案的配送成本Ctotal設為inf，即無限大，使得該染色體的適應度f=0。

4.4 遺傳操作

（1）選擇算子。選擇操作的目的是選擇較好的個體進入下一代，淘汰掉適應度差的個體。選擇操作以適應度的大小為依據判斷個體是否能進入下一代，即種群基因的優勝劣汰。本文選擇輪盤賭策略和最大保留策略相結合的方法來選擇算子。輪盤賭策略是通過個體適應度占群體總適應度的比例計算出來，通過個體適應度的占比來選擇個體，但是當種群數量過大時，往往不能選擇合適的算子，即相當于隨機選擇個體，所以結合最大保留策略，即將群體中適應度最高的個體保存到下一代，并且保留的個體不進行交叉變異操作，以確保目前較好的染色體會保留到子代，提高算法的有效性，促進算法收斂。

（2）交叉操作。交叉操作是生成新染色的主要途徑，通過將兩條染色體的部分基因互換來生成新的染色體，參加交叉的染色體由交叉概率來確定，本文采取單點交叉的方法隨機選擇一個位置作為交叉點進行配對交叉，如圖3所示。

圖3 交叉操作示意圖

（3）變異操作。為了擴大遺傳算法的搜索空間，對部分染色體進行變異操作，通過改變某個染色體的部分基因來生成新的染色體，進行變異操作的個體通過變異概率進行選擇。本文采用產生隨機數的方法進行變異，即隨機選擇一個基因位進行變異，如圖4所示。

4.5 終止條件

當整個基因流程操作循環次數達到迭代次數上限時，即可得到最優染色體，從而得出最優的行車線路方案。

圖4 變異操作示意圖

5 算例分析

5.1 算例數據

以某牛奶公司部分配送訂單為例，該公司對市內12個配送點進行配送，配送出發點和終點為0，配送需求點為12家超市，配送中心與12個配送點的間距見表1。

表1 配送中心及配送點間距表（單位：km）

每天運載奶制品的冷藏車從配送中心出發的時間為上午8:00，出發后，依次到達各個配送需求點位置進行配送。每個客戶的時間窗和需求量各不相同，為方便程序計算，將客戶要求到貨時間轉換為發車時間的差值的時間窗，當天客戶的時間窗和需求量見表2。

公司的冷藏車采用耗油制冷，通過計算即可得出單位時間內的制冷成本αβ=7元/h。冷藏車每公里的運輸成本c0=0.75元/km。以客戶數目換算人力資源使用費用為車輛派遣成本，車輛派遣成本為Cp=60元。冷藏車在市區中的行駛速度V=40km/h，因運輸產品為包裝較好的牛奶，所以在計算成本的過程中不計算貨品的損耗成本，所以η=0。

每輛冷藏車能裝載100件牛奶，客戶的需求量訂單也以件數為單位，故以牛奶的件數為冷藏車裝載量和客戶需求量單位，車輛載重P=100。

表2 配送點的需求量與時間窗

5.2 參數設定

需求點數量M0=12；配送站點閑置冷藏車數N0=5；冷藏車的額定載重量P=100；冷藏車每公里的運輸成本c0=0.75；冷藏車單位時間的制冷成本αβ=7；貨品的損耗系數η=0；冷藏車行駛的平均速度V=40；遺傳算法交叉概率jc=0.9；遺傳算法變異概率by=0.1；遺傳算法每代個體數gan=100；遺傳算法迭代次數gn=100。

5.3MATLAB求解

本文運用MATLAB2013a進行編程求解冷鏈產品配送路徑優化問題，設定好參數后在MATLAB2013a中導入程序代碼，即可得出最佳路線方案。

冷藏車1：配送中心→配送點1→配送點3→配送點7→配送點9→配送中心；

冷藏車2：配送中心→配送點8→配送點11→配送中心；

冷藏車3：未發車；

冷藏車4：配送中心→配送點12→配送點4→配送點5→配送點2→配送點6→配送點10→配送中心；

冷藏車5：未發車。

具體各配送點到達時間見表3。

冷藏車返回配送站點的時間也做了記錄，記錄情況如下：

冷藏車1：發車時間8:00，返回配送站點時間10:04，耗時124min；

表3 配送點到達時間

冷藏車2：發車時間8:00，返回配送站點時間9:08，耗時68min；

冷藏車3：未發車；

冷藏車4：發車時間8:00，返回配送站點時間10:19，耗時139min；

冷藏車5：未發車。

5.4 優化結果分析

本文運用數學模型和遺傳算法，通過MATLAB編程進行求解運算，并以某牛奶公司的部分配送數據為例，規劃了一套新的冷鏈配送車輛路徑規劃方案，可以從以下兩個方面檢驗方案的可行性：

（1）配送路徑的合理性。被選中的3輛冷藏車從配送中心出發，按照各自的配送順序依次對客戶完成配送服務，完成所有配送服務后返回配送中心。

（2）配送的時間窗約束。本文的配送模型加入了時間窗的約束條件，目的是讓所有冷藏車都能在客戶規定的時間內到達客戶位置，若算例的優化結果發生了提前配送或者超時配送的情況，則說明模型算法不合理。由表3可知，冷藏車到達客戶位置對客戶進行服務的時間均在客戶的時間窗要求內，3條配送線路均沒有出現提前配送或者超時配送的情況，滿足了所有客戶的時間窗要求，對客戶滿意度有很大的提升。

綜上所述，通過本文的模型與算法得出的配送車輛路徑規劃方案科學合理，路徑無交叉、重復的現象，同時，得出的車輛路徑規劃方案滿足了所有客戶的時間窗，有效提升了客戶滿意度。

6 結語

本文綜合考慮了冷鏈物流的易腐敗特點、客戶的時間窗要求等，以總成本最低為數學模型的決策目標，提出產品冷鏈物流配送路徑優化的數學模型，然后合理使用并改進遺傳算法，使用MATLAB數學軟件進行編程求解，合理規劃冷鏈配送車輛的行駛路徑。最后以某牛奶公司的配送情況為算例，優化配送路線，使配送車輛都能在規定時間窗內對客戶進行服務，提升了客戶滿意度，真實反映最小化配送總成本的同時達到全局優化。

本文設計的數學模型與算法編程仍有一定的局限性。如當訂單過多、約束條件過多時，可能出現無法進行遺傳操作的情況，所以當出現訂單過多的情況時，要結合實際情況，對遺傳算法的部分參數進行修改，如種群數量、迭代次數以及交叉變異的概率，從而使模型算法更加高效地運行。