共享出行服务在现代交通中发挥着至关重要的作用,一定程度上缓解了城市中交通拥堵和废气污染。在共享出行问题中,提高乘客之间的共享（拼车）率不仅可以节省乘客和司机的出行成本,还可以更有效地利用车辆资源。而现有的基于在线和批处理模式的共享出行问题的算法缺乏对乘客之间共享关系的分析。此外,基于批处理模式的算法相较于在线处理算法虽然具有更高的服务质量,但需要耗费大量的时间成本进行订单组合的枚举。针对于现有工作中所存在的问题,本文主要工作从如下三个方面展开:·可共享性网络的快速构建。众所周知,图结构是分析节点间结构信息的有力工具。本文通过提取订单之间的可共享关系来构建了一张可共享性网络。通过对可共享性网络的观察发现,节点的度数和所属k-Cliques结构揭示了订单在网络中的可共享能力,能够为订单与车辆之间的匹配过程提供指引。因此,本文通过对订单之间的时空分布进行细致的理论分析,提出了一种高效的可共享性网络构建方法。此外,为了能够支持多笔订单之间的可共享关系,本文基于超图的数据结构提出了一种可共享关系预测模型。该模型能够支持若干订单之间的可共享关系预测,显著降低了批处理算法中订单组合枚举过程的规模及其时间成本。·结构感知的共享出行分派。为了改进现有批处理算法的性能和服务质量,本文提出了一个新的共享出行服务框架,STRide。它通过利用可共享性网络的结构信息改进共享出行问题中的分派方案。具体而言,本文为车辆定义了一个“可共享性损失”的衡量指标,STRide通过降低订单组合分派过程中的可共享性损失来使未被选择的订单仍保持有较高的共享概率。本文通过广泛的实验证明了本文所提出的SARD算法的效率和有效性。与最先进的前沿算法相比,SARD算法的运行速度是已有算法的72.68倍,同时平台的总体服务率能够取得最多高达50%的提升。·事件驱动的窗口匹配。为了满足不同应用场景下用户对订单响应时间和服务质量的权衡,本文提出了一个基于事件驱动的在线共享出行服务框架ε-Ride,该框架充分地利用了订单的个性化匹配窗口。具体来说,本文通过混合图结构来维护订单组合,并通过后续到达的订单持续优化平台已有的订单组合。此外,本文通过KL-UCB策略在线学习的方式提出了一种自适应订单调度算法,能够通过用户给定参数?实现对服务质量和响应时间的平衡。本文通过在真实订单数据集上的大量实验结果证明了本文提出的ε-Ride框架能够以近乎于在线的性能实现批处理算法的服务质量。