编者按
在现代出行需求不断增长的背景下，网约车平台作为创新的出行方式，迅速改变了传统出租车行业的格局。然而，随着平台规模的扩大，调度系统面临着更加复杂的挑战。本篇文章介绍了三篇相关论文，深入探讨了按需网约车系统对交通效率的影响，并给出了可能的解决方案，带来运营管理的新思路。
Empty-Car Routing in Ridesharing Systems
Reference: Braverman, A., Dai, J. G., Liu, X., & Ying, L. (2019). Empty-car routing in ridesharing systems. Operations Research, 67(5), 1437-1452.
原文链接：https://doi.org/10.1287/opre.2018.1822
Problem
现如今，滴滴出行、Lyft和Uber等交通公司均已提供拼车服务，本文即研究在这些共享出行系统中，如何通过空车调度来优化系统总效用。具体来说，就是当乘客到达某个区域时，系统如何采用合适的空车调度策略来确保该区域内有空车可用，从而提高乘客的满意度和系统的效率。
本研究将整个拼车网络建模为一个由单服务站（single-server stations）和无限服务站（infinite-server stations）组成的封闭排队网络，而汽车则视为在排队网络中移动的“工作”。该封闭排队网络模型即来模拟多个地理区域内的网约车移动情况。其中，单服务站即那些在某区域中等待服务顾客的车，而无限服务站则用来描述在不同区域之间移动的汽车。站的缓冲区对应正在等待的汽车数量；站的服务完成情况对应乘客的乘车请求。因此，单服务站的服务时间为乘客到达该区域的到达间隔时间（interarrival time）。
Method
假设乘客的到达满足泊松分布，区域的可用性（availability）为长时间内，该区域至少有一辆可用车辆的时间占总时长的比例。在此，笔者定义当一辆汽车完成上一个订单时，该空车既可以概率停留在区域（它可以在此立刻服务新乘客），或是以概率在没有服务新乘客的情况下重定位至区域，并在该区域等待新乘客。在此基础上，调度矩阵（routing matrix）就是空车的调度策略，为本文研究问题的决策变量。它可以随系统状态改变（state-dependent），即Q$是静态的时，该排队网络属于BCMP网络。BCMP网络是一种特殊的多区域排队网络模型，它的一个显著特点是其平稳分布具有“乘积形式解”（product form solution）。当调度策略不随系统状态改变时，将其视为BCMP网络可以利用其乘积形式解来简化分析和优化。
接着，研究构建了一个基于流体极限的优化模型，该模型假设在大市场环境下（即当车辆数和乘客需求趋于无穷大时），网约车系统的行为可以用流体模型来近似描述，从而将原本复杂的离散事件流转化为连续的流体动态。这种转换可以有效减少计算复杂度，使问题更易于求解。在此模型中，车辆状态通过连续时间马尔可夫链（Continuous Time Markov Chain, CTMC）建模，车辆的每一个状态变化（如接载乘客、完成订单、空车移动）都是一个连续时间马尔可夫过程。车辆可在各区域之间流动，具体位置和状态可以用区域的“空车”和“满车”状态来表示。CTMC过程的状态描述如下：
流体极限优化模型的核心是最大化系统的整体可用性（availability），即各区域在任一时刻都能有足够空车满足乘客需求的概率。而约束条件确保了车辆在区域之间的动态平衡（即空车和满车在不同区域的流动率相等），从而形成一个稳定的流体状态。在该模型下，作者证明了该问题可以转化为一个线性规划问题，从而得出最优的空车调度策略。
Main Result
本研究首先证明了基于流体极限的优化方法在大市场条件下可以达到系统效用的最优上界，即当车辆数量和乘客需求趋于无穷大时，通过流体极限模型得到的静态调度策略能够实现系统整体的最高效用。这意味着，采用流体极限优化得到的调度方案可以保证每个区域有足够的空车满足乘客需求，从而显著提升系统的资源利用效率。此外，作者进一步指出，即使在有限车辆的实际网约车系统中，流体极限模型得出的静态调度策略仍然可以近似达到最优效能。这一结果表明，即使在现实条件下，基于流体极限优化的方案仍然是一个良好的近似解，有效地解决了车辆资源在不同区域间的平衡问题。而为了实现这种流体极限优化，作者将其转化为线性规划问题，通过最大化各区域的空车可用性来找到最优的空车分配策略。
数值仿真验证了这种流体极限优化策略在实际系统中的可行性和优越性。研究利用真实的网约车数据进行实验，将基于流体极限优化的静态调度策略与几种常用的动态调度策略进行比较，包括“最少拥挤区域策略”（Join-the-Least-Congested-Region, JLCR）和“最短等待时间策略”（Shortest-Wait, SW）。
结果显示，该静态调度策略在满足乘客需求和系统可用性方面优于传统的动态调度策略。流体极限优化策略在大部分区域内均能显著提高乘客请求的满足率。在实验场景中，流体极限策略通过合理分配空车，使高需求区域能够在乘客抵达时提供充足的空车服务，从而减少了乘客因空车短缺而转向其他出行方式的情况。与其他动态策略相比，流体极限方法在系统可用性和响应效率方面表现出更高的稳定性和一致性。在区域需求剧烈变化的情况下，流体极限优化策略依然能够保持较高的服务水平，而动态策略则会出现因需求高峰期间的资源分配不均而导致的空车短缺现象。具体而言，基于流体极限的静态策略在各区域间的空车分布实现了更好的平衡，显著降低了高需求区域的乘客流失率。特别是在实验模拟的高需求时段，流体极限优化策略的乘客需求满足率远高于其他策略，尤其在供需不平衡的情况下更为显著。与JLCR和SW等状态依赖的动态调度策略相比，流体极限优化策略在不需要实时计算的情况下依然能够保持相似甚至更优的性能，这说明了其在实际应用中的效率和可靠性。
同时，作者还在理论上证明了任何状态依赖的动态调度策略在有限车辆条件下的期望系统效用都受限于流体极限优化解所提供的上界。这一发现进一步强化了流体极限模型的优越性，表明即便在具有动态响应能力的状态依赖调度策略中，基于流体极限的静态调度方案也能达到最优性能，从而为网约车系统提供了一个简洁而有效的调度策略。
Why recommend
本研究不仅在理论上证明了基于流体极限优化策略的有效性，而且还通过实际数据的模拟实验展示了这种策略在实际应用中的潜力，尤其在需求波动较大的场景中，该策略表现出更高的可用性和服务质量。 本文的方法论部分也可为其他类型的动态资源分配问题提供一种可能的解决方案。
Dynamic Pricing and Matching for Two-Sided Queues
Reference: Varma, S. M., Bumpensanti, P., Maguluri, S. T., & Wang, H. (2023). Dynamic pricing and matching for two-sided queues. Operations Research, 71(1), 83-100.
原文链接：https://pubsonline.informs.org/doi/10.1287/opre.2021.2233
Problem
在现代经济中，诸如共享出行、在线市场和众包服务等平台的运营面临着复杂的供需平衡问题。这些平台必须同时处理客户和服务提供者的到达与匹配，并使用动态定价来优化平台的利润。这篇文章解决的问题是如何在两侧排队系统（即客户和服务器两者均会顺序到达并等待匹配的系统）中，通过动态定价和匹配策略来优化系统运营者的长期平均利润。作者首先定义了双边排队系统，其中客户和服务提供者分别到达系统并排入各自的队列。每种客户类型只能与特定的服务提供者类型匹配，这构成了一个二分图模型。系统运营商的任务是通过控制价格来调节客户和服务提供者的到达率，同时决定匹配策略，以实现长期平均利润的最大化。为了更具体地描述问题，作者引入了一个基于到达率和价格间关系的模型，体现了客户和服务提供者对价格和等待时间的敏感性。
Method
首先，为了简化系统的随机特性并提供理论上可解析的框架，作者引入了流体近似模型。在这种模型中，系统的随机到达过程被近似为确定性过程，使得复杂的随机行为转化为求解优化问题。论文中，流体模型的目标是求解长期平均利润的上界：
这里，l 和 m 分别表示客户和服务提供者的到达率向量， 表示类型 i 的服务提供者与类型 j 的客户的匹配速率。约束条件如下：
该优化问题的解提供了系统运营商可以实现的理论最优利润上界，为动态定价和匹配策略的设计提供了一个基准。
其次，论文将双边排队系统建模为连续时间马尔可夫决策过程（CTMDP），其中客户和服务提供者的队列长度构成了系统状态。系统的动作包括动态定价和匹配决策，状态转移依赖于当前队列长度和动作选择。贝尔曼方程用于描述最优策略下的长期利润和偏差函数：
为了简化CTMDP 的求解，作者使用均匀化技术将 CTMDP 转化为离散时间 MDP，这在处理复杂的双边系统时尤其有效。这一技术确保在每个时间步中，系统最多有一个客户或服务提供者到达，使得状态转移更易于分析。
然后，最大权匹配算法是解决动态匹配问题的核心策略。该算法在每次决策时选择匹配方案，使得匹配权重（即队列长度的内积）最大化，其定义为：
最后，为了提高策略的动态适应性，作者提出了两价格政策。这种政策在流体策略基础上增加了调整灵活性，当队列长度超过某个阈值时，系统会降低到达率来减少队列增长。具体的两价格策略表示如下：
Main Result
在论文的数值实验部分，作者通过仿真分析验证了所提出策略的实际表现：
1.对于单链路系统，实验结果显示在客户和服务提供者到达率为时，流体模型的最优利润为3.08。分析表明，当队列长度增加时，客户价格高于服务提供者价格，且两者随着队列差异增大而升高，这与论文附录中的理论一致。实验显示，流体定价策略的利润损失为 ，而两价格策略的利润损失为 ，两价格策略的利润损失几乎接近最优，证明了其实际应用的有效性。
2.对于多类型系统，作者对不同策略组合的利润损失进行了比较，包括流体定价与最大权匹配（FP + MW）、流体定价与随机匹配（FP + Rand）、两价格策略与最大权匹配（TP + MW）、以及两价格策略与随机匹配（TP + Rand）。结果显示，随着系统参数的增加，两价格策略结合最大权匹配的利润损失增速最慢，表现出优于其他组合的性能。对数图分析验证了 FP + MW 和 TP + MW 的理论斜率分别为 0.51 和 0.33。实验结论表明，两价格策略结合最大权匹配能够在大系统中实现最小的利润损失，显著优于随机匹配策略，验证了理论上两价格策略的最优性。
Why recommend
理论性：这篇论文在双边排队系统中动态定价和匹配的研究中引入了创新的方法，如流体近似模型和两价格策略，并结合最大权匹配算法来优化长期利润。作者通过数学建模、马尔可夫决策过程和 Lyapunov 稳定性分析等技术，详细推导并证明了这些策略的最优性，具有理论价值。 实用性：论文中提出的策略不仅限于理论研究，还具备广泛的应用场景，尤其是在网约车平台、外卖服务和任务众包平台等现代双边市场。数值实验验证了两价格策略在复杂和大规模系统中的优越性，对从事平台运营、供应链管理或共享经济研究的学者具有参考价值。
We Are on the Way: Analysis of On-Demand Ride-Hailing Systems
Reference: Guiyun Feng , Guangwen Kong , Zizhuo Wang (2020) We Are on the Way: Analysis of On-Demand Ride-Hailing Systems. Manufacturing & Service Operations Management 23(5):1237-1256.
原文链接：https://doi.org/10.1287/msom.2020.0880.
Problem
按需网约车系统（如Uber和滴滴）的兴起，改变了传统的街招出租车模式，提供了更加便捷的出行服务，也带来了新的研究问题。
这篇文章主要研究了按需网约车平台（如Uber和滴滴）的匹配机制对交通系统效率的影响，特别是与传统街招出租车系统相比，这些新平台是否能减少乘客的平均等待时间？
这个问题的答案并不是显而易见的。Schaller（2017）从纽约曼哈顿收集的数据中发现，网约车系统平台（如uber）的平均空车时间间隔为11分钟，明显长于街头叫出租车服务的平均8分钟空车时间。这可能是因为在交通繁忙的情况下，司机前往接载要求服务的乘客时，可能会在途中遇到另一名乘客，从而增加了本应较短的接载时间，从而导致效率下降。针对按需网约车平台潜在的低效率，上海政府2014年禁止在交通高峰时段使用按需网约车平台（Sweeney 2014）。尽管禁令后来被解除，但与传统的出租车相比，按需叫车平台的表现仍存在许多问题。
针对这个问题，本文考虑了一个出租车在环形道路上行驶的模型，并研究了该模型不同匹配机制的性能。对于传统的出租车系统，本文考虑了“不呼叫机制”，即没有平台将乘客与出租车匹配，到达的乘客由第一辆经过的可用出租车搭载。对于按需叫车系统，本文考虑了“呼叫机制”，在该机制中，只要有出租车可用，等待的乘客就会被匹配到最近的闲置出租车。
Method
本文考虑一个周长为的环形道路。乘客按照泊松过程到达系统，其到达点均匀分布在环形路上。每个到达的乘客请求的服务距离遵循均值为的指数分布。出租车的初始位置是独立的，并且均匀分布在环形路上，都有恒定的速度。因此，服务持续时间遵循平均数为的指数分布，利用水平(交通强度)定义为。
本文考虑了两种不同的系统：单向系统和双向系统。在单向系统中，所有出租车都顺时针行驶，乘客的请求也是顺时针行驶（即如果乘客请求距离为l的服务，那么她请求顺时针方向行驶距离为l）。相反，在双向系统中，出租车和乘客被允许在两个方向上行驶。在双向系统中，每辆出租车的初始方向、每名乘客请求的服务方向以及出租车完成服务后的行驶方向都是随机选择的，其中50%的可能性是顺时针方向，50%的可能性是逆时针方向。
本文的重点是比较两种需求匹配机制。第一种机制被称为呼叫机制，用于模拟按需叫车平台的匹配过程。在呼叫机制中，当乘客到达时，如果有出租车可用，平台会立即为乘客匹配最近的出租车；否则，到达的乘客将等待，直到下一辆出租车可用，此时出租车将与最近的乘客匹配（如果有的话，剩余的乘客将继续等待下一辆出租车可用）。一旦出租车和乘客匹配，出租车就会承诺下一个为该乘客服务，而乘客则等待匹配的出租车到来。在单向系统中，乘客与出租车之间的距离定义为出租车顺时针行驶时到达乘客的距离；在双向系统中，距离定义为顺时针行驶与逆时针行驶之间较短的距离。另一种机制是不呼叫机制，该机制模拟了传统的出租车匹配过程。在不呼叫机制中，不发生匹配，乘客由经过的第一辆可用出租车搭载。
本文的目的是研究和比较呼叫和不呼叫机制的效率。
当乘客不放弃网约车服务时，本文使用乘客的平均等待时间作为主要绩效指标。乘客等待时间是指从乘客到达系统到乘客被出租车接送的时间。根据Little’s law，乘客的平均等待时间与系统中平均等待人数成正比。因此，平均等待时间可以衡量乘客的满意度和系统的拥堵程度。
当乘客的耐心水平有限，可能会放弃网约车服务时，本文从出租车的角度用有效利用率（即出租车搭载乘客行驶的时间比例）来衡量匹配效率。有效利用率可以用来定义，其中为弃用率。在没有放弃的系统中，上述所有机制都具有相同的有效利用率水平（尽管它们可能导致不同的平均等待时间）。
Main Result
按需网约车系统与传统出租车系统的不同之处在于，在系统利用水平上，平均等待时间可能是非单调的。这种非单调性是由于这种系统中平均途中时间的非单调性，它捕获了从匹配建立到实际拾取发生之间的时间。 通过对按需网约车和传统出租车系统的比较，本文确定了每种机制的优缺点。呼叫机制的优点在于它能够告诉司机去哪里接下一个乘客。然而，使用呼叫机制的出租车可能会在接受传入请求时放弃未来更好的匹配机会。 在乘客在服务前不放弃叫车的情况下，在交通强度（系统利用率）为较低或较高时，呼叫机制在乘客等待时间方面更有效，而在交通强度为中等范围时，不呼叫机制可能更有效。 在乘客可能在服务前放弃叫车的情况下，当乘客耐心水平较低且交通强度较大时，呼叫机制的效率可能低于不呼叫机制，这与Schaller（2017）的实证研究结果一致。 为了克服按需网约车系统的缺点，本文提出了添加响应上限的平台机制，即只有当乘客与出租车的距离在一定范围内时，才会进行匹配。这种机制旨在减少司机因过早承诺而错失更近乘客的风险。
Why recommend
本文从一个实证研究（Schaller, 2017）中发现的重要的研究问题出发，分析了按需网约车系统在不同情况下的效率，特别是在系统利用率中等、道路长度较长的情况下，与传统出租车系统相比，按需匹配机制可能存在的效率问题。 乘客可能在服务前放弃系统的设置。在此设置下，本文发现当乘客耐心水平较低且交通强度较大时，呼叫机制的效率可能低于不呼叫机制。
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
推文作者：杨子萱，杨春苇，Guo
责任编辑：Guo
微信编辑：疑疑
文章由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知
关注我们
FOLLOW US
