【摘要】：車輛路徑問(wèn)題是目前研究最為廣泛,應(yīng)用價(jià)值較高的一類組合優(yōu)化問(wèn)題。制造業(yè)中的注塑排程可建模為帶時(shí)間窗的車輛路徑問(wèn)題,并由車輛路徑問(wèn)題的算法進(jìn)行求解,該類問(wèn)題的求解最常采用的是啟發(fā)式算法。啟發(fā)式算法目前已廣泛應(yīng)用于各類優(yōu)化問(wèn)題的求解。對(duì)于較大規(guī)模優(yōu)化問(wèn)題,現(xiàn)有啟發(fā)式算法常面臨運(yùn)算時(shí)間長(zhǎng)、求解精度不高等困難。通過(guò)歸約的方法將大規(guī)模優(yōu)化問(wèn)題轉(zhuǎn)化為規(guī)模較小的優(yōu)化實(shí)例是求解該類問(wèn)題的有效途徑之一。本論文圍繞車輛路徑問(wèn)題、生產(chǎn)排程中的注塑排程及如何利用歸約的方法設(shè)計(jì)求解大規(guī)模優(yōu)化問(wèn)題的高效啟發(fā)式算法這三個(gè)方面進(jìn)行研究,主要工作和成果如下:1)提出求解車輛路徑問(wèn)題的快速多鄰域迭代局部搜索算法。局部搜索算法中需要反復(fù)對(duì)鄰域解進(jìn)行評(píng)估,該評(píng)估占用了算法大部分運(yùn)行時(shí)間。為此,提出應(yīng)用于車輛路徑問(wèn)題多種鄰域解的合法性快速評(píng)估策略,該策略將時(shí)間、容量、最大行駛距離等各種約束嵌入客戶節(jié)點(diǎn)信息,將鄰域解的評(píng)估計(jì)算復(fù)雜度降低為O(1),提高了算法的計(jì)算效率。構(gòu)造車輛路徑問(wèn)題偏移實(shí)例,采用可變長(zhǎng)編碼,實(shí)現(xiàn)車輛數(shù)和運(yùn)輸成本的同步優(yōu)化。算法仿真結(jié)果表明,該算法能在短時(shí)間內(nèi)獲得車輛路徑問(wèn)題的滿意解。2)提出基于歸約的迭代局部搜索算法。優(yōu)化問(wèn)題的可行解可看作是由一組基元構(gòu)成的,可行解的進(jìn)化過(guò)程可看作是基元不斷改善的過(guò)程。所謂“歸約”是指將解個(gè)體中的優(yōu)質(zhì)基元固化,將原問(wèn)題轉(zhuǎn)化為規(guī)模更小的歸約實(shí)例�；诖�,提出一種新穎的歸約實(shí)例構(gòu)造方法,該方法依據(jù)近似骨架概率選擇優(yōu)質(zhì)基元,優(yōu)質(zhì)基元在新的歸約實(shí)例中以封裝成虛擬客戶節(jié)點(diǎn)的方式被固化�；跉w約的迭代局部搜索算法是一種基于種群的優(yōu)化方法。在算法進(jìn)化過(guò)程中,利用近似骨架概率信息可不斷獲得規(guī)模數(shù)更小的歸約實(shí)例,縮小鄰域搜索范圍,進(jìn)而提高算法的搜索效率。實(shí)驗(yàn)結(jié)果表明該算法能夠獲得比快速多鄰域迭代局部搜索算法更為精確的結(jié)果。3)提出一種新型的求同優(yōu)化算法。該算法的基礎(chǔ)是對(duì)可行解中基元的合理評(píng)估,為此,提出結(jié)合解個(gè)體的優(yōu)劣程度和基元在種群中那個(gè)的獲接受程度的基元認(rèn)同度計(jì)算方法,并依據(jù)基元認(rèn)同度選擇優(yōu)質(zhì)基元。優(yōu)質(zhì)基元構(gòu)成優(yōu)質(zhì)個(gè)體,定義個(gè)體認(rèn)同度,并利用個(gè)體認(rèn)同度指導(dǎo)算法的優(yōu)化過(guò)程。在求同優(yōu)化算法的迭代過(guò)程中,解個(gè)體的共同基元獲保留,其他基元在后續(xù)迭代中不斷優(yōu)化。隨著共同基元的增加,種群中所有解個(gè)體進(jìn)化為同一個(gè)解,此即為所求。求同優(yōu)化算法的收斂速度快,求解精度高,能有效求解大規(guī)模容量約束車輛路問(wèn)題。4)提出應(yīng)用于注塑排程的快速多鄰域迭代局部搜索算法。注塑排程本質(zhì)上可建模為帶時(shí)間窗的車輛路徑問(wèn)題。提出機(jī)器碼和時(shí)間窗交疊檢測(cè)方法,得到應(yīng)用于注塑機(jī)約束和模具約束的快速評(píng)估策略。該算法能夠在短時(shí)間內(nèi)獲得注塑排程的滿意解,具有很強(qiáng)的實(shí)用性。
【圖文】：

會(huì)必不可少的工具。目前，計(jì)算機(jī)能夠高效地實(shí)現(xiàn)的計(jì)算、統(tǒng)計(jì)、檢索等工作中解放出來(lái)�，F(xiàn)實(shí)生活計(jì)算模型，并設(shè)計(jì)相應(yīng)的算法由計(jì)算機(jī)進(jìn)行求解。例、交通領(lǐng)域的航線規(guī)劃問(wèn)題、制造業(yè)中的生產(chǎn)排程問(wèn)合計(jì)算機(jī)求解的模型。其中制造業(yè)和物流業(yè)是我國(guó)的高制造業(yè)和物流業(yè)的管理水平，對(duì)節(jié)約企業(yè)生產(chǎn)成本務(wù)的迅速普及，中國(guó)的物流行業(yè)得到快速發(fā)展。然而商務(wù)的運(yùn)營(yíng)成本，制約了電子商務(wù)的快速擴(kuò)張。數(shù)用為 10.2 萬(wàn)億元，，占 GDP 的比率為 18%。圖 1.1 給用與 GDP 的比率變化趨勢(shì)。從該趨勢(shì)圖可見(jiàn)，近年率維持在 17~18%之間。而美國(guó)、日本和德國(guó)的這一約為 11.5%，這反映出中國(guó)物流成本明顯偏高。

tion molding scheduling，IMS）的數(shù)學(xué)模型。同時(shí)，針對(duì)注塑排程，窗交疊檢測(cè)方法，進(jìn)而得到應(yīng)用于注塑機(jī)約束和模具約束的快速評(píng)估解 VRPTW 的快速多鄰域迭代局部搜索 (fast multi-neighborhood iteraNILS) 算法的基礎(chǔ)上，提出應(yīng)用于注塑排程的改進(jìn) FMNILS(iMNILS)算法。仿真實(shí)驗(yàn)結(jié)果表明，iFMNILS 算法能夠在較短的時(shí)間解，具有很強(qiáng)的實(shí)用性。程及其數(shù)學(xué)模型產(chǎn)過(guò)程型（Injection molding）工藝是目前應(yīng)用最為廣泛的塑料材料加工方法、自動(dòng)化程度高、生產(chǎn)效率高、原料浪費(fèi)少、能生產(chǎn)復(fù)雜形狀的產(chǎn)品于電氣和電子、電信工程、航空航天、日用品等領(lǐng)域[131]。通過(guò)注塑品稱為注塑產(chǎn)品，即通過(guò)注塑機(jī)加熱塑料至塑化熔融，再注射至模具經(jīng)冷卻固化后脫模所獲的制品，其生產(chǎn)過(guò)程示意圖如下所示：
【學(xué)位授予單位】：深圳大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP301.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 陳萍;黃厚寬;董興業(yè);;基于多鄰域的車輛路徑優(yōu)化迭代局部搜索算法[J];北京交通大學(xué)學(xué)報(bào);2009年02期

2 宗瑜;李明楚;江賀;;近似骨架導(dǎo)向的歸約聚類算法[J];電子與信息學(xué)報(bào);2009年12期

3 駱劍平;李霞;陳泯融;;基于改進(jìn)混合蛙跳算法的CVRP求解[J];電子與信息學(xué)報(bào);2011年02期

4 劉云忠,宣慧玉;車輛路徑問(wèn)題的模型及算法研究綜述[J];管理工程學(xué)報(bào);2005年01期

5 鄒鵬,周智,陳國(guó)良,顧鈞;求解TSP問(wèn)題的多級(jí)歸約算法[J];軟件學(xué)報(bào);2003年01期

6 鄒鵬,周智,陳國(guó)良,江賀,顧鈞;求解QAP問(wèn)題的近似骨架導(dǎo)向快速蟻群算法(英文)[J];軟件學(xué)報(bào);2005年10期

7 戚玉濤;劉芳;焦李成;;求解大規(guī)模TSP問(wèn)題的自適應(yīng)歸約免疫算法[J];軟件學(xué)報(bào);2008年06期

8 王成堯,高麟,汪定偉,殷秩松,王書寧;有模具約束的平行機(jī)臺(tái)最小拖期和調(diào)度問(wèn)題[J];系統(tǒng)工程學(xué)報(bào);1999年04期

相關(guān)碩士學(xué)位論文 前4條

1 李雪;不確定數(shù)據(jù)聚類研究[D];大連理工大學(xué);2009年

2 周月娥;汽車鈑金件加工智能排程方法研究與系統(tǒng)設(shè)計(jì)[D];南京理工大學(xué);2010年

3 劉冬妮;中小制造企業(yè)高級(jí)計(jì)劃與排程系統(tǒng)關(guān)鍵技術(shù)研究[D];華中科技大學(xué);2009年

4 王路鳳;基于關(guān)鍵設(shè)備生產(chǎn)排程優(yōu)化的產(chǎn)品線成品庫(kù)存改善研究[D];上海交通大學(xué);2012年

本文編號(hào)：2542212