当前,POI(Point of Interest)推荐技术已经在基于 LBS(Location-Based Service)的移动导航系统中广泛应用。它实时感知用户当前的位置信息,利用用户即时给出的偏好集或者历史偏好信息,为用户推荐路网上的兴趣点以及到达兴趣点的最佳路径。在这个方面,以往的研究工作主要集中在两点:一是POI与用户兴趣偏好的相似度计算;二是POI位置与用户位置之间的最佳路径选择。然而,在实际生活场景中,单点的POI推荐往往不能满足用户的需求,用户需要的是一系列POI活动以及和连接这些活动的路径的组合,这就构成了行程规划问题。实际中的行程往往带有强烈的总时间约束,带有时间约束的行程规划问题本质上等价于广义旅行商问题,属于NP-hard问题,这为求解提出了巨大的挑战。而且,在活动上往往也有存在两方面的约束:活动的时空约束(比如,时间约束或是地点约束),活动之间顺序约束(比如,在商场购物后进行晚餐活动),这又求解的难度进一步的提高。本文提出并定义了带有总时间约束的行程规划问题,创新地把POI点之间的静态路径抽象为路程活动,从而建立了全局一致的用户活动模型。而且针对不同的约束情况,分别提出了 1)基于遗传算法的行程推荐算法,2)针对约束性活动(即带时间约束的活动)的基于遗传算法的行程推荐算法,3)反序搜索算法。并且针对充分利用时间这一点上提出了活动插入策略。而且给出了行程推荐度函数,可以用与对候选行程进行排序,使其更加符合用户的期望。本文通过实际路网数据,对所提算法的效率、推荐结果(使用行程的推荐度函数来评估)的质量和候选行程集合的排序合理性进行了实验测试。实验结果表明,使用本文的推荐算法能够得到符合用户期望的合理行程。