基于贪心算法的智能旅游行程规划系统设计与实现

1. 个性化旅游行程规划系统概述

这个毕业设计项目构建了一个基于用户偏好的智能旅行规划平台。系统通过算法分析用户输入的时间、预算、兴趣标签等参数，自动生成包含景点、交通、住宿的完整行程方案。作为计算机专业毕业设计的典型选题，它融合了数据库设计、算法应用和前后端开发等多项核心技术。

我在实际开发中发现，这类系统最核心的价值在于平衡"个性化推荐"与"可行性验证"。不仅要根据用户喜好匹配景点，还需考虑地理位置分布、开放时间、门票预约等现实约束条件。比如用户选择"博物馆"兴趣标签时，系统需要自动避开周一闭馆的场馆，并合理分配各景点间的交通时间。

2. 系统架构设计

2.1 技术栈选型

采用SpringBoot+MyBatis后端框架组合，配合Vue.js前端架构。数据库选用MySQL 8.0，主要基于以下考量：

• SpringBoot的自动配置特性大幅简化了微服务搭建过程
• MyBatis的动态SQL能力便于处理多条件行程查询
• Vue的组件化开发适合构建交互复杂的路线编辑器
• MySQL的GIS空间函数支持景点距离计算

特别注意：MySQL必须启用innodb_large_prefix参数，因为行程数据的JSON字段经常超出默认索引长度限制

2.2 核心数据模型

主要包含5张核心表：

1. 用户画像表：存储年龄、兴趣标签（枚举值：自然风光/历史人文/美食购物等）、体力等级
2. 景点知识库：包含经纬度坐标、建议游览时长、门票政策、开放时间（精确到星期几）
3. 行程模板表：预置经典路线（如"三日经典游"、"亲子慢旅行"）
4. 实时行程表：使用JSON类型存储每日的景点序列和交通方式
5. 用户反馈表：记录对推荐结果的评分和修改行为

CREATE TABLE `scenic_spot` ( `id` bigint NOT NULL AUTO_INCREMENT, `name` varchar(100) COLLATE utf8mb4_bin NOT NULL, `geo_point` point NOT NULL SRID 4326, `recommended_duration` int COMMENT '分钟数', `tags` json DEFAULT NULL, PRIMARY KEY (`id`), SPATIAL KEY `idx_geo` (`geo_point`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin;

3. 核心算法实现

3.1 贪心算法行程生成

采用改进的贪心算法进行每日行程编排，关键步骤如下：

1. 根据用户选择的兴趣标签过滤景点池
2. 按评分降序排列候选景点
3. 从第一个景点开始，依次尝试加入行程单：
   • 检查与已选景点的通勤时间（调用高德API）
   • 验证开放时间是否冲突
   • 累计当日总时长不超过8小时（含交通）
4. 当无法继续添加时，生成当日行程并开始下一天

public List<ScenicSpot> generateDayPlan(List<ScenicSpot> candidates, Point startPoint) { List<ScenicSpot> dayPlan = new ArrayList<>(); LocalTime currentTime = LocalTime.of(9, 0); // 假设每天9点出发 Point lastPoint = startPoint; for (ScenicSpot spot : candidates) { int commuteMinutes = mapService.getCommuteTime(lastPoint, spot.getGeoPoint()); LocalTime arriveTime = currentTime.plusMinutes(commuteMinutes); if (arriveTime.isBefore(spot.getClosingTime()) && dayPlan.stream().mapToInt(ScenicSpot::getDuration).sum() < 8*60) { dayPlan.add(spot); currentTime = arriveTime.plusMinutes(spot.getDuration()); lastPoint = spot.getGeoPoint(); } } return dayPlan; }

3.2 个性化权重调整

通过用户行为数据动态优化推荐策略：

• 点击"不喜欢"的景点，降低同类标签权重
• 手动调整过顺序的行程，提高时间弹性系数
• 频繁查看但未选择的景点，适当提升优先级

4. 关键功能实现细节

4.1 实时交通时间计算

集成高德地图API时需要注意：

1. 申请"路径规划"服务权限而非基础地图服务
2. 缓存常用路线组合（如机场到市中心）
3. 设置合理的请求间隔（建议≥500ms）避免QPS超限
4. 备用方案：直线距离×1.5作为估算值

4.2 行程冲突检测

实现时间冲突检测算法：

1. 将每个景点的开放时间转换为时间线段
2. 使用区间树数据结构存储
3. 新增景点时快速查询重叠时段

# Python示例代码 from intervaltree import IntervalTree tree = IntervalTree() tree.addi(9*60, 17*60, "故宫") # 9:00-17:00 tree.addi(13*60, 18*60, "景山") # 查询14:00-15:00是否已有安排 conflicts = tree.search(14*60, 15*60)

5. 毕业设计特别注意事项

5.1 论文写作要点

LW文档应重点突出：

1. 算法对比实验：展示贪心算法与遗传算法在求解质量、响应时间的差异
2. 系统性能指标：并发用户数、平均响应时间、推荐准确率
3. 创新点说明：如引入实时交通数据动态调整方案

5.2 答辩演示技巧

1. 准备对比案例：展示同一用户选择不同标签生成的差异化行程
2. 演示异常处理：输入不合理的预算/时间组合，展示系统的约束检查
3. 强调实用价值：与传统旅行社固定路线的区别

6. 常见问题解决方案

6.1 景点数据获取

推荐数据源及处理方法：

• 政府开放数据平台（如文旅部官网）
• 高德POI接口（需企业资质）
• 大众点评爬虫（注意robots.txt限制）
• 手工录入时使用OpenStreetMap验证坐标

6.2 性能优化经验

1. 空间索引加速：对景点表添加R树索引

   ALTER TABLE scenic_spot ADD SPATIAL INDEX(geo_point);

2. 行程预生成：对热门城市组合提前跑批处理
3. 前端防抖：用户连续调整参数时延迟触发请求

6.3 部署踩坑记录

1. 地图API域名限制：需备案域名才能调用
2. 时区问题：确保服务器与数据库时区统一
3. 内存泄漏：定期重启SpringBoot应用

我在实际开发中发现，当用户同时选择"徒步"兴趣标签和"老年人"年龄段时，系统需要自动降低每日景点数量并优先推荐无障碍设施完善的场所。这种细节处理往往能大幅提升用户体验，建议在论文中作为典型场景重点说明。