旅游线路推荐问题的建模及优化.doc

《旅游线路推荐问题的建模及优化.doc》由会员分享，可在线阅读，更多相关《旅游线路推荐问题的建模及优化.doc（7页珍藏版）》请在三一文库上搜索。

1、精品论文旅游线路推荐问题的建模及优化翟来鹏，柯良军（西安交通大学机械制造系统工程国家重点实验室）5摘要：旅游线路推荐问题的目标是根据旅客的需求为其推荐合适的旅游线路。本文通过分析 旅游线路推荐问题，给出了该问题的数学模型，并提出了求解该问题的蚁群算法和贪婪算法。最后，实验分析了所提出算法的性能，仿真结果表明，所提出蚁群算法能够有效解决旅游线 路推荐问题。10关键词：旅游线路推荐；蚁群算法；贪婪法中图分类号：TP18On the Model and Optimization of Tour TripRecommendation Problem15ZHAI Laipeng, KE Liangjun

2、(State Key Laboratory for Manufacturing Systems Engineering, Xian Jiaotong University) Abstract: The goal of tour trip recommend problem is to recommend suitalbe tour trips for passengers. Based on the analysis of characteristics of the tour trip recommendation problem, this paper provides its model

3、. Moreover, an ant colony algorithm and greedy method is proposed to20solve this problem. The results of numerical experiments show that the ant colony algorithm is effective.Key words: Tour trip recommendation, ant colony algorithm, greedy algorithm0引言25随着我国经济的迅速发展，旅游行业日新月异，旅游景点数目和旅客数量均不断增多。 面对数目众多

4、的旅游景点，对旅客而言，旅游线路的选择与规划已经更加困难。因此，结合 不同旅游景点的信息，为旅客推荐合适的旅游线路，具有一定的应用价值。目前，旅游线路设计、旅游信息推荐等相关问题受到广泛关注。文献1介绍了基于移 动网络设备的个性化旅游信息推荐系统的设计方法。Garcia 等开发了旅游信息的推荐系统，30该系统既能够为单个旅客推荐个性化旅游信息，又能够为团体推荐最大程度满足团体内所有 成员的旅游信息2；文献3中，Vansteenwegen 等开发了一个专家系统，该系统能够为到某 城市旅行的旅客推荐旅行线路。文献4 总结了旅游线路设计问题的现有主要研究成果。本文对旅游线路推荐问题进行了分析，讨论了

5、其与团队定向问题5的联系。提出并验 证了求解旅游线路推荐问题的蚁群算法。351旅游线路推荐问题分析与建模1.1旅游线路推荐问题旅游线路推荐问题可具体地描述如下：在旅行时间、消费金额、景点开放时间受限等条 件下，为旅客推荐由若干景点组成的旅游线路，使其最大程度地享受到旅行的乐趣，即获得最大收益。基金项目：高等学校博士学科点专项科研基金（20090201120042）；国家自然科学基金（60905044）作者简介：翟来鹏，硕士通信联系人：柯良军（1976-），男，博士，副教授，复杂系统建模与优化，模式识别. E-mail: - 7 -40在对问题建模求解之前，首先对模型相关的若干问题进行分析与说明

6、：1)旅客需求 主要包括所花费的时间、消费金额和对不同类型景点的偏好等。本文暂时只考虑旅行所花费时间及消费金额两方面的因素，并设旅客旅行总时间为Tmax ，最大总消费金额为 Cmax 。2)景点描述45对景点的描述主要包括三个方面：游览费用、景点开放时间以及对景点质量的评价。本 文用 ci 表示景点 i 的游览费用，且每个景点对应的游览费用均取为固定值；景点开放时间用 时间窗Oi , Ci 表示，即，对景点 i 的游览，只能在从 Oi 到 Ci 这一时间段内进行；对景点的 质量用大于零的数字值描述，数值越大则对应景点的质量越高，旅客游览该景点获得的收益 越大。显然，在不同的评价标准下，用于描述

7、景点的数字值的大小将会有所差别，但考虑到50不同旅客对同一景点的评价一般不会相差太多，为了研究方便，本文将用以评价各景点质量 的数字值均取为固定值，并用 ri 表示。3)时间问题旅游线路推荐问题中涉及到的时间问题主要包括：旅客在景点 i 的游览时间 ti ，景点 i 的开放时间Oi , Ci ，从一个景点 i 到另一个景点 j 所需花费时间 tij 以及旅客旅行的总时间55Tm a x 。其中，所推荐旅游线路中包含的每个景点的游览时间 ti 和景点间线路上花费时间tij 之和应小于等于旅客旅行总时间应，设 P 为旅游线路中所包含的景点的集合，则，ti + tij Tmaxi, j P（1）旅客

8、在景点 i 的游览时间Ti ，是旅客在景点 i 的停留时间，Ti 的大小同旅客对景点的兴 趣及景点的大小等因素有关，简单起见，本文中Ti 暂取为固定值。60景点 i 的开放时间Oi , Ci ，是考虑到实际中旅游景点一般均有固定的开发时间而设定 的，是对景点的描述的一部分，旅客对景点的游览必须在时间区间Oi , Ci 内开始和结束。 一个景点 i 到另一个景点 j 所需花费时间 tij ，是指在连续游览的两景点间路上花费的时间， tij 的大小与景点 i 和景点 j 间的距离有关，为研究方便，在本文中，设 cij 同景点 i 和景 点 j 间的距离成正比。654)费用问题 旅游线路推荐问题中的

9、费用主要指游览所选择景点时门票等固定费用。设 ci 为景点 i 对应的消费金额，根据用户需求，旅游线路中所包含景点的费用总和应小于等于最大总消费金 额，即ci Cmax705)旅客收益i P（2）旅客收益用 R 表示，用来描述旅客对旅游线路的满意程度。显而易见，旅客收益同旅 游线路中所含景点的质量与数量密切相关，本文中用旅游线路中所包含的景点的数字值之和 来表示旅客收益，即R = rii P（3）756)线路评价考虑到推荐旅游线路的目的是使得旅客收益最大化，故用旅客收益对旅游线路进行评 价，即，在满足约束条件的所有旅游线路中，使得旅客收益越大的旅游线路，其质量也越高； 当两条路径对应的旅客收益

10、相同时，则线路总长度较小的旅游线路更好。1.2旅游线路推荐问题的数学模型80根据上面的分析，借助图论知识旅游线路推荐问题可描述如下：给定一个完全图G = (V , E) ，其中V = 1,., n是顶点的集合，E = (i, j) | i, j V 是边的集合。集合V 中每一个顶点 i 都对应有一个非负收益 ri 、一个非负游览费用 ci 和一个非负的游览时间 ti 。其中，1是起点， n 是终点，且 r1 =rn = 0 ， c1 = cn = 0 ， t1 = tn = 0 。对于边集 E 中的每一条边，都有一个对称的非负的参数 tij 与之对应，此处 tij 指从顶点 i 到顶点 j 间

11、的行驶时间，85与两点间距离成正比。与此对应的旅游线路推荐问题为，寻找从起点1到终点 n 的 m(m 1) 条路径，使得所访问顶点的总收益最大。每一个顶点最多只能被访问一次，且每条路径花费 的总时间不能超过 Tmax ，总游览费用不能超过 Cmax 。当顶点 i 包含在第 k 条路径中时，令 yik = 1 ，否则令 yik = 0 ；当边 (i, j) 包含在第 k 条路径中时，令 xijk = 1 ，否则令 xijk = 0 ， 由于 tij = t ji ，故只在 i j 的区域内定义了 xijk ；设 sik 为第 k 条路径中，开始游览顶点 i 的时90间；设U 为V 的子集，则旅游

12、线路推荐问题的模型的数学描述如下： 目标函数为：n -1 mmax ri yiki = 2 k =1（4）约束条件为：n m n -1 m x1 jk = xink = m（5）j = 2 k =1i =1 k =195 xijk + xijk = 2 y jk i j( j = 2,., n -1; k = 1,., m)（6）m yik 1 (i = 2, .n - 1)k =1（7）n-1 ntij xijk + ti yik Tmax(k = 1,., m)（8）i =1j i i =1n -1 m ci yik Cmaxi = 2 k =1（9）Oi sik Ci(1 i j n;

13、k = 1, .m)（10）100xijk 0,1 (1 i Lki + tij Ojt(i, j) = （13）Oj + t j - Lkiif Oj Lki + tij130旅游线路推荐问题的目标是寻找收益较高但时间较短，费用较低的线路，故在定义启发 信息时，考虑了以下三个因素：结点收益 rj 、访问所用时间 t(i, j) 以及访问所需费用 c j 。 为了找到最优解，蚂蚁将会偏向于访问那些收益较高且消耗时间和费用较小的点。故启发信息定义如下： rj c jif C L + t O gh = (tij + t j )ij cmaxj ki ij j（14） rj c jif O L +

14、tg (Oj + t j - Lki )cmaxj ki ij135其中，g 为参数， cmax 为所有结点的访问费用中的最大值。2) 解构造过程 本文所提出的用于解决旅游线路推荐问题的蚁群算法采用串行法构造解，即，在构造一条路径时，蚂蚁从起点开始，每一步依概率选择一个点，直到没有可行点，便完成了一条路径。假设在构造第 k 条路径时，在第 j 步时的可行点集为 C j ， B j C j 是候选链表中的点集，依概率从 B j 中选择一个结点 v j +1t (u, v)h (u, v)if v Ba ba b jp(vj +1= v | t ) t (u, w)wB h (u, w)（15）j

15、0else140145为了能够较快地找到较好解，在算法中引入了贪婪机制，即，每只蚂蚁串行地构造一条 路径，并从中选出最优路径作为第一条路径；然后，用相同的方法构造其它 m -1 条路径。 当贪婪搜索不能找到新的优解时，便改用串行法继续构造，直至算法结束。3) 信息素更新规则 蚁群算法信息素更新规则采用最大最小蚂蚁系统中所给出的规则。对于每个边 (u, v) ，其信息素值按下式更新：t (u, v)l +1 = (1 - r )t (u, v)l + Dt (u, v)if t (u, v)l +1 t，t (u, v)l +1 =tminminmaxmax，t (u, v)l +1 =t（16

16、）其中，1- r 为信息素残留因子，t (u, v) 是边 (u, v) 在第 l 代时的信息素值。如果最优蚂 蚁经过边 (u, v) ，则 Dt (u, v) 为 F (sbest ) ，否则，Dt (u, v) = 0 。 F (x) 为解对应的总收益同所有点的总收益之比：n -1 m n150F ( x) = ri yki / ri（17）i = 2 k =1i = 2sbest 既可以是本次迭代中最优解 sib 也可以是全局最优解 sgb 。t max 和t min 分别是信息素 的上下界，分别设置为：t maxtF (s )= gbr(1 - n Pbest ) t（18）min =

17、n(- 1) n Pbest2max（19）155160其中， n 为结点数目， Pbest 为参数，一般取为 0.05。 为了提高搜索效率，算法采用了候选表策略。候选表是一个表，它记录从当前景点出发偏好程度较高的景点。只要候选表还有未访问过的景点，蚂蚁就会按照状态转移规则从候选 表中选取一个景点。当候选表所有景点都被访问过时，蚂蚁才会考虑不在候选表中的景点。 所提出蚁群算法的流程图如图 1 所示。Initialize the parameters,the heuristic information and the pheromone trails sib Null sgb Nullitera

18、tion = 0while iteration is less than for i = 1 to m doNC dosi Constrction(h,t )si LocalSearch(si )end forsib arg max(F (s1 ), F (s2 ),L, F (sm )if F (sib ) F (sgb )sgb sib1652.2贪婪法end ifPheromoneUpdate(t , sib , sgb )iteration = iteration + 1 end while图 1 旅游线路推荐蚁群算法执行过程Fig. 1 The flow chart ofACO fo

19、r tourism circuit recommend problem170贪婪法是一种在每一步都根据求解问题的启发信息选择局部最优，以期望最终得到全局 最优解的算法。贪婪法在构造解的过程中每一步都要选择一个当前看来最优的点，直至完成 一个解的构造，这个过程称为贪婪决策，进行贪婪决策的标准称为贪婪准则，贪婪准则是否 合理，直接决定了贪婪法所得到的解的优劣。用贪婪法求解旅游线路推荐问题时，贪婪准则取为在单位时间和消费金额条件下的收 益。同时，考虑到时间窗，对候选结点按 g i 排序，并依次选择满足约束条件的结点构成一个解， g i 的定义如式(20)。gi =rici (Oi + ti )(i

20、= 1, 2,L, n -1)(20)1753算法实现及验证为了测试所设计蚁群算法的性能，以贪婪法为对比算法，分别用带时间窗的团队定向问 题相关的科技文献中常用的两个测试问题 pr01 和 pr02（在原问题中对每个景点描述的基础 上，添加一项消费金额描述）对其进行测试。测试中所选择的蚁群算法参数分别取为：m = 20,a = 1,b = 1,r = 0.98,Pbest = 0.05,g = 3 。在路径数目 n 分别为 1、2、3、4 条的情况下，分别求解 pr01 和 pr02，蚁群算法在运行180185300 次后停止，所得结果见表 1 和表 2。从求解结果可知，对 pr01 和 pr

21、02 问题，在路径数目分别为 1、2、3、4 条的情况下， 所提出蚁群算法求解得到的结果的平均值均优于贪婪法求解得到的结果，且路径数目越小， 优势越明显。另一方面，注意到蚁群算法求解 pr01 的时间 1.1 秒，pr02 的时间为 2.7 秒 （其 中 n = 4 ）。由此可知，所提出的用于解决旅游线路推荐问题的蚁群算法具有良好的性能。表 1 对 pr01 问题求解结果Tab. 1 Results of problem pr01路径数目贪婪法最大值蚁群算法平均值最小值189.0300.0296.4291.02234.0379.0373.4362.03323.0386.0377.4370.04

22、374.0389.0378.0366.0表 1 对 pr02 题求解结果Tab. 1 Results of problem pr02路径数目贪婪法最大值蚁群算法平均值最小值1171.0398.0394.9388.02377.0698.0682.5671.03526.0827.0807.7793.04699.0834.0821.6803.01901954结论本文首先对旅游线路推荐问题进行了分析，并在此基础上给出了该问题的数学模型。分 析了该问题与带时间窗的团队定向问题的联系。然后，采用蚁群算法对旅游线路推荐问题进 行求解，给出了求解旅游线路推荐问题的蚁群算法的具体形式和求解过程，并以贪婪法为对

23、比算法对其进行验证，验证了算法的有效性。在后续研究中，将考虑其他的智能优化算法（如 禁忌搜索等）以及规模更大的实际问题。参考文献 (References)2002051 Katerina Kabassi. Personalizing recommendations for touristsJ. Telematics and Informatics, 2010, 27: 51-66. 2 Inma Garcia, Laura Sebastia, Eva Onaindia. On the design of individual and group recommender systems for

24、tourismJ. Expert Systems with Applications, 2011, 38: 7683-7692.3 Pieter Vansteenwegen, Wouter Souffriau, Greet Vanden Berghe abd Dirk Van Oudheusden. The City TripPlanner: An expert system for touristsJ. Expert Systems with Applications,2011,38:6540-6546.4 Wouter Souffriau and Pieter Vansteenwegen.

25、 Tourist Trip Planning Functionalities: State-of-the-Art andFutureJ.Computer Science,2010, 6385: 474-485.5 柯良军, 章鹤等. 一类求解具有时间窗约束的团队定向问题的改进蚁群算法 J.计算机科学, 2012,04.6 I-Ming Chao, Bruce L. Golden and Edward A. Wasil. The team orienteering problemJ. European Journal ofOperational Research,1996,88: 464-474.