本文選題：旅行商問題　切入點：不確定理論　出處：《聊城大學》2017年碩士論文

【摘要】：旅行商問題(TSP)是一類易于解釋但求解異常困難的整數(shù)規(guī)劃問題.因其是路線問題的基礎,且它的可能路徑數(shù)目與總體城市數(shù)目之間的函數(shù)關系為指數(shù)型函數(shù),求解非常困難,所以它一直是人們廣泛研究的最優(yōu)化問題之一.本文對不確定環(huán)境下的旅行商問題進行了以下研究.一.假設各城市之間旅行所花費的費用具有不確定分布,基于不確定理論,建立了以期望值最小化為目標,方差為約束的期望—方差模型.并基于遺傳算法設計了針對該模型的一種改進遺傳算法.二.假設各城市之間旅行所花費的費用是不確定隨機變量,基于機會理論,給出了機會左測度的概念,并基于此建立了以旅行的不確定隨機總花費的期望最小為目標,機會左測度為風險約束的模型——TSP的機會左約束模型.并依據(jù)新模型的特點,融合了不確定隨機仿真技術和遺傳算法,設計了針對該模型的一種新算法(稱為GASO算法).同時,針對以上兩種模型分別給出了數(shù)值例子,以驗證其有效性。
[Abstract]:Traveling Salesman problem (TSP) is a class of integer programming problems which are easy to explain but difficult to solve.Because it is the basis of the route problem and the function relationship between the number of possible paths and the total number of cities is an exponential function, it is very difficult to solve, so it has been one of the most widely studied optimization problems.In this paper, the traveling salesman problem in uncertain environment is studied as follows.I.Assuming the uncertain distribution of the cost of travel between cities, an expected variance model is established based on the uncertainty theory, which aims at minimizing the expected value and constrains the variance.An improved genetic algorithm for this model is designed based on genetic algorithm.II.Assuming that the cost of traveling between cities is an uncertain random variable, this paper gives the concept of opportunity left measure based on opportunity theory, and based on this, the objective is to minimize the expected total uncertain random total cost of travel.The chance left measure is the model of risk constraint, which is the opportunity left constraint model of tsp.According to the characteristics of the new model, the uncertain stochastic simulation technology and genetic algorithm are combined, and a new algorithm (called GASO algorithm) for the model is designed.At the same time, numerical examples are given to verify the validity of the two models.
【學位授予單位】：聊城大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP18;O221.4

【參考文獻】

相關期刊論文 前10條

1 于瑩瑩;陳燕;李桃迎;;改進的遺傳算法求解旅行商問題[J];控制與決策;2014年08期

2 蘇曉勤;范書瑞;郭會娟;狄雅靜;;基于蜂群的改進混合算法求解旅行商問題[J];河南科技大學學報(自然科學版);2013年04期

3 周永權;黃正新;;求解TSP的人工螢火蟲群優(yōu)化算法[J];控制與決策;2012年12期

4 王銀年;葛洪偉;;求解TSP問題的改進模擬退火遺傳算法[J];計算機工程與應用;2010年05期

5 張霞;傅海英;孫金領;;隨機規(guī)劃問題的兩種分解算法研究[J];山東大學學報(理學版);2008年02期

6 周康;強小利;同小軍;許進;;求解TSP算法[J];計算機工程與應用;2007年29期

7 高海昌;馮博琴;朱利b;;智能優(yōu)化算法求解TSP問題[J];控制與決策;2006年03期

8 戎曉霞,劉楊;隨機規(guī)劃的合成機會約束模型[J];山東大學學報(理學版);2005年05期

9 郭慶強,李歧強;基于變精度粗集的生產(chǎn)調(diào)度規(guī)則獲取[J];山東大學學報(工學版);2005年02期

10 胡純德,祝延軍,高隨祥;基于人工免疫算法和蟻群算法求解旅行商問題[J];計算機工程與應用;2004年34期

，

本文編號：1717381