论文标题
面向个人购物者的困境：时间与费用
Towards A Personal Shopper's Dilemma: Time vs Cost
论文作者
论文摘要
考虑一个需要履行购物清单的客户，也是一个愿意购买并转售给客户购物清单中商品的个人购物者。找到（购物）路线是符合个人购物者的最大利益，它（i）最大程度地减少了为客户服务的时间，以便能够为更多的客户提供服务，并且（ii）最大程度地减少为商品支付的价格，以便在转售时最大化其潜在利润。这些通常是竞争标准，导致我们称之为个人购物者的困境查询，即确定在何处购买所需商品的何处，同时尝试同时优化这两个标准。鉴于查询的NP硬度，我们提出了一种启发式方法，以确定上述标准的任何线性组合，即查询的近似线性天际线集。为了衡量我们的方法的有效性，我们还介绍了两个新的指标，最佳和覆盖差距W.R.T.一种最佳但计算上昂贵的基线解决方案。我们使用现实的城市规模数据集的实验表明，我们提出的方法比基线快两个数量级，并且产生较低的值的最优性和覆盖范围。
Consider a customer who needs to fulfill a shopping list, and also a personal shopper who is willing to buy and resell to customers the goods in their shopping lists. It is in the personal shopper's best interest to find (shopping) routes that (i) minimize the time serving a customer, in order to be able to serve more customers, and (ii) minimize the price paid for the goods, in order to maximize his/her potential profit when reselling them. Those are typically competing criteria leading to what we refer to as the Personal Shopper's Dilemma query, i.e., to determine where to buy each of the required goods while attempting to optimize both criteria at the same time. Given the query's NP-hardness we propose a heuristic approach to determine a subset of the sub-optimal routes under any linear combination of the aforementioned criteria, i.e., the query's approximate linear skyline set. In order to measure the effectiveness of our approach we also introduce two new metrics, optimality and coverage gaps w.r.t. an optimal, but computationally expensive, baseline solution. Our experiments, using realistic city-scale datasets, show that our proposed approach is two orders of magnitude faster than the baseline and yields low values for the optimality and coverage gaps.
