[摘要] 本文基于建立一種多目標(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)化

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

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

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

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

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

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

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

式(4)

式(5)

0nkL式(6)

式(7)

式(8)

式(9)

式(10)

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

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

1.編碼方法

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

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

2.基本操作算子

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

三、小結(jié)

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

參考文獻(xiàn)：

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

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