多物流配送中心路徑優(yōu)化問(wèn)題及其遺傳算法

1、多物流配送中心路徑優(yōu)化問(wèn)題及其遺傳算法廖成林柳茂森(重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院，重慶，400030)摘 要： 論文建立了多物流配送中心路徑優(yōu)化問(wèn)題的數(shù)學(xué)模型，并針對(duì)該問(wèn)題的特點(diǎn)構(gòu)造出求解該問(wèn)題的遺傳算法，把多物流配送中心路徑優(yōu)化問(wèn)題綜合起來(lái)用一個(gè)數(shù)學(xué)模型求解。本文提出了無(wú)效基因的概念，從而不局限于使得個(gè)體中每個(gè)基因都必須表達(dá)出來(lái)，因此增強(qiáng)了編碼的靈活性。仿真實(shí)驗(yàn)證明了該方法的有效性和可操作性。關(guān)鍵詞：無(wú)效基因遺傳算法物流配送1 引言物流配送是物流管理中一個(gè)極其重要的環(huán)節(jié)，它是指按用戶的訂貨要求,在配送中心進(jìn)行分貨、配貨,并將配好的貨物及時(shí)送交收貨人的活動(dòng)。物流配送主要研究車輛調(diào)度及路徑安排問(wèn)題

2、。近年來(lái)，國(guó)內(nèi)外學(xué)者對(duì)物流配送問(wèn)題進(jìn)行了大量的研究，這些研究主要集中在單物流配送中心的車輛調(diào)度及路徑安排方面。由于配送路徑優(yōu)化問(wèn)題是一個(gè)NP難題，因此，研究者大都使用啟發(fā)式算法和智能算法或者是在智能算法優(yōu)化過(guò)程中加入優(yōu)化策略以構(gòu)造混合智能算法來(lái)求解物流配送問(wèn)題。但是，目前國(guó)內(nèi)外對(duì)多個(gè)物流配送中心的物流配送問(wèn)題的研究成果很少，而且現(xiàn)有研究成果大都是把多個(gè)配送中心問(wèn)題通過(guò)任務(wù)分派轉(zhuǎn)化為單物流配送中心問(wèn)題來(lái)研究13，使用這種方法把需求點(diǎn)預(yù)先劃分給各個(gè)配送中心，在求解過(guò)程中再作適當(dāng)?shù)恼{(diào)整，這種方法其實(shí)只是單物流配送中心優(yōu)化的簡(jiǎn)單組合，通常只能求得近似最優(yōu)配送方案。魏百鑫等 4 針對(duì)整車配送需求點(diǎn)分散特

3、征解決了多倉(cāng)庫(kù)的整車配送問(wèn)題，但并不是一個(gè)通用的解決多物流中心配送問(wèn)題的方法。由于遺傳算法具有良好的全局尋優(yōu)性能，并且對(duì)不要求搜索空間具是連續(xù)的，這正符合該問(wèn)題的特點(diǎn)和要求。因此本文亦采用遺傳算法求解。本文基于整體路徑最優(yōu)由多個(gè)物流配送中心同時(shí)服務(wù)多個(gè)需求點(diǎn)建立一個(gè)通用的多物流配送中心的配送模型，并給出求解算法。單物流配送中心路徑優(yōu)化問(wèn)題可以事先確定需要派出的車次，但是多物流配送中心路徑優(yōu)化問(wèn)題中，每個(gè)配送中心需要派出多少車次是不確定的，因此，無(wú)法用常規(guī)的方法確定染色體的長(zhǎng)度。為解決基因編碼的問(wèn)題，本文提出了無(wú)效基因的概念。所謂無(wú)效基因就是在一次基因表達(dá)的過(guò)程中不作表達(dá)的基因。但是，在交叉過(guò)程

4、中無(wú)效基因處可以被選為交叉點(diǎn)，交叉后無(wú)效基因可能轉(zhuǎn)化為有效基因。因此，有些基因時(shí)而是有效基因時(shí)而是無(wú)效基因，因而無(wú)效基因在不清楚有些基因是否表達(dá)較好的時(shí)候起到緩沖作用。2 模型的建立多物流配送路徑優(yōu)化問(wèn)題可描述為：從多個(gè)配送中心用多輛配送車向多個(gè)需求點(diǎn)送貨，每個(gè)需求點(diǎn)的位置和需求量一定，要求安排合理的配送路線，使得目標(biāo)函數(shù)最優(yōu)或接近最優(yōu)。為了研究的方便且具有實(shí)際意義，做以下假設(shè)：(1) 每條配送路徑上各需求點(diǎn)的需求量之和不超過(guò)配送車的載重量；(2) 每個(gè)需求點(diǎn)都必須滿足，且只能由一輛配送車送貨。本文的各種符號(hào)及其含義做如下說(shuō)明：M配送中心的個(gè)數(shù)i配送中心的下標(biāo)j配送車輛的下標(biāo)k需求點(diǎn)的下標(biāo)N需

5、求點(diǎn)的個(gè)數(shù)Li第i個(gè)配送中心的配送車的個(gè)數(shù)Qij第i個(gè)配送中心的第j輛車的載重量qk第k個(gè)需求點(diǎn)的需求量dk（i）dk（2）從需求點(diǎn)k到k的運(yùn)距d0k配送中心到需求點(diǎn)k的運(yùn)距nj第i個(gè)配送中心的第j輛車配送的需求點(diǎn)個(gè)數(shù)，nj=0表示未使用第j輛車Rj-第i個(gè)配送中心的第j輛車配送的路徑rjk第i個(gè)配送中心的第j輛車配送的第k個(gè)需求點(diǎn)，rj0表示配送中心Q = minQij,i = 1,2, ,M ; j = 1,2,N qk k =1n = 1J I + 1其中，口表示不大于括號(hào)內(nèi)數(shù)字的最大整數(shù)Q J若以配送路徑最短為目標(biāo)函數(shù)，則可以建立如下配送路徑的優(yōu)化模型： M LinijminZ'

6、; dr 一rdr nr f nj 1rij k -1 rijkrijOrijnijiji =1 j =1 IL k =1nij、qrjk iQj2k =10±nN3M Li工工, = N4i 1 j =1Rij w k rijk w1,2,N1,k = 1,2, ,nj 口 A D=飛 i i -i r i (1) = i Ri(1)j區(qū)(2打(2) - - i i , j j61nij - 1f n 二ijij；0其他上述模型中：(1)式為目標(biāo)函數(shù)；(2)式保證每條路徑上各客戶的貨物需求量之和不超 過(guò)配送車輛的載重量；(3)式表明每條路徑上的客戶數(shù)不超過(guò)總客戶數(shù)；(4)式表明每個(gè)

7、 客戶都得到配送服務(wù)；(5)式表示每條路徑的客戶的組成；(6)式限制每個(gè)客戶僅能由一臺(tái) 配送車輛送貨；式表示當(dāng)?shù)趇個(gè)配送中心的第j輛車服務(wù)的客戶數(shù)1時(shí),說(shuō)明該臺(tái)車參 加了配送，則取f (nj) = 1，當(dāng)?shù)趇個(gè)配送中心的第j輛車服務(wù)的客戶數(shù) 1時(shí)，表示未使用該 臺(tái)車輛，因此取f (nj) = 0。3遺傳算法設(shè)計(jì)3.1 編碼方法的確定和初始種群的產(chǎn)生根據(jù)多物流配送中心路徑優(yōu)化問(wèn)題的特點(diǎn)，作者提出了一種配送中心和需求點(diǎn)直接排列的編碼方法。這種表示方法是直接生產(chǎn) N個(gè)1N間的互不重復(fù)的自然數(shù)給這N個(gè)需求點(diǎn)編碼，再生產(chǎn)M個(gè)-M-1之間的互不重復(fù)的負(fù)整數(shù)給這 M個(gè)配送中心編碼。 把這M個(gè)-M-1之間的互

8、不重復(fù)的負(fù)整數(shù)各n個(gè)和這N個(gè)1N間的互不重復(fù)的自然數(shù)各一個(gè)組成一個(gè)長(zhǎng)度為n*M+N的數(shù)列，數(shù)列的第一個(gè)位置隨機(jī)排上一個(gè)負(fù)整數(shù)，其余位置隨機(jī)全排列，即形成一個(gè)染色體。隨機(jī)產(chǎn)生 m個(gè)這樣的個(gè)體即可形成種群規(guī)模為 m的初始種群。這樣的染色體結(jié)構(gòu)可解釋為：(1)從負(fù)數(shù)對(duì)應(yīng)的配送中心出發(fā)向緊接著該負(fù)數(shù)后面的若干個(gè)正數(shù)所對(duì)應(yīng)的需求 點(diǎn)配送，再回到該配送中心，形成一條子路徑。(2)后面未緊接著正數(shù)的負(fù)數(shù)為無(wú)效基因，不表示任何意義，但是可以在該基因 處進(jìn)行交叉操作。若交叉后該負(fù)數(shù)后面緊接正數(shù)，則該負(fù)數(shù)由無(wú)效基因變?yōu)?有效基因，其意義與(1)所述相同。例如染色體(-1, -4, 1, 2, -1, -2, -3

9、, 3, 4, 5,-5)表示的意義：r子路徑1：配送中心-4 需求點(diǎn)1 -需求點(diǎn)2 配送中心-4=、子路徑2： 配送中心 -3a需求點(diǎn)33需求點(diǎn)4)需求點(diǎn)5a配送中心 -3其中，-2、-5和兩個(gè)-1都是無(wú)效基因。這種染色體結(jié)構(gòu)子路徑內(nèi)部是有序的，子路徑中需求點(diǎn)1和2交換位置，會(huì)使目標(biāo)函數(shù)值改變；而子路徑之間是無(wú)序的，若子路徑1和2交換位置，卻不會(huì)改變目標(biāo)函數(shù)值。3.2 適應(yīng)度評(píng)估方法的確定。適應(yīng)度函數(shù)同目標(biāo)函數(shù)有關(guān)，要求非負(fù)，通過(guò)變換目標(biāo)函數(shù)得到適應(yīng)度函數(shù)：fk =bz'/ zk。其中，b為常數(shù)，z'為初始群體中最好的染色體配送距離，zk為當(dāng)前染色體對(duì)應(yīng)的配送距離。3.3 選

10、擇操作。本文采用如下最佳個(gè)體保留與賭輪選擇相結(jié)合的選擇策略：將每代群體中的m個(gè)個(gè)體按適應(yīng)度由大到小排列，排在第一位的個(gè)體性能最優(yōu)，將它復(fù)制一個(gè)直接進(jìn)入下一代，并排在第一位;下一代群體的另m -1個(gè)個(gè)體需要根據(jù)前代群體的m個(gè)個(gè)體的適應(yīng)度，采用賭輪選擇 法產(chǎn)生，具體地說(shuō)，就是首先計(jì)算上代群體中所有個(gè)體適應(yīng)度的總和2 Fj，再計(jì)算每個(gè)個(gè)體的適應(yīng)度所占的比例Fj/2 Fj （j = 1 ,2 , ?,m），以此作為其被選擇的概率。上述選擇方法既可 保證最優(yōu)個(gè)體生存至下一代，又能保證適應(yīng)度較大的個(gè)體以較大的機(jī)會(huì)進(jìn)入下一代。3.4 交叉操作對(duì)通過(guò)選擇操作產(chǎn)生的新群體，除排在第一位的最優(yōu)個(gè)體外，另m - 1

11、個(gè)個(gè)體要按交叉概率Pc進(jìn)行配對(duì)交叉重組。本文采用類 OX法實(shí)施交叉操作，其操作過(guò)程為：如果染色體交 叉點(diǎn)處的兩個(gè)基因都為負(fù)數(shù)，則直接用基于序的交叉進(jìn)行運(yùn)算；如果染色體交叉點(diǎn)處的 基因不全為負(fù)數(shù)，則將交叉點(diǎn)左移（右移），直到左右兩個(gè)交叉點(diǎn)處的基因都為負(fù)數(shù)，再進(jìn) 行運(yùn)算.如：父代 1: -1, -4, | 1, 2, | -1, -2, -3, 3, 4, 5, -5父代2: -5, -1, 3, 1, 5, -2,1 -4, 4,| 2, -1, -3I I內(nèi)為匹配段，經(jīng)過(guò)最大保留交叉運(yùn)算后形成子代 1:-1,1,-4,4,2,-1, -2,-3,3,5, -5子代2:-5,-1,3,5,-2,

12、-4, 1,2,-1,4, -33.5 變異操作由于在選擇機(jī)制中采用了保留最佳個(gè)體的方式，為保持群體內(nèi)個(gè)體的多樣化，本文采 用連續(xù)多次對(duì)換的變異技術(shù)，使個(gè)體在排列順序上有較大的變化。變異操作是以概率Pm發(fā)生的，一旦變異操作發(fā)生，則用隨機(jī)方法產(chǎn)生交換次數(shù)J對(duì)所需變異操作的個(gè)體的基因 進(jìn)行J次對(duì)換（對(duì)換基因的位置也是隨機(jī)產(chǎn)生的）。3.6 終止準(zhǔn)則采用最佳個(gè)體保留指定代數(shù)的終止準(zhǔn)證，即若某個(gè)體在連續(xù)若干代都是最佳個(gè)體， 說(shuō)明該個(gè)體是很好的個(gè)體，則停止操作。4仿真實(shí)驗(yàn)本文用matlab編制了多物流配送中心路徑優(yōu)化問(wèn)題的遺傳算法計(jì)算程序。 算例：有兩 個(gè)配送中心各兩輛配送車向9個(gè)需求點(diǎn)配送，配送車的載重

13、量均是10噸。配送中心（編號(hào) 為-1和-2）與需求點(diǎn)之間以及需求點(diǎn)相互之間的距離 dkdk、9個(gè)客戶的需求量qk均見下 表1。要求安排合理的配送路線，使得總的配送路徑最短。根據(jù)算例的特點(diǎn)，在用遺傳算法對(duì)其求解時(shí)采用了一下參數(shù)：種群規(guī)模取 25,進(jìn)化 代數(shù)取100,交叉概率取0.9,變異卞S率取0.01,對(duì)不可行路徑的懲罰權(quán)重取100km。對(duì)算 例求解10次，所得的計(jì)算結(jié)果見表2。表1算例的已知條件表dk(1)k(2) (km) kk-1-2123456789-10106124104610133-2012812468499101351189131062015101081051130106.510

14、1114640373108505712760884701210801090qk (t)-344232321表2算例的遺傳算法計(jì)算結(jié)果計(jì)算次序1234567891o""平均配送總距離(km)67646870646864676864首次搜索到最終解的代數(shù)43383642535749 514852由表2可以看出：用遺傳算法對(duì)算例的10次求解中，有4次得到了問(wèn)題的最優(yōu)解64km(其對(duì)應(yīng)的配送路徑方案為：路徑1:-1,1,3,-1;路徑2: -1, 5, 6, 9,-1;路徑3: -2, 4, 7,-2;路徑4: -2, 2, 8, -2) , 6次得到了問(wèn)題的近似最優(yōu)解，這種方法求

15、解多物流配送中 心路徑優(yōu)化問(wèn)題明顯的優(yōu)于把多個(gè)配送中心問(wèn)題通過(guò)任務(wù)分派轉(zhuǎn)化為單物流配送中心問(wèn) 題求解。5 結(jié)束語(yǔ)(1)本文建立了一個(gè)多物流配送中心模型，并基于多物流配送中心配送的特點(diǎn)，設(shè)計(jì)了 求解算法。由于每個(gè)配送中心需要派出多少車次是不確定的，文章通過(guò)采用無(wú)效基因很 好的解決了這個(gè)由于各配送中心需要派出多少車次不確定引起的對(duì)個(gè)體無(wú)法編碼的問(wèn) 題。這樣就可以把多個(gè)物流配送中心配送優(yōu)化問(wèn)題用一個(gè)數(shù)學(xué)模型來(lái)求解，這種方法要 優(yōu)于把需求點(diǎn)預(yù)先劃分給各個(gè)配送中心，以轉(zhuǎn)化為單物流配送中心求解的方法。(2)遺傳算法是模擬生物遺傳學(xué)的規(guī)律的算法，但是，在生物體內(nèi)的基因是存在無(wú)效基 因的，而目前使用的遺傳算法

16、編碼的基因都是有效的。因此，無(wú)效基因的概念的提出是 遺傳算法的一次發(fā)展，拓寬了遺傳算法適用范圍，也使得遺傳算法更接近生物遺傳的規(guī) 律。本文設(shè)計(jì)個(gè)體的編碼方法對(duì)解決類似的組合優(yōu)化問(wèn)題具有一定的參考價(jià)值。(3)個(gè)體中增加了無(wú)效基因，就等于在更大的空間內(nèi)尋優(yōu)。這樣一來(lái)就加大了尋優(yōu)的難度，需要迭代更多的代數(shù)才能尋得最優(yōu)解或近似最優(yōu)解。如何降低迭代次數(shù)以盡快尋得 最優(yōu)解或近似最優(yōu)解，有待進(jìn)一步研究。參考文獻(xiàn)1 張俊偉，王 勃,馬范援.多倉(cāng)庫(kù)多配送點(diǎn)的物流配送算法J .計(jì)算機(jī)工程,2005 ,31 (21) :192 - 194.2 Skok M , Skrlec D , Krajcar S. The g

17、enetic algorithm methodfor multiple depot capacitated vehicle routing problem solving C/ / The Fourth International Conference on Knowled ge -based Intelligent Engineering Systems & Allied Technologies.Brighton ,U K: U K Press , 2000 :520 - 526.3 Filipec M , Skrlec D , Krajcar S. Genetic algorithm approachfor multiple depot capacitated vehicle routing problem solvingwith heuristic improvements built - inJ .International Jour2nal of Modeling and Simulation , 2000,20 (4) :320 - 328.4 魏百鑫，史海波.基于整車配送的多倉(cāng)庫(kù)開路VRPTW問(wèn)題的研究與實(shí)現(xiàn)J .信 息與控制,2005 ,34 (3) :350 - 355.5李大衛(wèi)，王莉，王夢(mèng)光.遺傳算法在有