论文标题
Envy \ Mbox { - }小组旅行计划查询问题中的免费旅行计划
Envy\mbox{-}free Trip Planning in Group Trip Planning Query Problem
论文作者
论文摘要
最近，小组旅行计划查询（此后称为GTP查询）是空间数据库中研究的问题之一。该问题的输入是一个道路网络，顶点代表利益点（称为POIS之后），它们分为不同的类别，边缘代表道路段，而边缘的重量代表距离和一组用户及其来源和目的地的位置。这个问题要求从每个类别中返回一个POI，以使小组的总距离最小化。由于目的是最大程度地减少汇总距离，因此现有的解决方案方法不考虑小组成员所旅行的个体距离。为了解决这个问题，我们介绍和研究\ textsc {eNvy Free Group Trip Planning查询}问题。除了GTP查询问题的输入外，在此变体中，我们还具有阈值距离$ d $，因此小组旅行的汇总距离被最小化，并且对于任何成员，他们的单个距离旅行之间的差异小于$ d $。但是，可能会碰到给定的$ d $值，找不到这样的pois。为了解决此问题，我们介绍了替代问题\ textsc {Engy Free Group Trip Planning查询与最小距离}问题，该问题询问至少要使用$ d $添加的最小距离以获取至少一个解决方案。对于这些问题，我们设计了有效的解决方案方法，并对现实世界中的数据集进行了实验。从实验中，我们观察到，与具有合理计算开销的基线方法相比，提出的解决方案方法的聚合距离较小。
In recent times, Group Trip Planning Query (henceforth referred to as GTP Query) is one of the well\mbox{-}studied problems in Spatial Databases. The inputs to the problem are a road network where the vertices represent the Point-of-Interests (mentioned as POIs henceforth) and they are grouped into different categories, edges represent the road segments, and edge weight represents the distance and a group of users along with their source and destination location. This problem asks to return one POI from every category such that the aggregated distance traveled by the group is minimized. As the objective is to minimize the aggregated distance, the existing solution methodologies do not consider the individual distances traveled by the group members. To address this issue, we introduce and study the \textsc{Envy Free Group Trip Planning Query} Problem. Along with the inputs of the GTP Query Problem, in this variant, we also have a threshold distance $D$ such that aggregated distance traveled by the group is minimized and for any member pairs the difference between their individual distance traveled is less than equal to $D$. However, it may so happen that a given $D$ value no such set POIs are found. To tackle this issue, we introduce the surrogate problem \textsc{Envy Free Group Trip Planning Query with Minimum Additional Distance} Problem which asks what is the minimum distance to be added with $D$ to obtain at least one solution. For these problems, we design efficient solution approaches and experiment with real-world datasets. From the experiments, we observe that the proposed solution approaches lead to less aggregated distance compared to baseline methods with reasonable computational overhead.
