2019WWW–Beyond Shortest Paths: Route Recommendations for Ride-sharing

这篇文章的主要思想就是先将网络塑造为一个前向（forward）网络，然后在这个网络上通过动态规划寻找到一条最佳路径（即节点权值（节点权值表示将会接到非冲突用户的可能性）最大的路径）

贡献

提出了一个新问题：Route Recommendation，区别于Route Planning 和 Taxi assignment。考虑到所有出租车和乘车订单的现状，出租车分配问题着眼于将每个乘车订单映射到一辆出租车上，以使特定的目标函数最大化。该目标函数可以是最大化利润、最小化迂回等。路线规划问题确定最大化目标函数的客户接送的顺序。在这两方面的工作中，都假设的士在两个连续上落客点之间的最短路径上行驶。此外，没有预测因素：所有的计算本质上都是确定性的，并且仅基于已知的乘车顺序和出租车位置。Route Recommendation 本质上就是能否预测一条稍长一点的路径，从而显著提高找到兼容客户的机会？即绕一定距离的远路，以提高获得更多兼容客户的可能性。提出了前向网络这个概念，并在这上面做了实际路径在前向网络的覆盖百分比等实验。动态规划等寻路方法都不新，不再赘述。

细节

前向（forward)网络 前向边的意思就是这条边的终点离最终目的地的距离大于这条边的起点距离最终目的地的距离，而前向网络就是由前向边构成的。如图所示，V1为初始节点，V10为最终目的地，实线的边就是前向边，实线网络也就是前向网络。

前向网络的效果 图a显示的是旧金山轨迹数据中前向边所占的比例，可以看到有50%的轨迹都只包含前向边，而多达80%的轨迹数据中至少有80%也全是前向边。 图b描述的则是额外距离（也就是可在后向网络里绕路打转的距离）对实际路径的覆盖度。可以看到当绕路距离保持在0.5km时，85%左右的实际轨迹都可被覆盖。 这两个实验说明：1、出租车的轨迹数据大多数都是一直趋向目的地的，说明了前向网络的有效性；2、适当绕路有助于获取更多的兼容乘客。