论文研读时间： 2018年10月26日9点30分
论文研读地点： 四川大学望江校区基础教学楼B座318（视觉计算实验室）
论文分享者： 李晓伟、李簦芸
分享者一：李晓伟
分享内容：Order Dispatch in Price-aware Ridesharing
分享来源：Proceedings of the Vldb Endowment，Vol.11, No.8(The 44th International Conference on Very Large Data Bases, August 2018)
分享理由：本文从最大化拼车平台利润的角度出发，来优化拼车算法，分析问题的角度很新颖，这是之前的拼车算法中没有提到的。
论文简介：
- 内容简介
订单调度是拼车的关键问题，对乘客体验和平台性能有很大影响。订单的价格是一个重要的因素，直接关系到平台的利润。但是现有的订单调度研究工作并没有考虑到订单的价格，本文考虑订单价格，提出了一个基于价格意识的约束优化问题，以平台利润为优化目标，对乘客的行程距离和等待时间进行控制。本文的主要贡献包括以下3个：
a)提出了基于价格意识的最大化拼车利润（MPPR）问题，并且证明了该问题是NP-hard问题。
b)提出了解决MPPR问题近似方法。包括贪心算法和基于匹配的订单调度算法。
c)开发了一个基于真实拼车顺序和车辆数据的仿真框架。并使用这个模拟框架进行实验，来评估所提出的方法的有效性和效率。 - 内容详解
a)证明MPPR是NP-hard问题
利用TSP的一个变体TSP without return（TSP-WR）来进行MPPR为NP-hard的证明。先证明TSP-WR是NP-hard问题，再由TSP-WR可以约化成MPPR证明MPPR为NP-hard问题。
b)贪心算法和基于匹配的调度算法
c)基于拼车顺序和车辆数据的仿真框架
开发了一个仿真框架来评估这些方法的性能。它是基于滴滴出行拼车业务中获取的真实数据而设计的。包括车辆模拟、订单模拟以及支付模拟三个方面。
d)有效性和效率的评估
通过设置不同的阈值判断不同算法利润和运行时间的区别，得出实验结论。
总体而言，就实现的利润而言，PBM和贪婪表现比BM更鲁棒稳定。在表7中总结了方法之间的比较结果。注意，当t小于等于5s时，只有贪婪才能满足时间要求。当t> 5 s (6 s)时，PBM (BM)可以在时间窗口内安全地完成调度。
分享者二：李簦芸
分享内容：Toward Visualization for Games: Theory, Design Space, and Patterns
分享来源：IEEE Transactions on Visualization & Computer Graphics 2012
分享理由：文章提出的在游戏数据中运用可视化方法，可增强玩家的游戏体验，便于开发者设计、优化游戏，帮助竞争对象分析游戏优劣。而其提出的框架对游戏和可视化技术两个方向都有一定影响和启发。
论文简介：
- 内容简介：电子游戏开始大规模的收集有关个人用户、团体的性能数据，当数据量开始累积后，高效分析数据的需求也随之而来。文章以不同流派的新旧游戏为样本，探讨游戏可视化的理论和设计空间。基于这些案例，文章定义了一种用于设计空间，并用它来讨论如何最佳应用可视化技术到游戏中的问题。文章还讨论了上述框架在未来对游戏和可视化技术的设计及发展的潜在应用价值。
- 主要贡献：在游戏中使用可视化的理论框架和方法，以提高玩家游戏动机，得到更好的空间和视觉体验；此外还能帮助游戏设计者和开发者更好的平衡、调试游戏。
- 内容详解：文章以“在游戏中使用可视化的理论框架和方法”为话题，通过以下几个方面来展开讨论。
a) exam existing evidence of visualization and data collection in games
b) derive a design space of data and visualization types in the context of games
c) propose a set of design patterns for how to best approach games as a visualization researcher or practitioner, based on this design space and on the evidence collected
d) derive implications that this framework will have on both game and visualization research