车辆合乘即具有相同或相似行程的多名乘客共同乘坐同一辆车出行,是共享出行领域最为流行的一种出行模式,具有提高车辆利用率、缓解交通压力、降低出行成本、保护环境等诸多优点。近期研究表明^[11],行程相似的乘客采用合乘方式出行,可日均释放超过59%的交通运力,相当于全国日均公交和轨道交通承载人次的8倍。现有合乘出行服务主要包括Ride Sharing^[18][19][32]和Ride Hitching^[16][34][22]两种形式,本文聚焦于研究Ride Hitching合乘服务。在Ride Hitching服务中,司机和乘客通常以“发布/订阅”模式提交各自行程,司机在系统中注册合乘匹配邀请,乘客的合乘请求以订单流形式进入系统,系统基于实时订单流持续为司机推送满足合乘服务约束的合乘订单,直至司机选择到合适的合乘乘客。本文主要研究静态和动态两种场景下的发布/订阅合乘匹配算法,旨在通过设计高效的匹配算法提高合乘服务的在线匹配效率,具体内容概括如下:首先,在静态发布/订阅合乘匹配场景中,合乘订单的匹配发生在司机出行之前,常见现实应用如Grab Hitch^[22]等,系统持续为司机监控系统内的合乘订单数据流,将与司机行程最为匹配的Top-k订单推荐给司机,直到司机选出最为满意的合乘订单为止。为此,本文提出了基于订阅发布模式的静态车辆合乘算法。从新合乘订单派发、过期订单的Top-k维护两个角度实时更新合乘匹配结果。基于合乘剪枝策略、混合索引构建和建立缓冲区等方式,提出了三种合乘匹配算法:基于单体处理的合乘算法、基于混合索引的合乘算法以及两级缓存级联的合乘优化算法。其次,在动态发布/订阅合乘匹配场景中,合乘订单的匹配发生在司机出行过程中。与静态合乘匹配方式不同,动态合乘场景下的合乘匹配结果不仅与司机和乘客的行程有关,还与司机行使过程中的实时位置相关,任何时刻车辆位置的移动都有可能导致原有Top-k订单的改变。为此,本文提出了动态订阅/发布模式下的合乘匹配算法,从动态订单派发和动态过期订单维护两个方面实时护合乘订单匹配结果。基于车辆和合乘订单的时空关系,本文构建了高效时空剪枝和安全区域划分等策略,提出了基于边索引的合乘算法和基于网格索引的合乘算法两种的动态车辆合乘匹配算法。最后,在真实数据集上进行了发布/订阅合乘仿真实验。基于2017年3月的纽约市出租车的NYCTaxi的订单数据集与2016年1月的成都市Didi Hitch订单数据集,本文对所提合乘算法性能进行验证,实验结果表明,本文提出的合乘匹配算法在求解质量和求解效率方面,均好于当前主流算法。