基于遺傳算法的SDLRPTW數(shù)學(xué)模型及其算法研究.pdf

1、隨著社會(huì)經(jīng)濟(jì)的不斷發(fā)展，人民生活水平的不斷提高，產(chǎn)業(yè)化、信息化的不斷加速，產(chǎn)品生產(chǎn)成本的降低空間已越來(lái)越小，而物流作為一個(gè)新興產(chǎn)業(yè)，其發(fā)展空間十分可觀。美國(guó)、日本等發(fā)達(dá)國(guó)家的物流集成化已發(fā)展到一定水平，而我國(guó)的物流僅處于初級(jí)發(fā)展階段，為了更好的適應(yīng)我國(guó)經(jīng)濟(jì)發(fā)展的需要，就必須盡快提高我國(guó)物流集成化水平。 物流中心的選址作為物流運(yùn)作中的基礎(chǔ)要素，其優(yōu)化和求解意義重大，對(duì)此問(wèn)題的研究即為定位配給問(wèn)題(Location Associat

2、ion Problem，LAP)；而物流配送作為物流系統(tǒng)的重要組成部分，對(duì)物流系統(tǒng)成本也有較大影響，綜合考慮這兩個(gè)方面并對(duì)其進(jìn)行優(yōu)化求解設(shè)計(jì)就可以大大降低物流系統(tǒng)總成本；隨著物流集成化水平的不斷提高，人們對(duì)物流服務(wù)的要求也越來(lái)越高，因此就要考慮物流服務(wù)中的時(shí)間約束問(wèn)題，即時(shí)間窗約束，綜合考慮以上三個(gè)方面的因素，即為本文所要研究的帶時(shí)間窗的定位路線問(wèn)題(LocationRouting Problems With Time－Windows，

3、LRPTW)。 在結(jié)合定位配給問(wèn)題和車輛路線問(wèn)題數(shù)學(xué)模型的基礎(chǔ)上，本文建立了帶時(shí)間窗的定位一路線問(wèn)題的數(shù)學(xué)模型，并用Lingo10.0軟件對(duì)其進(jìn)行檢驗(yàn)，證明了本文建立的數(shù)學(xué)模型的正確性。因其NP-hard屬性，當(dāng)節(jié)點(diǎn)數(shù)較多時(shí)精確解不宜得到，本文設(shè)計(jì)了啟發(fā)式算法進(jìn)行求解，先用空間填充曲線(Space Filling Curves，SFC)求解定位配給問(wèn)題，再用遺傳算法求解帶時(shí)間窗的車輛路線問(wèn)題。遺傳算法采用自然數(shù)編碼的方法使得交叉

4、和變異操作更加簡(jiǎn)便，利用隨機(jī)構(gòu)造初始解的方法產(chǎn)生初始種群，可以使解更具有遍歷性，避免了“早熟”現(xiàn)象的發(fā)生。用本文設(shè)計(jì)的遺傳算法對(duì)小規(guī)模數(shù)據(jù)進(jìn)行測(cè)算，其結(jié)果與Lingo10.0所得優(yōu)化解十分接近，說(shuō)明本文設(shè)計(jì)的遺傳啟發(fā)式算法的有效性；對(duì)于一定規(guī)模的LRPTW模型，通過(guò)實(shí)例仿真測(cè)算并與有關(guān)文獻(xiàn)進(jìn)行對(duì)比顯示：本文所采用的遺傳算法在求解一定規(guī)模的LRPTW模型時(shí)其求解速度較快，解的精度較高，說(shuō)明本文設(shè)計(jì)的算法求解該問(wèn)題具有一定的有效性，這對(duì)實(shí)際