互联网时代所有闲置资源都可能被共享,共享经济是一种新兴的经济业态,该业态中资源持有者通过在线平台将闲置资源使用权有偿让渡给他人,实现闲置资源的价值再创造。拼车服务作为一种“共享经济”,通过合理利用汽车上的空余座位,有效的减少出行成本,降低环境污染,实现绿色出行。在拼车场景中,如何设计高效的调度算法,实现车辆资源的合理分配,是决定服务质量的关键。目前已有的调度算法只考虑为当前用户分配最近的车辆,未进行全局的调度优化,导致了拼车匹配成功率低、整体绕路距离大的问题。论文针对传统的拼车算法中存在的不足,提出了全局匹配优化的动态拼车算法,并在多核与多机场景下,对全局匹配优化的动态拼车算法进行并行化设计与实现。论文的主要工作如下:(1)针对传统拼车算法存在的匹配成功率低、整体绕路距离大的问题,提出了全局优化的动态拼车算法。算法使用区域网格化与欧式距离筛选,初步排除了大部分不满足乘客时间约束的司机,避免了大量的最短路径计算,节省了 CPU的计算时间。采用全局匹配优化算法进行乘客与司机匹配,提高拼车服务的匹配成功率,最小化合乘后整体车辆里程数。(2)在多核架构下对提出的动态拼车算法进行并行化设计与实现。提出了基于OpenMP框架的并行化拼车算法,该方法将乘客搜索候选司机集的过程分发到多线程中处理,减少了大量计算最短路径造成的时延。另外,在使用Kuhn-Munkres算法进行全局匹配优化阶段,采用BFS算法并行化的方法优化其中的增广路搜索过程,实现算法的提速。实验表明并行后的拼车算法性能是串行的拼车算法的4倍。(3)基于Spark平台,设计了一个可扩展的动态拼车服务框架。针对乘客与司机匹配进行并行化设计与实现,实验表明在增加计算资源后,该算法具有很好的扩展性。