游客行程多目标智能规划算法研究

发布时间：2018-08-22 19:08

【摘要】：国家经济的发展使得人民生活水平不断提高,出行旅游成了生活的一部分。如今,人们出行旅游不仅仅局限于某一个旅游点,往往涉及到很多个景点。因此,如何规划旅游线路就成了必须解决的问题。大量旅游网站的存在使得人们可以在网站上发布海量的与旅游相关的信息,游客可以根据这些信息制定自己的出游计划。然而,这些旅游网站上的信息通常比较散乱,缺少结构化的特征,普通游客难以根据这些信息制定完美的旅游线路。因此,旅游推荐的研究逐渐得到广大学者的关注。时间依赖的旅行时间和用户的多种偏好是实际旅游过程中最重要的两个因素。本文的研究主要是在规划行程的同时综合考虑这两方面的因素,称为多目标时间依赖定向问题(Multi-Objective Time-Dependent Orienteering Problem,简称MOTDOP)。同时处理多个偏好和时间依赖的旅行时间在这个NP-hard问题中提出了一个具有挑战性的优化任务。本文在广泛深入地查阅国内外文献的基础上,对多目标优化问题及时间依赖的旅行时间问题分别进行了描述并将这两方面的因素结合起来进行了深入的理论研究和实验分析。主要内容如下:首先,对多目标优化的理论做了介绍,提出了多目标优化模型,并且阐述了多目标优化问题Pareto最优解的概念和传统的多目标优化方法;介绍了传统定向问题的相关概念、目标函数及约束条件;蚁群算法的理论基础和相关算法的改进。接着本文提出了多目标时间依赖定向问题(MOTDOP)的数学模型,为了解决这个问题,通过流程图以及伪代码的形式阐述了两个元启发式方法:多目标文化基因算法(Multi-Objective Memetic Algorithm,简称MOMA)和多目标蚁群系统(Multi-objective Ant Colony System,简称MOACS)。最后,本文生成了两组基准实例来评估所提出的算法并与其它算法进行对比。实验研究表明,MOMA和MOACS设法找到更好的解决方案。
[Abstract]:With the development of national economy, people's living standard has been improved, and travel and tourism has become a part of life. Nowadays, people travel not only to one tourist spot, but also to many scenic spots. Therefore, how to plan tourism routes has become a problem that must be solved. The existence of a large number of tourism websites makes it possible for people to publish vast amounts of tourism-related information on the website, according to which tourists can make their own travel plans. However, the information on these travel websites is often scattered and lack of structured features, and it is difficult for ordinary tourists to make perfect travel routes based on these information. Therefore, the study of tourism recommendation has gradually attracted the attention of scholars. Time-dependent travel time and user preferences are the two most important factors in the actual travel process. In this paper, we mainly consider these two factors while planning the trip, which is called Multi-Objective Time-Dependent Orienteering problem (MOTDOP). For short). Dealing with multiple preference and time dependent travel time presents a challenging optimization task in this NP-hard problem. On the basis of extensive and in-depth reference to domestic and foreign literature, this paper describes the multi-objective optimization problem and the time-dependent travel time problem, and combines the two factors together to carry out in-depth theoretical research and experimental analysis. The main contents are as follows: firstly, the theory of multi-objective optimization is introduced, the multi-objective optimization model is proposed, and the concept of Pareto optimal solution for multi-objective optimization problem and the traditional multi-objective optimization method are expounded. This paper introduces the related concepts, objective function and constraint conditions of the traditional orientation problem, the theoretical basis of ant colony algorithm and the improvement of the related algorithm. Then, a mathematical model of multi-objective time dependent orientation problem (MOTDOP) is proposed in this paper. In order to solve this problem, In this paper, two meta-heuristic methods, Multi-Objective Memetic algorithm (MOMA) and Multi-objective Ant Colony System, (MOACS).), are described in the form of flow chart and pseudo-code. Finally, two sets of benchmark examples are generated to evaluate the proposed algorithm and compare it with other algorithms. Experimental studies show that MOMA and MOACS try to find better solutions.
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】