TSP的扰动恢复问题及其轮换算法

TSP的扰动恢复问题及其轮换算法 On the Recovery of TSP from Disruptions and a Circle Permutation Algorithm 杨磊 YANG Lei 1 2 first-author 马俊 MA Jun 1 2 高成修 GAO Cheng-xiu 1 2 武汉大学数学与统计学院 武汉大学数学与统计学院 School of Mathematics and Statistics, Wuhan University School of Mathematics and Statistics, Wuhan University 武汉大学数学与统计学院,湖北,武汉,430072 武汉大学数学与统计学院,湖北,武汉,430072 对旅行商问题进行了扰动恢复讨论 ,在对旅行商问题进行数学描述的基础上 ,分析了各种扰动 ,由于增加或删除点可以转化为对边的费用进行处理 ,所以只讨论了边受到扰动的问题 ,并给出旅行商问题的扰动恢复问题的数学模型 ,然后用近世代数中置换群工具得到一种求解此问题的轮换算法 ,并给出了一个算例 . This paper discusses traveling salesman problem about the recovery from disruptions. Based on the mathematical description of given traveling salesman problem the paper analyzes kinds of disruptions from the outside. For adding or deleting nodes can be transferred to changes of cost of edges, so the paper only discusses the case when the edges are disrupted. Then the mathematical model of post-disruption traveling salesman problem is given, and the circle permutation algorithm for solving the model is got from the permutation group in modern algebra, then the availability of the algorithm is proved and its complexity is got, at last a computational example is given. 实时决策支持系统 旅行商问题 扰动恢复 轮换算法 线性规划 AIRDSS TM TSP PDTSP circle permutation algorithm linear programming O224 国家自然科学基金资助项目 （ 7992 80 0 1,79870 0 91,A0 2 2 40 17） 2003-03-01 2021-04-01 3