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

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

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

?

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

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

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

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

關(guān)鍵詞：冷鏈物流;模糊時間窗;配送路徑優(yōu)化;遺傳算法;顧客滿意度

0引言

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

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

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

1問題描述

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

圖1　帶模糊時間窗配送圖

2模型建立

2.1問題假設(shè)

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

2.2模型分析

本模型主要參數(shù)：

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

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

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

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

qi：客戶點i的需求量；

Q：車輛總載重量；

β：貨物對時間的敏感系數(shù)；

p：冷鏈貨物的價格；

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

δij：冷鏈運輸中的貨損系數(shù)；

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

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

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

①車輛運輸成本

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

(1)

②冷鏈貨損成本

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

(2)

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

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

(3)

(4)

2.3模型建立

本文以最小化冷鏈物流配送的綜合成本和最大化顧客滿意度為目標(biāo)建立數(shù)學(xué)模型。該模型綜合考慮了時間窗，運輸、貨損等成本和顧客滿意度，與傳統(tǒng)冷鏈路徑優(yōu)化模型相比，可以相對全面地考慮冷鏈運輸?shù)能囕v路徑優(yōu)化問題。這里為了方便多目標(biāo)求解計算，把顧客滿意度的最大化轉(zhuǎn)化為最小化求解。

(5)

(6)

約束條件：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

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

3算法求解

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

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

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

3.1染色體編碼

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

3.2生成初始種群

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

圖3　染色體編碼圖

3.3適應(yīng)值函數(shù)

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

3.4選擇操作

3.5交叉操作

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

圖4　順序交叉

3.6變異操作

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

圖5　逆轉(zhuǎn)變異

3.7基因修復(fù)

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

Step 1：在交叉后，當(dāng)配送車輛的數(shù)量多于兩輛時，染色體中有多個“0”出現(xiàn)，判斷是否存在刪除過多的“0”導(dǎo)致個體不一樣長。如果存在，則規(guī)定只刪除首次重復(fù)基因，如果不存在轉(zhuǎn)step 2；

Step 2：判斷染色體在交叉變異后是否存在間隔符“0”相鄰或處于基因鏈?zhǔn)啄┪坏那闆r，這種情況會導(dǎo)致有車輛閑置，應(yīng)修復(fù)該位置的基因，完成基因修復(fù)。

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

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

非支配排序：

①讓等級計數(shù)r變?yōu)?；

②使得r=r+1；

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

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

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

擁擠距離計算：

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

②對于每一個目標(biāo)函數(shù)fk，k=1,2,…,n升序排序成組；

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

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

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

圖6　NSGA-Ⅱ流程圖

4算例分析

表1　客戶點初始數(shù)據(jù)

根據(jù)表1數(shù)據(jù)，利用改進(jìn)遺傳算法解決多目標(biāo)冷鏈配送車輛路徑問題，通過計算獲得帕累托最優(yōu)解，如表2和圖7。

圖7　Pareto最優(yōu)解圖Fig.7　Figure of pareto optimal

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

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

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

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

表3　基于改進(jìn)遺傳算法的多目標(biāo)任務(wù)結(jié)果表

表4　基于標(biāo)準(zhǔn)遺傳算法的多目標(biāo)任務(wù)結(jié)果表

5結(jié)語

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

參考文獻(xiàn):

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

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

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

[4]劉志碩,申金升,柴躍廷.基于自適應(yīng)蟻群算法的車輛路徑問題研究[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]向金秀.帶時間窗的農(nóng)產(chǎn)品冷鏈物流車輛路徑問題研究[D]. 大連:大連海事大學(xué),2011.

[8]李澤華.帶時間窗約束的生鮮產(chǎn)品配送車輛路徑優(yōu)化問題研究[D]. 大連:大連海事大學(xué),2009.

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

[10]魏凱.改進(jìn)遺傳算法在軟時間窗車輛路徑問題中的應(yīng)用[D]. 安徽:安徽工業(yè)大學(xué),2013.

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

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

[13]林清國.基于混合遺傳算法的有時間窗車輛路徑問題研究[D]. 山東:山東大學(xué),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]李淑琴,楊斌,趙磊,等.需求帶時間窗的環(huán)保多車型組合配送路徑優(yōu)化[J]. 廣西大學(xué)學(xué)報(自然科學(xué)版),2013,38(2):388-394.

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

(責(zé)任編輯梁碧芬)

收稿日期：2016-01-22；

修訂日期：2016-02-21

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

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

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

中圖分類號：TP301.6

文獻(xiàn)標(biāo)識碼：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ìn)遺傳算法求解帶模糊時間窗冷鏈配送問題[J].廣西大學(xué)學(xué)報(自然科學(xué)版)，2016，41(3)：826-835.