

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、(完整 word 版)多物流配送中心路徑優(yōu)化問(wèn)題及其遺傳算法編輯整理:尊敬的讀者朋友們:這里是精品文檔編輯中心, 本文檔內(nèi)容是由我和我的同事精心編輯整理后發(fā)布的, 發(fā)布之前我們 對(duì)文中內(nèi)容進(jìn)行仔細(xì)校對(duì),但是難免會(huì)有疏漏的地方,但是任然希望(完整word版)多物流配 送中心路徑優(yōu)化問(wèn)題及其遺傳算法)的內(nèi)容能夠給您的工作和學(xué)習(xí)帶來(lái)便利。同時(shí)也真誠(chéng)的希望 收到您的建議和反饋,這將是我們進(jìn)步的源泉,前進(jìn)的動(dòng)力。本文可編輯可修改,如果覺(jué)得對(duì)您有幫助請(qǐng)收藏以便隨時(shí)查閱,最后祝您生活愉快業(yè)績(jī)進(jìn)步,以 下為(完整word版)多物流配送中心路徑優(yōu)化問(wèn)題及其遺傳算法的全部?jī)?nèi)容。多物流配送中心路徑優(yōu)化問(wèn)題及其遺傳算
2、法廖成林 柳茂森(重慶大學(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è)極其重要的壞節(jié),它是指按用戶的訂貨要求,在配 送中心進(jìn)行分貨、配貨,并將配好的貨物及時(shí)送交收貨人的活動(dòng)物流配送主要研 究車(chē)輛調(diào)度及路徑安排問(wèn)題。近年來(lái),國(guó)內(nèi)外學(xué)者對(duì)物流配
3、送問(wèn)題進(jìn)行了大量的研 究,這些研究主要集中在單物流配送中心的車(chē)輛調(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)研究 心,使用這種方法把需求點(diǎn)預(yù)先劃分給各個(gè)配送中心,在求解過(guò)程中再作適當(dāng)?shù)?調(diào)整,這種方法其實(shí)只是單物流配送中心優(yōu)化的簡(jiǎn)單組合,通常只能求得近似最優(yōu) 配送方案。魏百鑫等4 針對(duì)整車(chē)配送需求點(diǎn)分散特征, 解決了多倉(cāng)
4、庫(kù)的整車(chē)配送 問(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)題可 以事先確定需要派出的車(chē)次,但是多物流配送中心路徑優(yōu)化問(wèn)題中,每個(gè)配送中心需 要派出多少車(chē)次是不確定的,因此,無(wú)法用常規(guī)的方法確定染色體的長(zhǎng)度。為解決 基因編碼的問(wèn)題,本文提出了無(wú)效基因的概念。所謂無(wú)效基因就是在一次基因表達(dá) 的過(guò)程中不作表達(dá)的基因。但是,在交叉過(guò)
5、程中無(wú)效基因處可以被選為交叉點(diǎn), 交 叉后無(wú)效基因可能轉(zhuǎn)化為有效基因。 因此, 有些基因時(shí)而是有效基因時(shí)而是無(wú)效基 因,因而無(wú)效基因在不清楚有些基因是否表達(dá)較好的時(shí)候起到緩沖作用.2模型的建立多物流配送路徑優(yōu)化問(wèn)題可描述為:從多個(gè)配送中心用多輛配送車(chē)向多個(gè)需求 點(diǎn)送貨,每個(gè)需求點(diǎn)的位置和需求量一定,要求安排合理的配送路線,使得目標(biāo)函 數(shù)最優(yōu)或接近最優(yōu)。為了研究的方便且具有實(shí)際意義,做以下假設(shè):(1)每條配送路徑上各需求點(diǎn)的需求量之和不超過(guò)配送車(chē)的載重量;(2)每個(gè)需求點(diǎn)都必須滿足,且只能由一輛配送車(chē)送貨。本文的各種符號(hào)及其含義做如下說(shuō)明:M-配送中心的個(gè)數(shù)i-配送中心的下標(biāo)j-配送車(chē)輛的下標(biāo)k
6、-需求點(diǎn)的下標(biāo)N-垂求占的個(gè)埶L,-第入配送中心的配送車(chē)的個(gè)數(shù)Qj_第i個(gè)配送中心的第j輛車(chē)的載重量qk-第k個(gè)需求點(diǎn)的需求量dkcU-從需求點(diǎn)k到k的運(yùn)距dou-配送中心到需求點(diǎn)k的運(yùn)距g-第i個(gè)配送中心的第j輛車(chē)配送的需求點(diǎn)個(gè)數(shù),g 二0表示未使用第j輛車(chē)際- 第i個(gè)配送中心的第j輛車(chē)配送的路徑r,-第i個(gè)配送中心的第j輛車(chē)配送的第k個(gè)需求點(diǎn),表示配送中心0 = m in 0, i = 1,2,;丿 =1,2,,厶若以配送路徑最短為目標(biāo)函數(shù),則可以建立如下配送路徑的優(yōu)化模型:nu陽(yáng)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)式保證每條路徑上各客戶的貨物需求量之 和不超過(guò)配送車(chē)輛的載重量;(3)式表明每條路徑上的客戶數(shù)不超過(guò)總客戶數(shù);(4)式表明每個(gè)客戶都得到配送服務(wù);(5)式表示每條路徑的客戶的組成;(6)式限制每個(gè)客戶僅能由一臺(tái)配送車(chē)輛送貨;(7)式表示當(dāng)?shù)趇個(gè)配送中心的第j輛車(chē)服務(wù)的客戶數(shù)時(shí),說(shuō)明該臺(tái)車(chē)參加了配送,則取f(m)= 1,當(dāng)?shù)趇個(gè)配送 中心的第j輛車(chē)服務(wù)的客戶數(shù)1時(shí),表示未使用該臺(tái)車(chē)輛,因此取f (nJ二0 o 3遺傳算法設(shè)計(jì)3. 1編碼方法的確定和初始種群的產(chǎn)生根據(jù)多物流配送中
8、心路徑優(yōu)化問(wèn)題的特點(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è)長(zhǎng)度為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ù)為無(wú)效基因,不表示任何意義,但是可以在該基 因處進(jìn)行交叉操作若交叉后該負(fù)數(shù)后面緊接正數(shù),則該負(fù)數(shù)由無(wú)效基因變?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 都是無(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)估方法的確定。適
10、應(yīng)度函數(shù)同目標(biāo)函數(shù)有關(guān),要求非負(fù),通過(guò)變換目標(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)生,具體地說(shuō),就是首先計(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ì)通過(guò)選擇操作產(chǎn)生的新群體,除排在第一位的最優(yōu)個(gè)體外,另m 1個(gè)個(gè)體要按 交叉概率Pc進(jìn)行配對(duì)交叉重組。本文采用類0X法實(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, | -4, 4
12、, | 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,-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ō)明該
13、個(gè)體是很好的個(gè)體,則停止操作。4仿真實(shí)驗(yàn)本文用mat I ab編制了多物流配送中心路徑優(yōu)化問(wèn)題的遺傳算法計(jì)算程序算例: 有兩個(gè)配送中心各兩輛配送車(chē)向9個(gè)需求點(diǎn)配送,配送車(chē)的載重量均是10噸配送 中心(編號(hào)為 T 和-2)與需求點(diǎn)之間以及需求點(diǎn)相互之間的距離dk(1)dk、9個(gè)客戶 的需求量qk均見(jiàn)下表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é)果見(jiàn)表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次得到了問(wèn)題的最優(yōu) 解64km(其對(duì)應(yīng)的配送路徑方案為:路徑路徑2:1, 5, 6, 9, 1路徑3:-2,
15、4,7, -2;路徑4:-2,2,8,-2) , 6次得到了問(wèn)題的近似最優(yōu)解,這 種方法求解多物流配送中心路徑優(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è)配送中心需要派出多少車(chē)次是不確定的,文章通過(guò)采用無(wú) 效基因很好的解決了這個(gè)由于各配送中心需要派出多少車(chē)次不確定引起的對(duì)個(gè)體無(wú) 法編碼的問(wèn)題.這樣就可以把多個(gè)物流配送中心配送優(yōu)化問(wèn)題用一個(gè)數(shù)學(xué)模型來(lái)求 解,這種方法要優(yōu)于把需求點(diǎn)預(yù)先劃分給各個(gè)配送中心,以轉(zhuǎn)化為單物流配送中心 求解的方法。(2)遺傳算法是模
16、擬生物遺傳學(xué)的規(guī)律的算法,但是,在生物體內(nèi)的基因是存在 無(wú)效基因的,而目前使用的遺傳算法編碼的基因都是有效的。因此,無(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 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 魏百鑫,史海波.基于整車(chē)配送的多倉(cāng)庫(kù)開(kāi)路VRPTW問(wèn)題的研究與實(shí)現(xiàn)J o信息與控制,2005 , 34 (3):350 -
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 民間借貸房產(chǎn)證抵押流程
- 二零二五版人力資源管理顧問(wèn)聘用合同
- 二零二五辦公地址租賃合同范例
- 二零二五房地產(chǎn)企業(yè)股權(quán)轉(zhuǎn)讓
- 項(xiàng)目薪酬績(jī)效管理制度
- 超市餅干面板管理制度
- 行政費(fèi)用管理制度通知
- 食堂熱水開(kāi)放管理制度
- 公司冰柜使用管理制度
- 飯店保潔人員管理制度
- 2025購(gòu)銷商品合同模板
- 2024年山西華陽(yáng)新材料科技集團(tuán)有限公司招聘筆試真題
- 2025年03月雙鴨山市“市委書(shū)記進(jìn)校園”引才活動(dòng)黑龍江能源職業(yè)學(xué)院13人筆試歷年典型考題(歷年真題考點(diǎn))解題思路附帶答案詳解
- 2025年湖南興湘投資控股集團(tuán)有限公司春季校園招聘28人筆試參考題庫(kù)附帶答案詳解
- 比例的應(yīng)用(教學(xué)設(shè)計(jì))-2024-2025學(xué)年六年級(jí)下冊(cè)數(shù)學(xué)北師大版
- 農(nóng)業(yè)機(jī)械設(shè)備使用與操作指南
- 2025年03月春季甘肅臨夏州引進(jìn)高層次人才和急需緊缺專業(yè)技術(shù)人才344人筆試歷年參考題庫(kù)考點(diǎn)剖析附解題思路及答案詳解
- 2025年03月州省氣象部門(mén)第二批公開(kāi)招聘應(yīng)屆高校畢業(yè)生34人(第6號(hào))筆試歷年參考題庫(kù)考點(diǎn)剖析附解題思路及答案詳解
- 上海市第一至十八屆高一物理基礎(chǔ)知識(shí)競(jìng)賽試題及答案
- 《建筑工程設(shè)計(jì)文件編制深度規(guī)定》(2022年版)
- 病例報(bào)告表(CRF)模板
評(píng)論
0/150
提交評(píng)論