移动打车服务,如滴滴、Uber、Lyft等,由于其便捷性和实时响应性,显著减少了乘客等待时间和司机巡航时间,在国内外受到广泛欢迎。移动打车服务中的关键组成模块是订单分配,其以一对一的派单形式和一对多的拼单形式为司机和乘客提供最佳匹配方式。传统的订单分配主要针对单个乘客优化,在每一时间点为当前乘客寻找最合适的司机。虽然传统方法能够实现单个乘客与司机的即时最佳匹配,但对系统内的所有司机和乘客而言可能会导致整体接单收益减少、匹配率降低;同时从长远的角度来看,可能导致系统累积接单总收益减少。近年来,出现了许多基于强化学习的订单分配方法,这些方法通常同时关注多个优化目标,能够从长远角度实现系统整体最佳匹配,但通常需要经过长期、复杂的训练过程,且当智能体过度拟合外在奖励时,会导致泛化能力较差,无法获得预期的效果。此外,传统的订单分配通常采用集中匹配,此时数据、运算、处理任务等集中完成,当订单需求量过大时,会由于运算任务复杂度高而导致计算过载,订单分配效率低下等问题。虽然现有的基于强化学习的订单分配使用多处理器对订单实现分布式处理,可以在一定程度上缓解此问题,但是,仍然面临因各处理器间的负载不平衡而导致的部分订单难以高效匹配的问题。针对以上问题,本文提出了一种轻量高效的方法,实现局部资源最佳匹配,全局资源动态调配,最大化系统整体订单匹配率,减少司机巡航成本和乘客等待时间,提高接单收益。首先,本文将订单分配视为一个在线二分图匹配问题,并据此构建分区域的多队列模型,使各区域内存在一个待匹配队列和匹配池,将空闲司机与订单请求放入待匹配队列,匹配成功的司机和订单请求放入匹配池。然后,本文提出的派单算法Ridis和拼单算法Cardis为待匹配队列构建动态网络流模型,寻找网络流图中的最小代价最大流,实现各区域内的最佳匹配。同时,为了实现全局资源的动态调配,本文设计了一种基于增量式K-means算法的车辆引导策略,使得位于多个区域交界处和等待较久的空闲司机前往订单较多的区域,实现各区域订单和司机资源的动态平衡。为了验证所提方法的效果,本文搭建了一个在线订单分配系统,并利用滴滴盖亚平台提供的数据,通过系统单日接单总收益、单日订单匹配率和乘客平均等待时间等指标比较了本文所提方法与常用任务处理算法Greedy、First Come First Serve（FCFS）和Random的效果,分区域处理与集中处理订单请求的效果,单个司机同一时间只能服务一个订单与可同时服务多个行程信息相似的订单时的效果,以及进行全局资源调配和无资源调配时的效果。结果表明,与Greedy、FCFS和Random相比,本文所提方法平均单日接单总收益分别提高了28.1%、27.8%、27.9%,单日接单数量分别提高了4.8%、5.0%和4.8%,乘客平均等待时间分别减少了53.4%、53.5%和6.2%;与集中处理相比,分四个区域处理时单日接单总收益提高了40.1%,单日订单匹配率提高了27.2%,乘客平均等待时间减少了21.2%;与服务单个订单相比,司机可以同时服务多个订单时单日接单总收益提高了82.1%,单日订单匹配率提高了41.3%,乘客平均等待时间减少了61.3%;与无资源调配时相比,有资源调配时单日接单总收益提高了4.4%,单日订单匹配率提高了4.2%,乘客平均等待时间减少了8.4%。本文所提方法关注多个优化目标,以网络流为基础设计了一种轻量式的派单与拼单算法,实现各区域内司机与订单的最佳匹配。同时,基于增量式K-means的动态资源调配关注各区域间司机与订单的动态平衡,提示可移动司机前往订单最多的区域,提高车辆利用率,进一步提升订单匹配的效率。由此,本文所提方法实现了复杂环境下更加轻量高效的订单分配方式。