基于贪心算法的黄山景区旅游路线优化设计.docx

基于贪心算法的黄山景区旅游路线优化设计袁绛书 冯振宇 朱天乐 陈铭思 姜雨辰摘 要：黄山景区景点众多且许多知名景点分布过于分散、彼此间相距较远，使得很多游客没有办法在有限的时间内游览完期望的景点。因此根据游客个性化选择为其推荐一条满意度最高的路线尤为重要。本文考虑游客的景点偏好、金钱预算和精力等约束条件，建立了基于游客满意度最大化的旅游路线优化模型，引入两点之间的高程、直线距离和路程量化游客的精力，根据年龄和性别赋予不同的初始精力，并赋予金钱和精力在不同线路的影响权重。利用贪心算法求解，在最优条件下，根据不同的初始数据，可以得到基于游客个性化选择为基础，游客满意度最大的最优路线，从而可解决游客在有限的时间内游览黄山景区期望景点的需求。关键词：黄山;路线优化;0-1规划;贪心算法中图分类号：F27     文献标识码：A      doi：10.19311/ki.1672-3198.2020.20.0161 研究背景黄山景区占地面积共计1200平方千米，一日之内难以全部游览，因此，如何根据不同游客的个性化需求推荐旅游线路，成了大家关注的问题。现有文献大都仅考虑用户某一方面的约束，张久腾、吴小竹等人基于时间约束对多日游行程进行规划和优化，王东基于用户的对景点的兴趣进行旅游路线规划，往往都没有考虑到游客的时间预算、资金预算、自身身体状况等约束条件，基于单一约束的推荐结果难以满足用户需求。本文基于黄山旅游景点开放的线路，研究多约束多目标的旅游线路推荐方法。对于多目标规划旅行线路，Weimin Zheng和Zhixue Liao提出用启发式算法求得最优解，牛悦诚提出用蚁群算法求最有路径解，而本文提出一种多属性景点的评价机制，引入金钱、精力、游客偏好等因素，引用一种在多约束条件下的贪心算法，使用贪心算法选出前N条总体评价较高的路径，然后，通过综合评估路径的有效性及多样性，最终选出相对较优的路径作为推荐结果。2 问题分析根据人群不同赋予不同的精力初始值，景点开放接待游客的时间为每天早上900到下午1800，金钱的权值只考虑部分路线中的索道、缆车费用，在时间方面，本文通过查询相连景点之间的游客步行时间和游览时间之和进行赋值，精力方面，采取相关算法将精力的定性分析转化为定量分析，并给予不同类型游客人群以不同的初始值。最后求解出三者权值之和再进行归一化，利用动态规划方法进行求解。3 模型假设根据上述背景，我们对相关过程做出简化并做出以下假设：（1）游客所具备的时间、预算及精力都是有限的且可以量化的;游客偏好可通过游客对各景点赋分，以进行量化。（2）景区的交通情况影响游客精力消耗及通行时间。为简化模型，游客在景点逗留时间根据资料赋予一个固定值。（3）游客游览时间局限于景区开放时间，假设景区开始营业时游客即开始在景区游览。（4）游览天数及预算金额任一值消耗殆尽，停止游览。（5）游客精力值根据年龄体能区别赋予，精力值可于第二天全额恢复，当日精力或可游览时间耗尽时，停止当日游览。（6）游客不会重复游览。4 模型的建立与求解4.1 模型建立基于以上假设，将各景点设为节点，景点间交通路线设为边，通过游客偏好对景点价值进行赋值，并将该值作为节点的权值;根据路线长度，路线精力耗费值及路线所需金钱对各边进行赋值。根据假设，运用贪心算法进行模拟计算，在每个游览日中生成当日游览路线，最终解出在约束条件下使得游客满意度最高的游览路线集。其中，n为景点序号，Tij为交通时间，t为游览时间，Eij为交通精力，e为游览精力，M为预算金额，m为景区消费，V代表景点价值，S代表游客满意值，h为景点海拔，hij为景点高差，sij代表景点距离，xij为景点路程，W是新定义指标，用于统一T、E、m三个变量，yE为交通精力决策变量，ye为游览精力决策变量，yT为交通时间决策变量，yt为游览时间决策变量，ym为预算金额决策变量，yV为景点价值决策变量。考虑到简化模型的原则，对赋予到边上的各指标进行归一处理，定义新的指标W，对于路线指标归一有：W=0.3T+0.3E+0.4m在本模型中，精力作为主观指标，无法通过查找资料直接获取。本文进行如下计算以量化精力：假设A点与C点为景区两景点，A点海拔为hA，C点海拔为hC，两点高差hac=|hA-hC|，AC两点直线距离为sac，AC两点交通距离为xac，游客从A景点到C景点的交通精力消耗值为：最终得出如表1所示权值。4.2 模型的求解用阶段变量k表示节点编号，状态变量Sk表示游客抵达k节点时身上携带资源换算成单权后的剩余权值，决策变量xk表示是否游览k号节点。具体操作如下：游客从一个起点开始，对图进行遍历操作，直到游客携带的资源不能支持游客抵达终点为止。选用贪婪算法，就要明确每一次决策时选择k号节点的方法。此处提出单位权满意度的概念，即目的节点的满意度值与从当前节點到目的节点边的权值的比，每次决策时，选择单位权满意度最大的边的后继节点。本模型与背包问题存在微小的差异，所以不能直接套用贪婪算法。此处笔者对贪婪算法进行了一些改良，增加了算法的终止条件，即每次抵达一个新的节点时，检查当前节点到终点的最短路所花费的权值，如果这个权值大于当前游客携带资源的权值时，将状态退回到上一节点。如果在上一节点发现无论下一步选择哪个节点都不能满足上述条件，则这个上一节点就是遍历操作的停止点。最终在遍历停止的时候，记录遍历节点的顺序，这就是模型的局部最优解。5 模型应用根据某旅行社的大数据统计，笔者对上文所述16个代表景点进行满意度赋值，并对时间、预算和精力分别赋以540min、300、100，预设游客游览天数为3天，每天游览8小时，各景点游览半小时，从早上9时起到达游览出发点。经模型计算得出如下游览路线集和计划时间集：第1天：云谷寺迎客松光明顶丹霞峰西海大峡谷云门峰老龙潭第2天：鸣弦泉花谷吊桥庵天都峰猴子观海丹霞峰老龙潭第3天：九龙瀑香炉峰慈光阁老龙潭本文基于黄山景点分布分散且彼此之间相距较远的现象，提出了基于游客满意度最大化的旅游路线优化模型。通过挖掘景点的信息为游客在黄山提供推荐旅游路线，并在金钱和精力，以及考虑游客年龄性别的各种限制下，为游客提供满足其需求的推荐路线。参考文献1张久滕，吴小竹，陈崇成，等.基于时间框架的多日游行程规划及其优化方法J.福州大学学报（自然科学版），2018，46（06）：787-793.2王东.基于用户兴趣与关注度的旅游路线推荐研究J.电脑知识与技术，2018，14（01）：18-19，22.3Weimin Zheng， Zhixue Liao. Using a heuristic approach to design personalized tour routes for heterogeneous tourist groupsJ. Tourism Management，2019，（72）.4牛悦诚.基于蚁群算法的智慧旅游路线规划研究D.南京：南京邮电大学，2017.5Becky P. Y. Loo， Linna Li. Carbon dioxide emissions from passenger transport in China since 1949： Implications for developing sustainable transportJ. Energy Policy，2012，（50）.6吴育华，杜刚.管理科学基础M.天津：天津大学出版社，2009：94-97.7周啸，李少梅，李森，等.一种基于局部贪心搜索的兴趣旅游路线规划算法J.河北师范大学学报（自然科学版），2019，43（03）：262-268.