發(fā)布時(shí)間：2017-08-20 20:26

  本文關(guān)鍵詞：基于隨機(jī)機(jī)會(huì)約束規(guī)劃模型的旅行商問題及其求解算法

  更多相關(guān)文章： 旅行商問題 隨機(jī)機(jī)會(huì)約束規(guī)劃 遺傳算法

【摘要】：為了提高旅行商的效率,將旅行時(shí)間引入旅行商問題(TSP),以最短時(shí)間和最短路徑為目標(biāo)對(duì)旅行商問題進(jìn)行求解。假設(shè)旅行商在不同城市間的旅行時(shí)間服從正態(tài)分布,以最短路徑為優(yōu)化目標(biāo),將旅行時(shí)間以一定的置信水平成立作為機(jī)會(huì)約束條件,構(gòu)建了旅行商問題的隨機(jī)機(jī)會(huì)約束規(guī)劃模型。提出已構(gòu)建模型的確定性等價(jià)類,設(shè)計(jì)出遺傳算法并編寫算法代碼,以一定規(guī)模的城市為例進(jìn)行仿真驗(yàn)證。結(jié)果表明:給定期望的總旅行時(shí)間和置信水平時(shí),可經(jīng)過(guò)計(jì)算得出最短距離,并繪制出最優(yōu)路徑圖,同時(shí)驗(yàn)證了所提出模型的可行性和算法的有效性。
【作者單位】： 北京交通大學(xué)軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室;北京交通大學(xué)交通運(yùn)輸學(xué)院;北京市商業(yè)學(xué)校物流交通系;
【關(guān)鍵詞】： 旅行商問題 隨機(jī)機(jī)會(huì)約束規(guī)劃 遺傳算法
【基金】：軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室(北京交通大學(xué))自主研究課題(RCS2013ZZ001)
【分類號(hào)】：U116
【正文快照】： 0引言旅行商問題(traveling salesman problem,TSP)是一個(gè)典型的組合優(yōu)化難題,屬于NP難題。TSP可敘述為:在N個(gè)城市中,尋求一條旅行商可到達(dá)每個(gè)城市且只到一次的最短路徑,這種TSP僅尋求一個(gè)性能指標(biāo),即最短路徑。TSP在許多領(lǐng)域都有著廣泛的應(yīng)用,已經(jīng)解決了交通運(yùn)輸、管道敷設(shè)

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前9條

1 唐立新;旅行商問題(TSP)的改進(jìn)遺傳算法[J];東北大學(xué)學(xué)報(bào);1999年01期

2 盧厚清,王輝東,黃杰,李波;任務(wù)均分的多旅行商問題[J];系統(tǒng)工程;2005年02期

3 劉荷花;崔超;陳晶;;一種改進(jìn)的遺傳算法求解旅行商問題[J];北京理工大學(xué)學(xué)報(bào);2013年04期

4 陳斌,徐華中;一種改進(jìn)遺傳算法及其在TSP問題中的應(yīng)用[J];計(jì)算機(jī)工程;2002年09期

5 朱獻(xiàn)文;李福榮;;求解旅行商問題的幾種智能算法[J];計(jì)算機(jī)與數(shù)字工程;2010年01期

6 周輝仁;唐萬(wàn)生;魏穎輝;;基于GA的最小旅行時(shí)間的多旅行商問題研究[J];計(jì)算機(jī)應(yīng)用研究;2009年07期

7 陳德良;陳治亞;;隨機(jī)的庫(kù)存—路徑問題的機(jī)會(huì)約束規(guī)劃模型與算法[J];模糊系統(tǒng)與數(shù)學(xué);2010年03期

8 呂善國(guó);曹義親;陳紅麗;;求解旅行商問題的一種新方法[J];華東交通大學(xué)學(xué)報(bào);2012年05期

9 劉星材;何世偉;孫楊;黎浩東;;基于時(shí)間滿意度的鐵路樞紐空車調(diào)配隨機(jī)機(jī)會(huì)約束模型及算法研究[J];鐵道學(xué)報(bào);2013年09期

【共引文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 阮懷忠,張建中;基于改進(jìn)遺傳算法的TSP問題求解[J];安徽建筑工業(yè)學(xué)院學(xué)報(bào)(自然科學(xué)版);2003年04期

2 蘇發(fā)慧;;模糊支持向量機(jī)在糧食安全預(yù)警中的應(yīng)用[J];安徽建筑工業(yè)學(xué)院學(xué)報(bào)(自然科學(xué)版);2009年02期

3 韋忠良;崔斌;;基于管徑的管道輸水灌溉管網(wǎng)優(yōu)化設(shè)計(jì)[J];安徽農(nóng)業(yè)科學(xué);2009年25期

4 張琳;李海燕;王莉;;模糊需求下批量生產(chǎn)優(yōu)化模型[J];遼寧科技大學(xué)學(xué)報(bào);2008年01期

5 劉衛(wèi)果,胡思繼;旅客交通方式選擇行為的模糊機(jī)會(huì)約束規(guī)劃模型[J];北方交通大學(xué)學(xué)報(bào);2002年02期

6 呂擰,賈燕兵;應(yīng)用遺傳算法進(jìn)行給水管網(wǎng)優(yōu)化設(shè)計(jì)[J];北京工業(yè)大學(xué)學(xué)報(bào);2001年01期

7 畢春長(zhǎng),張有忱;基于實(shí)碼遺傳算法的汽車變速箱可靠性優(yōu)化設(shè)計(jì)[J];北京化工大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年05期

8 蘆永明;徐安軍;賀東風(fēng);田乃媛;;一種有利于提高DHCR比例的熱軋批量計(jì)劃編制方法[J];北京科技大學(xué)學(xué)報(bào);2011年10期

9 楊業(yè)建;姜澤毅;張欣欣;;板坯熱軋批量計(jì)劃數(shù)學(xué)模型及求解算法[J];北京科技大學(xué)學(xué)報(bào);2012年04期

10 左秀峰,韓伯棠,何世偉;供應(yīng)鏈庫(kù)存控制策略的進(jìn)化仿真[J];北京理工大學(xué)學(xué)報(bào);2004年08期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前10條

1 楊吉會(huì);;模糊關(guān)系規(guī)劃概述[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

2 麻倩倩;馬新順;石彤菊;;求解機(jī)會(huì)約束規(guī)劃的回溯算法[A];第四屆中國(guó)不確定系統(tǒng)年會(huì)論文集[C];2006年

3 李平;戴政國(guó);;灰色線性規(guī)劃問題的隨機(jī)模擬解法[A];第一屆中國(guó)智能計(jì)算大會(huì)論文集[C];2007年

4 劉金亮;;求解模糊需求條件下車輛路徑問題的混合螞蟻算法[A];第三屆中國(guó)智能計(jì)算大會(huì)論文集[C];2009年

5 戎麗霞;;模糊需求條件下的多車場(chǎng)車輛路徑問題[A];第三屆中國(guó)智能計(jì)算大會(huì)論文集[C];2009年

6 蔡洪文;張殿業(yè);;隨機(jī)需求條件下的生產(chǎn)—定位—路徑集成問題研究[A];第七屆中國(guó)不確定系統(tǒng)年會(huì)論文集[C];2009年

7 熊翠;吳慧萍;李波;;多旅行商問題遺傳算法求解及其改進(jìn)[A];第四屆中國(guó)智能計(jì)算大會(huì)論文集[C];2010年

8 張雷;楊大地;劉冬兵;劉凌晨;;DNA遺傳算法在M-TSP問題中的應(yīng)用[A];'2006系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會(huì)論文集[C];2006年

9 宣吉;廖祖維;榮岡;陽(yáng)永榮;;基于隨機(jī)規(guī)劃的煉廠氫網(wǎng)絡(luò)改造設(shè)計(jì)[A];2009中國(guó)過(guò)程系統(tǒng)工程年會(huì)暨中國(guó)mes年會(huì)論文集[C];2009年

10 包莉麗;胡正華;;基于機(jī)會(huì)約束規(guī)劃的制造／再制造混合系統(tǒng)生產(chǎn)決策[A];第八屆中國(guó)管理科學(xué)學(xué)術(shù)年會(huì)論文集[C];2006年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 彭北青;第三方物流配送車輛路徑問題模型及算法研究[D];華中科技大學(xué);2009年

2 孔令啟;基于內(nèi)外圈協(xié)同優(yōu)化策略的間歇化工過(guò)程不確定性調(diào)度研究[D];華南理工大學(xué);2010年

3 李艷紅;綜合運(yùn)輸通道客運(yùn)結(jié)構(gòu)優(yōu)化理論與方法研究[D];北京交通大學(xué);2010年

4 王宏亮;鋼鐵企業(yè)多粒度分型生產(chǎn)計(jì)劃管理方法研究[D];大連理工大學(xué);2011年

5 王書齊;可變模糊集多屬性決策理論在大型編隊(duì)防空決策中的應(yīng)用研究[D];大連理工大學(xué);2011年

6 陳德良;物流網(wǎng)絡(luò)可靠性的關(guān)鍵問題與應(yīng)用研究[D];中南大學(xué);2010年

7 李峰;樁錨土釘復(fù)合支護(hù)基坑施工時(shí)變力學(xué)研究[D];鄭州大學(xué);2010年

8 李彥來(lái);物流網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性及優(yōu)化設(shè)計(jì)問題研究[D];北京交通大學(xué);2011年

9 左大杰;鐵路快速客運(yùn)網(wǎng)絡(luò)旅客列車開行方案優(yōu)化研究[D];西南交通大學(xué);2010年

10 孫力勇;電力市場(chǎng)環(huán)境下發(fā)電公司的短期經(jīng)濟(jì)運(yùn)行研究[D];上海交通大學(xué);2007年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 石麗麗;智能優(yōu)化算法對(duì)比研究及其在船體雙底結(jié)構(gòu)優(yōu)化中的應(yīng)用[D];哈爾濱工程大學(xué);2010年

2 趙海坤;模糊線性規(guī)劃理論的模糊結(jié)構(gòu)元解法研究[D];遼寧工程技術(shù)大學(xué);2009年

3 周聰;高維多目標(biāo)減少算法的比較與研究[D];湘潭大學(xué);2010年

4 陳小燕;高校人力資源模糊管理研究[D];福建師范大學(xué);2010年

5 劉娟容;實(shí)時(shí)PCR儀熒光信號(hào)監(jiān)測(cè)系統(tǒng)的研究[D];浙江大學(xué);2011年

6 高偉;基于全年負(fù)荷的冷熱電聯(lián)供系統(tǒng)優(yōu)化分析[D];東華大學(xué);2010年

7 張宇;農(nóng)產(chǎn)品銷售物流中風(fēng)險(xiǎn)控制模型及求解方法研究[D];沈陽(yáng)工業(yè)大學(xué);2011年

8 李國(guó)華;不確定條件下電廠燃料供應(yīng)優(yōu)化研究[D];華北電力大學(xué)（北京）;2011年

9 孫翠英;基于可信性理論含規(guī)模化風(fēng)電的機(jī)組組合問題研究[D];華北電力大學(xué)（北京）;2011年

10 何曉璇;基于收益管理理論的兩級(jí)裝配系統(tǒng)最優(yōu)控制策略研究[D];吉林大學(xué);2011年

【二級(jí)參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 張春霞;王蕊;;基于遺傳算法求解TSP問題的算法設(shè)計(jì)[J];安陽(yáng)工學(xué)院學(xué)報(bào);2007年04期

2 穆艷玲;李學(xué)武;高潤(rùn)泉;;遺傳算法解TSP問題的并行實(shí)現(xiàn)[J];北京聯(lián)合大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年02期

3 楊華芬;魏延;;一種求解TSP問題的改進(jìn)遺傳算法[J];重慶工學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年05期

4 封全喜,劉誠(chéng);物流配送車輛路徑問題的并行遺傳算法研究[J];鐵道科學(xué)與工程學(xué)報(bào);2005年04期

5 唐立新;熱軋調(diào)度并行處理策略的多旅行商模型[J];東北大學(xué)學(xué)報(bào);1999年02期

6 高雷阜;劉旭旺;;基于模擬退火的Hopfield網(wǎng)全局優(yōu)化方法[J];遼寧工程技術(shù)大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年01期

7 盧厚清,王輝東,黃杰,李波;任務(wù)均分的多旅行商問題[J];系統(tǒng)工程;2005年02期

8 陳冬華;;旅行商問題推廣及其混合智能算法[J];華東交通大學(xué)學(xué)報(bào);2011年02期

9 萬(wàn)穎瑜,周智,陳國(guó)良,顧鈞;SizeScale:求解旅行商問題(TSP)的新算法[J];計(jì)算機(jī)研究與發(fā)展;2002年10期

10 葉玉玲;傘冶;;一種混合優(yōu)化算法及其性能[J];吉林大學(xué)學(xué)報(bào)(工學(xué)版);2009年01期

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前6條

1 胡大偉;劉貴英;;基于空間填充曲線和or-opt搜索求解旅行商問題[J];長(zhǎng)安大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年02期

2 柳祖鵬;李克平;朱曉宏;;基于蟻群算法的公共自行車站間調(diào)度優(yōu)化[J];交通信息與安全;2012年04期

3 黃X;;向蜜蜂學(xué)習(xí)或許可解決堵車問題[J];中國(guó)蜂業(yè);2011年Z5期

4 張瑞友;汪定偉;尹原永;;集裝箱卡車運(yùn)輸問題的基于圖的建模方法[J];系統(tǒng)工程理論與實(shí)踐;2011年08期

5 王金妹;張勤;朱東紅;;基于圖論的物流配送線路問題研究[J];交通標(biāo)準(zhǔn)化;2011年Z1期

6 ;[J];;年期

，

本文編號(hào)：708693