网约车平台混合预约与即时请求的实时订单分配
《TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES》:Real-time order assignment for ride-sharing platforms with a mixture of pre-booked and on-demand requests
【字体:
大
中
小
】
时间:2026年09月20日
来源:TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 8.4
编辑推荐:
提出了一种带有预订订单重新分配的序贯两阶段分配机制。将网约车平台的混合请求分配问题建模为定制化马尔可夫决策过程。基于DDQN并采用二分图匹配的分配策略优于传统基线方法。预订渗透率和提前预订时间对系统绩效的影响呈非单调关系。
1. 引言
网约车服务,由Uber、Lyft和滴
提出了一种带有预订订单重新分配的序贯两阶段分配机制。将网约车平台的混合请求分配问题建模为定制化马尔可夫决策过程。基于DDQN并采用二分图匹配的分配策略优于传统基线方法。预订渗透率和提前预订时间对系统绩效的影响呈非单调关系。
1. 引言
网约车服务,由Uber、Lyft和滴滴等出行网络公司(TNC)提供,已从根本上改变了全球城市出行方式。用户只需在智能手机上轻点几下即可无缝叫车,平台则高效地将乘客与旗下车辆进行匹配,以满足其出行需求。通过以极低的交易成本连接乘客与司机,按需电子叫车服务提供了一种便捷、灵活且经济的出行解决方案。这些优势推动了TNC平台的快速发展和广泛应用。例如,仅Uber目前就在70个国家的超过10,000个城市运营,服务于1.56亿活跃用户,拥有570万司机构成的网络,并在2023年完成了94.5亿次出行(WallStreetZen, 2024)。
面对日益多样化的出行需求,此前专注于按需服务的TNC平台逐步扩展了业务。无论是拼车还是独享,预约用车已成为一种受欢迎的选择。与需要立即接驾的按需出行不同,预约用车允许乘客提前指定期望的出发时间和地点进行预订,从而实现更加可靠、无忧的出行规划。如今,几乎所有主流TNC平台都同时提供按需和预约用车选项,以适应广泛的用户偏好和出行场景(图1展示了Uber和滴滴的预约用车选项示例)。预约服务的引入为TNC平台带来了显著的运营优势。通过纳入预约请求,平台可以提前获知未来需求,从而实现更主动、高效的车辆调度。这种前瞻性可以显著改善系统效率和盈利能力,相较于纯按需模式具有明显优势。这些优势在拼车(或拼线)服务中尤为突出(Ke等, 2020),因为提前获取的需求信息能够增强拼车机会,促进行程串联,并提高整体车队利用率。然而,预约请求与按需请求有本质区别——预约请求通常必须得到服务保障,这对平台施加了严格的服务保证要求,可能限制上述运营收益。为确保及时接驾,车辆可能过早到达并空等,或从较远地点被调度,从而增加空驶里程和运营成本。当提前预订时间较短时,这些负面影响尤为严重,因为平台缺乏足够的灵活性来安排接驾、调整路线或组织拼车。在这种情况下,预约用车可能会降低路线灵活性、增加调度复杂性,并与按需请求争夺车辆资源,从而可能抵消提前信息的优势,甚至降低整体系统绩效。因此,有必要仔细协调预约和按需服务以平衡这些取舍,并系统性地评估在不同运营条件(如不同的预约请求渗透率、提前预订时间等)下预约服务的净影响,而这在现有文献中尚未得到充分研究。
与此同时,按需请求和预约请求的共存,加上拼车服务,为实时订单调度和车队协调引入了复杂的运营挑战。首先,一个核心挑战在于决定何时为预约行程分配和调度车辆。这些行程是提前安排的,要求在预订时间准时接驾。平台收到预约请求后,必须确定分配和调度的时机。这些时机决策将重塑车队的未来可用性和可行性窗口,从而具有长期性和全局性影响:过早分配可能因车辆空等而浪费运力,而分配过晚则可能导致接驾延迟并降低服务质量。其次,预约用车与拼车行程之间的相互作用显著增加了车辆分配和路由的复杂性。实际上,预约请求和按需请求交错到达,且各请求可能是拼车或非拼车。尽管预约请求的提前信息可以增强拼车机会并实现前瞻性规划,但也施加了严格的接驾时间窗约束,可能降低拼车灵活性并增加绕路。因此,分配和路由策略必须联合协调未来的预约承诺与实时按需需求,同时保持准时性。第三,混合预约和按需请求的实时拼车系统在订单到达时间、行程类型、上下车地点、提前揭示时间、预约和拼车占比、车辆行驶时间等方面面临巨大的不确定性。这些不确定性比纯按需环境下产生更加复杂的系统动态,进一步增加了运营决策的难度。这些挑战共同要求针对混合预约和按需拼车系统中的订单分配设计定制化算法。尽管已有研究考察了预约和按需混合运营,但大多数依赖简化假设——例如假设所有预约请求都在按需请求之前被揭示(Engelhardt等, 2023; Kawase, 2024),排除拼车(Chen等, 2024; Duan等, 2020),或仅允许同一类型请求之间拼车(Tang等, 2025)——这些假设限制了其实用价值。因此,在现实信息约束和不确定性下,联合优化混合预约和按需拼车服务的实时订单分配与拼车决策仍是一个很大程度上未被探索的领域。
为填补上述研究空白,我们考虑一个在动态环境中运营的拼车平台,其中预约请求和按需请求持续到达,且可能涉及拼车或非拼车行程。我们关注将这些异构请求实时分配给车辆车队,旨在通过利用预约行程的提前信息同时保持按需服务的灵活性来优化整体系统绩效。为解决预约决策的时机问题,我们提出了一种带重新分配的两阶段分配机制:在每个决策时段,首先将预约订单在车辆间进行分配或重新分配,然后将按需请求匹配到剩余可用车辆。该方案被建模为定制化的马尔可夫决策过程(MDP),并使用双深Q网络(DDQN)框架求解以获得有效的订单分配策略。我们进行了大量数值实验来评估不同运营条件下预约行程的影响并提取具有实践意义的管理启示。本文的主要贡献总结如下:
- 我们提出了一种带预订订单重新分配的序贯两阶段订单分配机制,并基于该机制将网约车平台的混合请求订单分配问题建模为定制化MDP。在每个决策区间内,首先将预约订单在车辆间进行分配或反复重新分配直至其预定接驾时间(预约分配阶段);随后,根据更新后的系统状态将按需订单匹配到剩余可用车辆(按需分配阶段)。定制化MDP将车辆车队建模为独立同质的智能体,将预约和按需请求分别建模为各自分配阶段的可行动作。每个阶段的集中式车队全域分配被建模为二分图匹配问题,边权由车辆的状态-动作值给出,并纳入相关的可行性和运营约束。为学习有效的非短视分配策略,我们采用双深Q网络(DDQN)来近似车辆级动作值,其中Q网络对车辆信息和订单信息使用独立编码器,并引入注意力机制以捕捉异构订单类型与车辆状态之间的复杂交互。据我们所知,这是首项同时考虑预约和按需请求以及拼车和非拼车行程的网约车平台实时订单分配问题使用强化学习的工作。
- 我们进行了大量数值实验来评估所提出的基于强化学习的框架。基于纽约市真实出租车数据开发了定制化模拟器,以模拟具有混合预约和按需请求的拼车系统运营,并作为训练和评估订单分配策略的环境。通过与基于距离的方法和非短视贪心方法进行全面的基准对比,我们的方法在总系统奖励和实时计算效率方面表现出显著提升。特别值得注意的是,所提出的带预约订单重新分配的序贯两阶段机制在预约和按需绩效之间实现了更优的平衡,相比不带重新分配的DDQN变体,总奖励提高了14%。这些详细的仿真结果有力地证明了我们的框架具有实用价值和有效性,突出了其在现实大规模条件下内化长期权衡并优化车队全域运营的能力。
- 利用所开发的框架,我们系统研究了预约请求的渗透率和提前预订时间如何影响整体系统绩效。结果揭示了总奖励的非单调模式。当提前预订时间较短(例如15分钟)时,增加预约请求的渗透率会持续降低总奖励,因为短提前量提供的预见性有限,且缓冲不足,无法将提前信息转化为准时服务和主动车队协调。即使在提前预订时间足够长(例如20-30分钟)的情况下,在低渗透率水平上增加预约渗透率也最初会减少总奖励。这揭示了稀疏的预约行程无法揭示足够的未来需求以充分利用提前规划的优势,却施加了刚性的服务保障和准时约束,优先消耗运力并压制按需绩效。这些发现揭示了一个关键权衡:预约订单虽然提供了有价值的提前信息,但也引入了额外的服务约束,可能超过其信息优势。
本文其余部分组织如下:第2节综述相关工作。第3节正式介绍混合预约和按需请求的拼车订单分配问题。第4节阐述模型公式,包括分配机制、定制化MDP模型和集中式车队全域订单分配问题。第5节详细说明基于DDQN的策略学习框架并总结所提算法。第6节讨论仿真实验和结果。最后在第7节给出结论。
2. 文献综述
2.1 网约车平台的订单分配
订单分配在拼车运营中起着关键作用,已在文献中得到了广泛研究。早期工作主要采用基于模型的优化方法,通常将车辆-订单匹配建模为线性或整数分配问题。例如,Alonso-Mora等(2017a)提出了一种实时、大容量的拼车框架,构建了请求-行程-车辆(RTV)图,将请求打包成可行的行程并连接到兼容的车辆,边权捕捉等待时间、延迟和未服务请求的惩罚。然后在该图上求解整数线性规划(ILP)以获得成本最小化的分配。重要的是,他们的框架允许尚未接驾的请求在新请求和更新的系统状态到达时被重新分配。这种重新分配策略提高了对随机运营(如乘客需求变化和交通状况)的适应性,但也需要反复构建大型RTV图并求解高维ILP。为减轻这一计算负担,Simonetto等(2019)通过限制每个车辆在每采样周期内最多匹配一个新请求来避免显式枚举所有请求组合。他们提出了一种联邦架构,集成了线性分配步骤、上下文映射模块和带取送货及时间窗约束的有容量车辆路径问题,在性能相当的情况下比Alonso-Mora等(2017a)快约四倍。然而,这些方法在很大程度上忽略了拼车系统中固有的不确定性以及序列决策的长期后果,导致每个决策时段做出短视分配。
为解决这一局限性,后续研究开始明确考虑决策过程中的不确定性和未来影响。例如,Alonso-Mora等(2017b)从历史数据中预测未来订单,并将预测的(虚拟)请求增补到Alonso-Mora等(2017a)的RTV图中,从而实现更具前瞻性的优化。Hyland和Mahmassani(2018)将自动驾驶(AV)赋能的按需出行服务(不含拼车)的运营建模为动态AV-旅行者分配问题,并通过基于智能体的仿真比较了六种分配策略;他们的基于优化的策略在新信息到达时反复重新求解短视优化问题,以捕捉系统动态和随机性。同样,Riley等(2021)提出了一种分层框架,将宏观层面的车辆重新部署与微观层面的行程-车辆分配相结合,其中微观决策通过滚动优化处理,宏观决策则依赖向量自回归(VAR)需求预测和基于MPC的整数规划进行未来需求下的重新部署。
Luo等(2023)研究了一种具有混合车队的随机拼车分配问题,并建立了两阶段随机规划模型:第一阶段决策确定车队规模和车场位置,第二阶段决策在需求不确定性下优化拼车分配方案。他们设计了结合滚动时域控制与前瞻需求估计的近似算法,以高效地求解该问题。Lyu等(2024)将网约车市场中的实时车辆-乘客匹配问题表述为基于样本平均近似的多目标随机优化问题,并开发了一种适应供需不确定性的在线算法。尽管取得了这些进展,基于模型的方法仍然面临两个根本性局限。首先,其计算成本仍然高昂。例如,每对车辆-行程的成本评估通常需要求解非平凡的路线子问题,整体优化复杂度随车队规模和订单量迅速增长,这使得大规模平台的严格实时运行变得困难。其次,解的质量在很大程度上取决于如何显式地对不确定性进行建模(例如,通过需求预测或场景生成)以及相关的建模假设。预测或建模误差可能导致系统性偏差或不稳定的分配结果,使得难以获得能够良好适应多样化且动态演变的需求模式的稳健且具有泛化能力的策略。另一方面,无模型的深度强化学习(DRL)作为一种有前景的替代方案,被应用于共享出行订单分配。它用神经网络的高效前向传播取代了基于模型的优化中复杂的计算过程。此外,DRL通过与环境的交互学习分配策略,通过价值函数隐式地捕捉不确定性和长期效应,而无需依赖显式预测模型或手工设计的不确定性表征。然而,由于大量车辆和订单构成的联合状态-动作空间带来的维度灾难,将标准强化学习算法应用于大规模共享出行仍面临严峻挑战。Xu等(2018)首次通过将分布式强化学习与二部匹配集成到网约车系统中来解决这一问题。他们训练一个神经网络来估计每辆车的价值(V),然后通过将这些价值与即时奖励相结合来计算Q值。最优分配通过最大化全局Q值获得,该问题被表述为二部匹配问题,其中行程和车辆构成两个节点集,边权重由对应的Q值给出。许多后续研究在此基础上展开。例如,Qin等(2020)用优势值取代了Q值,而Hu等(2025c)则直接训练神经网络估计Q值而非V值,从而减少了共享出行系统中奖励计算的计算负担。这一系列工作被应用于多种运营场景。Shi等(2019)研究了电动汽车运营,同时考虑订单分配和车辆充电。Wang等(2023)和Hu等(2025b)研究了带有乘客换乘的共享出行,其中乘客可以在多个换乘站点中进行选择,这些站点被嵌入到二部图中。Zhang等(2023)研究了定价和订单调度的联合优化,显式地建模了定价对未来需求的影响,并通过均值场Q学习学习定价策略。Jiang等(2025)考虑了具有灵活上下车点的共享出行,并提出了递归树生成方法来构建可行组合。在此基础上,后续工作通过采用多智能体深度强化学习技术,如QMIX(Hao和Varakantham, 2022)、COMA(Hoppe等, 2024)和均值场方法(Li等, 2019),侧重于增强智能体协调和提高训练稳定性。除了共享出行分配之外,另一个相关的研究方向是将强化学习与元启发式方法相结合,以解决路径规划和其他组合优化问题。例如,RL4CO为基于强化学习的组合优化提供了一个统一基准,涵盖多种路径规划和调度任务(Berto等, 2025),而Bi等(2026)提出了一种基于学习的构建与改进框架,以改善神经路径求解器中的约束处理。本文遵循类似的强化学习-优化整合范式,将价值函数近似与集中式二部匹配步骤相结合,使用学习到的价值作为边权重,同时强制执行运营约束。
然而,上述所有方法均专为按需订单分配而设计,没有一个考虑了拼车场景中有预定时请求的整合问题。直接将这些算法适应到混合场景并非易事。首先,现有方法无法解决预定时订单分配的时机问题,而这对平衡运营效率和服务准点率至关重要。其次,预定时请求和按需请求的共存及其异构特性大幅扩展了动作空间,如果在联合优化中进一步使二部匹配问题复杂化,从而削弱了计算效率,并使探索策略学习更加困难。
**2.2 具有混合请求的共享出行运营**
尽管在传统按需共享出行订单分配方面取得了显著进展,但关于存在预定时请求时共享出行运营的研究相对较少。特别是,Duan等(2020)考虑了混合预定时和按需订单的实时共享自动驾驶车辆(SAV)调度问题,但未纳入拼车机制。他们设计了一个用于短期订单调度的集中式调度器和一个用于长期路线规划的分布式调度器。集中式调度器采用整数线性规划(ILP)来分配按需订单、即将到来的预定时订单以及预测的未来按需订单,而分布式调度器则尝试将预定时订单插入潜在司机中,以确定能否及时服务或平台是否应拒绝这些订单。类似地,Chen等(2024)在非拼车场景中处理了实时SAV调度问题,并提出了一种基于近似动态规划(ADP)的新型求解方法。该方法使平台不仅能根据能否满足预定时间来拒绝订单,还能考虑接受订单是否能带来更高的长期利润。然而,ADP方法需要准确的环境模型,并且价值函数必须显式设定先验知识(即使具有可学习参数),与现代农业神经网络相比,其表达能力受到限制。
仅有少数研究在预定时请求和拼车同时存在的情况下研究了共享出行运营。Engelhardt等(2023)首次考虑了同时包含预定时和按需请求的拼车服务,但假设所有预定时请求至少提前一天提交。他们提出了一个离线规划模块来确定已知的预定时订单的初始车辆排班/路线,同时设计了一个在线规划模块,在按需请求实时到达时调整车辆排班并策略性地选择拒绝哪些预定时请求。Kawase(2024)聚焦于具有预定时和按需请求的SAV系统的设计与运营。他们考虑将SAV运营商的规划时段划分为多个阶段,其中所有预定时请求均假设在车队规模确定阶段被揭示,之后在后续运营阶段才观察到按需请求。他们建立了一个多阶段随机线性规划模型,在宏观层面上联合优化长期网络设计、中期车队规模策略和短期拼车匹配,将车辆和顾客视为时间扩展网络上的连续流。最近,Tang等(2025)使用两个车队和结合强化学习、启发式方法和优化的分层四层框架,探索了预约式包容性出行服务与传统按需网约车服务的集成运营。然而,他们的模型同样假设每个时期初所有预定时请求已知,且只允许预定时订单之间进行拼车。值得注意的是,Tang等(2025)的研究结论与早期研究相矛盾。他们发现提高预定时比例对平台不利,而先前的研究认为这有利于平台,因为它为平台提供了额外的提前信息。这种差异根本原因在于早期研究仅关注平台利润,导致拒绝可能引起潜在逾时的订单,结果是仅选择性地接受预定时订单。相比之下,Tang等(2025)提出的方法优先考虑客户体验,使预定时订单成为一种额外约束,因为平台必须在预定时间内为其提供服务。
与这些通常做出简化假设的先前工作不同——如提前揭示所有预定时请求、忽略拼车或限制拼车为同一类型请求——我们解决了一个更现实且具有挑战性的场景。我们考虑了一个动态共享出行系统,其中预定时和按需请求实时持续且同时到达,且两种类型均可为拼车或独享出行。这种混合请求环境引入了复杂的交互和运营不确定性,是先前模型未能充分捕捉的,因此需要新的算法方法来有效进行共享出行运营。
**3. 问题描述与挑战**
考虑一个共享出行平台,运营着一支车队,提供预定时和按需服务,每种服务均可选择拼车或独享出行。按需请求对应即时出行:顾客请求乘车并要求在当前位置被迅速接载。每位按需顾客有一个最大可容忍响应时间1(例如,5分钟);如果在此时间内未分配车辆,顾客将放弃平台。从平台的角度来看,在此时间窗口内不分配车辆等同于策略性地拒绝请求。预定时请求对应未来出行:乘客提前指定上车时间和地点。从请求提交到预定上车时间之间的间隔称为提前预订时间。与按需请求不同,预定时出行一旦接受即为有保证的预约,必须被服务。拼车允许多名乘客同时共享一辆车,而独享出行则保证车辆专用。平台以长度为Δ的离散决策区间运行(例如,每1分钟)。在每个区间内,平台收到混合的预定时和按需请求,可能涉及拼车或独享出行,并确定车辆-订单分配以优化给定运营时段(如高峰需求时段)的系统级目标,平衡客户体验和平台收入。
该订单分配问题构成了一个经典的序列决策任务。由于高维度和复杂的系统动态,使用传统优化方法显式地建立和求解该问题并非易事。一种标准方法是将该问题建模为马尔可夫决策过程(MDP),并应用强化学习(RL)算法来获得最优的订单分配策略。在基于强化学习的共享出行订单分配中,一种成熟的范式是使用Q学习方法来估计每个时间步长中每对司机-订单匹配的状态-动作(Q)值,然后求解一个二部匹配问题以最大化总Q值,从而获得车队范围的分配决策(Hu等, 2025c; Shi等, 2019; Xu等, 2018)。然而,按需和预定时请求的共存引入了复杂且微妙的运营约束,阻碍了现有强化学习流程的直接应用。首先,预定时和按需订单的车辆可行性条件存在显著差异。对于按需订单,只能分配给可用车辆:独享订单只能分配给空闲车辆,而拼车订单只能分配给有空座且车上无非拼车乘客的车辆。按需订单一旦被分配,车辆立即执行该分配并前往接载顾客。相比之下,预定时订单原则上可以分配给任何车辆,无论其当前状态如何(即可用或暂不可用),因为分配可能在预定上车时间临近时才执行。当按需和预定时请求共存时,在同一决策周期内一辆车可以同时被分配一个预定时订单和一个按需订单。这大幅扩展了动作空间,使不同类型订单的异构可行性约束相互耦合,并在每个决策周期联合优化预定时和按需订单分配时,显著增加了集中式二部匹配问题的复杂度。此外,预定时请求的存在还提出了一个关于分配决策时机的关键问题。现有的基于强化学习的框架通常专为纯按需场景设计,在此场景中订单到达后即被分配并立即执行,因此并未明确解决何时以及如何随时间分配或重新分配预定时订单的问题。
**备注1** 本文采用承诺式预定时服务设定:一旦预定时请求被接受,它将持续留在匹配池中直到执行,并且必须由平台服务。因此,不考虑预定时订单的放弃或取消。这一假设与预约产品的服务承诺一致,乘客在确认后通常期望获得可靠的接载服务。
引入乘客侧取消功能会给车辆状态转移和订单重新分配决策带来额外的不确定性,并显著增加当前框架的复杂性。我们将这一扩展留作未来研究。
## 4. 模型构建
为应对上述挑战,我们提出了一种两阶段订单分配机制,将每个决策区间内的订单分配决策划分为两个相互关联的阶段,并允许在各车辆之间重新分配已预订订单。具体而言,在每个时间区间内,平台首先在各车辆之间分配或重新分配预订订单,然后基于更新后的车辆状态分配即时订单。这种分解使平台能够分别处理各类订单的运营约束,并将两个阶段的车队级分配问题都建模为二分图匹配问题。此外,已经分配但尚未执行的预订订单可在后续区间内被重新分配,从而使平台能够利用其提前预订时间优势,随着系统条件的演变动态调整分配方案。本节详细阐述了两阶段订单分配机制,并基于该机制构建了定制的MDP模型。
### 4.1 两阶段订单分配机制
预订请求带来的一个关键挑战在于确定分配时点,即在何时分配订单以及在何时执行分配。为避免显式优化预订订单的分配时间,所提机制在每个区间对预订订单进行分配或重新分配,但将执行推迟至计划接送时间临近之时(预订订单分配阶段)。即时订单随后在预订阶段及相应的系统状态更新后进行分配并执行(即时订单分配阶段)。总体而言,平台采用了一种包含预订订单重新分配的两阶段订单分配机制:
- **阶段1(预订订单分配)**:在每个时间区间的开始,平台收集新到达的预订订单以及此前已分配但尚未执行的订单信息,评估每一对订单-车辆的收益,并在以下排他性约束下确定使全局收益最大化的车队级最优分配:(a) 每辆车最多匹配一个订单;(b) 每个订单最多分配给一辆车。每一对订单-车辆的收益评估基于状态-动作(Q)值函数,车队级最优分配通过二分图匹配获得,其细节将在后续章节中呈现。为确定何时执行分配(即派遣被分配车辆去接送客户),平台采用"尽可能晚"(ALAP)原则(H?rl et al., 2024)。在该原则下,预订订单仅在计划接送时间临近时才会被执行;否则,订单将保留在匹配池中,并随着系统状态的演进而可能在下一区间被重新分配。为此,平台会估算被分配车辆到达接送地点的最早可能时间,并将其与计划接送时间进行比较。该估算取决于车辆的当前状态,因为车辆只有在可用后才能开始接送流程。对于非拼车订单,要求车辆处于空闲状态且没有正在进行的分配任务;对于拼车订单,只要车辆处于空闲状态,或已载有拼车客户且至少还有一个空座,即视为可用。若估算到达时间落入计划接送时间的某一指定阈值范围内(例如5分钟内),或已超过该时间,则执行分配,并在车辆可用时立即派遣其去接送客户。否则,该分配不被执行,订单可能在后续区间被重新分配给其他车辆。ALAP原则背后的考量是避免车辆过早到达(否则会牺牲车队利用率),同时仍能确保预订客户获得及时接送。这种方法使车辆能够承接更多即时订单,从而在不影响客户体验的前提下提升整体车队效率。
- **阶段2(即时订单分配)**:在完成预订订单的分配与执行后,平台更新每辆车的状态以反映新分配的预订订单。然后,平台基于更新后的车辆状态(包括车辆位置、正在进行的即时订单以及已分配的预订订单)分配即时订单。对于每一对即时订单-车辆,平台评估收益,并在与阶段1相同的排他性约束下确定使全局收益最大化的车队级最优分配:(a) 每辆车最多匹配一个订单;(b) 每个订单最多分配给一辆车。与预订订单不同,即时订单在分配后即被执行,被分配的 veh 辆会立即被派遣去接送客户。因此,只有当前可用的车辆才会被考虑分配。具体而言,车辆只有处于空闲且无乘客的车上状态时,才可接送非拼车即时客户;对于拼车订单,只要车辆处于空闲状态或正在接送仍有空座的拼车客户,即视为可用。
- 脚注2:与预订订单不同,即时订单在分配后即被执行,被分配车辆立即被派遣去接送客户。因此,只有当前可行的车辆才会被考虑分配。
- 图2总结了候选即时订单-车辆对的可行性检查。每个箭头流代表一种可能的分配场景。若某候选分配会产生拼车冲突或预订冲突,则该分配被视为不可行。当非拼车即时订单被分配给已载有乘客的车辆时,即发生拼车冲突;当分配即时订单会延误某个已分配预订请求的接送,使其超过计划接送时间时,即发生预订冲突。这通过将候选分配下到达预订接送地点的最早可能时间进行估算来检查。若两类冲突均未发生,则该分配可行,车辆即开始接送即时客户。例如,底部的流对应于将一个拼车即时请求分配给一辆可用的、已被分配了一个预订拼车订单且在接受即时请求后仍有空座(即未满载)的车辆。在此情况下,通过估算预订客户的最早可能接送时间来检查预订冲突,该时间为车辆首先接送当前即时客户后再前往预订接送地点所需的时间。若该估算时间超过计划接送时间,则该即时订单分配被视为不可行。这些可行性约束被进一步纳入即时订单的车队级二分图匹配问题中。请注意,图2中所示的顺序总结了可行性检查的可能场景,而实际的接送与送达顺序并不局限于这一特定顺序。
**图2**:即时订单分配各种场景的总结。方框估算了按照所示流程后,到达已分配预订订单接送地点的最早可能时间。
**图3**展示了所提的序贯两阶段订单分配机制的工作流程。在上一区间订单分配与执行之后,司机①、②和④分别被分配了预订订单1、2和3,但尚未执行。在当前区间,一个新的预订订单4到达。在阶段1(预订订单分配)期间,所有尚未执行的预订订单(订单1、2和3)连同新到达的订单4,无论其当前可用性如何,都会被纳入重新分配考量。该过程的结果是,订单3被重新分配给司机③,新订单4被分配给司机④。此外,订单1被执行,因为当前时间已接近其计划接送时间,促使车辆①开始接送并成为不可用,无法再分配即时订单。在阶段2(即时订单分配)中,新到达的即时订单被分配给剩余可用车辆。分配过程纳入了运营约束以避免冲突,例如确保任何即时订单分配都不会危及任何预订订单的及时接送。
> **注记2**:我们强调,与同时分配预订订单和即时订单相比,两阶段方法对解质量的影响非常有限。这是因为无模型强化学习已隐式地学习了未来不确定性,而这些不确定性被编码在所学习的值函数中。因此,在即时订单分配阶段,潜在到达的即时订单的影响已被隐式考虑在内。尽管如果我们直接利用真实的确定性即时订单信息时仍存在一定的差距,但我们的方法在解质量与算法复杂度之间实现了良好的折中,满足了网约车系统的实时性要求。
>
> **注记3**:所提的包含预订订单重新分配的序贯两阶段订单分配机制在实际TNC平台中易于实施。该机制主要影响平台的内部决策与策略输入,而非司机和乘客的物理状态或体验。司机仅在分配被执行时才会被通知去接送预订客户,而客户则被告知其请求已被接受和管理,但具体司机信息仅在执行时才披露。这确保了双方都有无缝的体验,并使平台能够在系统条件变化时动态优化分配方案。类似的订单重新分配策略已被应用于现有的网约车系统。例如,Uber允许在接送乘客过程中进行车辆更换,以提升运营效率。
**图3**:包含预订订单重新分配的序贯两阶段订单分配机制工作流程。在阶段1,新到达的预订订单和此前已分配但尚未执行的预订订单均被匹配给司机,并对任何可能超时施加惩罚。预订订单的执行仅在司机可用且计划接送时间临近时才发生。在阶段2,当前即时订单基于更新后的车辆状态被分配给可用司机。任何可能导致已分配预订订单延迟接送的分配被视为不可行,并推迟到下一区间重新分配。
### 4.2 定制的MDP模型
网约车订单分配问题通常被建模为马尔可夫决策过程(MDP),其中系统状态编码车辆与订单信息,而动作对应订单-车辆分配。将该框架直接扩展到混合预订与即时运营的做法,是将所有分配视为每个决策时刻所采取的一个联合动作。然而,这种直白的建模方式会给解的设计与基于强化学习的策略训练带来显著的方法学挑战。首先,预订请求与即时请求的联合分配显著扩大了动作空间。在每个决策时刻,车辆可能被分配 (i) 仅预订订单,(ii) 仅即时订单,(iii) 两者兼有,或 (iv) 两者皆无,且这些选择必须在整个车队范围内联合考虑。这种组合式增长破坏了标准二分图匹配建模的可处理性,并增加了值函数(Q-或V-函数)精确估计的难度。由此产生的动作空间也使探索更为困难,阻碍了学习算法充分采样并识别高质量分配策略的能力。其次,两种订单类型的同时分配会在预订决策与即时决策之间产生强干扰效应,类似于多智能体强化学习(Hu et al., 2025a, Takayama and Fujita, 2025, Wen et al., 2022)中观察到的非平稳性与信用分配问题。在每个决策步骤,平台仅观察到聚合奖励,难以将表现变化归因于联合动作的特定组成部分。此外,当所有决策在单一、无差异的步骤中作出时,理想的协调模式难以表示和学习。
为克服这些困难,我们设计了一个定制的MDP,将所提的序贯两阶段分配机制嵌入决策结构之中。在每个决策时刻,先分配或重新分配预订订单,相应更新系统状态,然后基于这些更新后的车辆承诺分配即时订单。这种构造提供了两个关键优势:(i) 即时订单分配显式条件于预订订单分配之上,实现了两种订单类型之间更为协调的协作;(ii) 每辆车在每个阶段最多分配一个订单,这保留了二分图匹配建模的适用性,并促进了稳定的值函数近似。
下面将详细介绍这一特定马尔可夫决策过程(MDP)的状态、动作、转移和奖励规范。具体来说,整个规划时间范围(例如高峰时段)被离散化为 $H+1$ 个长度相同的区间 $\Delta$,记为 $\mathcal{H}=\{0,\Delta,2\Delta,\cdots,H\Delta\}$,其中每个区间由 $h$ 索引。为了捕捉每个区间内顺序的两阶段订单分配,我们将每个时间区间进一步划分为两个连续的时间步,分别用于预约订单分配和即时订单分配。这产生了一个时间步集合 $\mathcal{T}=\{0,1,2,\cdots,2H+1\}$,其中每个时间步由 $t$ 索引。具体来说,对于每个区间 $h$,时间步 $t=2h$ 和 $t=2h+1$ 分别代表预约和即时分配阶段。需要注意的是,这两个时间步不一定代表区间内的不同时间戳。相反,它们作为一种建模抽象,将分配动作分解为两个顺序决策阶段以用于优化。在我们的 MDP 公式中,拼车平台充当中央控制器,共同决定 $N$ 辆车的车队订单分配,每辆车被建模为独立的智能体,构成了一个多智能体系统。下面我们将详细介绍 MDP 公式的要素,包括状态、动作、状态转移、奖励函数、折扣因子和目标。
**状态:** 在每个时间步 $t \in \mathcal{T}$,单个智能体(车辆 $i$)的状态表示为一个元组 $s_{i,t}=(t,l_{i,t},c_i,v_{i,t},o_{i,t}^{pre},o_{i,t}^{on})$,其中 $t$ 是当前时间步,$l_{i,t}$ 是当前车辆位置,$c_i$ 是其总容量,$v_{i,t}$ 是剩余空位数,$o_{i,t}^{pre}$ 编码了已分配但尚未执行的预约订单信息,而 $o_{i,t}^{on}$ 封装了车辆 $i$ 当前正在执行的订单集合信息。预约订单指定为 $o_{i,t}^{pre}=(l_{i,t}^{pickup},l_{i,t}^{dropoff},\hat{t}_{i,t}^{pickup},k_{i,t}^{pre})$,其中 $l_{i,t}^{pickup}$ 和 $l_{i,t}^{dropoff}$ 分别是订单的上车和下车位置,$\hat{t}_{i,t}^{pickup}$ 表示预约行程的计划上车时间,$k_{i,t}^{pre}$ 指示预约订单的类型(拼车或非拼车)。进行中的订单包括车辆正在前往接送乘客或送乘客的订单。在拼车情况下,一辆车可能同时有多个进行中的订单。每个进行中的订单 $j$ 表示为 $o_{i,j,t}^{on}=(l_{i,j,t}^{pickup},l_{i,j,t}^{dropoff},\delta_{i,j,t}^{pickup},\delta_{i,j,t}^{dropoff},k_{i,j,t}^{on})$,其中 $l_{i,j,t}^{pickup}$ 和 $l_{i,j,t}^{dropoff}$ 分别是上车和下车位置,$\delta_{i,j,t}^{pickup}$ 是到上车地点的估计剩余时间,3 $\delta_{i,j,t}^{dropoff}$ 是到下车地点的估计剩余时间,$k_{i,j,t}^{on}$ 指定进行中的订单是预约还是即时,以及是拼车还是非拼车。时间 $t$ 时车辆 $i$ 的所有进行中订单集合表示为 $o_{i,t}^{on}=(o_{i,1,t}^{on},o_{i,2,t}^{on},\cdots,o_{i,m_{i,t},t}^{on})$,其中 $m_{i,t}$ 是时间 $t$ 时车辆 $i$ 的进行中订单总数。系统状态 $S_t$ 聚合了所有车辆的状态,表示为 $S_t=(s_{1,t},s_{2,t},\cdots,s_{N,t})$,其中 $N$ 是车队中车辆的总数。总体而言,在状态表示中,车辆和订单位置提供空间上下文,而估计的剩余旅行时间 $\delta_{i,j,t}^{pickup}$ 和 $\delta_{i,j,t}^{dropoff}$ 总结了时间承诺。这些变量共同构成了主要状态特征,通过它们价值函数学习分配决策的非近视后果。注意,尽管两个阶段的状态空间相同,但状态是在每个阶段执行动作后分别更新的,这将在状态转移部分详细介绍。
**动作:** 在每个时间步 $t$,单个智能体(车辆 $i$)的动作表示为 $a_{i,t}$,指定了车辆 $i$ 在待分配订单集合中的分配决策。具体来说,$a_{i,t}$ 是长度为 $m_t$ 的二进制向量,其中 $m_t$ 是时间 $t$ 待分配的订单数量,如果时间 $t$ 订单 $j$ 被分配给车辆 $i$,则 $a_{i,t}[j]=1$,否则为 0。时间 $t$ 的全车队动作,记为 $A_t \in \mathcal{A}(S_t)$,定义为所有单个车辆动作的集合:$A_t=[a_{1,t},a_{2,t},\cdots,a_{N,t}]$。在两个阶段中,动作空间的唯一区别是待分配订单集合不同,导致动作向量 $a_{i,t}$ 的长度不同。
**奖励:** 奖励函数旨在与平衡客户体验和平台收入的系统目标保持一致,并分别为即时订单分配阶段和预约订单分配阶段定义。对于即时订单分配阶段($t=2h+1, h=0,\cdots,H$),车辆 $i$ 在状态 $s_{i,t}$ 下采取动作 $a_{i,t}$ 时获得的即时奖励定义为:
(1)
$$ r_{i,t}^{on}(s_{i,t},a_{i,t}) = \begin{cases} \beta_1 + \beta_2 d_{j,t} - \beta_3 \delta_{i,j,t}^{pickup} - \beta_4 \delta_{i,j,t}^{detour} & \text{如果订单 } j \text{ 被分配} \\ 0 & \text{如果未分配订单} \end{cases} $$
其中 $\beta_1, \beta_2, \beta_3, \beta_4 \ge 0$ 是权重系数,$d_{j,t}$ 表示订单 $j$ 的行程距离,计算为从上车地点到下车地点的最短路径,$\delta_{i,j,t}^{pickup}$ 是估计的上车持续时间,$\delta_{i,j,t}^{detour}$ 代表当订单 $j$ 加入车辆 $i$ 的行程时所有进行中订单产生的额外绕路时间。4 这种奖励结构直接反映了平台的双重目标。项 $\beta_1 + \beta_2 d_{j,t}$ 捕捉了平台的收入模型,通常由基础车费加上基于距离的车费组成,从而与平台的财务利益保持一致;而 $-\beta_3 \delta_{i,j,t}^{pickup}$ 和 $-\beta_4 \delta_{i,j,t}^{detour}$ 分别惩罚延长的上车和绕路时间(由于拼车),从而促进更好的客户体验。通过适当调整权重系数,平台可以在最大化收入和增强客户满意度之间平衡权衡。
对于预约订单分配阶段($t=2h, h=0,\cdots,H$),奖励取决于执行和及时性。车辆 $i$ 在状态 $s_{i,t}$ 下采取动作 $a_{i,t}$ 时的即时奖励由下式给出:
(2)
$$ r_{i,t}^{pre}(s_{i,t},a_{i,t}) = \begin{cases} \alpha_1 + r_{i,t}^{on}(s_{i,t},a_{i,t}) & \text{如果订单 } j \text{ 被分配并准时执行} \\ -\alpha_2 (t + \delta_{i,j,t}^{pickup} - \hat{t}_{j,t}^{pickup}) + r_{i,t}^{on}(s_{i,t},a_{i,t}) & \text{如果订单 } j \text{ 被分配并延迟执行} \\ -\alpha_3 & \text{如果订单 } j \text{ 被分配但未执行且已经迟到} \\ -\alpha_4 & \text{如果订单 } j \text{ 被分配但未执行且估计会迟到} \\ 0 & \text{如果订单 } j \text{ 被分配但未执行且无潜在延迟} \\ 0 & \text{如果未分配订单} \end{cases} $$
其中 $\alpha_1, \alpha_2, \alpha_3, \alpha_4 \ge 0$ 是权重系数,$\delta_{i,j,t}^{pickup}$ 是车辆 $i$ 在时间 $t$ 开始接送订单 $j$ 时的估计上车持续时间,$\hat{t}_{j,t}^{pickup}$ 是订单 $j$ 的计划上车时间。这种奖励结构旨在反映完成预约订单的目标及其执行的及时性。项 $\alpha_1 + r^{on}(s_{i,t},a_{i,t})$ 奖励预约订单的成功且准时执行,其中执行奖励遵循与即时订单分配阶段相同的结构,以确保对两类请求进行评估的一致性。如果预约订单延迟执行(即实际上车时间超过计划上车时间),除了即时奖励外,还会施加与延迟时间成正比的惩罚,即 $-\alpha_2 (t + \delta_{i,j,t}^{pickup} - \hat{t}_{j,t}^{pickup})$,以抑制迟到取车。如果订单未执行且已经迟到(即当前时间超过计划上车时间),将施加固定惩罚 $-\alpha_3$,而如果订单未执行但估计会迟到(即最早可能的上车时间超过计划上车时间),则分配较小的惩罚 $-\alpha_4$。如果车辆未分配预约订单,或者分配了预约订单但未执行且没有潜在延迟,车辆将获得零奖励。总体而言,这种针对预约订单分配的奖励设计鼓励按时完成预约订单并惩罚延迟,在运营效率和客户满意度之间保持平衡。
**注 4** 所提出的框架通过奖励函数 (2) 中的软惩罚来处理预约取车的准时性。在该框架下,所有已接受的预约请求都保持承诺状态并最终必须得到服务,但其计划上车时间并不作为硬可行性约束施加。相反,奖励函数明确权衡了预约取车延迟与分配决策的系统级后果,包括服务即时请求的能力。这种公式避免了在变化的系统条件下过度僵化,同时实现了预约取车准时性与即时服务性能之间的战略平衡。
假设整个车队在每个阶段获得的总奖励是各车辆获得奖励的总和。令 $R_t^{pre}(S_t, A_t)$ 和 $R_t^{on}(S_t, A_t)$ 分别为在预约订单和即时订单分配阶段,车队在状态 $S_t$ 下采取动作 $A_t$ 时获得的即时奖励。它们满足:
(3)
$$ \begin{cases} R_t^{pre}(S_t, A_t) = \sum_{i=1}^{N} r_{i,t}^{pre}(s_{i,t},a_{i,t}) \\ R_t^{on}(S_t, A_t) = \sum_{i=1}^{N} r_{i,t}^{on}(s_{i,t},a_{i,t}) \end{cases} $$
**注 5** 预测的旅行时间和位置在估计即时奖励与未来奖励中扮演不同角色。预测的旅行时间明确用于方程 (1) 和 (2) 中评估即时奖励,执行即时订单分配的可行性检查,以及更新状态转移(例如 $o_{i,t}^{on}$ 中的 ALAP 执行和剩余旅行时间)。相比之下,未来奖励并不是通过旅行时间估计解析计算的。它们由动作 - 价值函数从状态 $s_{i,t}$ 和动作 $a_{i,t}$ 中学习,其中嵌入了位置和旅行时间信息。
**状态转移:** 状态转移函数定义为 $P(S_{t+1}|S_t, A_t)$,表示在采取动作 $A_t$ 后从当前状态 $S_t$ 转移到下一状态 $S_{t+1}$ 的概率。预约订单分配阶段和即时订单分配阶段的状态转移动态不同,尽管两个阶段都在相同的状态空间上运行。
在预约订单分配阶段,平台将预约订单分配或重新分配给车辆。对于时间 $t$($t=2h, h=0,\cdots,H$)给定的车辆 $i$,决策后状态取决于已分配的预约订单是立即执行还是作为未来承诺保留。如果分配被执行(即根据 ALAP 规则,车辆 $i$ 开始向预约乘客行驶的时间到了),已分配的预约订单变成进行中的订单。具体来说,订单信息从 $o_{i,t}^{pre}$ 中移除并附加到进行中订单集合 $o_{i,t}^{on}$ 中。然后车辆开始沿最短路径向预约乘客的上车地点移动。相应地,车辆位置 $l_{i,t}$ 和剩余空位数 $v_{i,t}$ 被更新,并且 $o_{i,t}^{on}$ 中的旅行时间估计(即 $\delta_{i,j,t}^{pickup}$ 和 $\delta_{i,j,t}^{dropoff}$)被调整。如果分配尚未执行(即根据 ALAP 规则,计划上车时间仍然足够远),预约订单保持“尚未执行”状态。在这种情况下,$o_{i,t}^{pre}$ 被更新以反映新分配的预约订单(或其重新分配),而车辆状态的其他组成部分,包括 $l_{i,t}, v_{i,t}$ 和 $o_{i,t}^{on}$ 保持不变。
即时订单分配阶段的状态转移更为直接,因为即时分配是立即执行的。如果时间 $t$($t=2h+1, h=0,\cdots,H$)车辆 $i$ 被分配了即时订单,新分配的订单被添加到进行中订单集合 $o_{i,t}^{on}$ 中,表示为额外的 $o_{i,j,t}^{on}$。然后车辆开始沿最短路径向该订单的上车地点移动。因此,其位置 $l_{i,t}$,剩余容量 $v_{i,t}$ 以及剩余旅行时间 $\delta_{i,j,t}^{pickup}$ 和 $\delta_{i,j,t}^{dropoff}$ 被更新。如果该阶段车辆 $i$ 未被分配即时订单,其状态仅通过进行中行程的自然进展演化(例如,车辆继续向先前分配的上车或下车地点移动)。
总体而言,每个时间步的系统状态 $S_t$ 是通过在每个阶段后聚合所有车辆的更新状态获得的。尽管两个阶段使用相同的状态空间,但状态是顺序更新的:首先在预约订单分配阶段后更新,该中间状态然后作为即时订单分配阶段的输入,其决策进一步更新系统状态(见图 3 示意图)。我们并不显式建模状态转移概率,因为我们采用无模型强化学习框架来解决 MDP 并学习最优策略。在策略学习期间,状态转移由环境提供。5
**折扣因子:** 折扣因子 $\gamma \in [0, 1]$ 决定了未来奖励与即时奖励相比的相对重要性,较小的值更重视短期收益,较大的值优先考虑长期结果。
**策略与平台目标:** 令 $\Pi(A_t|S_t)$ 表示一个中央策略,将系统状态 $S_t$ 映射到时间 $t$ 可能动作 $A_t$ 上的分布。状态 - 动作价值函数 $Q_{\Pi}(S_t, A_t)$ 代表从状态 $S_t$ 开始,采取动作 $A_t$,随后遵循策略 $\Pi$ 时平台预期的累计奖励:
(4)
$$ Q_{\Pi}(S_t, A_t) = \mathbb{E}_{\Pi}[G_t|S_t, A_t] = \mathbb{E}_{\Pi}\left[\sum_{\tau=0}^{2H+1-t} \gamma^\tau R_{t+\tau} \mid S_t, A_t\right] $$
其中 $\gamma \in [0, 1]$ 是折扣因子,$R_{t+\tau}$ 是时间 $t+\tau$ 的奖励,$H$ 是规划时间范围(即时间区间的总数)。
该平台的优化目标是确定最优集中式策略Π\*,以最大化整个规划周期内的期望折扣累积回报。由于维度灾难问题,直接优化Π在计算上是不可行的:网约车系统是一个大规模多智能体系统,平台的期望回报取决于所有智能体状态和动作的联合演化。在每个时间步,可能需要同时调度数千辆车,导致状态空间和动作空间维度过高。为应对这一挑战,我们引入以下在多智能体强化学习中常用的假设:
假设1 智能体独立性
每个智能体的奖励和状态转移概率仅取决于其自身的状态和动作,而不取决于其他智能体的状态和动作。
注6
我们强调,采用智能体独立性假设仅为便于阐述;本文的重点是设计一种能够应对预订订单与即时订单混合带来的挑战的订单分配机制,并将其与现有的MARL方法相结合。具体而言,开发处理预订订单与即时请求共存、共享行程与非共享行程共存的管理方案,构成了我们工作的核心技术挑战和关键贡献。我们所提出的方法本质上具有即插即用的特性:只需对MDP建模进行小幅修改,即可无缝融入各种MARL框架,无论这些框架是否依赖智能体独立性假设。因此,在当前建模中省略智能体间的相互依赖关系并不会削弱我们的主要贡献,因为该框架可以轻松地扩展到考虑智能体间相互依赖的MARL方法,包括先前研究中提出的高级MARL方法(Hao和Varakantham, 2022, Hoppe等人, 2024, Li等人, 2019, Zhao和Li, 2025b)。
假设1意味着每辆车的奖励反馈和状态转移独立于其他车辆的状态和动作。在独立性假设下,系统的状态转移函数可以分解为各智能体转移概率的乘积:
(5) P(S_{t+1} | S_t, A_t) = ∏_{i=1}^{N} p(s_{i,t+1} | s_{i,t}, a_{i,t})
其中 p(s_{i,t+1} | s_{i,t}, a_{i,t}) 表示车辆i的转移概率。因此,平台的期望回报可以分解为各智能体期望回报之和:
(6) Q_Π(S_t, A_t) = ∑_{i=1}^{N} q_{π_i}(s_{i,t}, a_{i,t})
其中 Q_{π_i}(s_{i,t}, a_{i,t}) 是智能体i在其策略π_i下的期望回报。同质性假设进一步简化了模型,使所有智能体可以共享一个公共策略π(a_{i,t} | s_{i,t})和状态-动作价值函数q_π(a_{i,t} | s_{i,t}),从而有:
(7) Q_Π(S_t, A_t) = ∑_{i=1}^{N} q_π(s_{i,t}, a_{i,t})
在这种情况下,优化全局集中式策略Π等价于确定一个策略π\*,在满足每个决策周期车队整体运营约束的同时,最大化平台在整个规划周期内的期望回报:
(8) π\* = arg max_π E_π[∑_{i=1}^{N} ∑_{τ=0}^{2H+1-t} γ^τ r_{i,t+τ}] = arg max_π ∑_{i=1}^{N} q_π(s_{i,t}, a_{i,t}), ? s_{i,t}, a_{i,t}
需要注意的是,虽然这种分解实现了可扩展的策略学习,但它并不能内在地在分散式策略π中强制施加车队整体的运营约束,例如确保每辆车最多分配一个订单以及每个订单最多分配给一辆车。在原始的集中式建模(4)中,这些约束通过将不可行动作的概率设为零来自然地纳入策略Π,即如果A_t违反运营约束,则Π(A_t | S_t) = 0。然而,在分别优化各智能体策略和价值函数时,如果每个智能体独立行动,这些全局约束可能会被违反。为了解决这一问题,平台聚合所有可能的车辆-订单对的状态-动作价值q_π(s_{i,t}, a_{i,t}),并在每个决策周期通过二部图匹配求解集中式订单分配问题。这确保了所得的车队整体分配方案在学习到的价值函数下是最优的,同时满足运营约束。平台集中式车队整体订单分配的详细内容见4.3节。
4.3 平台的集中式车队整体订单分配
最优的车队整体订单分配可以通过集中方式求解一个带权二部图匹配问题来确定。考虑图4所示的二部图。在每个时间步t,设V_t = {v_1, v_2, …, v_N}表示代表N辆车的顶点集合,设O_t = {o_1, o_2, …, o_{m_t}}表示代表待分配的m_t个订单的顶点集合。定义决策变量X = {x_{ij} | i = 1, …, N; j = 1, …, m_t},其中x_{ij}是二元变量,当订单j分配给车辆i时取1,否则取0。二部图中v_i和o_j之间的边表示车辆i被分配订单j。连接v_i和o_j的边的权重w_t(i, j)量化了在决策时间步t将订单j分配给车辆i对全局目标(8)的贡献。对于可行分配,该权重由车辆i在当前状态s_{i,t}下执行分配订单j动作(即a_{i,t}[j] = 1且对所有j' ≠ j有a_{i,t}[j'] = 0)的状态-动作价值q_π(s_{i,t}, a_{i,t})给出。对于不可行分配,权重被设为一个足够大的负值(-W),以确保此类车辆-订单对不会被选择。特别地,在预订订单分配阶段,所有订单对车辆而言都是可行的,无论其当前状态如何,因为它们可能不会立即执行。因此,w_t(i, j) = q_π(s_{i,t}, a_{i,t}), ? t = 2h, h = 0, …, H。也就是说,每个预订订单-车辆对(i, j)都被保留在预订二部图中,在此阶段不施加硬性可行性约束。潜在的接驾延迟则通过预订奖励来体现,并反映在相应的状态-动作价值中。另一方面,在即时分配阶段,订单只能分配给当前可以接驾的车辆,因为订单在分配后立即执行。车辆-订单分配的可行性取决于车辆状态和订单类型,这在图2中进行了总结。形式化地,在即时分配阶段(t = 2h+1, h = 0, …, H)二部图的边权重为:
(9) w_t(i, j) = { q_π(s_{i,t}, a_{i,t}), 如果将订单j分配给车辆i是可行的; -W, 否则 }
其中a_{i,t}[j] = 1且对所有j' ≠ j有a_{i,t}[j'] = 0。式(9)表明,不可行的即时订单车辆-订单对通过将其边权重赋予足够大的负值而被明确地剪枝。给定边权重,决策时间步t的集中式车队整体订单分配问题可以建模为:
(10a) max_X ∑_{i=1}^{N} ∑_{j=1}^{m_t} w_t(i, j) · x_{ij}
(10b) s.t. ∑_{j=1}^{m_t} x_{ij} ≤ 1, ? i = 1, …, N
(10c) ∑_{i=1}^{N} x_{ij} ≤ 1, ? j = 1, …, m_t
(10d) x_{ij} ∈ {0, 1}, ? i = 1, …, N, ? j = 1, …, m_t
(10e) ∑_{i=1}^{N} ∑_{j=1}^{m_t} x_{ij} = min{m_t, N}, 如果t = 2h, h = 0, …, H
图4. 二部图的示意说明。
目标函数(10a)通过对所有已分配的车辆-订单对的贡献求和来最大化平台的总期望回报。约束(10b)确保在每个决策周期中每辆车最多分配一个订单,约束(10c)保证每个订单最多匹配一辆车。约束(10d)强制执行分配变量的二元性质。这个二部图匹配问题在每个决策轮次中执行两次:一次在预订订单分配阶段,另一次在即时分配阶段,各自对不同阶段的权重参数w_t(i, j)有不同的定义。此外,约束(10e)仅在集中式预订订单分配阶段的二部图匹配问题(即在决策步t = 2h)中施加。它要求在此阶段,已分配的预订订单数量应最大化至车队规模与预订订单数中较小者的程度,也就是说,当N ≥ m_t时,所有预订订单都应被分配或重新分配。当m_t > N时,未分配的预订请求将保留在匹配池中,并在后续区间中重新考虑,直到最终被执行。这防止了平台通过简单地不分配预订请求来策略性地拒绝它们,并与预约行程的服务承诺相一致。总体而言,二部图匹配建模(10)构成一个整数线性规划问题,可以通过Kuhn-Munkres(KM)算法(Munkres, 1957)在多项式时间内求解。它保证了在每个时间步,车队整体运营约束得到满足,并且分配方案在当前的状态-动作价值函数下是全局最优的。
5. 价值函数近似与策略学习
策略学习过程旨在获得一个高质量的、具有泛化能力的最优动作价值(Q)函数近似。为实现这一目标,我们使用深度神经网络来近似单辆车的最优状态-动作价值函数,并采用成熟的Double Deep Q-learning(DDQN)算法来训练网络并导出最优策略。下面我们详细介绍网络训练和策略学习流程的管线。
不失一般性,设Q\*(·)为平台的最优全局状态-动作价值函数。策略学习的目标是找到一个好的逼近器Q?\*(·),以最小化真实Q值与逼近Q值之间的期望平方误差。由于真实的动作价值函数未知,基于贝尔曼最优方程(Sutton等人, 1998, Zhao, 2025)构建了Q\*(S, A)的备份估计。这导致了如下的损失函数,可以视为函数逼近下的贝尔曼最优误差的平方:
(11) J = E[(R + γ max_{A'∈A(S')} Q?\*(S', A') - Q?\*(S, A))^2]
其中S和A分别表示车队整体状态和动作,R是总即时奖励,S'是下一状态。在最大化项中,A'表示下一状态下的车队整体动作。括号内的前两项构成贝尔曼最优备份,即即时奖励与在采取最优车队整体动作时下一状态估计动作价值之和。括号内的完整表达式是该备份与当前逼近Q?\*(S, A)之间的贝尔曼最优误差。
然而,由于系统涉及数千辆车和数百个订单,状态维度极高,直接逼近全局动作价值函数具有挑战性。为解决这一问题,我们提出对单智能体状态的最优动作价值函数进行近似。基于独立性和同质性假设,平台的最优全局动作价值函数可以分解为各车辆最优动作价值函数之和:
(12) Q\*(S_t, A_t) = ∑_{i=1}^{N} q\*(s_{i,t}, a_{i,t})
其中q\*(·)是单辆车的最优动作价值函数。我们引入一个神经网络q?_NN(·)来逼近q\*(·)。损失函数(11)可以重写为:
(13) J = E[((∑_{i=1}^{N} r_i + γ ∑_{i=1}^{N} q?_NN(s'_i, a*_i; θ) - ∑_{i=1}^{N} q?_NN(s_i, a_i; θ))^2)]
其中s_i、a_i、r_i和s'_i分别是第i辆车的状态、动作、即时奖励和下一状态,a*_i是通过求解二部图匹配问题(10)获得的车第i辆车的最优动作,θ是网络参数。
由于单辆车被建模为独立且同质的智能体,策略学习等价于训练一个单独的神经网络q?_NN(·)来最小化针对单智能体的以下损失函数:
(14) J = E[(r + γ q?_NN(s', a*; θ) - q?_NN(s, a; θ))^2]
其中(s, a, r, s')是一条记录了智能体状态、动作、即时奖励和下一状态的经验,a*是从集中式车队整体订单分配中推导出的该智能体的最优动作。通过与环境交互,生成并收集各智能体的经验。在每个决策周期,平台观测当前系统状态S = [s_1, …, s_N],并根据行为策略选择一个车队整体可行的动作A = [a_1, …, a_N]。执行动作后,系统转移到下一状态S' = [s'_1, …, s'_N]并获得相应的即时奖励R = [r_1, …, r_N]。然后,每个智能体的经验被记录为一个四元组(s_i, a_i, r_i, s'_i)并存储以备后续训练使用。这些经验被聚合到所有车辆中,并通过随机梯度下降来训练神经网络。
为了稳定训练并提高学习效率,我们遵循标准的DDQN流程,引入了经验回放和目标网络。评估网络以参数θ_E表示,在每个训练步骤更新;目标网络以参数θ_T表示,更新频率较低,每隔C步复制一次评估网络的参数。在计算历史经验(s_i, a_i, r_i, s'_i)的TD目标时,使用评估网络计算下一状态的二部图匹配问题的边权重,具体如下:
(15) w(i, j) = { q?_NN(s'_i, a_{i,j}; θ_E), 如果在状态s'_i中将订单j分配给车辆i是可行的; -W, 否则 }
其中a_{i,j}表示车辆i对应分配订单j的动作向量。基于计算出的边权重,我们求解下一状态的集中式车队整体订单分配问题并获得最优分配。设a*_i为第i辆车在下一状态的最优动作。然后每个智能体的TD目标计算为:
(16) y_i = r_i + γ q?_NN(s'_i, a*_i; θ_T)
其中r_i是即时奖励,s'_i是下一状态,a*_i是第i辆车在下一状态的最优动作。用于更新评估网络的损失函数为:
(17) J = E[(y_i - q?_NN(s_i, a_i; θ_E))^2]
其中期望是在从回放缓冲区采样的小批量经验(s_i, a_i, r_i, s'_i)上取的。
总体而言,我们采用ε-贪心行为策略来执行订单分配并在在线训练期间收集经验。
在每个决策时刻,以概率 $1-\epsilon$,由求解集中式车队全域订单分配问题(10)并利用当前的 Q-网络估计值来确定车队全域的订单分配;以概率 $\epsilon$,每辆车被随机分配一个可行动作。$\epsilon$ 的初始值为 0.99,并在每次训练步后乘以一个衰减因子逐渐退火至 0.0005,从而在保持充分探索的同时,使策略能够越来越多地利用已学习到的动作价值。完整的 Q-网络训练与策略学习过程算法见算法 1。该算法将个体智能体的动作-价值函数逼近(Q 学习)与集中式二部图匹配相结合,以推导最优策略。训练过程利用经验回放和目标网络来稳定学习并提高数据效率。测试期间,关闭神经网络训练与 $\epsilon$-贪心探索,车队按照已学习的最优策略运行。
下载:下载高分辨率图片(183KB)
下载:下载全尺寸图片
算法 1. 基于 DDQN 的策略学习完整算法。
6. 实验
本节通过全面实验评估所提出的基于强化学习的实时拼车订单分配框架,该框架同时处理预订与即时请求。由于该算法是无模型的,我们开发了一个高保真模拟器来模拟拼车系统的运行环境,并纳入两种订单类型。该模拟器作为策略学习生成轨迹的环境,并用于在真实数据上评估算法的有效性。本节其余部分介绍了模拟器设计、实验设置以及展示所提方法收敛性与性能的结果。
6.1 模拟器设计
我们开发了一个定制化的模块化模拟器,以模拟同时服务预订请求与即时请求的拼车平台。时间被离散化为以一分钟为单位的决策时刻。在每一时刻,模拟器执行以下操作:(i) 通过 Q-网络评估车-单对的价值;(ii) 通过二部图匹配计算集中式车队全域分配;(iii) 根据参数化绩效模型发出即时奖励;(iv) 通过更新车辆与请求状态将系统转移至下一状态。该模拟器由以下相互关联的模块组成:
- 需求生成:我们使用纽约市黄色出租车数据集(Taxi and Commission, n.d.),选取 2024 年 7 月 1 日曼哈顿地区 18:00 至 20:00 之间的行程记录,以模拟拼车平台的高峰期运营。前 1 小时记录用于训练分配策略,涵盖 4870 笔由黄色车牌出租车完成的街头拦客行程和预先安排行程,每条记录包含上车时间与地点、下车时间与地点。保留记录的行程平均时长(即从上车到下车的时间)约为 17.2 分钟。在训练过程中,每个 episode 对应由前 1 小时记录构建的一个小时规划窗口。即时请求在训练窗口内随机到达,分配后立即派单。我们将每条历史行程记录中记录的上车时间视为即时请求的到达时间。与之相对,预订请求会提前发布,其计划上车时间发生在公布后的固定提前预订时间(例如 30 分钟)之后。当某条记录被指定为预订请求时,我们将其记录的上车时间视为计划上车时间。为确保每个预订请求都在一小时的训练窗口内被发布,我们仅从计划上车时间在后 30 分钟的记录中选择预订请求。在每个训练 episode 中,提前预订时间从 $U(10, 30)$ 分钟均匀分布中采样,而后 30 分钟时段内记录中比例为 $P_{\text{prebook}}$ 的记录被指定为预订请求;其余记录均视为即时请求。因此,每个预订请求在公布时进入匹配池,即在其计划上车时间前按提前预订时间的时长进入匹配池。尽管预订客户的计划上车时间仅出现在训练 episode 的后 30 分钟内,但其请求可能在头 30 分钟内就已经存在于匹配池中,并影响即时订单的分配决策。具体而言,即时客户最大可容忍的响应时间为 5 分钟;如果他们在到达后 5 分钟内未被分配车辆,他们将离开平台,需求即告流失。与之相反,预订订单由于服务的预订性质,保证会被服务。在整个 episode 期间,比例为 $P_{\text{pooling}}$ 的请求被指定为可拼车,其余为不可拼车。这些比例对即时与预订两类订单一致适用。为引入随机性并促进泛化,在每个训练 episode 中,$P_{\text{prebook}}$ 与 $P_{\text{pooling}}$ 分别从 $U(0, 1)$ 中独立采样,并依据这些比例从筛选后的历史记录中合成相应的请求流。测试时,我们使用完整需求流模拟一个两小时的运营窗口。同样地,预订订单计划在 30 分钟后被接起,以确保每个预订请求都在运营窗口内被发布。为评估混合请求系统稳态下的表现,我们剔除前 30 分钟作为预热期,在此期间车队从空闲状态被激活且预订上车尚未开始;同时剔除最后 30 分钟作为尾部期,在此期间剩余行程可能因有限的时间窗口被截断,且新的预订请求可能不再被发布(例如提前预订时间为 30 分钟时)。随后,使用剩余的中间一小时订单(即 [30, 90] 分钟区间)评估性能。
- 车队与状态表示:我们考虑一支 1000 辆车的车队,每个 episode 开始时它们随机分布于曼哈顿各处。每辆车由一个紧凑的状态向量表示,编码当前位置、剩余座位容量、正在进行的行程、任何关联的预订分配,以及一组携带其目的地和剩余旅行时间的活跃乘客列表。所有状态均以适合输入 Q-网络的向量化形式表示。
- 旅行时间与路由规划:为捕捉真实的道路网络动态,模拟器向本地托管的开源路由机器(OSRM)服务器查询起点-终点旅行时间和距离。对于拼车服务,该模块构建可行的接送序列,求解一个小型组合子问题(固定上车起点、优化排序剩余停靠点的旅行商问题变体),并返回结果路线与各路段旅行时间,以驱动后续状态转移。
- 集中式决策与分配:该模块使用 Q-网络对长期收益的估计值,计算二部图中所有车-单对的边权重。根据车辆与订单状态(可用性、座位容量、时间一致性、拼车的路由可行性以及拼车兼容性)对每个候选对进行可行性检查。不可行分配通过赋予足够大的负边权被过滤掉,确保被优化器排除。随后,通过求解该加权图上的最大权二部图匹配问题(10)获得车队全域最优订单分配。在训练期间,采用 $\epsilon$-贪心探索策略:以概率 $1-\epsilon$,如上所述计算分配;以概率 $\epsilon$,每辆车被随机分配一个可行动作。
- 平台动态与状态转移:根据所选分配,该模块将系统推进一个时刻,并对预订订单与即时订单采用不同的方式更新状态。预订订单遵循尽可能晚原则(ALAP):模拟器决定是在当前时刻执行已分配的预订接起,还是推迟至稍后时刻以实现准时到达。相比之下,即时订单在分配后立即执行。系统状态(车辆可用性、路线、容量及请求池)根据各订单类型相应更新,从而实现从当前状态与动作到下一状态的马尔可夫转移。
- 奖励与日志记录:模拟器对即时订单与预订订单分别采用独立的参数化奖励函数(公式 (1) 和 (2)),以捕捉关键运营权衡。所有奖励在 episode 内指数折扣。平台按订单类型(预订/即时、拼车/非拼车)记录丰富的、细粒度的绩效统计信息,包括预订订单的迟到率与平均接起延迟、即时订单的平均接起时间、拼车订单的平均绕路时间、车辆空闲时间以及平台利润。这些统计数据支持对已学习策略的离线评估以及训练期间的监控。
6.2 算法收敛性与性能
每辆车被建模为一个独立智能体,其动作-价值(Q)函数由一个共享神经网络近似。Q-网络架构遵循 Zhao 和 Li(2026)的设计。具体而言,两个独立编码器分别从司机信息和订单信息中提取特征,随后通过一个 QK-注意力模块(Zhao et al., 2025)基于所得嵌入估计 Q 值。为适配没有预订订单的车辆,使用可训练向量进行填充。详细网络结构见图 5,更多细节可参见(Zhao and Li, 2025c, Zhao and Li, 2026)。对于奖励函数,即时奖励函数中的 $\beta$ 参数在拼车服务中具有直接运营含义。我们参考拼车调度研究中常用奖励结构(Hu et al., 2025b, Zhao and Li, 2025c)以及真实的运价与时间成本统计来校准其取值。相比之下,预订奖励函数中的 $\alpha$ 参数决定了平台对及时、可靠预订服务的相对侧重。由于在混合预订与即时场景下,这些优先级参数没有可直接迁移的经验值,我们将它们的取值设为反映平台对预订服务的预期优先级,并在附录 B 中进一步检验系统性能对 $\alpha$ 参数的敏感性。模型配置汇总见表格 1。
下载:下载高分辨率图片(454KB)
下载:下载全尺寸图片
图 5. Q-网络架构(Zhao and Li, 2026)。
表格 1. 模型参数简要汇总。
配置 / 我们的设置
配置 / 我们的设置
批大小 / 512
探索率 / 0.99 → 0.0005
优化器 / Adam
训练 episode 数 / 1000
调度器 / ExponentialLR
智能体(司机)数 / 1000
初始学习率 / 0.0005
参数总数 / 157,200
公式 (1) 中 $(\beta_1, \beta_2, \beta_3, \beta_4)$ / (5, 3, 4, 2)
公式 (2) 中 $(\alpha_1, \alpha_2, \alpha_3, \alpha_4)$ / (10, 3, 1, 1)
模型训练使用 PyTorch 框架在配备 Intel(R) Core(TM) i7-14700KF 处理器和 NVIDIA RTX 4080 显卡、运行 Windows 11 的工作站上完成。训练期间模型占用约 1.1 GB 显存。
图 6 展示了基于 DDQN 的方法在有和无所提出的两阶段分配机制下的学习曲线。在不含该机制的变体中,预订订单被视为即时订单:它们在收到后即被分配并执行,车辆提前到达上车点必须等待至计划接起时间。学习曲线来自五次独立运行,以减轻随机初始化、订单采样及其他随机因素造成的干扰。每次运行使用平滑因子为 0.1 的指数移动平均进行平滑;实线表示跨运行的均值,阴影带表示跨运行的变异。如图 6 所示,累积奖励稳步增加,并在约 600 个 episode 后趋于稳定,表明所提算法的收敛性以及有效订单分配策略的成功学习。
下载:下载高分辨率图片(337KB)
下载:下载全尺寸图片
图 6. 含与不含所提机制的基于 DDQN 方法的学习曲线。实线表示五次独立运行经平滑因子为 0.1 的指数移动平均后的均值,阴影带表示跨运行的变异。
为评估所提基于强化学习方法的有效性,我们将其与两种基线方法进行比较:(i) 基于距离的方法和 (ii) 近视贪心方法。在所有方法中,车队全域订单分配均通过求解二部图匹配问题(10)并采用不同边权来确定。基于距离的方法在每个决策时刻通过用车接距离作为边权,最小化车辆与乘客之间的总上车距离。近视贪心方法通过用即时奖励作为边权,最大化总即时奖励。为进一步评估所提两阶段订单分配机制的影响,我们评估所有三种方法在有和无该机制下的表现。在不含该机制的情况下,预订订单通过一次性固定提前期分配处理:预订请求仅在剩余时间到计划上车时间不超过固定提前期 $T_{\text{lead}}$ 时才进入匹配池,且一旦分配即执行,不再重新分配。
如果车辆提前到达取车点,则必须等到计划取车时间才能出发。而相比之下,在所提出的机制下,预约请求一旦披露便进入匹配池,可在不同决策阶段进行分配和重新分配,并且仅在平台决定车辆应出发前往取车点时才执行取车。
为了对混合请求系统进行公平且稳健的评估,我们模拟了一个两小时的时段,并使用订单的中间一小时(第30至90分钟)来评估所有变体,以消除预热期和尾部效应的影响。主要比较采用预约比例$P_{\text{prebook}}=50\%$和拼车比例$P_{\text{pooling}}=50\%$。订单按照这些比例从历史出租车行程记录中抽样,所有预约订单均被指定为固定的30分钟提前预订时间。我们分别对基于DDQN的方法、基于距离的方法和短视贪心方法进行了测试,其中基于DDQN的方法为文献8中提出的方法。
在没有所提出机制的情况下(单次固定提前量分配),我们测试了不同的固定提前量$T_{\text{lead}} \in \{5, 10, 15, 30\}$分钟。特别地,当$T_{\text{lead}}=30$分钟时,由于提前预订时间为30分钟,预约订单在出现时即被分配并执行。对于每个变体,实验重复多次以确保评估的稳健性。
图7总结了在不同固定提前量下,三种分配方法在有无重新分配机制下即时需求奖励、预约奖励和总奖励的对比。结果从两个方面展示了我们所提框架的优越性。首先,在三种分配方法之间进行比较,基于DDQN的方法在总奖励方面始终优于短视贪心和基于距离的基线方法。例如,在所提出的机制下,DDQN实现总奖励45.73,而短视贪心方法为38.98,基于距离的方法为-1.86。其次,比较有无所提出重新分配机制的DDQN,带有重新分配的前置分配相比单次固定提前量分配带来了显著的奖励提升。所提出的机制实现了最高的总奖励(45.73),而没有重新分配的最佳单次DDQN变体在$T_{\text{lead}}=30$分钟时达到40.07。此外,单次分配中的固定提前量存在明显的权衡:较短的提前量通过减少车辆提前空闲来增加即时需求奖励,但会因预留较少时间来协调预约行程而大幅降低预约奖励。特别是,当$T_{\text{lead}}$较短时(例如5或10分钟),预约奖励变为负值,且这种恶化程度在短视贪心和基于距离的方法下比在DDQN下严重得多。预约性能的损失抵消了即时需求奖励的提升,导致总奖励降低(见图7)。
图7. 在所提出的重新分配机制与固定提前量单次分配变体($T_{\text{lead}}=5, 10, 15, 30$分钟)下即时需求奖励、预约奖励和总奖励的对比。
为了进一步理解驱动我们所提方法优越性的内在机制,我们比较了有无所提出机制下不同方法按订单类型的不同影响。评估了与平台和客户利益相关的性能指标,包括总奖励、即时需求和预约订单的奖励、计算时间、平台利润、即时需求订单的服务率和平均取车时间、预约订单的迟到率和迟到时间、拼车行程的平均绕行时间。表2报告了所提出的机制和对应的一次性分配基准($T_{\text{lead}}=30$分钟)在不同订单类型下的详细性能指标。
表2. 在$P_{\text{prebook}}=50\%$和$P_{\text{pooling}}=50\%$条件下不同方法的综合比较。指标计算自两小时模拟的中间小时评估窗口(第30至90分钟)。粗体表示最佳结果,下划线表示次佳结果。
| 指标 | 方法(有无所提出机制) |
|------|------|
| | 有机制:DDQN | 有机制:短视贪心 | 有机制:基于距离 | 无机制($T_{\text{lead}}=30$):DDQN | 无机制($T_{\text{lead}}=30$):短视贪心 | 无机制($T_{\text{lead}}=30$):基于距离 |
| **整体性能** |
| 总奖励 | **45.73** | 38.98 | -1.86 | 40.07 | 35.10 | 6.26 |
| 即时需求奖励 | 25.67 | **36.07** | 21.83 | 17.30 | 23.44 | 16.65 |
| 预约奖励 | 20.06 | 2.91 | -23.69 | **22.77** | 11.66 | -10.39 |
| 平台利润 | 68.47 | **74.47** | 60.92 | 50.95 | 59.21 | 48.84 |
| 总模拟时间(分钟) | 4.80 | 2537.68 | 6.00 | 4.80 | 2503.73 | 4.80 |
| 平均绕行时间(分钟) | 13.57 | **7.17** | 16.15 | 13.59 | 17.95 | 19.89 |
| **拼车与预约订单** |
| 服务率(%) | **100** | 99.49 | 98.97 | **100** | 98.36 | 99.71 |
| 迟到率(%) | 20.00 | 36.99 | 69.77 | **6.56** | 17.14 | 35.51 |
| 平均迟到时间(分钟) | 2.15 | 5.58 | 19.26 | **0.78** | 2.33 | 12.95 |
| **非拼车与预约订单** |
| 服务率(%) | **100** | 74.26 | 44.29 | **100** | 78.99 | 47.71 |
| 迟到率(%) | 33.21 | 89.58 | 88.31 | 33.22 | 60.54 | 95.47 |
| 平均迟到时间(分钟) | **4.25** | 26.23 | 45.20 | 16.63 | 6.90 | 34.82 |
| **拼车与即时需求订单** |
| 服务率(%) | 91.45 | **99.52** | 80.92 | 51.34 | 74.25 | 49.73 |
| 平均取车时间(分钟) | 5.35 | **2.19** | 8.33 | 6.46 | 5.58 | 8.61 |
| **非拼车与即时需求订单** |
| 服务率(%) | 82.05 | **99.12** | 80.56 | 39.79 | 62.80 | 58.81 |
| 平均取车时间(分钟) | 5.19 | **3.06** | 8.47 | 7.81 | 7.59 | 8.58 |
对于预约拼车订单(表2第二块,"拼车与预约订单"),没有所提出机制的DDQN提供了最可靠的服务,实现了100%的服务率、最低的迟到率(6.56%)和最短的平均取车延迟(0.78分钟)。启用预约订单重新分配后,迟到情况有所增加(迟到率20.00%,平均取车延迟2.15分钟),这是因为延迟和重新分配利用了时间灵活性,但增加了错过计划取车时间的风险。尽管存在这种权衡,在所提出的机制下,DDQN仍然实现了最强的服务率,并且迟到率明显低于短视贪心和基于距离的方法,这突显了基于长期动作价值的集中式分配的优势。
对于非拼车预约订单(第三块,"非拼车与预约订单"),我们的基于DDQN的方法始终表现最佳,在两种设置下均实现100%的服务率。所提出的机制进一步提高了准点率:平均迟到时间从16.63分钟(无机制)降至4.25分钟(有机制),迟到率略有降低(33.21%对比33.22%)。这与重新分配的预期效果一致:原本在等待计划取车时空闲的车辆可以在取车前被更有效地部署,从而提高车队利用率,改善依赖专属运力保障的非拼车预约订单的准点性。
另一方面,对于即时需求订单(拼车和非拼车;第四和第五块,"拼车与即时需求订单"和"非拼车与即时需求订单"),带有所提出机制的短视贪心方法实现了最高的服务率和最短的取车时间,而带有该机制的基于DDQN的方法通常排名第二。这是因为基于DDQN的策略显式地保留车辆运力以满足未来预约行程的承诺,牺牲了部分即时响应性以换取来自预约订单的更高长期回报,这反过来降低了即时需求客户的服务率并延长了取车时间(相较于短视贪心方法)。同时,预约重新分配在ALAP(尽可能晚到达)原则下有效防止了车辆过早到达并等待到计划取车时间,增加了即时需求订单分配的车队可用性,从而提高了接单率并缩短了取车时间。在没有重新分配的情况下,所有方法的即时需求性能均有所下降(例如,DDQN的拼车即时需求服务率从91.45%降至51.34%),这突显了该机制对于释放即时需求行程更高吞吐量的关键作用。
基于订单类型分析,我们已识别出不同方法和所提出机制在预约和即时需求订单方面的不同侧重点。这些影响与图7中的聚合奖励模式一致,并转化为不同的系统级性能表现(见表2第一块,"整体性能")。总体而言,主要发现总结如下:
- 基于DDQN的方法能够更好地平衡即时需求和预约订单的奖励,在两种设置下均实现了高于两个基线方法的总奖励。这一优势源于在集中式分配中使用状态-动作(Q)值来内化长期影响,特别是对于可能延迟执行且奖励延迟的预约订单而言。通过纳入反映未来收益的Q值,DDQN可以选择即时奖励为零或较低但预期长期回报较高的预约分配(例如避免迟到取车或实现高效拼车),从而在捕获即时需求机会的同时提高预约奖励。相比之下,短视贪心基线方法在每个阶段最大化即时奖励,实现了较高的即时需求奖励但预约性能较弱。这反映了其过度优先处理即时执行订单而忽视长期影响的倾向。
- 所提出的两阶段机制与预约订单重新分配显著提升了即时需求收益,同时保持了强劲的预约性能。与$T_{\text{lead}}=30$分钟下无重新分配的单次分配相比,带有重新分配机制的DDQN将总奖励从40.07提高到45.73(提升14%)。这一提升主要由即时需求奖励的大幅增加(从17.30到25.67)驱动,而预约奖励的减少相对温和(从22.77到20.06)。与依赖手动选择提前量来权衡即时需求可用性和预约准点性的单次分配不同,重新分配机制使这种时序决策具有自适应能力。它允许平台尽早利用提前信息,随着车队状态变化调整分配,并仅在需要时执行预约取车。这大幅提升了即时需求吞吐量和整体车队利用率,实现了更高的综合性能。
- 基于DDQN的方法计算高效,适用于实时部署。基于DDQN的方法仅需约4.80分钟完成两小时模拟,与启发式基于距离的方法相当,比短视贪心基线方法(超过42小时)快数个数量级。短视贪心方法需要在每个决策阶段评估所有可能的车辆-订单对的即时奖励边权,这极其耗时且在大规模场景下不切实际。相比之下,基于DDQN的方法依赖于通过Q网络的前向传播进行批量Q值评估;一旦离线训练完成,Q网络即可在线部署以支持响应式集中订单调度。
总体而言,我们所提出的方法(在两级分配和预约重新分配机制下的DDQN)实现了最高的总奖励,平衡了客户和平台的利益,并保持了实时可行性。通过将动作价值函数逼近与二分匹配结合用于集中式分配,该方法内化了长期权衡(延迟奖励、迟到惩罚、绕行成本),并实现了批量可扩展的推理。此外,预约订单重新分配机制提高了车队利用率并释放了即时需求订单的更高吞吐量。这些互补优势共同产生了卓越的总奖励、第二高的平台利润以及实际可行性。
### 6.3 预约请求的影响
本节通过两个因素的数值分析,考察纳入预约订单如何影响拼车系统性能:渗透率$P_{\text{prebook}}$和提前预订时间。我们在固定的拼车比例$P_{\text{pooling}}=50\%$下评估了一组场景,渗透率从0%到100%以10%为间隔,提前预订时间为15、20、25和30分钟。我们部署训练中学到的基于DDQN的订单分配策略,并在每个场景中测量系统结果。具体而言,对于每个渗透率和提前预订时间的组合,我们使用历史记录生成的需求进行两小时时段模拟。将18:30至20:00期间记录的取车时间中有指定比例$P_{\text{prebook}}$的记录指定为具有给定提前预订时间的预约订单,其余则作为即时需求请求到达。所有报告的指标均从订单的中间一小时(第30至90分钟)计算,以消除预热期和尾部期的影响。总体而言,50%的订单(包括预约和即时需求订单)被随机选为拼车行程,其余则指定为非拼车行程。为减少采样噪声,每个场景使用独立的随机种子重复多次,并报告跨重复实验的聚合性能指标。
图8展示了预约请求在不同渗透率和提前披露时间下预约订单的(a)平均取车时间、(b)迟到取车率和(c)平均取车延迟。对于预约订单,取车时间指从分配执行时(即车辆开始向乘客移动时)到实际接载乘客的时间。取车延迟指相对于计划取车时间的正迟到量,即实际取车时间超出计划取车时间的部分。迟到取车率是指具有正取车延迟的预约请求所占比例。图8(a)显示,随着渗透率增加,预约订单的平均取车时间下降,在较长的提前披露时间下降幅更大。这突显了提前需求披露的价值:预约请求留在匹配池中,可在每个区间被反复重新分配,使平台能够利用已披露的取车时间、起点和终点主动协调车队,并将订单匹配到取车距离较短的车辆。当请求更早披露时,这一效应更加明显,因为更长的缓冲期允许更多的重新分配和更广泛的可行车辆搜索。
另一方面,对取车准点性的影响更为复杂,取决于提前披露时间。在较短的提前披露时间(15分钟)下,迟到取车率(图8(b))和平均取车延迟(图8(c))随渗透率增加而上升,且保持相对较高水平。在较长的提前披露时间(≥25分钟)下,迟到取车率和取车延迟均随渗透率增加而下降。
这些不同的模式之所以产生,是因为预告时间直接影响分配可行性:当需求在计划上车时间前不久才披露时,更多预先预订的订单会在紧迫的时间窗口内争夺短期内车辆运力,导致重新分配的余地有限,迫使系统做出近视式匹配,从而增加了迟到和延误的风险。而当预告时间较长时,更长的缓冲期创造了更多重新分配和更优时间同步的机会,使系统能够在满足计划上车时间的同时利用已披露的信息。下载:下载高分辨率图片(458KB)下载:下载全尺寸图片图8.(a)不同渗透率下预先预订订单的平均上车时间,(b)迟到率,以及(c)不同预先预订渗透率和预告时间下的平均上车延误。图9报告了预先预订订单如何影响即需出行性能和拼车结果:(a)即需订单的平均上车时间,(b)完成的拼车数量,以及(c)即需请求的响应率。对即需上车时间的影响随预告时间而变化(图9(a))。当预告时间较短(15–20分钟)时,平均上车时间在低到中等渗透率下先下降,而当预先预订请求占比变高时(例如超过0.6)则开始上升。当预告时间较长(25–30分钟)时,平均上车时间在整个范围内持续下降,且在较高渗透率下降幅更为显著。这一模式反映了提前需求信息价值与预先预订准时约束之间的权衡。更大比例的预先预订请求提供了更多未来需求信息,使得平台能够主动进行车队协调并同步预先预订和即需上车时间。然而,这也使准时要求更加严格,减少了可用于即需分配的车辆可用性。在预告时间较短的情况下,紧迫的时间窗口使已承诺预先预订上车的车辆几乎没有灵活性,因此当预先预订需求变得密集时,即需上车时间会延长。相比之下,当预告时间足够长(25–30分钟)时,平台可以调整预先预订分配以确保按时上车,同时利用已披露的信息更有效地串联行程并将车辆匹配到上车距离更短的即需请求,从而随着渗透率提高而降低即需上车时间。图9(b)表明,完成的拼车数量呈非单调模式。当预先预订渗透率从低水平升至中等水平时,完成的拼车数量下降,因为准时约束预留了车辆运力,使可行的共享组合减少。然而,随着渗透率继续增加,在所有预告时间下完成的拼车数量又会再次上升。这是因为更大比例的预先预订请求揭示了更多未来起终点信息,使平台能够更系统地识别兼容行程对并形成拼车。因此,一旦提前信息足够密集,预先预订就会扩大拼车而非抑制拼车。总体而言,即需请求的响应率随预先预订渗透率上升而下降(图9(c)),反映了平台在满足预先预订准时性方面的优先性。此外,更长的预告时间会触发更频繁的预先预订订单重新分配,这会占用车辆,减少即需上车的可用性,并可能导致匹配超过最大等待时间。因此,当预先预订订单提前披露时间更长时,即需响应率更低。下载:下载高分辨率图片(420KB)下载:下载全尺寸图片图9. 不同预先预订渗透率和预告时间下的(a)即需订单平均上车时间、(b)完成的拼车数量和(c)即需订单响应率。预先预订和即需性能的影响会反映在各自收益中,并共同决定系统总收益。随着预先预订请求渗透率增加,车队服务的预先预订订单增多,获得更高的预先预订收益(图10(a))。一旦渗透率超过临界水平(约??prebook=40%),预先预订收益的增长会变得明显更陡峭,尤其在较长预告时间下更为如此。这种更陡峭的增长反映了提前需求信息价值方面的结构性变化。只有足够高的预先预订订单占比才能提供充足的未来行程信息以支持可靠的提前调度,使平台能够更有系统地为已承诺的预先预订行程分配车辆运力。这些调度收益提高了上车效率(图8(a))并减少了上车迟到(图8(c))。更长的预告时间通过提供更大的未来承诺预见性和更多缓冲来进一步放大这一效果,从而获得更高的实际预先预订收益。相比之下,即需收益随预先预订渗透率上升而下降(图10(b)),当预先预订渗透率达到100%时最终降至零。同时,更长的预告时间能保持更高的即需收益,因为额外的缓冲留下了更多空间来协调剩余的即需行程。下载:下载高分辨率图片(431KB)下载:下载全尺寸图片图10. 不同预先预订渗透率和预告时间下的(a)预先预订订单收益、(b)即需订单收益和(c)总收益。这些相反的趋势共同产生了总收益中的非单调模式(图10(c))。对于所有预告时间,总收益在预先预订渗透率从极低水平开始增加时会先下降。在这一区间内,预先预订行程过于稀疏,系统无法充分利用提前预订的信息价值,导致预先预订收益仅有边际增长。相反,它们主要引入了刚性的服务保障和额外的时间约束,挤占了灵活的即需行程并降低了整体性能。随着渗透率进一步增加,不同预订预告时间下的趋势出现分歧。当预告时间较短时(例如15分钟),预先预订信息在接近计划上车时间时才到达,留出的缓冲不足以战略性地调整车辆调度以确保准时并提高运营效率。在这种情况下,较高的预先预订渗透率主要加剧了准时压力,迫使平台将更多运力从即需请求中调离以避免迟到上车。因此,总收益随渗透率增加而几乎单调下降。相比之下,当预告时间足够长时(例如20–30分钟),平台有足够的缓冲来重新分配预先预订请求并根据已披露的未来需求重塑车辆调度。在这种设置下,系统能够将提前信息转化为更准时的服务和更有效的车队协调。超过一定渗透率水平后,改进的调度和减少预先预订迟到所带来的收益开始超过即需请求损失所带来的成本,总收益开始回升并随渗透率增加而增长。总体而言,这些结果揭示了一个关于提前预订时间和预先预订渗透率之间的二维权衡。预先预订订单提供了有价值的提前信息,但同时也施加了严格的服务约束,并优先消耗了本可用于即需请求的运力。当提前预订时间较短或预先预订渗透率较低时,约束效应占主导地位,引入更多预先预订请求会恶化整体系统性能。只有当预告时间足够长(例如20–30分钟)且预先预订渗透率足够高时,平台才能系统性地利用提前信息来协调车队、减少迟到并提高总收益。这一结论提供了一个管理启示:当预先预订需求占比高时,平台可能从鼓励更长的预告时间中获益;而当预先预订需求稀疏时,主动控制预告时间的运营价值则不够明确。
7. 结论
本文使用强化学习框架研究了混合包含预先预订和即需请求的网约车平台的实时订单分配问题。我们考虑一个管理平台管理同质车队的场景,该平台接收预先预订和即需请求的混合流——每一单可能是拼车或独享——并必须在实时条件下将车辆分配给订单,以优化平衡收入和客户体验的系统目标。为适应不同订单类型间的异构运营约束,我们提出了一种针对预先预订订单的两阶段分配机制,包含重新分配。基于该机制,我们构建了一个定制的马尔可夫决策过程,显式地捕捉了两个阶段中预先预订和即需订单之间的交互作用。为学习鲁棒且可泛化的策略,我们采用双深度Q网络来近似车辆层级的动作价值,并在每一阶段通过双匹配在相关可行性和运营约束下计算集中式车队全局分配。基于真实出租车数据的仿真实验表明,所提方法在总收益方面优于基于距离和近视贪心的基线方法,同时保持了实时的计算效率。特别是,带有预先预订订单重新分配的两阶段机制在预先预订和即需性能之间取得了更优的平衡,与没有重新分配的双深度Q网络变体相比,总收益提高了14%。利用该框架,我们进一步考察了预先预订请求的渗透率和提前预订时间如何共同影响系统整体性能。结果揭示了一个二维且本质非单调的权衡关系。预先预订订单提供了有价值的提前信息,但同时也施加了严格的准时约束,并优先消耗了本可用于即需请求的运力。当提前预订时间较短(例如15分钟)或预先预订渗透率较低时,约束效应占主导地位,引入更多预先预订请求会恶化整体系统性能。只有当预告时间足够长(例如20–30分钟)且预先预订渗透率足够高时,平台才能系统性地利用提前信息来协调车队、减少迟到并提高总收益。
本研究聚焦于混合预先预订和即需场景下的订单分配。未来研究仍有若干方向:首先,该框架可以扩展到分配以外的其他实时决策,例如定价和车辆调度,使平台能够跨服务类型联合管理供需,从而更充分地释放预先预订信息的运营价值。其次,纳入司机在不同订单类型下的偏好和接受行为,将使分配策略能够考虑司机效用的异质性和参与约束,从而同时改善系统性能和司机满意度。第三,未来工作可以建模乘客的预订选择和异质的准时偏好。当前框架将已接受的预先预订请求视为已承诺,并施加统一的延误惩罚,没有建模确认时机、乘客取消或客户对可靠性的支付意愿。在实践中,如果经历严重迟到,乘客可能会取消订单,这将给车辆状态转移和重新分配决策引入额外的不确定性。联合建模这些需求侧响应和分配决策可能支持差异化的预先预订服务设计、定价和客户特定的迟到惩罚。第四,当前的数值研究在出租车区域粒度上进行,上车和下车地点用区域质心表示。未来研究可以在有精确经纬度数据时将该框架应用于更细粒度的门到门网络,以进一步验证所提方法。第五,数值实验采用了基于曼哈顿两个高峰时段历史出行记录的单日单小时评估。在其他日期和一天中其他时间测试所学习的策略将进一步评估其对需求变化的鲁棒性,包括需求量和运营时段内请求的时空分布,这些留待未来研究。
CRediT作者贡献声明
赵子健:论文撰写——初稿、方法论、调查研究、形式分析、数据整理。
高晶:论文撰写——初稿、方法论、调查研究、资金获取、概念构思。
李森:论文撰写——审稿与编辑、指导、调查研究、资金获取。
赵子健 | 高晶 | 李森