第 ３１卷　第 １０期 重 庆 理 工 大 学 学 报（自然科学） ２ ０ １ ７年 １ ０月 Ｏｃ ｔ ．２ ０ １ ７ Ｊ ｏ ｕ ｒ ｎ ａ ｌｏ ｆＣｈ ｏ ｎ ｇ ｑ ｉ ｎ ｇＵｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙｏ ｆＴｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ （Ｎａ ｔ ｕ ｒ ａ ｌＳ ｃ ｉ ｅ ｎ ｃ ｅ ） Ｖｏ ｌ ． ３１　　Ｎｏ ． １ ０  ｄ ｏ ｉ ：１ ０． ３ ９ ６ ９／ ｊ ． ｉ ｓ ｓ ｎ． １ ６ ７ ４－８ ４ ２ ５（ｚ ）． ２ ０ １ ７． １ ０． ０ ２ ５ 基于蚁群算法的旅游线路优化 刘训星，胡　敏，黎　颖 （宣城职业技术学院，安徽 宣城 ２４２ ０００） 摘　　　要：旅游成为当今休闲放松的重要方式，每位旅客受空间、时间和经济能力限制具有不 同需求，因此游客面临的首要问题就是选择适合的旅游线路。针对宣城市丰富的旅游资源，利 用蚁群算法对 １３个特色景点进行线路规划，然后建立带约束线路规划模型，并通过评价分析求 得最优结果。实验表明：该方法能为不同游客推荐不同需求的旅游线路。 关　键　词：蚁群算法；线路规划；旅游；线路优化 中图分类号：Ｏ２ １１；ＴＰ３ １９　　　文献标识码：Ａ 文章编号： １ ６７４－８４２ ５（２ ０１７）１０－０１５８－０７ ＴｈｅＡｎｔＣｏ ｌ ｏ ｎｙＡｌ ｇ ｏ ｒ ｉ ｔ ｈｍ Ｂａ ｓ ｅ ｄＲｅ ｓ ｅ ａ ｒ ｃ ｈｏ ｎＣｕｌ ｔ ｕｒ ａ ｌ Ｔｏ ｕｒ ｉ ｓ ｔＲｏ ｕｔ ｅＯｐｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ＬＩ ＵＸｕ ｎｘ ｉ ｎ ｇ ，ＨＵＭｉ ｎ，ＬＩＹｉ ｎ ｇ （Ｘｕａ ｎ ｃ ｈｅ ｎｇＶｏ ｃ ａ ｔ ｉ ｏ ｎ ａ ｌａ ｎｄＴｅ ｃ ｈｎ ｉ ｃ ａ ｌｃ ｏ ｌ ｌ ｅ ｇ ｅ ，Ｘｕａ ｎ ｃ ｈ ｅ ｎｇ２ ４２０ ００，Ｃｈｉ ｎａ ） Ａｂｓ ｔ ｒ ａｃ ｔ ：Ｎｏ ｗａ ｄａ ｙ ｓ ，ｔ ｏ ｕ ｒ ｉ ｓ ｍ ｈａ ｓｂ ｅ ｃ ｏ ｍｅａ ｎｉ ｍｐｏ ｒ ｔ ａ ｎｔｗａ ｙｏ ｆｒ ｅ ｃ ｒ ｅ ａ ｔ ｉ ｏ ｎ．Ｅｖ ｅ ｒ ｙｔ ｏ ｕｒ ｉ ｓ ｔｐ ｏ ｓ ｓ ｅ ｓ ｓ ｅ ｓ ｄｉ ｆ ｆ ｅ ｒ ｅ ｎｔｄ ｅ ｍａ ｎｄｓｒ ｅ ｓ ｔ ｒ ｉ ｃ ｔ ｅ ｄｂｙｓ ｐａ ｃ ｅ ，ｔ ｉ ｍｅａ ｎ ｄｅ ｃ ｏ ｎ ｏ ｍｉ ｃｃ ａ ｐ ａ ｂ ｉ ｌ ｉ ｔ ｙ ，ｔ ｈ ｕｓ ，ｔ ｈｅｆ ｉ ｒ ｓ ｔｑｕ ｅ ｓ ｔ ｉ ｏ ｎｆ ａ ｃ ｉ ｎ ｇ ｔ ｏ ｕｒ ｉ ｓ ｔ ｓｉ ｓｈ ｏ ｗｔ ｏｃ ｈ ｏ ｏ ｓ ｅａｐｒ ｏ ｐ ｅ ｒｔ ｏ ｕｒ ｉ ｓ ｍｒ ｏ ｕ ｔ ｅ ．Ｔｈ ｅｔ ｈ ｅ ｓ ｉ ｓ ，ａ ｉ ｍｉ ｎｇａ ｔａ ｂｕｎｄ ａ ｎｔｔ ｏ ｕｒ ｉ ｓ ｍｒ ｅ ｓ ｏ ｕｒ ｃ ｅ ｓｏ ｆ Ｘｕａ ｎｃ ｈ ｅ ｎｇｃ ｉ ｔ ｙ ，ｃ ｏ ｎｄ ｕ ｃ ｔ ｓａｒ ｏ ｕ ｔ ｅｐｌ ａ ｎｏ ｎ１ ３ｓ ｃ ｅ ｎ ｉ ｃｓ ｐ ｏ ｔｉ ｎａｗａ ｙｏ ｆａ ｎ ｔａ ｌ ｇ ｏ ｒ ｉ ｔ ｈｍ，ａ ｎｄｅ ｓ ｔ ａ ｂ ｌ ｉ ｓ ｈｅ ｓ ｃ ｏ ｎｓ ｔ ｒ ａ ｉ ｎ ｅ ｄｒ ｏ ｕ ｔ ｅｐ ｌ ａ ｎｍｏ ｄｅ ｌａ ｎ ｄｐ ｕ ｒ ｓ ｕ ｅ ｓｔ ｈｅｂ ｅ ｓ ｔｒ ｅ ｓ ｕ ｌ ｔ ｓｔ ｈ ｒ ｏ ｕ ｇ ｈｍａ ｋｉ ｎｇａ ｎａ ｎａ ｌ ｙ ｓ ｉ ｓ ．Ｔｈ ｅｅ ｘ ｐ ｅ ｒ ｉ ｍｅ ｎｔ ｓ ｈｏ ｗｓｔ ｈ ａ ｔｔ ｈ ｉ ｓｗａ ｙｃ ａ ｎｐ ｒ ｏ ｖ ｉ ｄｅｖ ａ ｒ ｉ ｏ ｕ ｓｔ ｏ ｕ ｒ ｉ ｓ ｍｒ ｏ ｕ ｔ ｅｆ ｏ ｒｄｉ ｆ ｆ ｅ ｒ ｅ ｎｔｔ ｏ ｕｒ ｉ ｓ ｔ ｓ ． Ｋｅ ｙｗｏ ｒ ｄｓ ：ａ ｎｔｃ ｏ ｌ ｏ ｎ ｙａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ；ｒ ｏ ｕ ｔ ｅｐ ｌ ａ ｎ ｎｉ ｎ ｇ ；ｔ ｏ ｕｒ ｉ ｓ ｍ；ｐ ａ ｔ ｈｏ ｐｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　　随着老百姓生活水平的提高，旅游已成为最 旅游路径 规 划 从 区 域 范 围 可 以 分 为 ３个 部 时尚的休闲活动，怎样在假期有限、预算不增加的 分：城市之间的旅游路径规划、城市内各景区的旅 情况下游玩更多的景点是广大旅游爱好者迫切需 游路径规划、景区内各景点的旅游路径规划。城 要解决的问题，所以景点路径规划十分必要，有助 市之间的旅游路径规划和景区内各景点的旅游路 于游客寻找最佳旅游路线。 径规划都是从一点出发，经过其他点，且只经过一 　　收稿日期：２０１７－０８－０１ 基金项目：安徽省高等学校自然科学重点研究项目（ＫＪ ２ ０ １ ６Ａ７ ８ ４） 作者简介：刘训星（１ ９ ８ １—），男，安徽宣城人，硕士，讲师，主要从事网络并行分布计算、数据挖掘、教育信息化研究， Ｅ ｍａ ｉ ｌ ：８ ２ ６ ０ ３ ８ １ １ ５＠ｑ ｑ．ｃ ｏ ｍ。 引用格式：刘训星，胡敏，黎颖．基于蚁群算法的旅游线路优化［Ｊ ］．重庆理工大学学报（自然科学），２ ０ １ ７（１ ０）：１ ５ ８ －１ ６ ４． Ｃｉ ｔ ａ ｔ ｉ ｏ ｎｆ ｏ ｒ ｍａ ｔ ：ＬＩ ＵＸｕ ｎ ｘ ｉ ｎ ｇ ，ＨＵＭｉ ｎ，ＬＩＹｉ ｎ ｇ ．Ｔｈ ｅＡｎ ｔＣｏ ｌ ｏ ｎ ｙＡｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ Ｂａ ｓ ｅ ｄＲｅ ｓ ｅ ａ ｒ ｃ ｈｏ ｎＣｕ ｌ ｔ ｕ ｒ ａ ｌＴｏ ｕ ｒ ｉ ｓ ｔＲｏ ｕ ｔ ｅＯｐ  ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ［Ｊ ］．Ｊ ｏ ｕ ｒ ｎ ａ ｌｏ ｆＣｈ ｏ ｎ ｇ ｑ ｉ ｎ ｇＵｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙｏ ｆＴｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ （Ｎａ ｔ ｕ ｒ ａ ｌＳ ｃ ｉ ｅ ｎ ｃ ｅ ）， ２ ０ １ ７（１ ０）： １ ５ ８－１ ６ ４． 刘训星，等：基于蚁群算法的旅游线路优化 １５９  次，最后回到出发点的路线规划，即 ＴＳＰ回路问 接口。② 编译器：先对查询语句检查，然后转化语 题。这是一个经典的 ＮＰ难题，所以解决方法非常 法树，接着生成汇编代码，最后交由虚拟机运行。 多。其中包括：蚁群算法、退火算法、遗传算法、粒 ③ 虚拟机：用于解释运行代码，完成特定的操作。 子群算法和禁忌搜索算法等。对景点路径规划的 ④后端：管理运行数据，搜索数据维系页面关系。 研究有助于解决很多类似路径规划问题，所以研 １． ２　Ｗｅ ｂＳｅ ｒ ｖ ｉ ｃ ｅ Ｗｅ ｂＳ ｅ ｒ ｖ ｉ ｃ ｅ是一种跨平台应用程序。移动终 究景点路径规划问题具有重要意义。 目前路径规划已经在工业、物流方面大规模 应用，国内 外 学 者 开 展 了 深 入 研 究，提 出 许 多 算 法 ［１］ 和 方 案，包 括 启 发 式 搜 索、蚁 群 算 法 ［２］ 、 端及网络终端都能够同时使用 Ｗｅ ｂＳ ｅ ｒ ｖ ｉ ｃ ｅ方法。 Ｗｅ ｂＳ ｅ ｒ ｖ ｉ ｃ ｅ具 有 以 下 优 势：① 数 据 交 换 更 加 便 利，适合异构系统间数据交换和通信。 ② 使用了 Ｄｉ ｊ ｋ ｓ ｔ ｒ ａ 、神经网络。宣城市是文房四宝之乡，有着 ＸＭＬ技术对对数据进行封装，使用者仅能看到功 丰富的旅游文化资源，文中首次将蚁群算法应用 能列表。③ 用标准的方法把不同语言开发和不同 到宣城市文房四宝文化旅游线路规划，通过在宣 平台程序集成起来。文中将采用 Ｗｅ ｂＳｅ ｒ ｖ ｉ ｃ ｅ来 城市旅 游 信 息 平 台 的 应 用，得 出 了 最 佳 的 旅 游 获取移动终端信息，管理数据库和生成具有导航 路线。 功能的地图。 １． ３　蚁群算法 １　旅游信息服务平台技术设计分析 蚁群算法由 Ｍａ ｒ ｃ ｏＤｏ ｒ ｉ ｇ ｏ等 ［４］受蚂蚁觅食启 发提出的一种随机智能算法。蚂蚁在没有辅助的 １． １　Ａｎｄｒ ｉ ｏｄ系统 Ａｎｄｒ ｉ ｏ ｄ系统主要用于平板、手机智能移动终 情况下找到巢穴至食物最短路径，蚂蚁选择路径 的过程是一种正反馈机制。旅客在不同景点游玩 端，具有性能卓越、开源、市场占 有 率 高 等 特 点。 与蚂蚁觅食有惊人的相似处，所以蚁群算法适用 Ａｎｄｒ ｉ ｏ ｄ系统具有以下优势：① 任意移动终端生产 于景点间路径规划。 商能够自由融入 Ａｎ ｄ ｒ ｉ ｏ ｄ联盟。 ② Ａｎｄ ｒ ｉ ｏ ｄ系统 蚂蚁算法的优势表现在以下几个方面：① 蚂 具有开源 免 费 的 特 点，有 利 于 第 三 方 软 件 开 发。 蚁算法能够用来解决至今没有找到合适算法的问 ａ ｖ ａ语言也具有开 ③ 用于开发第三方软件，程序 ｊ 题。② 蚂蚁算法采用启发式思维算法框架。 ③ 源免费的特点。 蚂蚁算法是近似算法，具有较大弹性，可以针对不 Ａｎｄｒ ｉ ｏ ｄ系统提供多种存储方式：文件存储、 内容提供器、网络存储 ［３］和 Ｓｑ ｌ ｉ ｔ ｅ存储，文房四宝 文化旅游系统采用 Ｓｑｌ ｉ ｔ ｅ存储数据。 Ｓｑｌ ｉ ｔ ｅ具有操作方便、灵活高效、跨平台等特 ｑ ｌ ｉ ｔ ｅ在同 点，能够嵌入应用程序中关联数据库。Ｓ 同应用问题加以改进，运用到不同领域。 蚁群算法应用领域很广泛，刘利强等研究在 水下三维空间路径规划；朱庆保研究机器人路径 规划；张维泽等研究物流配送规划；王慧等 ［５］研究 旅游线路规划。 一进程空间服务器和客户端同时运行，在应用程 序运行时无需管理和网络配置。Ｓ ｑｌ ｉ ｔ ｅ使用权限 ２　旅游信息服务平台功能设计分析 只与文件系统有关。Ｓｑｌ ｉ ｔ ｅ由于高效占用内容空 间小，非常适合用户移动终端，在使用过程中只需 ｉ ｔ ｅ编 译 到 文 房 四 宝 文 化 旅 游 信 息 服 务 平 把 Ｓｑｌ 台中。 Ｓｑｌ ｉ ｔ ｅ数据库架构由接口、编译器、虚拟机、后 端组成。① 接口：用于 Ｓｑｌ ｉ ｔ ｅ与文件、程序交互的 ２． １　系统框架设计 文房四宝旅游文化信息服务系统中客户端采 用 Ａｎ ｄｒ ｏ ｉ ｄ系 统 使 用 Ｓｑｌ ｉ ｔ ｅ数 据 库，服 务 器 采 用 ｌ ｉ ｎｕｘ系统使用 ｍｙ ｓ ｑｌ数据库，实现了多媒体播放、 电子地图、天气查询、交友等功能。 重庆理工大学学报 １６０ 