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

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

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

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

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

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

6、-需求點(diǎn)的下標(biāo)N-垂求占的個(gè)埶L,-第入配送中心的配送車的個(gè)數(shù)Qj_第i個(gè)配送中心的第j輛車的載重量qk-第k個(gè)需求點(diǎn)的需求量dkcU-從需求點(diǎn)k到k的運(yùn)距dou-配送中心到需求點(diǎn)k的運(yùn)距g-第i個(gè)配送中心的第j輛車配送的需求點(diǎn)個(gè)數(shù)，g 二0表示未使用第j輛車際- 第i個(gè)配送中心的第j輛車配送的路徑r,-第i個(gè)配送中心的第j輛車配送的第k個(gè)需求點(diǎn)，表示配送中心0 = m in 0, i = 1,2,;丿 =1,2,，厶若以配送路徑最短為目標(biāo)函數(shù)，則可以建立如下配送路徑的優(yōu)化模型:nu陽k -QiJ（3）J=N（4）AIj=i其中,表示不大于括號(hào)內(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）式表明每個(gè)客戶都得到配送服務(wù)；（5）式表示每條路徑的客戶的組成；（6）式限制每個(gè)客戶僅能由一臺(tái)配送車輛送貨；（7）式表示當(dāng)?shù)趇個(gè)配送中心的第j輛車服務(wù)的客戶數(shù)時(shí)，說明該臺(tái)車參加了配送，則取f（m）= 1,當(dāng)?shù)趇個(gè)配送 中心的第j輛車服務(wù)的客戶數(shù)1時(shí)，表示未使用該臺(tái)車輛，因此取f （nJ二0 o 3遺傳算法設(shè)計(jì)3. 1編碼方法的確定和初始種群的產(chǎn)生根據(jù)多物流配送中

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

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 需求點(diǎn)1需求點(diǎn)2配送中心-4子路徑2：配送中心_3需求點(diǎn)3需求點(diǎn)4需求點(diǎn)5配送中心_3其中，-2s -5和兩個(gè) T 都是無效基因.這種染色體結(jié)構(gòu)子路徑內(nèi)部是有序的，子 路徑中需求點(diǎn)1和2交換位置，會(huì)使目標(biāo)函數(shù)值改變;而子路徑之間是無序的，若子 路徑1和2交換位置，卻不會(huì)改變目標(biāo)函數(shù)值。3.2適應(yīng)度評(pí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)前染色體對(duì)應(yīng)的配送距 離.3 3選擇操作本文采用如下最佳個(gè)體保留與賭輪選擇相結(jié)合的選擇策略:將每代群體中的H1個(gè)個(gè) 體按適應(yīng)度由大到小排列，排在第一位的個(gè)體性能最優(yōu)，將它復(fù)制一個(gè)直接進(jìn)入下 一代，并排在第一位；下一代群體的另m 1個(gè)個(gè)體需要根據(jù)前代群體的m個(gè)個(gè) 體的適應(yīng)度，采用賭輪選擇法產(chǎn)生，具體地說，就是首先計(jì)算上代群體中所有個(gè)體/()=1 10其他適應(yīng)度的總和Fj,再計(jì)算每個(gè)個(gè)體的適應(yīng)度所占的比例Fj/XFj （j = 1 ,2 , ，m）,以此作

11、為其被選擇的概率。 上述選擇方法既可保證最優(yōu)個(gè)體生存至下一代, 又能保證適應(yīng)度較大的個(gè)體以較大的機(jī)會(huì)進(jìn)入下一代。3.4交叉操作對(duì)通過選擇操作產(chǎn)生的新群體,除排在第一位的最優(yōu)個(gè)體外，另m 1個(gè)個(gè)體要按 交叉概率Pc進(jìn)行配對(duì)交叉重組。本文采用類0X法實(shí)施交叉操作，其操作過程為： 如果染色體交叉點(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, | -4, 4

12、, | 2, -1,-3I I內(nèi)為匹配段，經(jīng)過最大保留交叉運(yùn)算后形成子代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ī)制中采用了保留最佳個(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è) 體，說明該

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

14、_2123456710106124104610133-2012812468499101351189131062015101081051130106o 5101114640373108505712760884701210801090Qk(t)344232321表2算例的遺傳算法計(jì)算結(jié)果計(jì)算次序110平均23456789配送總距離（km）67646468706468646768首次搜索到最終解的代數(shù)43523836425357495148由表2可以看出：用遺傳算法對(duì)算例的10次求解中，有4次得到了問題的最優(yōu) 解64km（其對(duì)應(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)于把多個(gè)配送中心問題通過任務(wù) 分派轉(zhuǎn)化為單物流配送中心問題求解。5結(jié)束語（1）本文建立了一個(gè)多物流配送中心模型，并基于多物流配送中心配送的特點(diǎn)，設(shè) 計(jì)了求解算法。由于每個(gè)配送中心需要派出多少車次是不確定的，文章通過采用無 效基因很好的解決了這個(gè)由于各配送中心需要派出多少車次不確定引起的對(duì)個(gè)體無 法編碼的問題.這樣就可以把多個(gè)物流配送中心配送優(yōu)化問題用一個(gè)數(shù)學(xué)模型來求 解，這種方法要優(yōu)于把需求點(diǎn)預(yù)先劃分給各個(gè)配送中心，以轉(zhuǎn)化為單物流配送中心 求解的方法。（2）遺傳算法是模

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