一种新的行程推荐算法研究
佟玉军 吕行 李煜 何俊
【摘 要】论文在研究POI等行程推荐技术的基础上，提出了基于遗传算法和总时间约束的行程推荐算法，并通过实际路网数据，对所提算法的效率、推荐结果合理性等进行了实验测试，实验结果表明，论文所提出的推荐算法能够得到符合用户期望的合理行程推荐。
【Abstract】 Basing on the research of POI recommended schedule， a schedule recommendation algorithm based on genetic algorithm and total time constraints is proposed， through the actual network data， the algorithms efficiency and result rationality are tested. The results show the new recommendation algorithm can obtain the reasonable travel which meet the users expectations.
【关键词】POI行程推荐； 时间约束； 遗传算法
【Keywords】POI schedule recommendation； time-constraint； genetic algorithm
【中图分类号】TP311 【文献标志码】A 【文章编号】1673-1069（2017）07-0142-02
1 POI行程推荐方法
POI推荐只能够根据用户给定的偏好活动，推荐用户相对应的活动地点，但是用户还是需要根据自己的位置和时间的约束来决定去哪个活动地点，即使对位置十分熟悉的用户这也将是一个比较难的问题，并且还有总时间的限制。在目前的研究中，也有涉及多个活动而且包含活动之间限制的研究[1]。这些研究考虑了多个活动，而且还考虑了活动之间的顺序，但是这些研究都忽略了时间因素。
早期的一些研究主要基于GPS轨迹数据，LBSN上的签到数据等进行[2]，都是通过利用传统的协同过滤技术来为用户推荐POI。此外，有些研究工作通过用户生活和居住的区域来计算用户之间的相似度[3]，然后将用户之间的相似度作为传统的协同过滤技术，即认为来自同一区域的用户的兴趣、喜好相似，从而可以通过分析与给定用户来自同一区域的其他用户的行为来预测该用户的行为。这些POI推荐算法都能够很好地满足对于地点的查询，对于地点和地点之间的关系，如地点之间的先后关系，以及地点之间的路径等。但日常生活中，用户不仅需要的是一个点的信息，更多的是想要得到一个完整行程的更多信息[4]。
2 多目标行程推荐算法
本文提出了新的行程推荐算法（Stroke Recommend Algorithm based on Genetic Algorithm and total Time Constraint， SRGATC），对时间约束下的行程规划问题进行求解。本文的行程有效性包括两方面的含义：①用户偏好集合包含于活动类型集合；②行程总时间小于等于约束时间。在此，我们遵循这样的假设：一般情况下，用户希望从事兴趣活动的时间越多越好，也就说路程活动时间和松弛时间越少越好[5]。
2.1 算法总体流程
基于遗传算法的行程推荐算法主要分为三个部分，如图1所示。第一个部分为初始有效行程生成算法，主要根据用户的输入得到有效行程，同时使得行程的总时间尽可能小。第二部分为活动插入，基于第一部分得到的有效行程集，再根据各个行程的松弛时间来判断是否需要进行活动插入策略，从而使得松弛时间更短。第三部分进行候选行程多目标排序，完成推荐。
2.2 有效行程的创建
初始有效行程生成算法分为5个步骤。步骤1：初始化种群，构造染色体并生成一组规模为N的有效路径，作为时间约束条件下行程规划问题的一组初始解集。步骤2：计算初始种群的适应值，并确定当前种群中的最优解。步骤3：產生新一代种群。新一代种群由三个部分组成，第一部分用选择算子作用于上一代种群产生新的个体；第二部分用交叉算子作用于上一代种群产生新的个体；第三部分则是对上一代种群按照一定的概率进行变异操作后加入到这一代种群，这时种群将会达到N至3N 之间。步骤4 ：改进新一代种群。删除新一代种群中的非有效行程，然后按照有效行程的总时间进行排序，选择前N个有效行程代表这一代种群。步骤5：评价，判断是否满足终止条件，满足则退出，否则重复步骤3和步骤4。
3 实验及结果
3.1 实验环境和数据集
本文实验基于辽宁省某市真实的路网数据进行，主要包含地标性建筑物、主要街道及其属性标签。其中每个活动除包含位置信息以外还包含了活动标签、活动时间、活动花费、活动评分等属性。表1描述了实验数据集。
3.2 SRGATC实验结果
因为SRGATC是基于遗传算法进行修改的，所以本文针对初始种群大小、迭代次数、交换概率对行程推荐度的影响进行了实验测试。在图2中，横坐标为初始种群大小，纵坐标为推荐度。随着初始种群大小的增加，行程的推荐度也在增加，但是当初始种群大小增加到1000时，行程的推荐度就趋于稳定了。
4 结语
本文充分利用时间约束， 在满足总时间约束条件下，使其能充分的利用时间行程，进而得到所有满足总时间约束的排序行程，从而最终为用户推荐最佳行程。
【参考文献】
【1】吴清霞.基于用户兴趣和兴趣点流行度的个性化旅游路线推荐[J]. 计算机应用，2016，36（6）：1762-1766.
【2】 曹孟毅. 基于内容相似度的运动路线推荐[J]. 计算机工程与应用， 2016，52（9）：33-38.
【3】 方潇.一种基于协同过滤的旅游行程推荐算法[J]. 地理空间信息，2016，14（7）：53-56.
【4】 彭丹平， 王江晴. 一种求解旅行商问题的新算法[J]. 中南民族大学学报（自然科学版），2006，25（1）：79-80.
【5】 赵曦， 叶和平.广义旅行商问题及其求解[J].东莞理工学院学报，2007（05）：75-80.
【摘 要】论文在研究POI等行程推荐技术的基础上，提出了基于遗传算法和总时间约束的行程推荐算法，并通过实际路网数据，对所提算法的效率、推荐结果合理性等进行了实验测试，实验结果表明，论文所提出的推荐算法能够得到符合用户期望的合理行程推荐。
【Abstract】 Basing on the research of POI recommended schedule， a schedule recommendation algorithm based on genetic algorithm and total time constraints is proposed， through the actual network data， the algorithms efficiency and result rationality are tested. The results show the new recommendation algorithm can obtain the reasonable travel which meet the users expectations.
【关键词】POI行程推荐； 时间约束； 遗传算法
【Keywords】POI schedule recommendation； time-constraint； genetic algorithm
【中图分类号】TP311 【文献标志码】A 【文章编号】1673-1069（2017）07-0142-02
1 POI行程推荐方法
POI推荐只能够根据用户给定的偏好活动，推荐用户相对应的活动地点，但是用户还是需要根据自己的位置和时间的约束来决定去哪个活动地点，即使对位置十分熟悉的用户这也将是一个比较难的问题，并且还有总时间的限制。在目前的研究中，也有涉及多个活动而且包含活动之间限制的研究[1]。这些研究考虑了多个活动，而且还考虑了活动之间的顺序，但是这些研究都忽略了时间因素。
早期的一些研究主要基于GPS轨迹数据，LBSN上的签到数据等进行[2]，都是通过利用传统的协同过滤技术来为用户推荐POI。此外，有些研究工作通过用户生活和居住的区域来计算用户之间的相似度[3]，然后将用户之间的相似度作为传统的协同过滤技术，即认为来自同一区域的用户的兴趣、喜好相似，从而可以通过分析与给定用户来自同一区域的其他用户的行为来预测该用户的行为。这些POI推荐算法都能够很好地满足对于地点的查询，对于地点和地点之间的关系，如地点之间的先后关系，以及地点之间的路径等。但日常生活中，用户不仅需要的是一个点的信息，更多的是想要得到一个完整行程的更多信息[4]。
2 多目标行程推荐算法
本文提出了新的行程推荐算法（Stroke Recommend Algorithm based on Genetic Algorithm and total Time Constraint， SRGATC），对时间约束下的行程规划问题进行求解。本文的行程有效性包括两方面的含义：①用户偏好集合包含于活动类型集合；②行程总时间小于等于约束时间。在此，我们遵循这样的假设：一般情况下，用户希望从事兴趣活动的时间越多越好，也就说路程活动时间和松弛时间越少越好[5]。
2.1 算法总体流程
基于遗传算法的行程推荐算法主要分为三个部分，如图1所示。第一个部分为初始有效行程生成算法，主要根据用户的输入得到有效行程，同时使得行程的总时间尽可能小。第二部分为活动插入，基于第一部分得到的有效行程集，再根据各个行程的松弛时间来判断是否需要进行活动插入策略，从而使得松弛时间更短。第三部分进行候选行程多目标排序，完成推荐。
2.2 有效行程的创建
初始有效行程生成算法分为5个步骤。步骤1：初始化种群，构造染色体并生成一组规模为N的有效路径，作为时间约束条件下行程规划问题的一组初始解集。步骤2：计算初始种群的适应值，并确定当前种群中的最优解。步骤3：產生新一代种群。新一代种群由三个部分组成，第一部分用选择算子作用于上一代种群产生新的个体；第二部分用交叉算子作用于上一代种群产生新的个体；第三部分则是对上一代种群按照一定的概率进行变异操作后加入到这一代种群，这时种群将会达到N至3N 之间。步骤4 ：改进新一代种群。删除新一代种群中的非有效行程，然后按照有效行程的总时间进行排序，选择前N个有效行程代表这一代种群。步骤5：评价，判断是否满足终止条件，满足则退出，否则重复步骤3和步骤4。
3 实验及结果
3.1 实验环境和数据集
本文实验基于辽宁省某市真实的路网数据进行，主要包含地标性建筑物、主要街道及其属性标签。其中每个活动除包含位置信息以外还包含了活动标签、活动时间、活动花费、活动评分等属性。表1描述了实验数据集。
3.2 SRGATC实验结果
因为SRGATC是基于遗传算法进行修改的，所以本文针对初始种群大小、迭代次数、交换概率对行程推荐度的影响进行了实验测试。在图2中，横坐标为初始种群大小，纵坐标为推荐度。随着初始种群大小的增加，行程的推荐度也在增加，但是当初始种群大小增加到1000时，行程的推荐度就趋于稳定了。
4 结语
本文充分利用时间约束， 在满足总时间约束条件下，使其能充分的利用时间行程，进而得到所有满足总时间约束的排序行程，从而最终为用户推荐最佳行程。
【参考文献】
【1】吴清霞.基于用户兴趣和兴趣点流行度的个性化旅游路线推荐[J]. 计算机应用，2016，36（6）：1762-1766.
【2】 曹孟毅. 基于内容相似度的运动路线推荐[J]. 计算机工程与应用， 2016，52（9）：33-38.
【3】 方潇.一种基于协同过滤的旅游行程推荐算法[J]. 地理空间信息，2016，14（7）：53-56.
【4】 彭丹平， 王江晴. 一种求解旅行商问题的新算法[J]. 中南民族大学学报（自然科学版），2006，25（1）：79-80.
【5】 赵曦， 叶和平.广义旅行商问题及其求解[J].东莞理工学院学报，2007（05）：75-80.
