基于ＤＮＡ進(jìn)化算法的多目標(biāo)物流配送路徑優(yōu)化

[摘要] 本文基于建立一種多目標(biāo)物流配送車輛調(diào)度模型的基礎(chǔ)上，采用DNA進(jìn)化算法求解該問題，克服傳統(tǒng)算法的求解速率低，易陷入局部最優(yōu)的問題，為進(jìn)一步研究物流配送優(yōu)化調(diào)度問題提供參考。

[關(guān)鍵詞] 物流配送 車輛調(diào)度DNA進(jìn)化算法 優(yōu)化

物流配送是整個物流過程中最為重要環(huán)節(jié)，如何實現(xiàn)快速而準(zhǔn)確的配送是企業(yè)在經(jīng)營方面必須解決的重要課題，運用科學(xué)方法合理組織物流配送，以提高企業(yè)的服務(wù)質(zhì)量、減少庫存、降低經(jīng)營成本、增加經(jīng)濟(jì)效益是十分必要。本文將研究基于DNA進(jìn)化算法的多目標(biāo)物流配送路徑優(yōu)化問題。

一、配送車輛調(diào)度（VSP）問題的數(shù)學(xué)模型

基于直觀描述的無時限單向物流配送車輛調(diào)度問題的一般描述為：設(shè)物流中心有K臺配送車輛，每臺車的載重為，一次行駛的最大路程為Dk。需要向L個客戶送貨，每位客戶的客運需求為，客戶i到j(luò)的運距為dij，物流中心到客戶 的運距為，再設(shè)nk為第k臺車輛配送的客戶數(shù)（nk=0表示未使用第k臺車輛），用集合Rk表示第k條路徑，其中元素Rki表示客戶Rki在路徑k中的順序為i（不包括物流中心），令RK0=0表示物流中心。

若以配送車輛數(shù)最少為優(yōu)化目標(biāo)時，目標(biāo)函數(shù)表示為:式(1)

若以配送總里程最短為優(yōu)化目標(biāo)時，目標(biāo)函數(shù)表示為:式(2)

若以配送車輛的總噸位公里數(shù)最少為優(yōu)化目標(biāo)時，目標(biāo)函數(shù)表示為:式(3)

約束函數(shù)為式(4-10)

式(4)

式(5)

0nkL式(6)

式(7)

式(8)

式(9)

式(10)

二、DNA進(jìn)化算法

DNA進(jìn)化算法是對單親生物自然進(jìn)化過程和行為的一種模擬。在DNA中，分裂能繁衍生成具有等價關(guān)系意義下的同類個體，變異操作實現(xiàn)不同類個體間的演化。分裂和變異操作后分別經(jīng)水平選擇和垂直選擇，使群體得到雙向進(jìn)化，增加優(yōu)化效果，得到更優(yōu)解。

1.編碼方法

為了節(jié)省存儲空間，提高運行效率，對于多目標(biāo)物流配送問題采取自然編碼。首先構(gòu)造DNA單鏈，針對研究本文研究的問題，將DNA分子中的每個基因用客戶編號表示，隨機產(chǎn)生一個1～n 的序列（n表示客戶總數(shù)），這樣一個個體就產(chǎn)生了，重復(fù)上述過程，產(chǎn)生多個個體組成的初始群種。

在此算法中，個體適應(yīng)值采用其目標(biāo)函數(shù)。對于某個單鏈個體其目標(biāo)函數(shù)值為Zij，對應(yīng)的配送路徑方案的不可行路徑數(shù)為 表示該抗體對應(yīng)一個可行解），評價函數(shù)值為，定義適應(yīng)值函數(shù)為：，其中R為對每條不可行路徑的懲罰權(quán)重可根據(jù)目標(biāo)函數(shù)的取值范圍取一個相對較大的正數(shù)。

2.基本操作算子

DNA進(jìn)化編碼采用分裂、變異和選擇三種算子，其中選擇算子有兩個，分別是水平選擇算子和垂直選擇算子。分裂算子是產(chǎn)生新個體的方法，根據(jù)自身進(jìn)行繁殖得到后代，避免陷入局部最優(yōu)，分裂得到的個體多是經(jīng)過恒等變換，反演變換，同互補和異互補得到；水平選擇算子是從分裂集中選取一個DNA表形，不僅挑出最好的個體，而且最差的個體；變異算子是對經(jīng)過水平選擇的各個體進(jìn)行變異操作，由于研究問題的解的范圍較大，因此采用領(lǐng)域變異，最好個體的鄰域空間是將個體中的第一個基因和后面的每一個基因進(jìn)行依次交換得到的鄰域空間，最差個體的鄰域空間是隨機產(chǎn)生的1～n（客戶總數(shù)）的兩個數(shù)，將這兩個數(shù)中間的基因段進(jìn)行交換得到的鄰域空間；垂直選擇算子是從變異領(lǐng)域中選擇出某一變型，使得個體遷移，從而得到它的最優(yōu)變形型；將變異后的個體通過適應(yīng)值函數(shù)的求解從而得到最優(yōu)解。

三、小結(jié)

本文研究了DNA進(jìn)化算法，并對算法的變異操作進(jìn)行改進(jìn)，將這種算法運用于多目標(biāo)物流配送問題中，為進(jìn)一步研究物流配送優(yōu)化調(diào)度問題并用于實際，提高企業(yè)效益提供參考。

參考文獻(xiàn)：

[1]李軍郭耀煌.:物流配送車輛優(yōu)化調(diào)度理論[M].北京：中國物資出版社，2001，2～13

[2]余文李人厚:一種有效的雙向進(jìn)化算法[J].小型微型計算機系統(tǒng)，2003，24(3):527～530