基于不同条件的旅游路线规划问题研究  

Research on Tourism Route Planning Based on Different Conditions

作　　者：吴成明[1] 王毅[1] 毕红续 曾珍珍[1] 

机构地区：[1]三峡大学电气与新能源学院,湖北宜昌443002

出　　处：《数学的实践与认识》2016年第15期90-96,共7页Mathematics in Practice and Theory

摘　　要：运用2015年全国研究生数学建模竞赛F题的数据资料,针对旅游路线合理规划问题的第一问展开研究.以F题的问题一为起点进行了分析研究,是因为第一问的完成是解决后续问题的关键.首先通过地图搜集并补全了缺失数据并对数据进行合理的处理,然后采用将旅游年数最少目标转化为该最小生成树的"最少圈覆盖"方法来进行对问题一的求解,也可以理解为一个广义的多旅行商问题,以旅行商的人数(即年数)最少为目标.采用Dijkstra算法、最少圈覆盖法、智能算法和图论聚类等方法,通过这些方法建立了单目标优化模型,并运用旅行商问题和模型之间的转换来对问题进行分析与求解.Using the 2015 National Graduate Mathematical Contest in Modeling F’s data,the paper has done a deep research surrounding the first question of the rational planning of the tourism route.As the first question of F plays a key role in solving the subsequent questions,it is considered as the starting point of the analysis.Firstly,the first question,of which can also be understood as a generalized multiple traveling salesman problem to traveling salesman number（number of years） for at least the objective,is solved through the map collection and the complement of the missing data which are processed reasonably,and adopting the ＂minimum circle coverage＂ approach by minimizing the number of tourism objectives.In this question,the Dijkstra algorithm,the least circle covering method,the intelligent algorithm and the graph theory clustering method are used.The establishment of a single objective optimization model by these methods,and using conversion between the traveling salesman problem and the model to analyze and solve the question.

关 键 词：旅游路线规划 TSP问题 单目标规划 图论聚类 

分 类 号：O221.6[理学—运筹学与控制论]