从可行性到期望性：用于个性化设备端行程生成的计划-学习-适应（PLA）框架

# 从可行性到可取性：面向个性化设备端行程生成的规划-学习-适应（PLA）框架
来源：https://arxiv.org/html/2607.15552
Himel Dev¹, Tanmoy Sen², Madhusudan Basak³, Bashima Islam³¹529 Tech LLC,²弗吉尼亚大学,³马萨诸塞大学阿默斯特分校
[email protected], [email protected], [email protected], [email protected]
美国

(2026)

###### 摘要。

生成个性化旅行行程是一项复杂的规划任务，需要在严格的组合可行性与松散的潜在可取性之间进行权衡。经典优化方法能强制执行约束，但未能捕捉主观旅行者偏好。基于学习的方法可以建模偏好，但无法保证可行性。移动端部署为这两类方法都带来了额外的资源约束。为解决此问题，我们提出“规划-学习-适应”（PLA）这一三阶段框架，用于在设备端生成个性化行程。在“规划”阶段，我们构建一个由轻量级规划器组成的异构集成，生成结构多样的可行候选方案。通过成对行程比较，“学习”阶段拟合一个紧凑的 Bradley-Terry 奖励模型，该模型能捕捉步调、地理连贯性和每日平衡等涌现的行程属性，而这些是单个 POI 信号所遗漏的。最后，“适应”阶段在考虑设备计算预算的前提下，进行保持可行性的局部细化；每个中间状态在构造上都是可行的。在覆盖美国 100 多个城市的 2,519 次成对人类比较中，奖励引导的集成实现了 67.8% 的胜率（比最佳单一规划器高 11.2 个百分点），同时可行性达到 100%，而三个前沿 LLM（GPT-5、Claude Opus 4.5、Gemini 3 Pro）在相同约束下可行性为 0%。奖励模型能泛化到未见过的城市，留一城市交叉验证的平均准确率为 67.6%。在 FlyEnJoy 的生产部署中，PLA 使行程完成率提高了 91%，设备端平均延迟为 109.9 毫秒。

旅行规划，偏好学习，组合优化，设备端系统

††copyright:acmlicensed††journalyear:2026††doi:XXXXXXX.XXXXXXX††conference:确保从权利确认邮件中填入正确的会议标题；2026年2月1日；美国††isbn:978-1-4503-XXXX-X/2018/06

## 1. 引言

多日行程生成是一个典型的人类对齐组合规划问题。系统必须在严格的时空约束（营业时间、可用时间窗口、每日时间预算）下，跨多天选择、排序并安排一系列兴趣点（POI），同时还要满足步调、多样性和与所述兴趣一致性等软性的可取性标准。

参见标题
图 1. PLA 框架概览。“规划”阶段生成一组多样化的可行种子行程；“学习”阶段从成对偏好中拟合一个与人类对齐的奖励模型；“适应”阶段随后在资源预算下对选定的行程进行设备端细化，并在整个过程中保持可行性。
这种双重性在可行性和可取性之间造成了紧张关系。经典规划器 (Lim et al., 2015 (https://arxiv.org/html/2607.15552#bib.bib26); Zhang et al., 2016 (https://arxiv.org/html/2607.15552#bib.bib33)) 能够可靠地强制执行约束，但依赖手工构建的目标函数，而这些函数是人类满意度的弱代理。在我们早期的部署中，具有相似启发式分数的行程往往被用户判断为截然不同，这反映了没有单一复合分数能捕捉的偏好。基于学习的方法 (Chen et al., 2020 (https://arxiv.org/html/2607.15552#bib.bib30), 2022 (https://arxiv.org/html/2607.15552#bib.bib35)) 可以捕捉偏好，但如果没有显式的约束处理，经常会产生无效的时间表。基于 LLM 的方法 (Li et al., 2024 (https://arxiv.org/html/2607.15552#bib.bib62); Volchek and Ivanov, 2024 (https://arxiv.org/html/2607.15552#bib.bib32)) 面临同样的局限性。在我们的基准测试中（第 3.6 节 (https://arxiv.org/html/2607.15552#S3.SS6)），来自 GPT-5、Claude Opus 4.5 和 Gemini 3 Pro 的 294 个行程中，没有一个同时满足所有硬约束。

第三个要求是可行性。解决方案必须能够在最终用户设备上大规模部署。我们的产品 FlyEnJoy¹¹https://apps.apple.com/app/6745104853 是一款以离线优先为特点的 iOS 旅行应用，其用户经常需要在低连接或无连接环境（机场、飞行途中、国际漫游）下获取行程，并且对延迟有严格要求。依赖云的 LLM 和基于学习的方法成本高昂，无法大规模应用，也不兼容离线、延迟敏感、注重隐私的使用场景。

这三个要求——可行性、可取性和可行性——不太可能通过任何单一范式来满足。我们提出“规划-学习-适应”（PLA），这是一个面向个性化设备端行程生成的三阶段框架（图 1 (https://arxiv.org/html/2607.15552#S1.F1)）。在第 2.1 节 (https://arxiv.org/html/2607.15552#S2.SS1) 中，“规划”阶段通过异构规划器集成生成结构多样的可行候选方案。第 2.2 节 (https://arxiv.org/html/2607.15552#S2.SS2) 随后描述了“学习”阶段如何从成对行程比较中拟合一个紧凑的奖励模型。第 2.3 节 (https://arxiv.org/html/2607.15552#S2.SS3) 介绍了“适应”阶段，它在考虑设备计算预算的前提下进行奖励引导的局部细化，同时保持可行性。

我们的主要贡献如下。

*   **异构规划器集成**：没有任何单一规划算法能在所有旅行场景中占据主导地位；我们通过实证而非假设确立了这一点。对异构规划器集成进行奖励引导的选择，实现了 67.8% 的胜率，比最佳单一规划器高 11.2 个百分点（第 2.1 节 (https://arxiv.org/html/2607.15552#S2.SS1)）。
*   **行程级偏好建模**：行程质量涉及涌现属性（步调、地理连贯性、每日平衡），而这些是每个 POI 的分数无法捕捉的。我们收集了覆盖美国 100 多个城市的 2,519 次完整多日行程的成对比较，并训练了一个紧凑的 Bradley-Terry 奖励模型，实现了 67.6% 的平均留一城市交叉验证准确率（第 2.2 节 (https://arxiv.org/html/2607.15552#S2.SS2)）。
*   **设备端行程细化**：“适应”阶段通过奖励引导的局部编辑提高可取性，同时保证每个中间状态在构造上都是可行的（而不仅仅是最终输出）。设备感知预算将设备端延迟平均保持在 109.9 毫秒，从而实现了完全离线、交互速度的执行（第 2.3 节 (https://arxiv.org/html/2607.15552#S2.SS3)）。

## 2. 系统概述

问题设定。给定一个旅行上下文（包括目的地、时长、可用时间、预算、兴趣等）和一组候选 POI（包含位置、营业时间和参观时长），目标是生成一个既可行又可取的多日行程。可行性施加了营业时间、可用时间、旅行时间和时间预算的约束（第 2.1 节 (https://arxiv.org/html/2607.15552#S2.SS1)）。可取性反映了行程层面潜在的用户满意度，且无法直接观察。我们通过完整行程的成对人类偏好（第 2.2 节 (https://arxiv.org/html/2607.15552#S2.SS2)）学习一个紧凑的替代奖励模型，并在设备感知的计算预算下进行优化（第 2.3 节 (https://arxiv.org/html/2607.15552#S2.SS3)）。

### 2.1. 规划：多样化可行行程生成

我们实现了五个异构规划器，用于在共享的可行性层下进行多日行程生成。每个规划器输出一个可行的行程（有序的、带时间戳的 POI 参观序列），该行程遵守所有硬约束并优化一个共享的复合目标。尽管目标是共享的，但规划器不同的搜索范式会产生结构多样的候选方案，这些方案在 POI 选择、排序和时间分配上各不相同。规划器套件的设计旨在为下游的选择和细化提供一个多样化的候选池，因为在所有旅行场景中识别一个单一的最佳规划器是不可行的。

#### 2.1.1. POI 数据和用户输入

我们的系统运行在覆盖美国 100 多个城市的城市特定 POI 数据集上。每个 POI p 具有营业时间、参观时长、消费等级、位置（带有预计算的旅行时间区域）、类别以及从用户评分中得出的流行度分数。旅行上下文 u 指定了目的地、时长、感兴趣类别、预算等级、可用时间窗口以及步调（放松、均衡或紧凑），步调用于设置每日时间预算。这些输入共同定义了可行的搜索空间，同时保持足够精简以支持快速的设备端规划。

#### 2.1.2. 可行性约束

所有规划器均强制执行以下硬约束，这些约束定义了一个有效、可执行的行程：

*   **参观时间**：每次参观必须在开门后开始并在关门内结束，即 \(start(p) \ge open(p)\) 且 \(start(p) + dur(p) \le close(p)\)。
*   **可用时间窗口**：每次参观必须完全位于旅行者当天的可用时间内。
*   **旅行时间一致性**：连续两次参观之间必须有足够的时间进行换乘。如果到达时间早于开门时间，旅行者需要等待。
*   **时间预算**：每天的总活动时间（参观时间加上换乘时间）不得超过所选步调所隐含的预算。
*   **费用预算**：费用 \(cost(p)\) 超出用户预算等级的 POI 将被排除考虑。
*   **无重复**：每个 POI 在整个行程中最多访问一次。

所有规划器共享一个可行性层，该层计算最早可行到达时间（如果到达时间早于开门时间则等待），并统一强制执行逐日及全程级别的约束，因此跨规划器的差异反映的是搜索策略的不同，而非约束处理的不一致。

#### 2.1.3. 目标组成部分

除可行性外，规划器还使用一个手工制作、可解释的目标函数来优化行程质量。我们根据当前时间游标 t 和之前安排的 POI \(p_\ell\)，在候选 POI p 的最早可行开始时间 \(t_s\) 对其进行评分：

*   **换乘效率**：我们惩罚较长的换乘时间，以鼓励地理上连贯的行程：\(travel(p_\ell, p) = T(zone(p_\ell), zone(p))\)。
*   **等待时间**：在 POI 开门前到达会产生空闲时间，我们对此进行惩罚：\(wait(p, t) = \max\{0, open(p) - (t + travel(p_\ell, p))\}\)。
*   **安排紧迫性**：剩余时间窗口狭窄的 POI 应优先处理，以避免完全错过。我们根据参观结束与关门之间的差距来定义紧迫性：\(urgency(p, t_s) = \frac{1}{\epsilon + \max\{0, close(p) - (t_s + dur(p))\}}\)，其中 \(\epsilon\) 是用于数值稳定性的小常数。勉强能满足条件的 POI 获得高紧迫性分数。
*   **类别多样性**：为避免行程单调（例如，连续五个博物馆），我们奖励引入在日级和全程级别上代表性不足的类别的参观：\(div(p) = \lambda_d \sum_{c \in cat(p)} \frac{\gamma_c}{1 + count_d(c)} + \lambda_t \sum_{c \in cat(p)} \frac{\gamma_c}{1 + count_t(c)}\)，其中 \(count_d(c)\) 和 \(count_t(c)\) 分别是当天和整个行程中对类别 c 的参观次数，\(\gamma_c\) 是类别权重（用户偏好类别的权重更高），\(\lambda_d, \lambda_t\) 控制日级别与全程级别多样性之间的权衡。
*   **POI 流行度**：由 \(pop(p)\) 衡量的更高质量的 POI 能为行程贡献更多价值。

#### 2.1.4. 共享复合分数

目标组成部分被组合成一个加权的复合分数，供构造性规划器（贪婪、束搜索、A\*）用于步骤级决策：

\[
\begin{aligned}
score(p, t_s) = & w_{\text{pop}} \cdot pop(p) - w_{\text{travel}} \cdot travel(p_\ell, p) - w_{\text{wait}} \cdot wait(p, t) \\
& + w_{\text{urg}} \cdot urgency(p, t_s) + w_{\text{div}} \cdot div(p).
\end{aligned}
\]
所有权重 (\(w_{\text{pop}}, w_{\text{travel}}, w_{\text{wait}}, w_{\text{urg}}, w_{\text{div}}\)) 都是可配置的超参数，在各规划器间共享以实现公平比较。全局优化规划器和局部搜索使用类似的目标函数，但根据其表述形式进行了调整。共享的目标结构确保了跨规划器的性能差异源于搜索策略，而非不一致的质量定义。

#### 2.1.5. 规划算法

我们实现了五个规划算法，涵盖四种范式：构造性启发式（贪婪）、动态规划（DP）、树搜索（束搜索、A\*）和局部搜索（SA）。表 1 (https://arxiv.org/html/2607.15552#S2.T1) 总结了每个规划算法的关键特征。所有算法共享可行性层和复合目标（公式 1），仅在搜索策略上有所不同。

*   **贪婪**：在其最早有效开始时间迭代安排得分最高的可行 POI。
*   **动态规划（DP）**：在时间扩展的状态空间上进行资源受限优化，最大化 POI 流行度和覆盖率。
*   **束搜索**：在部分行程的有界前沿上进行任意时间树搜索，按复合分数剪枝。
*   **A\* 搜索**：使用剩余奖励的可容许上界进行最佳优先搜索。
*   **模拟退火（SA）**: 在可行种子上进行结构编辑的局部搜索，并采用概率接受机制。

表 1. 规划算法与权衡的比较。我们还原型设计了一个约束规划（CP-SAT）规划器，但由于 Google OR-Tools 缺少原生 Swift 实现，将其排除在部署之外。

### 2.2. 学习：人类偏好建模

用户对行程的满意度是潜在且依赖于上下文的。因此，我们针对完整行程进行了一项成对偏好研究，并基于可解释的行程级特征训练了一个紧凑的奖励模型。

#### 2.2.1. 偏好数据收集

我们通过一个网络平台收集偏好，该平台并排展示来自随机选择规划器的成对行程。规划器身份被隐藏，左右位置随机化以防止顺序偏差。指导原则强调整体的行程级判断；完成时间远低于中位数的提交被过滤掉。这产生了覆盖美国 100 多个城市的 2,519 次成对比较。我们使用基于特征的 Bradley-Terry 公式以提高数据效率：每次比较同时监督约 20 个可解释特征（第 2.2.2 节）。

#### 2.2.2. 奖励模型架构

我们学习一个评分函数 \(R(x)\)，用于根据预测的人类偏好对行程进行排序。

**特征工程**。每个行程 x 被映射到一个固定维度的特征向量 \(\phi(x) \in \mathbb{R}^d\)，