旅行规划这事儿，看着简单，其实门道不少。它本质上是一系列决策的集合：去哪儿、什么时候去、待多久、怎么转场，还得在有限的时间和预算里，尽可能让自己玩得开心。传统做法是靠一套形式化语言把问题定义好，再从网上扒拉信息，最后用求解器算出个答案。最近大语言模型（LLM）火起来之后，有人尝试直接让它用自然语言输出计划，确实方便，懂的东西也多，能推荐兴趣点、画个路线什么的。但问题随之而来——当前最先进的模型生成的计划，经常缺胳膊少腿：要么约束条件没满足，要么方案质量没保障。
这篇论文提出的TRIP-PAL，思路倒是很清晰：让LLM和自动规划器搭伙干活。LLM负责从用户需求里提取旅行信息，转成规划器能读的数据结构；规划器则上场求解，保证生成一个满足所有约束、同时让用户效用最大化的计划。实验跑了好几组场景，结论也很明确——TRIP-PAL在生成靠谱旅行计划这件事上，比单独用LLM强出一大截。
1 研究问题
核心问题就一个：怎么能把LLM的知识广度和规划器的逻辑严谨性结合起来，拿出一个有保障的旅行方案。
举个具体的例子。假设一位游客想去巴黎玩一天，卢浮宫、埃菲尔铁塔这些地标都想打卡。这时候去问ChatGPT，它确实能凭旅游知识库推荐几个热门景点，甚至帮你排个大致的顺序。但一落到细节就麻烦了：从卢浮宫到铁塔到底要多久？奥赛博物馆下午几点关门？每个地方逛多长时间才合理？LLM不太擅长处理这类硬约束，生成的行程往往理想化，实操起来满是坑。
反观传统的旅行规划系统，虽然能严格满足约束条件、生成可执行的方案，但背后需要大量人力把旅行知识抽象成形式化语言，灵活性自然大打折扣。理想的解法，应该是让LLM和规划器互补——一个负责理解人话、调动知识，一个负责逻辑推演、保证可行性。这样一来，人工建模的成本降下来了，计划的可靠性和最优性也保住了。
具体来说，挑战集中在几个方面：
- 传统系统依赖形式化语言（比如PDDL），人工抽取和建模成本高
- LLM知识储备足，能灵活分析需求、给出高层次推荐，但在硬约束和全局优化上容易掉链子
- 关键在于，既要保持知识表达的灵活性，又要确保解的可靠性，同时还得控制好LLM的调用开销
TRIP-PAL给出的解法很巧妙：让LLM和规划器各司其职。先用对话式LLM从用户输入里提取原始信息——感兴趣的景点、偏好程度、交通方式等等。接着，把这些信息翻译成规划器能读的数据结构，比如把景点偏好映射成数值化的效用函数。然后，规划器上场，以这些数据为输入，考虑游览时间、开放时间、交通时间等实际约束，搜索出一个能最大化用户效用的最优计划。
这个架构，就像请了一位懂行的导游和一位细心的行程管家。导游先根据你的口头描述迅速规划大方向，管家再接手，把每个细节敲实，最终交付一份可执行的精准指南。TRIP-PAL的创新之处就在这里——它让LLM充当“导游”，规划器充当“管家”，两个模块各管一摊，但接口设计得干净利落，既减少了不必要的交互开销，又最大程度保留了各自的性能和特性，实现了1+1>2的效果。
2 研究方法
TRIP-PAL的整体流程可以分为三步：用LLM提取旅行信息、构建自动规划问题、求解规划问题生成计划。下面一步步拆开看。
2.1 利用LLM提取旅行信息
第一步，让LLM（论文里用的是GPT-4）跟用户聊，把需求摸清楚。比如用户说“我想去巴黎玩5天，对艺术感兴趣，想逛逛知名博物馆和美术馆”，TRIP-PAL会通过一系列提示，引导GPT-4从中提取出几个关键信息：目的地城市、兴趣点类型（博物馆、美术馆等）、旅行总时长（5天）、期望游览的景点数量（比如10个）。
接下来，再让GPT-4结合它自己的旅游知识，推荐一组符合用户偏好的景点，附上每个景点的受欢迎程度打分（1-10分）作为效用值，以及推荐的游玩时长。这个环节就像旅游达人了解你的喜好之后，当场甩给你一份清单。
最后，从外部数据源（比如谷歌地图API）拉取景点之间的通勤时间。到这一步，构建规划问题需要的所有信息就齐了：候选景点集合、每个景点的效用值和推荐游玩时长、景点间的通勤时间。
2.2 构建自动规划问题
有了这些信息，接下来就是把它转化成一个形式化的自动规划问题。这个规划问题包含两部分：规划领域（定义动作的前置条件和效果）和规划实例（初始状态、目标状态等），通常用PDDL语言描述。
在旅行规划这个场景里，规划领域包含两类核心动作：
- Visit(?loc, ?t0, ?visit-time, ?tf)：在某个位置参观一段时间，从时间t0到tf
- Move(?from, ?to, ?t0, ?move-time, ?tf)：从一个位置移动到另一个位置，耗时move-time
这些动作的前置条件确保游客在对的时间出现在对的地点，效果则更新当前时间和位置信息。
规划实例的初始状态是旅行开始的时间和地点，加上景点信息（效用值、游览时间、通勤时间等）。目标状态则要求达到旅行结束的时间，比如下午6点。
这里需要特别处理一种情况——oversubscription，也就是“过度需求”。直觉上，如果让GPT推荐50个甚至更多的巴黎景点，一天之内肯定逛不完。所以访问所有景点的目标不一定要全部满足。论文参考了Keyder等人提出的编译方法，引入人工动作来处理未访问景点的惩罚，同时优化目标函数。
最终，TRIP-PAL会得到一个完整的、用PDDL表示的过度需求自动规划问题：在时间约束下，选择一组景点，使得访问景点的总效用最大。
2.3 求解规划问题生成旅行计划
问题建好了，剩下就是求解。TRIP-PAL采用Unified Planning框架里的Fast Downward规划器，配合LMCUT启发式函数。这套组合能高效找到一个满足时间约束的最优可行计划。
输出的旅行计划会清清楚楚地告诉用户：给定时间限制内（比如5天），每天几点到几点、去哪些景点、每个景点待多久、景点之间怎么通勤。所有这一切，都在满足时间约束的前提下，实现了访问景点效用的最大化。
还是拿巴黎5日游来举例。TRIP-PAL可能给出这样的计划：
第一天（总时长8小时）：
- 8:00-10:00 参观卢浮宫（2小时）
- 10:00-10:30 步行到奥赛博物馆（0.5小时）
- 10:30-12:00 参观奥赛博物馆（1.5小时）
- 12:00-14:00 午餐休息（2小时）
- 14:00-14:30 乘车到凯旋门（0.5小时）
- 14:30-15:30 参观凯旋门（1小时）
- 15:30-16:00 乘车到埃菲尔铁塔（0.5小时）
- 16:00-18:00 参观埃菲尔铁塔（2小时）
第二天（总时长7.5小时）：
- ……
之后几天以此类推，直到满足5天的旅行总时长。这个计划保证所有时间约束都得到满足，并且在可选景点中根据效用最大化原则做了取舍。
对比直接让LLM生成计划，TRIP-PAL的做法显然更靠谱——它用LLM来理解用户、推荐景点，再把这些信息交给规划器去求解，最终出来的计划可行性高、最优性好、可解释性强，真正帮用户做出明智的决策。
3 实验
3.1 实验场景介绍
为了验证效果，论文设计了一组对比实验，核心是比较GPT-4和TRIP-PAL在不同规模的一日游规划任务上生成方案的质量。
3.2 实验设置
- 数据集：从GPT-4生成的热门和冷门旅游城市中随机抽取20个，每个城市随机生成5组兴趣点集合，共100个规划任务
- 对照方法：GPT-4
- 实现细节：TRIP-PAL的规划器采用Fast Downward，配置为SEQ-OPT-LMCUT，运行在4GB RAM的EC2 T3实例上；单日旅游时长为8小时，时间离散化为15分钟的时隙
- 评价指标：
- 规划可行性：检查生成的计划是否满足动作可执行性和时间约束
- 规划效用：访问兴趣点的效用总和
- 运行时间：生成一个计划所需的秒数
3.3 实验结果
3.3.1 实验一：标准的一日游规划
这个实验的目的是对比GPT-4和TRIP-PAL在100个标准一日游规划任务（8小时旅游、10个候选兴趣点）上生成方案的质量。
结果非常直观：TRIP-PAL在所有任务上生成的规划效用都高于GPT-4。GPT-4只有14%的规划满足所有约束，主要问题出在访问时长、旅行时长这类硬约束上。即便去掉约束检查，TRIP-PAL在79%的任务上仍然优于GPT-4。
从访问兴趣点的数量来看，TRIP-PAL平均访问5.5个，GPT-4只有4.2个。GPT-4倾向于选择效用最高的3-5个点，虽然单点效用值高，但TRIP-PAL能在满足约束的前提下多覆盖一些次高效用的点，整体旅行效用反而更大。
3.3.2 实验二：扩展性分析
这个实验考察的是，当问题规模变化时，两种方法的表现如何波动。具体设置：固定旅游时长为8小时，兴趣点从8个增加到18个；或者固定10个兴趣点，旅游时长从6小时增加到10小时。对比指标包括GPT-4规划的有效性、次优率，以及TRIP-PAL相比GPT-4的额外耗时。
结果有意思。随着兴趣点数量增加，GPT-4生成有效规划的比例急剧下降，次优率也逐渐升高，最终稳定在1.6倍左右。这说明GPT-4在处理过度订阅问题时力不从心——景点多了，它很难在旅行约束和整体效用最大化之间找到平衡。
相比之下，TRIP-PAL在兴趣点不超过10个时，运行时间跟GPT-4基本持平。一旦超过10个，额外耗时逐渐上升，最多需要800秒。这主要是因为解决过度订阅问题的复杂度在增加。
再看旅游时长的影响。随着时长增加，GPT-4规划的有效性也在下降，但次优率变化不明显。TRIP-PAL的运行时间则基本稳定。综合来看，兴趣点数量对两种方法的影响要远大于旅游时长。
4 总结后记
这篇论文的核心贡献，就是提出了一种让LLM和自动规划器协同工作的混合方法TRIP-PAL，专门解决旅行规划中知识灵活性与方案可靠性之间的矛盾。LLM负责从用户需求中提取信息并转化为规划器能读的格式，规划器则负责在满足约束的前提下，输出一个最大化用户效用的最优计划。实验给出的答案很明确：相比单独用GPT-4，TRIP-PAL在计划的可行性和用户满意度上都明显更胜一筹。
值得深入思考的几个方向：
- TRIP-PAL这套“LLM + 规划器”的组合拳，显然不只适用于旅行规划。会议日程安排、供应链优化这类需要满足复杂约束的领域，是不是也能照方抓药？
- 目前在信息提取环节，主要靠LLM自身的知识。如果引入知识图谱等外部结构化知识源，会不会让LLM的理解和表达能力再上一个台阶？
- 用户效用函数的设计，目前还比较通用。怎么做出更个性化的效用函数，让生成的计划真正贴合每个用户独特的偏好和需求，是个值得深挖的方向。
论文中几个可以借鉴的方法点：
- 用LLM做信息抽取和转化，再结合领域特定的优化工具来求解——这个思路很有通用性，可以扩展到很多实际场景。
- 把过约束问题转化为软目标规划问题的技巧，在资源受限的任务中同样适用，能有效提高求解的灵活性。
- 通过离散化和编码技巧来简化问题表示，让规划器能够高效处理复杂的实际约束，这套方法论同样值得参考。