出行派单中，给定乘客-司机候选边和权重，如何建模最大权匹配？｜滴滴算法面经解析

60 秒回答模板

我会把乘客集合和司机集合建成二分图，只有满足距离、服务类型、司机状态、等待时间等硬约束的乘客-司机对才连边，边权表示这次派单的综合收益或匹配质量，例如接驾 ETA、成交概率、取消风险、司机空驶、乘客等待、订单价值和公平性惩罚。目标是在每个乘客最多匹配一个司机、每个司机最多接一个当前订单的约束下，最大化总边权；不能匹配的乘客或司机可以用 dummy 节点或未匹配惩罚处理。小规模、稠密、标准一对一问题可以用 Hungarian；稀疏图可用最大权二分图匹配；有容量、配额、禁配、软惩罚和多目标权衡时更适合最小费用最大流或整数规划建模。线上派单通常要先做候选召回和 topK 截断，再在很短时间窗口内滚动批量求解，必要时用贪心、拍卖算法、局部搜索或启发式兜底。评估不能只看总权重，还要看成交率、接驾时长、乘客等待、司机空驶、取消率、区域公平和 A/B 实验收益。

考点 候选边先行

难度 真实面经题

回答目标 讲清原理、实现和边界

深入解析

先把问题建成二分图

乘客是一侧节点，司机是另一侧节点。不是所有乘客和司机都能连边，只有满足业务可行性的乘客-司机对才是候选边，例如司机在线且空闲、车型或服务类型匹配、距离和 ETA 可接受、司机没有被规则禁派、乘客等待还在有效时间窗内。题目里的“每个乘客有自己满意的若干司机”正好对应稀疏候选边集合。

边权不是单一距离

边权可以理解为把一个司机派给一个乘客的综合价值。最简单可以是距离或接驾时间的负值，但面试中更好的回答是综合建模：w(i, j) = 成交收益 - 接驾成本 - 取消风险 - 空驶成本 - 体验惩罚 - 公平性惩罚。权重可以来自规则、线性打分、GBDT/深度模型预估或多目标标定，但必须和最终派单目标一致。

约束决定算法形态

基础约束是一对一：每个乘客最多分配一个司机，每个司机最多接一个订单。实际建模还可能有硬约束和软约束：最大接驾时间、服务类型、司机容量、区域供需保护、司机疲劳、乘客优先级、订单超时、平台规则和安全过滤。硬约束通常用于删边，软约束可以进入边权惩罚或流网络费用。

标准算法只是起点

如果是平衡、稠密、标准一对一最大权分配，可以把最大权转成最小成本后用 Hungarian。若候选边很稀疏，可使用稀疏最大权二分图匹配。若存在司机容量、区域配额、必须匹配数量、未匹配惩罚或多类约束，最小费用最大流更容易表达。若问题规模大且延迟严格，贪心、拍卖算法、局部搜索、拉格朗日松弛或启发式近似也可以作为工程选择。

在线派单要控制规模和延迟

线上不能把全城所有乘客和司机做一次巨大匹配。通常先用时空索引、服务规则和半径扩展生成候选边，再对每个乘客或司机保留 topK 候选，形成稀疏图。求解可以按区域和滚动时间窗批处理，也可以对紧急订单走快速局部决策。关键是让候选召回、打分、匹配求解和兜底策略都在延迟预算内完成。

护栏和评估要补齐

最大化总权重不等于业务成功。权重若只偏向短期成交，可能牺牲长尾区域、司机公平、乘客等待或安全体验。因此要设置业务护栏：最大等待、最大接驾、禁配规则、司机收入均衡、区域服务覆盖、异常天气和高峰保护。评估上既看离线 replay 或仿真里的总权重，也看线上 A/B 的成交率、接驾时长、取消率、司机空驶、乘客等待、投诉率和区域切片表现。

易错点

只说“用匈牙利算法”，没有定义乘客节点、司机节点、候选边、权重和约束。
把边权简单等同于距离最近，忽略成交概率、取消风险、司机空驶、乘客等待和业务目标。
对每个乘客独立选最优司机，没处理司机只能被一个订单占用的全局冲突。
只讨论离线最优解，不考虑线上候选规模、实时延迟、规则过滤、兜底和 A/B 评估。

面试官追问

如果乘客数和司机数不相等怎么办？

可以加入 dummy 乘客或 dummy 司机，把未匹配表示成一条带惩罚或零收益的边。这样算法仍能处理矩阵或流网络，同时保留“有些订单暂时不派、有些司机暂时空闲”的业务含义。

为什么不能每个乘客直接选权重最高的司机？

因为司机资源会冲突。多个乘客可能都把同一个司机作为最高权重候选，局部最优选择会让其他乘客拿不到合适司机，导致全局总收益下降。匹配算法的价值就在于处理这种双边竞争。

边权应该离线训练还是实时计算？

两者可以结合。离线模型学习成交概率、取消风险、接驾成本和体验影响，在线再叠加实时 ETA、司机状态、订单等待、区域供需和规则惩罚。关键是保证线上使用的特征可实时获得，并且分数校准后能被匹配层比较。

高峰期规模太大时怎么做？

先缩小图：按区域分桶、滚动时间窗、时空索引过滤、半径分层、topK 截断和低质量边过滤。求解上可以选择稀疏匹配、最小费用流的限时求解、拍卖算法、贪心加局部交换，必要时保留规则兜底，优先保证延迟和体验下限。