(推薦下載)多物流配送中心路徑優(yōu)化問題及其遺傳算法

1、（完整 word 版）多物流配送中心路徑優(yōu)化問題及其遺傳算法編輯整理:尊敬的讀者朋友們：這里是精品文檔編輯中心， 本文檔內(nèi)容是由我和我的同事精心編輯整理后發(fā)布的， 發(fā)布之前我們 對文中內(nèi)容進(jìn)行仔細(xì)校對，但是難免會有疏漏的地方，但是任然希望（完整word版）多物流配 送中心路徑優(yōu)化問題及其遺傳算法）的內(nèi)容能夠給您的工作和學(xué)習(xí)帶來便利。同時也真誠的希望 收到您的建議和反饋，這將是我們進(jìn)步的源泉，前進(jìn)的動力。本文可編輯可修改,如果覺得對您有幫助請收藏以便隨時查閱,最后祝您生活愉快業(yè)績進(jìn)步,以 下為（完整word版）多物流配送中心路徑優(yōu)化問題及其遺傳算法的全部內(nèi)容。多物流配送中心路徑優(yōu)化問題及其遺傳算

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

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

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

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

6、-需求點的下標(biāo)N-垂求占的個埶L,-第入配送中心的配送車的個數(shù)Qj_第i個配送中心的第j輛車的載重量qk-第k個需求點的需求量dkcU-從需求點k到k的運距dou-配送中心到需求點k的運距g-第i個配送中心的第j輛車配送的需求點個數(shù)，g 二0表示未使用第j輛車際- 第i個配送中心的第j輛車配送的路徑r,-第i個配送中心的第j輛車配送的第k個需求點，表示配送中心0 = m in 0, i = 1,2,;丿 =1,2,，厶若以配送路徑最短為目標(biāo)函數(shù)，則可以建立如下配送路徑的優(yōu)化模型:nu陽k -QiJ（3）J=N（4）AIj=i其中,表示不大于括號內(nèi)數(shù)字的最大整數(shù)nVminZ =k=I 做+ 呦伽

7、Rqerijkc1,2,= 1,2,知 （5）jA Ri（2）j=0R幻，巧f（7）上述模型中：（D式為目標(biāo)函數(shù)；（2）式保證每條路徑上各客戶的貨物需求量之 和不超過配送車輛的載重量；（3）式表明每條路徑上的客戶數(shù)不超過總客戶數(shù)；（4）式表明每個客戶都得到配送服務(wù)；（5）式表示每條路徑的客戶的組成；（6）式限制每個客戶僅能由一臺配送車輛送貨；（7）式表示當(dāng)?shù)趇個配送中心的第j輛車服務(wù)的客戶數(shù)時，說明該臺車參加了配送，則取f（m）= 1,當(dāng)?shù)趇個配送 中心的第j輛車服務(wù)的客戶數(shù)1時，表示未使用該臺車輛，因此取f （nJ二0 o 3遺傳算法設(shè)計3. 1編碼方法的確定和初始種群的產(chǎn)生根據(jù)多物流配送中

8、心路徑優(yōu)化問題的特點，作者提出了一種配送中心和需求點 直接排列的編碼方法。這種表示方法是直接生產(chǎn)N個廣N間的互不重復(fù)的自然數(shù)給 這N個需求點編碼，再生產(chǎn)M個一MT 之間的互不重復(fù)的負(fù)整數(shù)給這M個配送中 心編碼。把這M個-MT 之間的互不重復(fù)的負(fù)整數(shù)各n個和這N個廣N間的互不 重復(fù)的自然數(shù)各一個組成一個長度為n*M+N的數(shù)列，數(shù)列的第一個位置隨機(jī)排上 一個負(fù)整數(shù)，其余位置隨機(jī)全排列，即形成一個染色體。隨機(jī)產(chǎn)生ni個這樣的個體 即可形成種群規(guī)模為m的初始種群.這樣的染色體結(jié)構(gòu)可解釋為：（1）從負(fù)數(shù)對應(yīng)的配送中心出發(fā)向緊接著該負(fù)數(shù)后面的若干個正數(shù)所對應(yīng)的需求點配送，再回到該配送中心，形成一條子路徑。

9、（2）后面未緊接著正數(shù)的負(fù)數(shù)為無效基因，不表示任何意義，但是可以在該基 因處進(jìn)行交叉操作若交叉后該負(fù)數(shù)后面緊接正數(shù)，則該負(fù)數(shù)由無效基因變?yōu)橛行Щ?，其意義與（1）所述相同。例如染色體（-1, 4, 1,2, 1, -2, 3,3, 4, 5, 5）表示的意義:子路徑1：配送中心-4 需求點1需求點2配送中心-4子路徑2：配送中心_3需求點3需求點4需求點5配送中心_3其中，-2s -5和兩個 T 都是無效基因.這種染色體結(jié)構(gòu)子路徑內(nèi)部是有序的，子 路徑中需求點1和2交換位置，會使目標(biāo)函數(shù)值改變;而子路徑之間是無序的，若子 路徑1和2交換位置，卻不會改變目標(biāo)函數(shù)值。3.2適應(yīng)度評估方法的確定。適

10、應(yīng)度函數(shù)同目標(biāo)函數(shù)有關(guān)，要求非負(fù)，通過變換目標(biāo)函數(shù)得到適應(yīng)度函數(shù)：fk=bz/zko其中，b為常數(shù)，/為初始群體中最好的染色體配送距離，zk為當(dāng)前染色體對應(yīng)的配送距 離.3 3選擇操作本文采用如下最佳個體保留與賭輪選擇相結(jié)合的選擇策略:將每代群體中的H1個個 體按適應(yīng)度由大到小排列，排在第一位的個體性能最優(yōu)，將它復(fù)制一個直接進(jìn)入下 一代，并排在第一位；下一代群體的另m 1個個體需要根據(jù)前代群體的m個個 體的適應(yīng)度，采用賭輪選擇法產(chǎn)生，具體地說，就是首先計算上代群體中所有個體/()=1 10其他適應(yīng)度的總和Fj,再計算每個個體的適應(yīng)度所占的比例Fj/XFj （j = 1 ,2 , ，m）,以此作

11、為其被選擇的概率。 上述選擇方法既可保證最優(yōu)個體生存至下一代, 又能保證適應(yīng)度較大的個體以較大的機(jī)會進(jìn)入下一代。3.4交叉操作對通過選擇操作產(chǎn)生的新群體,除排在第一位的最優(yōu)個體外，另m 1個個體要按 交叉概率Pc進(jìn)行配對交叉重組。本文采用類0X法實施交叉操作，其操作過程為： 如果染色體交叉點處的兩個基因都為負(fù)數(shù)，則直接用基于序的交叉進(jìn)行運算；如 果染色體交叉點處的基因不全為負(fù)數(shù)，則將交叉點左移（右移），直到左右兩個交 叉點處的基因都為負(fù)數(shù)，再進(jìn)行運算。女山父代1 ： 1, 4, |1,2,| 1, -2, -3, 3, 4,5, 5父代2：5, -1, 3, 1, 5, -2, | -4, 4

12、, | 2, -1,-3I I內(nèi)為匹配段，經(jīng)過最大保留交叉運算后形成子代1 ： 1, 1, 4, 4, 2, -1,-2,3, 3,5,一5子代2：5, 1,3,5,-2,-4, 1,2, -1, 4, -33.5變異操作由于在選擇機(jī)制中采用了保留最佳個體的方式,為保持群體內(nèi)個體的多樣化，本 文采用連續(xù)多次對換的變異技術(shù)，使個體在排列順序上有較大的變化。變異操作是 以概率Pm發(fā)生的，一旦變異操作發(fā)生，則用隨機(jī)方法產(chǎn)生交換次數(shù)J，對所需變異 操作的個體的基因進(jìn)行J次對換（對換基因的位置也是隨機(jī)產(chǎn)生的）。3.6終止準(zhǔn)則采用最佳個體保留指定代數(shù)的終止準(zhǔn)證，即若某個體在連續(xù)若干代都是最佳個 體，說明該

13、個體是很好的個體,則停止操作。4仿真實驗本文用mat I ab編制了多物流配送中心路徑優(yōu)化問題的遺傳算法計算程序算例: 有兩個配送中心各兩輛配送車向9個需求點配送，配送車的載重量均是10噸配送 中心（編號為 T 和-2）與需求點之間以及需求點相互之間的距離dk（1）dk、9個客戶 的需求量qk均見下表1。要求安排合理的配送路線，使得總的配送路徑最短。根據(jù)算例的特點， 在用遺傳算法對其求解時采用了一下參數(shù):種群規(guī)模取25,進(jìn)化代數(shù)取100,交叉概率取0。9,變異概率取0.01,對不可行路徑的懲罰權(quán)重取100km。對算例求解10次，所得的計算結(jié)果見表2.表1算例的已知條件表dkk8k(km) k9

14、_2123456710106124104610133-2012812468499101351189131062015101081051130106o 5101114640373108505712760884701210801090Qk(t)344232321表2算例的遺傳算法計算結(jié)果計算次序110平均23456789配送總距離（km）67646468706468646768首次搜索到最終解的代數(shù)43523836425357495148由表2可以看出：用遺傳算法對算例的10次求解中，有4次得到了問題的最優(yōu) 解64km（其對應(yīng)的配送路徑方案為:路徑路徑2：1, 5, 6, 9, 1路徑3：-2,

15、4,7, -2;路徑4:-2,2,8,-2） , 6次得到了問題的近似最優(yōu)解，這 種方法求解多物流配送中心路徑優(yōu)化問題明顯的優(yōu)于把多個配送中心問題通過任務(wù) 分派轉(zhuǎn)化為單物流配送中心問題求解。5結(jié)束語（1）本文建立了一個多物流配送中心模型，并基于多物流配送中心配送的特點，設(shè) 計了求解算法。由于每個配送中心需要派出多少車次是不確定的，文章通過采用無 效基因很好的解決了這個由于各配送中心需要派出多少車次不確定引起的對個體無 法編碼的問題.這樣就可以把多個物流配送中心配送優(yōu)化問題用一個數(shù)學(xué)模型來求 解，這種方法要優(yōu)于把需求點預(yù)先劃分給各個配送中心，以轉(zhuǎn)化為單物流配送中心 求解的方法。（2）遺傳算法是模

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

17、:192 194.2 Skok M , SkrIec D , Krajcar S。The genet i c a Igor i thmmethodfor mu Itiple depot capac itated veh i cIe routing prob Iem so Iving C/ / The Fourth International Conferenee on Know Ied ge -basedI nteI Ii gent Eng i neer i ng Systems & Al Iied Techno Iogies.Brighton ,U K: U K Press , 20

18、00 :520 - 526.3 FiIipec M , SkrIec D , Krajcar So Genet i c a Igor i thm approachfor multipIedepot capac i tated veh i cIe routing prob Iem so Iv i ngwith heur i sticimprovements built - inJ . International Jour2naI of Mode Ii ng and Si mu I at i on ,2000 ,20 (4): 320 328。4 魏百鑫，史海波.基于整車配送的多倉庫開路VRPTW問題的研究與實現(xiàn)J o信息與控制，2005 , 34 (3):350 -