目前,大型城市面临愈发严峻的交通拥堵和环境污染问题。拼车出行因为可以提高现有车辆的座位使用率,成为了现有交通系统不可或缺的组成部分。本文以长期通勤拼车分组和实时拼车为主要研究内容,针对传统拼车算法的求解困难和实时性差的问题,提出了基于完全子图的通勤拼车算法和基于路线相似性的实时拼车算法,并结合上海城市道路、地铁刷卡、出租车GPS数据,进一步验证了拼车算法的有效性。论文主要内容包括:1、针对传统通勤拼车算法求解困题的问题,提出基于完全子图的拼车算法。根据时间、空间、信誉等因素,计算用户之间拼车满意度的大小,进一步以通勤需求为结点、拼车关系为连边、拼车满意度为权值建立通勤用户拼车需求网络。在拼车需求网络的基础上,将拼车小组用完全子图来表示,整体拼车方案是一个完全子图分割。原有的拼车线性规划问题就变成了一个图论中的最大权匹配问题。虽然最大权匹配是NP-hard问题,但是可以通过两种近似算法GSA和TSA快速有效的找到拼车分组方案。实验中利用上海地铁一卡通刷卡数据进行了仿真验证,地铁数据中的规律用户代表上海市民的通勤需求,结果表明在较小的司机覆盖率或者谈判成功率下,拼车依旧能有很好的表现。2、针对路线规划的时间不准确难题,提出基于OpenStreetMap开源地图数据的时间最短路线规划算法。算法利用OpenStreetMap开源地图数据提取得到上海城市道路网络骨干,然后以路口为结点、路口间的连接道路为连边,路口之间地理距离为权值建立上海城市道路路口网络。基于路口网络计算得到距离最短路径,结合上海强生出租车数据进一步估算各路段的平均行驶速度和时长,得到以路段时长为权值的时间道路网络。利用估算时间与实际行驶时间的差异反复迭代优化各路段的速度和时长,最终使得出租车训练集中的所有路线估算时长之和最小,得到最优时间道路网络,根据此网络得到的时间最短路径就是各路口之间的最优路线。实验结果表明,训练集所有路线的估算时长之和与实际行驶时间之和差异较小,路线规划快速准确。3、针对通勤用户与实时用户之间的需求差异,提出基于路线相似性的实时拼车算法。首先定义了实时拼车与通勤拼车约束的差异,之后以2人实时拼车为例,对拼车模式、路线时间约束、路线相似性进行了介绍。通过简单的的排序算法就可以验证基于路线相似性的2人拼车算法的有效性。之后将问题推广到k人拼车,重新对拼车问题和约束进行了定义,并基于完全子图模型对k人拼车问题进行建模。根据k人路线相似性需求网络,利用强生出租车GPS数据集以及近似算法GSA进行仿真验证,结果显示在k人的拼车过程中,基于路线相似性的实时拼车算法表现更为出色,在较小的等待时间内得到绝大多数的拼车推荐。