带必看POI的旅行行程推荐

11980带必看POI的旅行行程推荐0Kendall TaylorRMIT大学科学学院s9004570@student.rmit.edu.au0Kwan HuiLim墨尔本大学计算与信息系统kwan.lim@unimelb.edu.au0Jeffrey ChanRMIT大学科学学院jeffrey.chan@rmit.edu.au0摘要0旅行和观光是世界各地数百万游客喜爱的休闲活动。然而，对于游客来说，旅行行程的推荐和规划是繁琐而具有挑战性的任务，因为他们通常对城市中的各种POI不熟悉。除了识别受欢迎的POI外，游客还需要构建一个包含这些POI子集的旅行行程，并将这些POI按照可以在他/她可用的旅游时间内完成的访问顺序进行排序。为了更加真实的行程，游客还必须考虑POI之间的旅行时间和各个POI的访问时间。此外，这个行程还应该考虑游客的偏好，如期望的起点和终点POI（例如，靠近游客酒店的POI）和一部分必看POI（例如，游客必须参观的热门POI）。我们将其称为TourMustSee问题，它基于定向问题的一个变体。随后，我们提出了LP+M算法来解决TourMustSee问题，作为一个整数线性规划（ILP）。使用Flickr数据集中的七个旅游城市的POI访问，我们将LP+M与各种基于ILP的基线进行比较，结果显示LP+M在POI流行度、总POI访问数量、总旅游时间利用和必访POI包含方面推荐更好的旅行行程。0CCS概念0• 信息系统→个性化；推荐系统；基于位置的服务；数据挖掘；Web应用程序；0关键词0旅行推荐；旅行规划；推荐系统0ACM参考格式：Kendall Taylor，Kwan Hui Lim和JeffreyChan。2018。带必看POI的旅行行程推荐。在WWW'18Companion：2018年网络会议伴侣，2018年4月23日至27日，法国里昂。ACM，美国纽约，8页。https://doi.org/10.1145/3184558.31915580对于个人用户来说，旅行推荐和行程规划是具有挑战性的任务。一个主要的贡献因素是在一个城市中要访问的POI的选择通常很多，01 本文中“旅行”和“行程”可以互换使用。0本文发表在Creative Commons Attribution 4.0 International（CC BY4.0）许可下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW'18 Companion，2018年4月23日至27日，法国里昂©2018IW3C2（国际万维网会议委员会），根据创作共用CC BY 4.0许可发布。ACM ISBN978-1-4503-5640-4/18/04。https://doi.org/10.1145/3184558.31915580图1：示例图，其中顶点表示POI（具有效用分数si），边表示它们之间的旅行时间(ti，j)。未显示所有边和旅行时间值。0此外，用户通常在旅游中时间有限，因此任何推荐的行程也受到时间的限制，主要是考虑POI之间的旅行时间和适当的POI访问持续时间。此外，希望减少POI之间的距离和旅行时间，以便最大限度地增加POI的数量和/或访问时间。包括必看POI的可取性通常在用户的议程中非常高，因为通常有一些主要景点是必须参观的（例如布达佩斯的“布达城堡”或多伦多的安大略皇家博物馆）。在我们的工作中，推荐的行程由连接选择的POI的路径连接起始点和结束点组成，其中包括用户确定的所有或一部分必看POI。每个POI只能访问一次，并且行程必须包括至少一个起点或终点之外的POI。连接POI的链接与旅行时间成本相关，当总和时，将行程持续时间限制为用户指定的时间预算。此约束还确保单个行程只能访问可用POI的子集。为了表示用户对特定类型POI的偏好，每个POI都有一个表示其对用户的效用/分数的值。因此，一个好的建议行程是具有最大POI效用/分数值但可以在分配的时间预算内完成的行程。图1显示了这个问题的一个示例。我们的POI数据集来自YahooFlickr数据集[25]，包括具有高流行度和兴趣水平的POI，每个POI根据这些标准分配一个效用（或分数）。平均POI访问持续时间是从相同的数据中导出的0跟踪：第八届位置和Web国际研讨会WWW 2018，2018年4月23日至27日，法国里昂11990POI之间的地理空间距离用于表示旅行时间（根据步行速度进行转换）。2总时间预算包括旅行POI之间所需的时间总和和平均POI访问持续时间的总和。在本文中，我们对行程推荐领域做出了三方面的贡献，即：0（1）我们引入并制定了基于定向问题变体的TourMustSee问题[26]。（2）我们提出了LP+M算法，将TourMustSee问题作为整数线性规划来解决。（3）使用Flickr数据集中的七个城市，我们评估了我们的算法，并展示了它在各种基线上的良好性能。0本文的其余部分组织如下：第2节讨论了行程推荐领域的相关文献；第3节提供了我们的Tour-MustSee问题的一些背景和正式表述；第4节概述了我们的实验设计和评估指标；第5节讨论了主要结果和发现；第6节总结和结束本文。02 相关工作0在本节中，我们讨论了运筹学、前k个POI推荐和行程推荐等相关领域的一些关键作品，然后详细阐述了我们的研究与这些早期作品的主要区别。运筹学。行程推荐起源于旅行商问题（TSP）及其在运筹学领域中通常使用的许多变体。特别值得注意的是TSP的变体，如选择性TSP [3]、带利润的TSP [9]或定向问题 [11, 26,27]。这些作品的主要目标是为一般游客规划一套具有最高利润的景点行程，而定向问题则有特定的起点和终点的额外约束。这个问题的整数线性规划（ILP）公式被广泛使用，并已成功实施以提供最优解决方案[9,13]。这些作品的重点是他们方法的最优性，他们的评估涉及已知最优解的合成数据集。使用社交媒体进行行程推荐。近年来，研究人员将运筹学的作品与使用社交媒体进行行程推荐的作品相结合[4, 6, 7,18-20, 22, 23,28]。这些作品大多以定向问题或TSP变体为基础的ILP公式为基础，但是与使用合成数据集不同，这些作品使用社交媒体进行评估，例如反映世界各地几个城市基于POI的真实行程的Flickr地理标记照片。类似地，还有许多应用于旅行行程规划和推荐的应用程序[5,33]，它们利用社交媒体和类似于这些讨论作品的技术。这些作品的重点是推荐受欢迎且反映社交媒体用户实际行程的行程。前k个POI推荐。前k个POI推荐领域与旅行行程推荐密切相关0尽管我们使用步行速度和距离来表示旅行时间，但这种表示方法可以很容易地扩展到考虑不同的交通方式，例如驾车、骑自行车、乘火车等。0我们讨论了这个研究领域的关键工作。在这些工作中，主要目标是推荐一组 k个POIs，这些POIs根据它们与用户的相关性进行排序。这些工作通常利用基于各种矩阵分解或协同过滤算法的方法。类似地，已经开发了一些应用程序[1,12]来推荐一个个别POIs的列表，这些POIs不以行程的形式结构化。这些工作的重点更多地放在个别POIs与用户的相关性上，而不是推荐具有各种用户约束的连接POIs的行程。行程推荐与必看POIs。使用一组必须访问的POIs是行程推荐问题的进一步扩展，并且只有少数几篇论文明确地讨论了这个问题。Gendreau等人[10]提出了一个作为ILP的分支定界算法，并针对几个启发式算法进行了测试。强制顶点被纳入模型中，包括必须访问的总顶点的子集，以便成功完成旅行。结论集中在解决顶点数量较大的问题的成功上，而不是强制顶点的影响。Laporte等人[14]在早期论文中使用的模型中，将必看（或“指定节点”）纳入了模型中。这项工作使用分支定界算法来找到必须访问的节点只访问一次的最优旅行路线。再次，该工作的重点不是强制节点的效果，而是子旅行消除所需的计算工作量。Li等人[16]的后续工作提出了一种具有强制节点的约束定向模型的方法，但问题的制定基于网络流理论，并与此处使用的问题有明显不同。我们的工作与以前的工作的主要区别。虽然这些早期的工作对行程推荐问题提供了有趣的见解，但我们的工作与它们有以下不同之处：（i）运筹学的工作侧重于其解决方案的最优性，通常使用合成数据集，并不考虑必访POIs，而我们的工作使用从Flickr地理标记的照片数据集中挖掘的真实生活POI行程，并考虑必访POIs；（ii）使用社交媒体的行程推荐工作使用了真实生活数据集，但在问题制定中并不考虑必访POIs，而我们的工作考虑了这个额外的约束条件；（iii）关于Top-kPOI推荐的工作侧重于推荐一个个别POIs的排序列表，而我们的工作要求推荐相关的POIs，并且此外还要规划通过这些POIs的行程，其中包括一个特定的起始和结束POI，可以在一定时间内完成；（iv）关于具有强制POIs的行程推荐的工作，像运筹学的工作一样，侧重于解决方案的最优性，并使用随机生成的利润的合成数据集，而我们的工作使用了一个真实的数据集，其中POI的利润反映了POIs的访问次数。此外，我们对必访POIs的制定允许灵活地推荐包含一部分必访POIs的行程，而不必像早期的工作那样必须包含所有POIs。03 背景和问题0在本节中，我们介绍了我们工作中使用的一些基本定义，并制定了TourMustSee问题。0Track: 第八届位置和网络国际研讨会WWW 2018，2018年4月23日至27日，法国里昂Sixi,j(1)x1,j =xi,N = 1(2)xi,k =xk,j ≤ 1∀k = 2, ..., N − 1(3)(5)120003.1 问题定义0我们提出的TourMustSee问题，即推荐带有必看POIs的行程，是NP-hard问题[10,16]。随着POIs集合的增长，TourMustSee问题的复杂性呈指数级增长，使用“蛮力”方法无法解决。这个问题类似于“旅行推销员问题与利润”和“定向问题”，其目标是在保持POIs之间的旅行时间在固定预算内的情况下最大化总得分（从访问POIs中累积得分）。推荐的行程从指定的起始POI开始，并在另一个POI结束。这个问题可以表示为一个图 G = � V ,  E � ，其中 N = | V | ，V = { v 1 , ..., v N }是顶点（或POIs）的集合，E 是连接边的集合。连接顶点 i 和 j的每条边都有一个旅行时间成本，对于所有 v ∈ V ，t i , j都是已知的。旅行的总时间预算为 T max，限制了旅行中的顶点数量。每个顶点还有一个非负的已知得分 S i，对于所有 v i ∈ V ，其中 i ∈ { 1 , ...,  N }。我们将行程定义为起始和结束POIs之间的路径，至少包含一个其他POI，只访问POIs一次，并排除子行程。设 P 是一组具有 p 1作为起始POI和 p N 作为目的地POI的POIs，一个行程 I是一个连接的POIs序列，使得 I = { p 1 , ..., p N }。我们引入一个必看POIs的集合 M ，其中 M = { m 1 , ..., m L }，其中 L ≤ N ，理想情况下 L 远小于 N 。具有必看POIs的行程 I M可以随后表示为序列 I M = { p 1 , ..., m 1 , ..., m L , ..., p N } ，其中p 1 , p N  不属于 { m 1 , ... m L } 。03.2 公式化0通过将线性规划方法应用于问题，我们可以将不包含必看POIs的行程的生成指定为目标函数的优化，并遵守各种约束条件。我们首先描述了最大化推荐行程对用户的效用/得分的目标函数（方程1），其形式化表示为：0最大0N  −1是一0N是一个整0� 1 ，如果顶点 i 被顶点 j 0 访问，否则 S i 表示包含 p i在旅行中的得分，其中 i = 1 , ...,  N。得分是一个已知的非负值，表示POI的受欢迎程度，基于基于频率的访问计数，这些计数是从Flickr地理标记的照片中获得的，这些照片是在该POI附近拍摄的[20]。现有模型I（不包括必看POIs），受以下约束条件的限制：0(2)  旅行行程必须从选择的起始POI开始，并在选择的结束POI结束（方程2）。0N是一个整数0N  −1是一个整0这个约束条件允许游客根据他们的偏好选择起始和结束的POIs，比如那些方便位于他们住宿附近的POIs。0(2)不能访问同一POI多次，并且路径中的所有节点必须连接（方程3）。0N  −1是一个整0N是一个整数0由于我们的TourMustSee问题是针对游客的，这个约束条件确保我们不会推荐包含多次访问同一POI的旅行行程，也不会推荐不连通的旅行行程。0(3)必须包含至少一个额外的POI（除了起始和结束点）（方程4）。0x i , j  =  0 ,  其中  i  =  p 1  且  j  =  p N (4)0这个约束条件确保我们的算法不会推荐过于简单的旅行行程，即从起始POI到结束POI的直接路径，如果时间预算太小，可能会出现这种情况。0(4) 总行程时间D不能超过指定的预算B（方程5）。0N− 1≤0N0j = 2 Di,j xi,j ≤ B，其中Di,j = TravelTime(i, j)0+ VisitDuration(j)0TravelTime(i,j)是以4kph的速度从pi到pj步行所需的时间。这是一个已知的非负值，根据pi和pj之间的地理距离提供了一个基于分钟的时间近似值。VistDuration(j)是每个P中的每个p ∈P的平均访问时间（以分钟为单位），根据Flickr地理标记照片数据集中所有用户的真实行程确定。预算B表示行程完成的最长时间，不能超过该时间。0(5) 必须消除子行程（方程6和7）。02 ≤ pi ≤ N，�i = 2, ..., N (6)0pi − pj + 1 ≤ (N − 1)(i − xi,j), �i, j = 2, ..., N (7)0子行程是由不包括起始和结束景点的POI组成的单独循环，从而导致包含两个不相交行程的解决方案。因此，在Orienteering问题、TSP和类似的TourMustSee问题中，消除这些子行程非常重要。然而，在优化模型之前消除子行程的方法具有指数级的复杂度。一种常用的方法是使用MTZ[21]方法来消除子行程，同时避免过多的计算成本。该方法检查最初生成的行程t是否存在子行程，并为每个找到的子行程向模型添加一个约束。然后，使用新的约束重新评估模型，生成新的行程t'，再次评估是否存在子行程。03本文中我们使用了4kph的步行速度，但是这个行进速度可以推广到其他交通方式，例如汽车的更快速度。此外，我们可以使用时间相关的行进速度来表示不同时间的不同交通状况，例如高峰时段的行进速度较慢。0论文集：第八届国际位置与网络研讨会WWW 2018，2018年4月23日至27日，法国里昂122236.798325.3213795.7585947.614237.168958.67151631.57552230.6312010迭代继续，直到找到一个没有子行程的解决方案。03.3 必看景点约束0除了上述约束之外，我们还引入了一个约束，确保一组必看景点在成功的解决方案中被访问。必看景点集合M必须被访问，满足以下条件：0N0i = 1 xi,m0N0j = 2 xm,j = 1, �m ∈ M = {m1, ..., mL}，其中L = |M|0(8) 对于每个m ∈ M，m ∈ P且L ≤ N，其中N =|P|。该约束表达了有效行程必须包括到每个节点mi在集合M中的连接的要求。该约束反映了游客在行程中包括必看景点的现实考虑，这些景点通常是必须参观的主要景点，如布达佩斯的“布达城堡”或多伦多的皇家安大略博物馆。通过将L = |M|更改为L ≤|M|，该约束也可以轻松适应包括必访景点的子集，而不是所有景点，如早期的研究中所做的那样。04实验设计0在本节中，我们描述了我们的实验设计，包括数据集、基准算法、评估方法和指标的描述。0表1：POI数据集0集合ID 城市 连接 POI数量01 布达佩斯 1332 39 2 爱丁堡 650 26 3多伦多 812 30 4 维也纳 756 29 5格拉斯哥 600 29 6 珀斯 462 25 7 大阪552 2804.1 数据集0我们的实验评估使用了来自七个城市的POI集合进行，详见表1。这些集合是根据维基百科上每个城市的热门POI列表从YahooFlickr创意共享100百万数据集（YFCC100M）中选择的。YFCC100M数据集包含近1亿张照片，其中6900万张带有注释，4800万张带有地理标签[25]。然后根据它们的接近程度将Flickr地理标记照片映射到每个POI，从而使我们能够确定每个POI的受欢迎程度和平均访问持续时间。有关该数据集的更多详细信息，请参阅Lim等人的论文[20]。POI之间的距离是以米为单位的地理空间测量，我们将其转换为以分钟为单位的行程成本（基于4kph的步行速度）。表2提供了爱丁堡市POI集合的示例。0表2：示例POI数据集0起点 终点 距离 得分/访问持续时间 POI POI（米）利润（分钟）04.2 提出的算法和基准线0我们评估的基准线是旅游路线Topt，即在不考虑必看景点集合M的情况下找到的最优路径。如果M非空，则将元素m1包含在结果路线中作为潜在解决方案的约束。因此，预计包含必看景点将导致整体旅游路线得分与Topt相比的减少。除了我们提出的LP+M算法，我们还评估了其他基准算法，这些算法基于整数线性规划的变体：0(1) LP.生成一个没有必看景点的行程。这是现有的整数线性规划模型，根据第3.2节中概述的约束条件生成最优行程，并用于生成T opt旅游路线。这些行程包括从起始景点到结束景点的路径，其中收集的景点分数最大化，总行程时间受到给定预算的限制。必看景点可以在路径中访问，但它们的包含是优化行程的结果，而不是明确访问它们。(2)LP+M（我们提出的模型）。生成一个包含必看景点的行程。该模型在LP模型的基础上构建，使用相同的目标函数和约束条件，但添加了一个新的约束条件，确保所有解决方案中都包含必看景点。该函数模拟了一个典型的行程情况，用户希望作为更大更一般的行程的一部分访问多个景点。(3) MaxM.基于Laporte等人[14]使用的方法，通过为每个必看景点分配较大的利润值生成包含必看景点的行程。结合上述LP模型，成功的解决方案包含必看景点，因为它们的膨胀利润确保了它们的选择。这种方法提供了一种可靠的将必看景点纳入整数线性规划模型的方法。(4) GreedyM.首先为必看景点生成一个行程，然后为剩余的景点生成一个行程，并将它们连接在一起。这是一种简单而实用的基于访问强制景点的行程构建方法。由于必看景点是行程的重点，一个可行的选择是首先访问这些景点，然后使用剩余的时间预算访问剩余的景点。行程的两个部分都可以使用LP方法进行优化并合并在一起。0本研究使用R统计编程语言和lp_solve库实现了所使用的算法。lp_solve软件包是基于单纯形法和分支定界算法的混合整数线性规划（MILP）求解器[2]。0论文集：第八届国际位置与网络研讨会WWW 2018，2018年4月23日至27日，法国里昂120204.3 实验设置0共生成了9,100个旅游路线，以评估必看景点对行程规划和最优性的影响。对于数据集中的每个城市，生成了300个随机的起始和结束景点，并选择了五组随机的必看景点。这些必看景点集合包括从一个到四个景点的基数，并且是独立选择的。每组必看景点都会被完整地访问。对于LP算法，生成了700个旅游路线，并记录了每个路线中访问的必看景点的数量。对于LP+M、MaxM和GreedyM算法，为每个算法生成了2,800个行程，对于每个算法的四组必看景点，生成了2,100个旅游路线。用于本研究的城市包含不同数量的景点，分布在不同大小和密度的城市区域中。为了提供反映这些变化的旅游时间预算，使用以下公式计算了每个城市的预算：0[ µ ( P travel ) + µ ( P visit )] ∙ q，其中 q = L + 2 (9)0每个城市的时间预算是中位数旅行时间µ(Ptravel)和每个POI的参观持续时间µ(Pvisit)之和。结果乘以q，q代表需要访问最大必看POI集合的最小POI数量。在我们的案例中，最大的集合包括四个POI，并且包括起点和终点POI，q = 6。0表3：LP方法生成的成功访问所有或至少一个必看POI的旅行数量。数值越高越好。0访问所有 至少访问一个0# 必看POI数量 # 必看POI数量0城市 1 2 3 4 1 2 3 40布达佩斯 26 10 2 0 26 49 62 65 爱丁堡 39 14 13 0 39 6185 90 多伦多 31 12 6 0 31 57 77 85 维也纳 38 15 4 3 3857 70 87 格拉斯哥 34 15 8 4 34 66 72 83 珀斯 44 11 10 244 63 81 84 大阪 41 19 11 4 41 63 81 8404.4 评估指标0为了评估我们的算法与各种基线的性能，我们使用以下评估指标：（1）包含必看POI。推荐行程是否包含必看POI集合。（2）旅行利润。推荐行程中所有POI的总利润。（3）访问的POI。推荐行程中的唯一POI数量。（4）使用的预算。用于推荐行程的总预算，即在POI之间旅行和POI参观持续时间所需的总成本。04这个时间预算的定义实际上考虑了旅行时间和POI参观持续时间，我们的算法和所有基线都使用相同的时间预算，以确保公平评估的相同实验设置。虽然我们可以使用其他时间预算的定义，但是由于所有算法都使用相同的时间预算，结果趋势将是相同的。0表4：成功旅行的数量（100个中）包括必看POI。数值越高越好，LP+M、GreedyM和GreedyM中的最佳性能以粗体/蓝色显示。0LP+M MaxM GreedyM0# 必看POI数量 # 必看POI数量 # 必看POI数量0城市 1 2 3 4 1 2 3 4 1 2 3 40布达佩斯 79 58 39 21 74 53 37 19 77 59 39 17 爱丁堡 82 75 53 38 82 6950 36 82 75 53 32 多伦多 77 43 27 4 76 40 26 4 75 42 20 40维也纳 80 50 28 21 79 50 30 20 81 45 29 16 格拉斯哥 77 57 28 18 74 5325 15 76 52 26 13 珀斯 82 57 47 20 82 55 46 20 82 54 44 18 大阪 88 8266 49 87 76 65 45 91 80 62 390表5：平均访问的POI数量，包括失败的旅行，按算法、必看集大小和城市划分。数值越高越好，LP+M、GreedyM和GreedyM中的最佳性能以粗体/蓝色显示。0LP LP+M MaxM GreedyM0# 必看POI数量 # 必看POI数量 # 必看POI数量0城市 1 2 3 4 1 2 3 4 1 2 3 40布达佩斯 10.7 7.6 5.8 4.0 2.0 7.4 5.5 3.9 1.9 7.1 5.0 3.3 1.2 爱丁堡 10.2 8.6 7.9 5.4 4.0 8.67.4 5.2 3.8 8.2 7.1 4.8 2.8 多伦多 9.6 6.5 3.7 2.4 0.4 6.4 3.6 2.4 0.4 6.0 3.2 1.6 0.3 维也纳10.0 7.9 5.1 2.7 1.9 7.9 5.1 3.0 1.9 7.4 4.1 2.3 1.3 格拉斯哥 10.2 8.2 6.1 3.1 2.0 7.9 5.8 2.91.8 7.6 4.9 2.5 1.3 大阪 10.4 9.3 8.4 6.7 5.0 9.3 8.0 6.6 4.7 8.9 6.8 5.0 2.9 珀斯 9.0 7.6 4.9 4.21.9 7.6 4.9 4.2 1.9 7.4 4.4 3.7 1.50指标1允许我们确定推荐的旅行行程是否满足访问整个必看POI集合（或至少一个必看POI）的约束条件。指标2和3衡量推荐旅行行程中的总利润和访问的POI数量，反映了对游客的感知效用价值，即具有更高利润和更多POI的旅行行程更好。指标4检查旅行行程使用的总时间预算，首选的旅行行程是在POI之间旅行时利用更多时间访问POI。这些评估指标及其相关变体在类似的行程推荐工作中也常被使用[4, 6–8,17]。05 实验结果0在本节中，我们根据包含必看POI、总旅行利润、访问的POI总数和使用的预算来呈现和讨论实验结果。05.1 包含必看POI0没有必看POI约束的LP算法提供了最优旅行Topt，并与其他方法进行比较。LP算法不对生成的旅行中访问任何必看POI做出任何保证，在37%的情况下没有访问任何一个必看POI。表3列出了LP方法生成的成功访问所有POI的旅行数量。随着必看POI集的增加，这种旅行的发生率迅速下降，然而0Track: 第八届位置和网络国际研讨会WWW 2018，2018年4月23日至27日，法国里昂12030图2：根据必看POI数量的平均旅行利润。数值越高越好。0访问至少一个必看POI的旅行数量随着更多选择的出现而增加。虽然LP方法生成的几乎所有旅行都是成功的，但是当包含必看POI时，成功的旅行数量低于完美。由于必看POI作为约束条件包含在模型中，LP+M、MaxM和GreedyM都无法找到所有旅行组合的解决方案并不令人意外。表4列出了LP+M、MaxM和GreedyM找到的成功旅行数量，以及必看POI集的大小。每种方法的成功率几乎相同，清楚地显示了必看POI数量增加的影响。有趣的是，尽管多伦多有第二多的可选择POI数量，但几乎所有集合大小的成功率都低于其他城市。05.2 推荐旅行的利润0包含访问所有必看POI的约束会降低平均旅行利润，如图2所示，平均利润值低于LP+M、MaxM和GreedyM算法的最优值。图2呈现了平均利润和标准0错误，包括失败的旅行，并清楚地显示了必看POI的阻碍效果。旅行行程的平均利润结果证实了LP+M相对于MaxM和GreedyM算法的卓越性能。LP+M始终推荐具有更高盈利能力和更高POI访问率的旅行行程，比GreedyM找到更多的成功解决方案。如预期的那样，随着必看POI集的增加，平均利润会下降。然而，无论必看POI集的大小如何，LP+M在旅行利润方面都表现最佳，其次是MaxM，然后是GreedyM。05.3 推荐旅行中的总POI数量0如表5所示，每个算法的旅行中访问的POI总数随着必看景点集的增加而逐渐减少。四个必看景点集通常比较小的必看景点集在成功的旅行中包含更多的POI。GreedyM算法生成的旅行中的POI数量平均低于LP+M和MaxM。这个结果表明，与LP+M和MaxM相比，GreedyM的性能次优。0Track: 第八届位置和网络国际研讨会WWW 2018，2018年4月23日至27日，法国里昂Compared to GreedyM and MaxM, LP+M consistently recom-mends tour itineraries with the most number of POIs for the samenumber of must-see POI. This result shows that despite the sameconstraint in terms of must-see POIs, LP+M is able to recommendtours that satisfy these constraints and yet recommend better toursthat comprises more POIs.5.4Utilized Budget of Recommended ToursWhile the total time budget for the itineraries was never exceeded,GreedyM produced the shortest tours and wasted the largest amountsof available time, as shown in Figure 3. GreedyM also producedsolutions with higher average travel times compared with the LP,LP+M and MaxM approaches. This result is not surprising giventhat GreedyM does not optimise the tour as a whole, but ratherdoes it in two parts leading to inefficiencies.The inclusion of must-see POIs as a model constraint whengenerating travel itineraries results in tours with lower profitabilityand higher travel times compared to those without must-see POIs.The extent of this reduced performance increases markedly as thesize of the must-see set increases. Further, the likelihood of failingto generate a valid itinerary increases substantially as more must-see POIs are included in the tour. Interestingly though, there is ahigh chance (around 30%) that a single must-see POI may be visitedby an algorithm which ignores the must-see set when optimising.5.5DiscussionThese results show the general good performance of our proposedLP+M algorithm over the GreedyM and MaxM baselines, whilethe LP algorithm was included to demonstrate an optimal solutionthat does not consider must-see POIs. Compared to LP, GreedyMand MaxM, our proposed LP+M algorithm is able to recommendthe highest number of successful tour itineraries, i.e., those thatinclude the must-see POIs. In addition, our LP+M algorithm is ableto consistently recommend tour itineraries that comprises a highernumber of POIs and a higher total tour profit, compared to theGreedyM and MaxM baselines, thus resulting in tour itineraries thatare more satisfying for tourists based on these measures. The LP+Malgorithm also utilizes the available time budget more efficientlythan the GreedyM baselines, as it schedules tour itineraries withmore time allocated to visiting POIs than travelling between POIs.Track: Eighth International Workshop on Location and the Web WWW 2018, April 23-27, 2018, Lyon, France12040图3：平均旅行时间和参观持续时间，上面的列代表旅行时间，下面的列代表参观持续时间。参观持续时间越长越好，旅行时间越短越好。Based on these evaluation metrics, experimental results show thatLP+M is the overall best performing algorithm, followed by MaxMthen GreedyM.6CONCLUSION AND FUTURE WORKIn this work, we have proposed and formulated the TourMustSeeproblem, which incorporated a set of must-see POIs into travelitineraries, along with considerations of a starting/ending POIs andtravel times between POIs and visit durations at POIs. We thensolved this TourMustSee problem as an Integer Linear Program,and we denote this approach as the LP+M algorithm. Comparedwith various baselines, LP+M performed consistently better withhigher average profits, a greater average number of visited POIs,and a higher POI visit duration. Our algorithm incorporates bothtravel time and POI visit durations and incorporates real-world datagathered from publicly accessible sources. Using a well establishedILP model as the base for LP+M also ensures a robust and efficientoptimisation strategy which produces consistent results.This work fills a gap in existing research by providing a specificanalysis of must-see POIs and their impact on optimal itineraries.Future work would include further evaluation with a more diverserange of alternate heuristics to validate this research, and to re-peat the expe