不确定环境下旅行商问题的模型及算法

发布时间：2018-04-06 01:28

本文选题：旅行商问题　切入点：不确定理论　出处：《聊城大学》2017年硕士论文

【摘要】：旅行商问题(TSP)是一类易于解释但求解异常困难的整数规划问题.因其是路线问题的基础,且它的可能路径数目与总体城市数目之间的函数关系为指数型函数,求解非常困难,所以它一直是人们广泛研究的最优化问题之一.本文对不确定环境下的旅行商问题进行了以下研究.一.假设各城市之间旅行所花费的费用具有不确定分布,基于不确定理论,建立了以期望值最小化为目标,方差为约束的期望—方差模型.并基于遗传算法设计了针对该模型的一种改进遗传算法.二.假设各城市之间旅行所花费的费用是不确定随机变量,基于机会理论,给出了机会左测度的概念,并基于此建立了以旅行的不确定随机总花费的期望最小为目标,机会左测度为风险约束的模型——TSP的机会左约束模型.并依据新模型的特点,融合了不确定随机仿真技术和遗传算法,设计了针对该模型的一种新算法(称为GASO算法).同时,针对以上两种模型分别给出了数值例子,以验证其有效性。
[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

【参考文献】