Tour Pass 里的行程规划算法

Tour Pass 这个项目里，我最想讲清楚的是行程规划算法。

旅行规划看起来像“给我安排两天长沙怎么玩”，但拆开以后其实是很多约束叠在一起：用户兴趣、必去点、开放时间、餐饮时间、通勤成本、游玩时长、候选多样性，还有路线是否方便解释。

如果只给一个黑盒总分，项目会很难讲。我的做法是把算法链路拆成几个可以单独解释的模块：图搜索、日内 Beam Search、站点评分、时间窗复核、候选策略和 Pareto 排序。

从 POI 图开始

Tour Pass 先把城市建模成 POI 图。

POI 节点包含：

• id、name、type。
• 经纬度和所属区域。
• 开放时间和建议游玩时长。
• 标签、热度、价格等级和描述。

边包含两个 POI 之间的距离，以及步行、公交、打车耗时。当前图按无向图处理，默认通勤权重优先选公交时间。

这个建模让后面的算法有了统一基础。无论是查“五一广场酒店到岳麓书院怎么走”，还是评估“上午先去湖南博物院会不会太绕”，底层都可以问 PoiGraph。

最新版本里，POI 图不再只能承载手写样例。高德采集脚本可以在本地生成长沙真实 POI 数据集，通勤边生成脚本会把每条边标上 amap 或 geo_estimated 来源。这个设计对算法表达很重要：它让“扩大数据规模”和“真实路网可信度”分开讨论。POI 可以是真实地点，但只要还有估算边，算法报告就必须披露比例，不能把它说成实时交通规划。

Dijkstra 和 A*

项目里保留了两种点到点路径查询。

shortestRoute(from, to) 使用 Dijkstra。只要边权非负，它就能得到最短通勤时间。

aStarRoute(from, to) 使用 A*。它在累计代价上叠加一个地理启发函数：

h(n) = rough_distance_km / 28 * 60

这里假设城市通勤速度约为 28 km/h，用经纬度粗略估算直线距离。当前样例数据规模不大，所以 Dijkstra 和 A* 都很快。保留 A* 的意义更多是为了展示：当 POI 图变大时，可以通过启发式搜索减少实际扩展节点。

复杂度上，Dijkstra 是：

O((V + E) log V)

A* 最坏情况同级，但启发函数有效时通常会少扩展一些节点。

为什么不用纯贪心排一天

一个简单做法是：每个时间段都选当前分数最高的 POI。

这个方法很直觉，但在旅行规划里很容易翻车。比如上午选了一个高分但很远的点，下午就可能赶不上博物馆闭馆；或者中午为了分数选了远处餐厅，结果晚上的路线变得很绕。

所以 Tour Pass 用的是时间槽 Beam Search。

一天会被拆成：

上午 -> 午餐 -> 下午 -> 晚餐 -> 晚上

每个时间槽会先按 POI 类型筛选候选。比如午餐和晚餐更偏向餐厅，晚上可以放夜景和夜生活点。然后算法展开当前 Beam 中的状态，尝试加入新的 POI，再按状态评分排序，保留 Top-K。

一个 Beam 状态大致包含：

• 已选站点序列。
• 已使用 POI 集合。
• 当前所在 POI。
• 当前时间。
• 累计通勤时间。
• 累计游玩时间。
• 累计兴趣得分。

状态评分类似：

state_score = interest_score - total_travel_minutes * travel_penalty + stop_count * 8

这不是为了证明数学上最优，而是为了在性能、可解释性和路线质量之间取一个平衡。当前参数下，时间槽数量固定，Beam 宽度和分支数也有限，所以本地样例数据可以稳定快速返回。后来服务端接入热点缓存后，重复的候选请求还能直接从进程内缓存返回；这没有改变算法语义，只是把“规划计算”和“服务响应”分开优化。

真实规模下，项目还做了两层很务实的优化。第一，启动时可以为几百个 POI 预计算 all-pairs 最短通勤缓存，让规划热路径直接查表；默认阈值是 500 POI。第二，Beam Search 进入完整评分前先按类型、时间窗、策略标签和必去点粗筛候选池，避免每个时间槽都把所有 POI 展开一遍。它们都不是改变算法目标，而是减少重复计算和无意义分支。

评分拆解让推荐不黑盒

每个站点的选择都会输出 score_breakdown。

它包含几个主要部分：

• 热度分：热门 POI 更容易被选中。
• 兴趣匹配：命中用户兴趣标签时加分。
• 必去加权：命中 must_visit 时大幅加分。
• 通勤惩罚：从上一站过来越远，扣分越多。
• 价格惩罚：价格等级越高，适当扣分。
• 时间窗惩罚：早到等待或超出开放时间都会影响评分。
• 策略加权：不同候选策略会对不同标签加权。

这样页面上就可以解释“为什么选湖南博物院”“为什么这个餐厅排在这里”。对作品展示来说，这比只返回一个总分更有说服力。

时间窗要最后再复核一次

规划阶段会尽量过滤不合理安排，但我仍然做了最终严格时间窗复核。

复核会检查：

• 站点顺序是否可行。
• 到达和离开是否落在开放时间内。
• 午餐是否完整落在 11:30-13:30。
• 晚餐是否完整落在 17:30-19:30。
• 当天是否超过结束时间。

响应里会输出：

• stops[].time_window_status
• stops[].time_window_reason
• days[].time_window_feasible
• days[].time_window_diagnostics

例如某个站点可能会标成 wait，说明到得太早但可以等待；也可能标成 closed，说明预计离开时间已经超过关闭时间。

这块我觉得很必要。旅行规划如果只输出漂亮路线，但不说时间上是否可行，就很容易变成“看起来合理，实际走不了”。

日内通勤优化的取舍

Tour Pass 里有一个 optimizeDayOrder，会对非餐饮站点做局部交换，评估理论上能不能降低通勤时间。

但展示层不会随便打乱时间线。

原因是午餐、晚餐和晚上活动有很强的时间语义。算法可能发现“交换两个点能少走 12 分钟”，但如果交换后破坏了餐饮窗口或开放时间，那这个优化就不应该影响最终路线。

所以项目会输出优化摘要：

• 原时间线通勤时间。
• 局部交换后的理论更优通勤时间。
• 可节省分钟数。

只有交换后仍通过时间窗复核，收益才会被计入。

这也是我想表达的一个工程取舍：路线规划不是只追最短路，产品语义和用户理解成本也要被算法尊重。

候选策略不是换皮

当用户请求多个候选时，Tour Pass 会生成不同策略的方案。

当前主要策略包括：

这些策略会进入评分函数，所以候选差异会真实反映在 POI 选择、路线通勤和解释文本中。

如果不同候选只是标题不同，用户其实很快就能感觉出来。Tour Pass 还会计算相对基线方案的 POI 重合率、区域重合率、独有 POI 和多样性标签，用数据说明“它们到底有多不同”。

Pareto 非支配排序

候选路线很难用单一指标判断。

高分方案可能通勤更长，低通勤方案可能少覆盖一个必去点，雨天室内方案可能更稳但没有夜景。把这些目标强行压成一个总分，会丢掉很多取舍信息。

所以项目对候选方案做了 Pareto 非支配分层。

比较目标包括：

• 总评分越高越好。
• 必去覆盖越多越好。
• 总通勤越少越好。
• 开放时间风险越少越好。
• 未安排数量越少越好。

如果方案 A 在所有目标上不差于方案 B，并且至少一个目标更好，那么 A 支配 B。第一层 Pareto front 表示没有被其他候选完全支配的方案。

响应中的 comparison.pareto_rank、dominated、tradeoff_summary 和 pareto_debug 会把这个判断讲出来。Web 演示台也会显示分层证据。

这让候选对比更像真实的多目标优化，而不是“我随便挑一个最高分”。

BM25 检索服务于解释

除了规划，项目还有 /poi/search。

检索用的是轻量 BM25，加了字段权重：

• name：3.0
• tags：2.4
• area：1.5
• description：1.0

最终分数还会叠加 POI 热度。响应里会返回 matched_terms、score_explanation 和 score_contributions。

它的价值不只是让用户搜 POI。更重要的是，它能展示信息检索的基本思想：字段权重、词频饱和、逆文档频率和排序贡献。对一个旅行规划项目来说，这让“找景点”和“排路线”形成了完整链路。

性能基线

项目里有性能基准脚本，当前报告中本地样例数据的大致结果是：

基准运行时会强制 LLM_DISABLED=1，避免远程模型网络波动污染结果。

这个数据不是为了证明“性能极限很强”，而是为了建立回归基线。现在报告会区分冷缓存、热缓存、并发同步规划和异步任务端到端耗时。以后改 Beam Search、评分函数、缓存策略或候选数量时，至少能知道有没有把响应时间拖坏。

在真实数据实验里，当前记录的 100/200/500 POI 本地结果分别是：100 POI p95 6.5 ms，200 POI p95 6.3 ms，500 POI p95 128.9 ms。500 POI 明显变慢，这反而是有价值的证据：它说明报告不是只挑好看的小样例，也暴露了候选召回、缓存策略和 Beam 参数继续优化的位置。

我还加了一个小规模算法质量报告，用 10 个候选 POI 的精确枚举和贪心 baseline 对照 Beam Search。报告里 Beam Search 的简化目标分数接近精确枚举和贪心，但通勤并不总是最短。这正好说明了它的定位：Beam Search 是工程近似，不是全局最优证明。对作品集来说，我宁可把这个边界写出来，也不想把算法包装得过度漂亮。

我对这个算法版本的判断

Tour Pass 当前不是一个真实地图级别的最优规划器。

它的数据是人工样例，A* 启发函数也只是粗略地理估计，Beam Search 不保证全局最优，评分权重也还不是从用户行为学习来的。

但作为一个算法工程作品，它已经把几个关键问题串起来了：

• 点到点路径怎么查。
• 多时间窗行程怎么生成。
• 为什么不能只贪心。
• 为什么某个站点被选中。
• 候选路线如何真正不同。
• 多目标方案怎么排序。
• 最终路线是否真的可走。

这就是我认为它适合放进作品集的原因。它不是只展示“会写算法题”，而是展示“能把算法变成可解释、可验证、可演示的服务”。