改進遺傳算法求解帶模糊時間窗冷鏈配送問題

梁承姬，黃　濤，徐德洪，丁　一

(1.上海海事大學科學研究院物流研究中心， 上海201306;2.西安外事學院物流學院， 陜西西安710000)

?

改進遺傳算法求解帶模糊時間窗冷鏈配送問題

梁承姬1，黃濤1，徐德洪2，丁一1

(1.上海海事大學科學研究院物流研究中心， 上海201306;2.西安外事學院物流學院， 陜西西安710000)

摘要：為優化冷鏈物流配送路徑，降低配送成本、提高客戶對產品送達時間的滿意度水平是冷鏈物流的關鍵?？紤]到冷鏈物流承載的貨物具有一定的特殊性且對溫度的要求較高，提出在冷鏈物流配送中設定模糊時間窗反映顧客滿意度。建立了運輸成本、貨損成本、時間成本等配送成本最小化和以模糊時間窗進行量化客戶滿意度最大化的多目標優化模型，采用改進遺傳算法求解帶模糊時間窗冷鏈配送問題。通過算例分析，驗證了模型和算法的有效性與研究的實用價值。

關鍵詞：冷鏈物流;模糊時間窗;配送路徑優化;遺傳算法;顧客滿意度

0引言

冷鏈物流作為物流產業一個新興的、特殊的類別，正在當下國家振興物流產業和冷鏈物流發展規劃的背景下高速發展。冷鏈物流的特點是在整個供應鏈環節都需要對溫度進行把控，這就使得冷鏈物流相對于傳統物流成本更高，技術要求更強。在此基礎上，冷鏈物流的車輛路徑優化問題廣受關注，車輛路徑問題一直是物流配送中最重視的優化研究之一。Dantzig等[1]在1959年率先提出了車輛路徑問題的數學模型，并對模型進行求解分析。楊丹婷[2]在研究冷鏈配送時通過分析C-W節約算法、遺傳算法，粒子群算法三種算法，對不同算法的優化結果進行分析對比。廖小紅等[3]考慮單個配送中心，多個客戶點為第三方冷鏈配送模型，用改進遺傳算法加以分析求解。劉志碩等[4]在研究VRP的過程中，將蟻群算法的思想引入進來，同時針對其特點通過具有自改變功能的混合蟻群算法來解決VRP問題。

冷鏈物流對時間有較嚴格的要求，但受到調度策略和交通等主觀客觀條件的制約，將出現不能在規定的時間范圍內送達的情況。因此對車倆配送路徑優化問題的研究，通?？紤]時間窗的約束。Duygu等[5]通過加入靈活時間窗的約束，允許通過一定成本為代價超出部分時間窗，并和普通時間窗約束下的車輛路徑問題對比，驗證其可行性。Ali等[6]建立一個較為新穎的混合列生成和現代啟發式算法的數學模型，加入一般軟時間窗對車輛路徑問題進行優化，并通過該算法評估算例實驗。向金秀[7]從農產品冷鏈物流配送企業的角度出發，構造以總成本最小為目標的函數，進而得出了農產品冷鏈物流車輛配送路徑問題的優化模型。李澤華[8]在考慮多種因素影響的條件下，研究構建成本最小化的帶軟時間窗的生鮮產品配送車輛路徑問題的數學模型，通過自適應交叉率的遺傳算法進行求解。王君等[9]提出文化基因算法求解帶時間窗的物流配送車輛路徑問題，遺傳算法進行種群搜索，禁忌搜索機智進行局部搜索，然后通過可行鄰域結構避免不可行解，有效提高效率。魏凱[10]研究了帶有軟時間窗的車輛路徑問題，同時以遺傳算法和模擬退火算法相結合，在全局搜索和局部搜索上有了顯著提高，通過算例分析驗證了可行性。鄧愛民等[11]在考慮軟時間窗、車輛的固定成本、滿載系數等條件后，建立集配貨一體化車輛路徑問題數學模型。根據模擬退火算法，結合線路內和線路間交換，增加了記憶功能，采用了雙終止準則求解。周屹等[12]考慮建立一種能使配送計劃的安排在任何情況下都能統一為求解某種車輛路徑問題，采用遺傳算法計算第三方物流的帶時間窗物流配送車輛路徑問題的模型。林清國[13]通過分析比較遺傳算法、禁忌搜索算法及模擬退火算法，以遺傳算法為基礎，提出混合遺傳模擬退火算法及混合遺傳禁忌搜索模擬退火算法優化帶時間窗車輛路徑問題。Ghodratnamaa等[14]在研究流水線的多目標優化模型中提出了采用多目標粒子群算法(MOPSO)和NSAGA II算法相結合的方法解決多目標問題。李淑琴等[15]在研究環保多車型組合配送路徑時，考慮時間窗約束，采用模擬退火算法求解多目標環保多車型模型，以減少環境污染優化配送路徑為目標，求解低碳路徑優化問題。

綜上所述，傳統車輛路徑問題的研究大多數采用的是單目標模型、考慮傳統時間窗，忽略了目標的多樣性和算法的計算時間等的有效性。由于冷鏈運輸貨物的特殊性，時間窗的設定往往需要更加靈活，與客戶的聯系更加密切，不僅需要考慮成本，還需要考慮時間和客戶滿意度。本文綜合考慮了冷鏈物流配送中的成本、時間和客戶滿意度等因素，設置模糊時間窗來提高顧客的滿意度，建立了配送成本最小化和顧客滿意度最大化為目標的線性規劃模型，不同于上述文獻中多選擇單一傳統的算法求解，只能考慮個別約束條件對路徑優化的影響，同時只解決時間最短的單一目標模型。本文采用改進遺傳算法對多目標模型進行求解，增加基因修復確保算法求解符合約束條件，同時非支配排序和擁擠度策略進行解的優化。在求解多目標路徑優化問題中，可以綜合考慮多個約束條件，改進的遺傳算法能更有效地符合實際情況，并使計算結果更加精確。

1問題描述

在冷鏈物流運輸中，不同于傳統運輸配送只考慮距離成本因素，冷鏈運輸需要全程的溫度保證和時間把控。冷鏈貨物從配送中心出發至各個客戶點，需要一直調節貨箱內的溫度以保證冷鏈貨物的質量，同時越短的配送時間和服務時間就越有利于貨物的高質量，所以冷鏈運輸的時間窗約束和溫度能耗成本是關鍵所在，也是本文研究的重點。在該問題的研究中，考慮時間窗約束多為硬時間窗和軟時間窗兩種，硬時間窗即客戶點的任務必須要在規定時間內完成，軟時間窗則加入懲罰因子，如果車輛無法在規定時間窗內完成配送，將給予一定懲罰成本。

圖1　帶模糊時間窗配送圖

2模型建立

2.1問題假設

為了便于模型的建立和問題的分析求解，設定假設：主要研究進口冷凍食品由配送中心面向附近各主要客戶點的配送問題，各主要客戶點位置已知，距離已知，需求量已知；配送車輛數量已知，載重量已知；車輛從配送中心出發配送，配送完成返回配送中心；每條配送線路上的客戶點需求總量要求不大于配送車輛的最大載重量；貨物類型只有一種，每個客戶點只能被配送車輛遍歷一次。

2.2模型分析

本模型主要參數：

k：配送的車輛總數，v=1,2，…，k；

n：接受配送的客戶點，i=1,2，…，n，j=1,2..n；

a：車輛配送貨物每千米運輸成本；

dij：客戶點i與j之間的距離；

qi：客戶點i的需求量；

Q：車輛總載重量；

β：貨物對時間的敏感系數；

p：冷鏈貨物的價格；

α：裝卸過程中的貨損率；

δij：冷鏈運輸中的貨損系數；

λ1：提前服務所引起的懲罰成本；

λ2：延遲服務所引起的懲罰成本；

本文建立的是冷鏈配送問題的多目標模型，目標函數為最小化配送成本和最大化顧客滿意度，其中最小化成本目標函數包括車輛運輸成本、冷鏈貨損成本和時間窗懲罰成本。

①車輛運輸成本

車輛運輸成本即車輛在從配送中心或上一個客戶點運送至下一個客戶點所產生的運輸成本。該成本與配送路程有關，在計算時應通過決策變量判斷車輛是否經過該處。運輸成本表達如式(1)：

(1)

②冷鏈貨損成本

該成本體現了冷鏈食品運輸同其他產品配送的不同之處，由于食品的特殊性，在配送和服務過程中產生因溫度、時間等導致的貨損。在本文研究中，貨損成本包括運輸時間長短和在客戶點服務時配送效率導致溫度差兩方面因素所造成的成本。貨損成本如式(2)：

(2)

③時間窗懲罰成本和顧客滿意度

本文建立的是基于模糊時間窗的多目標冷鏈配送優化模型。模糊時間窗的設立表示車輛應盡量在顧客要求的時間窗內服務，但不同于對固定時間窗的硬性要求，而是面對大多數非剛性需求時要求服務時間外也可以進行服務，但以部分成本作為懲罰，同時將車輛服務時間轉化為顧客的滿意度，更加直觀全面地描述分析顧客需求。本文對模糊時間窗的分析設定如式(3)所示：

(3)

(4)

2.3模型建立

本文以最小化冷鏈物流配送的綜合成本和最大化顧客滿意度為目標建立數學模型。該模型綜合考慮了時間窗，運輸、貨損等成本和顧客滿意度，與傳統冷鏈路徑優化模型相比，可以相對全面地考慮冷鏈運輸的車輛路徑優化問題。這里為了方便多目標求解計算，把顧客滿意度的最大化轉化為最小化求解。

(5)

(6)

約束條件：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

目標函數(5)表示建立最小化配送成本，最大化顧客滿意度的目標模型,其中成本包括車輛運輸成本、冷鏈貨損成本和時間窗懲罰成本。目標函數(6)表示建立求解顧客滿意度最大化。建立約束條件(7)和(8)保證車輛能遍歷每一個客戶點，約束條件(9)確保車輛容量不被超出總量，約束條件(10)和(11)保證車輛從配送中心出發配送，配送完成返回配送中心。約束條件(12)確保車輛對客戶的服務發生在該客戶的模糊時間窗內。約束條件(13)為提早服務時間，同樣，約束條件(14)為延遲服務時間。約束條件(15)確保提早服務時間和延遲服務時間是非負的，即保證模糊時間窗存在。

3算法求解

圖2　算法流程圖Fig.2　The flowchart of algorithm

本文研究的是關于車輛路徑的多目標優化問題，采用的是遺傳算法求解。通過改進遺傳算法求解pareto最優解集的多目標優化問題。這種方法能通過不同代之間的優化組成潛在的最優解種群來避免局部最優從而搜索pareto最優解。本文基于非支配排序遺傳算法求解思想，改進自適應調整交叉率和變異率，較好的提高了收斂速度，通過對多目標函數的優化，最后得到Pareto最優解。與傳統算法相比，在選擇交叉后的基因修復可以有效地防止染色體不符合約束條件，合并新種群后的非支配排序和擁擠度計算又能提高對最優解選擇的精確性。對在具體遺傳算法求解過程中，求解流程如圖2。

首先生成初始種群，在父代種群通過聯賽選擇生成臨時較優種群，然后對較優種群進行先交叉再變異。交叉采用多點交叉，相對于單點交叉更有利于搜索能力和求解精度的提高，變異采用逆轉變異策略，與交叉策略同理。將交叉變異后的較優子代種群與父代種群進行重組(根據非支配排序和個體擁擠度距離的計算)生成新種群，最后滿足進化計算達到最大設定的進化代數的終止條件即終止計算，否則進行算法重啟，重新計算。

3.1染色體編碼

考慮到車輛路徑優化問題的特點，單純針對客戶的編碼方式，或者針對車輛路徑的編碼方式不能完整的對該問題有效處理，同時由于還要考慮模糊時間窗的優化以達到顧客滿意度最大的效果，所以本文采用的編碼形式是自然數編碼。染色體編碼如圖3所示，一個車輛路徑配送方案對應的染色體基因個數為(客戶點數量+車輛數-1)，各基因值為客戶點編號，“0”基因為不同車輛間的間隔符號，“0”基因的個數為(車輛數-1)，例如10個客戶點由3輛配送車完成的一個配送方案對應的染色體結構及說明如圖3所示。這樣的編碼結構簡單直接，從圖3中可知，車輛1、車輛2和車輛3服務的客戶點以及服務客戶點的順序分別為8-5-2，10-1-7-4，3-9-6。

3.2生成初始種群

初始種群是由一定數量染色體組成的群體，本文采用的是隨機生成一定數目的個體。首先任取n個基因(n=車輛數-1)，基因值設為間隔符號“0”，然后隨機將車輛編號設定給剩余的基因位，這樣就可以形成初始種群。同時設定間隔符號不能出現在基因整體的首末位或兩個間隔符號“0”相鄰，來確保種群的有效意義。

圖3　染色體編碼圖

3.3適應值函數

遺傳算法中，衡量一個個體質量優劣的標準是適應度。適應度是評價個體優劣和進行遺傳操作的重要依據，個體的適應度越大，被選擇到下一代的概率越大。本算例中選取目標函數的值為適應度值。即Fi=minLP1-100 n(minLP2)的形式，其中由于目標函數LP2是0到1內的小數，代表的是客戶對服務的滿意程度，對適應度函數的影響程度較小，所以選擇100作為變換因子，將顧客滿意度轉化為費用。

3.4選擇操作

3.5交叉操作

針對本文染色體編碼的特點，提出隨機順序交叉方法。第一步，隨機在父代的基因位中選擇兩個交叉點，交叉之間的基因位將被父代直接復制到下一代。第二步,為避免重復基因，將父代a和b基因中分別已經被父代b和a復制了的基因刪除。第三步，把a和b剩余的基因按順序分配到b和a的子代。這樣就得到了完整的沒有重復基因值的兩個子代。交叉方法如圖4所示：

圖4　順序交叉

3.6變異操作

變異操作有助于局部搜索能力的提高，同時可以保持群體的多樣性，防止早熟現象的發生。本文選擇逆轉變異方法，即在基因位中隨機選擇兩點，再將這兩點內的基因按反序插入到原來的位置中。如圖5所示。因為染色體中的間隔符“0”沒有實際意義，所以規定逆轉變異操作中不同時選擇個體的兩個“0”基因進行交換。

圖5　逆轉變異

3.7基因修復

在交叉和變異操作后，染色體將產生一些不符合模型約束條件和編碼規則的情況。因此筆者針對不符合條件的染色體進行基因修復操作，具體步驟如下：

Step 1：在交叉后，當配送車輛的數量多于兩輛時，染色體中有多個“0”出現，判斷是否存在刪除過多的“0”導致個體不一樣長。如果存在，則規定只刪除首次重復基因，如果不存在轉step 2；

Step 2：判斷染色體在交叉變異后是否存在間隔符“0”相鄰或處于基因鏈首末位的情況，這種情況會導致有車輛閑置，應修復該位置的基因，完成基因修復。

3.8非支配排序和擁擠度策略

多目標優化問題的設計關鍵在于求取Pareto最優解集。NSGA-Ⅱ算法中的快速非支配排序是依據個體的非劣解水平對種群分級，其作用是指引搜索向Pareto最優解集方向進行。高媛[16]在研究非支配排序遺傳算法NSGA-Ⅱ中，擴展算法的應用范圍，提出一種新的解決函數擬合問題的方法。本文通過引入NSGA-Ⅱ算法思想求解多目標冷鏈配送模型。在非支配排序和擁擠度策略中，與傳統計算方法相比，簡化了搜索和計算步驟，以保持種群的多樣性和避免算法發生早熟收斂。在整體算法安排中，改進了計算順序，先通過遺傳算法操作形成新的子代，與父代合并后再進行非支配排序和擁擠度策略。采用這種求解步驟，有利于擴大Pareto最優解集的搜索范圍，它是一個循環的適應值分級過程，如圖6以及下列流程所示：

非支配排序：

①讓等級計數r變為0；

②使得r=r+1；

③從種群中找出非支配解集，設為第一級，將其所有個體賦予非支配級r；

④把賦予非支配級的個體從種群中刪去；

⑤判斷種群是否為空，是，則停止運算，不是，則到第二步繼續運算；

擁擠距離計算：

①初始化每個個體i擁擠度為0，即：di=0, i=1,2,…,Z；

②對于每一個目標函數fk，k=1,2,…,n升序排序成組；

③設置兩端個體的擁擠度：d1=dZ=∞；

④令j=2到(Z-1)，設dj=dj+(fkj+1-fkj-1)。

擁擠度選擇算子：經過排序和擁擠距離的計算，群體中每個個體i都得到兩個屬性，一個是非支配級r，另一個是擁擠度di。根據結果，定義選擇排序規則：x>yifrxdy。這樣，就可以在父代子代合并的混合種群中選擇出符合條件的新種群。

圖6　NSGA-Ⅱ流程圖

4算例分析

表1　客戶點初始數據

根據表1數據，利用改進遺傳算法解決多目標冷鏈配送車輛路徑問題，通過計算獲得帕累托最優解，如表2和圖7。

圖7　Pareto最優解圖Fig.7　Figure of pareto optimal

解集配送總成本顧客滿意度1(A)4350.99323950.96733600.9534(B)3320.94153010.9162930.877(C)2830.82

由圖7得出，最優方案為B點，即目標函數1的值為332元，目標函數2的值為0.941，即完成該算例中的冷鏈物流配送所需的配送總成本為332元，同時顧客滿意度為94.1%。車輛在配送中訪問的路徑順序見表3。

由于本文是基于改進遺傳算法求解的多目標冷鏈配送問題，所以在相同控制參數條件下，利用標準遺傳算法，針對該問題進行搜索。搜索過程中的種群代數、染色體個數和變異概率等控制參數與上述改進遺傳算法中的完全相同，得到最優配送路線如表4，冷鏈物流配送所需的配送總成本為461元，顧客滿意度為87.3%。

根據表3和表4結果對比得知，基于改進遺傳算法求解得到的最優訪問路徑，能夠多方面考慮冷鏈配送優化，通過pareto最優求解有效兼顧成本和顧客滿意度的雙重優化，不僅配送總成本優于標準遺傳算法，同時保證顧客滿意度達到相同成本下的最優，更能接近理想解。因此，本文采用改進的遺傳算法，在求解冷鏈貨物配送路線優化問題時明顯優于標準遺傳算法。

表3　基于改進遺傳算法的多目標任務結果表

表4　基于標準遺傳算法的多目標任務結果表

5結語

根據冷鏈物流配送中實際考慮的因素，本文建立了以運輸成本、貨損成本，時間成本等成本優化和顧客滿意度優化為目標的多目標數學模型。成本模型中以貨損系數來突出貨損成本，時間窗懲罰來突出時間成本的控制。在考慮成本的同時，設立模糊時間窗，綜合考慮顧客滿意度，達到成本最小化和顧客滿意度最大化的優化效果。通過改進的遺傳算法，考慮NSGA-Ⅱ算法的非支配排序和擁擠度計算因素，進行求解，獲得了Paretp最優解。在算例分析的實際驗證中表明該算法對解決冷鏈物流配送問題有良好的效果。

參考文獻:

[1]DANTZIG G,RAMSER J.The truck dispatching problem[J]. Management Science, 1959 (6): 80-91.

[2]楊丹婷.冷鏈物流配送路徑優化研究[D]. 大連:大連海事大學,2014.

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

[4]劉志碩,申金升,柴躍廷.基于自適應蟻群算法的車輛路徑問題研究[J]. 控制與決策,2005,20(5):562-566.

[5]DUYGU T, OLA J, TOM V W. A vehicle routing problem with flexible time windows[J]. Computers & Operations Research,2014,52:39-54.

[6]ALI K B,SEYED R H,A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window[J]. Information Sciences,2015,316:598-615.

[7]向金秀.帶時間窗的農產品冷鏈物流車輛路徑問題研究[D]. 大連:大連海事大學,2011.

[8]李澤華.帶時間窗約束的生鮮產品配送車輛路徑優化問題研究[D]. 大連:大連海事大學,2009.

[9]王君,李波.帶時間窗車輛路徑問題的文化基因算法[J]. 計算機工程與應用,2012,48(7):26-29.

[10]魏凱.改進遺傳算法在軟時間窗車輛路徑問題中的應用[D]. 安徽:安徽工業大學,2013.

[11]鄧愛民,毛超,周彥霆.帶軟時間窗的集配貨一體化VRP改進模擬退火算法優化研究[J]. 系統工程理論與實踐,2009,29(5):187-192.

[12]周屹,李海龍,王銳.遺傳算法求解物流配送中帶時間窗的VRP問題[J]. 吉林大學學報,2008,46(2):300-304.

[13]林清國.基于混合遺傳算法的有時間窗車輛路徑問題研究[D]. 山東:山東大學,2007.

[14]GHODRATNAMAA A, JOLAIB F, TAVAKKOLI-MOGHADDAMB R. Solving a new multi-objective multi-route flexible flow line problem by multi-objective particle swarm optimization and NSGA-II[J]. Journal of Manufacturing Systems,2015,36:189-202.

[15]李淑琴,楊斌,趙磊,等.需求帶時間窗的環保多車型組合配送路徑優化[J]. 廣西大學學報(自然科學版),2013,38(2):388-394.

[16]高媛.非支配排序遺傳算法(NSGA)的研究與應用[D]. 浙江:浙江大學,2006.

(責任編輯梁碧芬)

收稿日期：2016-01-22；

修訂日期：2016-02-21

基金項目：國家自然科學基金資助項目(71471110；71301101)；中國博士后科學基金資助項目(2014M550084)；上海市科委資助項目(14170501500)；陜西省社會科學基金資助項目(2015D060)

通訊作者：梁承姬(1970—)，女(朝鮮族)，吉林龍井人，上海海事大學教授；E-mail:liangcj@shmtu.edu.cn。

doi:10.13624/j.cnki.issn.1001-7445.2016.0826

中圖分類號：TP301.6

文獻標識碼：A

文章編號：1001-7445(2016)03-0826-10

A solution for cold chain distribution with fuzzy time window based on improved genetic algorithm

LIANG Cheng-ji1, HUANG Tao1, XU De-hong2, DING Yi1

(1. Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China;2. Logistics Institute Xi’an International University, Xi’an 710000, China)

Abstract：The key problemsto optimize the path of cold chain logistics distribution include reducing the cost of distribution and improving the customer satisfaction level of product delivery time.Considering the specificity of cold-chain logistics and higher requirements for temperature,fuzzy time windowreflecting customer satisfactionis introduced into cold chain logistics distribution.A multi-objective mathematical model is established, which is to minimize the distribution costs including transportation costs, damage costsand time costs, and to maximize the customer satisfaction quantified by fuzzy time window.The model is solved by an improved genetic algorithm. The effectiveness of the model and the algorithm is verified by a certain example.

Key words：cold-chain logistics;fuzzy time window; distribution path optimization; genetic algorithm; customer satisfaction

引文格式： 梁承姬，黃濤，徐德洪,等.改進遺傳算法求解帶模糊時間窗冷鏈配送問題[J].廣西大學學報(自然科學版)，2016，41(3)：826-835.