下载后可任意编辑基于贪心算法的黄山景区旅游路线优化设计基于贪心算法的黄山景区旅游路线优化设计 袁绛书 冯振宇 朱天乐 陈铭思 姜雨辰 摘 要：黄山景区景点众多且许多知名景点分布过于分散、彼此间相距较远，使得很多游客没有办法在有限的时间内游览完期望的景点。因此根据游客个性化选择为其推举一条满意度最高的路线尤为重要。本文考虑游客的景点偏好、金钱预算和精力等约束条件，建立了基于游客满意度最大化的旅游路线优化模型，引入两点之间的高程、直线距离和路程量化游客的精力，根据年龄和性别给予不同的初始精力，并给予金钱和精力在不同线路的影响权重。利用贪心算法求解，在最优条件下，根据不同的初始数据，可以得到基于游客个性化选择为基础，游客满意度最大的最优路线，从而可解决游客在有限的时间内游览黄山景区期望景点的需求。 关键词：黄山;路线优化;0-1 规划;贪心算法 中 图 分 类 号 ： F27 文 献 标 识 码 ： A doi ： 10.19311/j.cnki.1672-3198.20XX.20.016 1 讨论背景 黄山景区占地面积共计 1200 平方千米，一日之内难以全部游览，因此，如何根据不同游客的个性化需求推举旅游线路，成了大家关注的问题。现有文献大都仅考虑用户某一方面的约束，张久腾、吴小竹等人基于时间约束对多日游行程进行规划和优化，王东基于用户的对景点的兴趣进行旅游路线规划，往往都没有考虑到游客的时间预算、资金预算、自身身体状况等约束条件，基于单一约束的推举结果难以满足用户需求。本文基于黄山旅游景点开放的线路，讨论多约束多目标的旅游线路推举方法。对于多目标规划旅行线路， Weimin Zheng 和 Zhixue Liao 提出用启发式算法求得最优解，牛悦诚提出用蚁群算法求最有路径解，而本文提出一种多属性景点的评价机制，引入金钱、精力、游客偏好等因素，引用一种在多约束条件下的贪心算法，使用贪心算法选出前 N 条总体评价较高的路径，然后，通过综合评估路径的有效性及多样性，最终选出1下载后可任意编辑相对较优的路径作为推举结果。 2 问题分析 根据人群不同给予不同的精力初始值，景点开放接待游客的时间为每天早上 9∶00 到下午 18∶00，金钱的权值只考虑部分路线中的索道、缆车费用，在时间方面，本文通过查询相连景点之间的游客步行时间和游览时间之和进行赋值，精力方面，实行相关算法将精力的定性分析转化为定量分析，并给予不同类型游客人群以不同的初始值。最后求解出三者权...
