1. 这篇文章真正要解决的问题先抛一个经常在后端开发群里被问到的问题做拼车类功能时需求文档里写着“把顺路的乘客拼到同一辆车里”你觉得这只是一个简单的“按起点终点过滤”的查询操作还是背后有一个独立的算法模块很多团队第一次做拼车会把拼车逻辑直接写在下单服务里新乘客来了查一下附近有没有未满座的订单有就塞进去没有就创建新订单。这种实现方式在前端体验上叫“快”但在运力使用效率上往往非常差。原因也很简单你把拼车当成了一次性匹配而没有把它当成一个“打包过程”。拼车打包的核心任务是在满足乘客出发时间、行程方向、车辆座位数的约束下把多个独立的出行请求组合成一辆车能完成的行程组合。它本质上是一个组合优化问题和装箱问题Bin Packing Problem非常相似。你面对的是一堆大小不一、目的地各异的“物品”需要把它们装进容量受限的“箱子”里同时让总成本最低、满意度最高。这篇文章不讲那些需要数学博士才能看懂的精确求解算法而是从工程实现的角度拆解“拼车打包”这个问题到底是什么、它的难点在哪、一个可运行的最小系统应该怎么设计、实际生产环境里有哪些坑。读完后你可以得到三样东西一套把拼车场景抽象成“打包模型”的建模思路一个基于 Python 的可运行最小示例能处理按方向分组、按容量打包、按时间窗过滤一份从“能跑”到“能用”的工程优化清单。无论你是做网约车、货运、顺风车还是做企业内部通勤系统“拼车打包”这个模块的设计思路都适用。2. 核心概念拼车匹配、拼车打包与装箱问题2.1 拼车匹配和拼车打包不是一回事很多团队会把“匹配”和“打包”混在一起导致系统上线后逻辑越改越乱。这两者是有明确边界的拼车匹配解决的是“哪几个乘客应该在同一辆车里”侧重人之间的关系。拼车打包解决的是“这一组乘客的订单如何组成一个可执行的行程”侧重订单和运力之间的关系。你可以这样理解匹配是选人打包是装车。乘客之间可能彼此合适但装到一辆车上之后路线是否绕、时间是否超、容量是否够这就是打包阶段要处理的问题。举一个具体的例子有两个乘客A 从起点 S 去往 T1B 从起点 S 去往 T2两个目的地距离不远方向上看起来完全顺路。但如果你把 AB 的行程放进同一辆车会发现先送谁、后送谁会导致总路程不同。如果先送 A 再送 B总路程可能是 12 公里先送 B 再送 A总路程可能是 9 公里。这就是打包时的路径顺序优化。2.2 装箱问题带来的直觉装箱问题的经典描述是有若干个体积不同的物品要把它们全部装进容量相同的箱子里目标是使用最少的箱子。拼车打包和装箱问题在结构上是同构的装箱问题拼车打包物品拼车请求物品体积乘客占用座位数箱子车辆箱子容量车辆剩余座位数最优目标使用的箱数最少等价拼车目标使用车辆数最少或运力利用率最高但拼车打包比标准装箱问题更复杂。因为装箱问题中的物品是可以任意组合的而拼车请求之间还有时间、空间、路径上的约束。你可以把拼车打包理解成“带约束的装箱问题”。2.3 为什么说这是一个 NP-Hard 问题从算法复杂度角度看当请求数量变大时精确求全局最优解的计算量会爆炸式增长。假设有 20 个请求每辆车最多坐 4 人你需要尝试的组合方式是海量的。这就是为什么生产环境里几乎不会用穷举法或整数规划去实时求解而是采用启发式算法、贪心算法或者把打包任务扔给离线调度系统异步计算。这里有个重要的工程判断在拼车场景里你并不需要“理论最优解”你更需要“在规定时间内能算出来的、满意的可行解”。认识到这一点你就不会去写一个试图暴力枚举所有组合的后端接口而是老老实实地做分层设计。回到我们的主题。拼车打包的核心流程可以概括为一句话先分组再装车最后排路线。3. 拼车打包的完整流程与关键设计3.1 输入与输出在设计拼车打包模块之前先定义清楚输入输出边界。输入一批待处理的拼车请求每个请求包含出发地、目的地、出发时间窗、人数、用户可接受的绕路时间。可用运力信息每个运力包含车型、座位数、当前位置。输出若干个行程组每组由若干请求和一个运力实例组成。每个行程组的行驶路线顺序例如从起点出发先到站点 A再到站点 B。每个请求的预计上车时间和预计到达时间。3.2 打包流程的阶段划分一个可落地的拼车打包流程可以拆成四个阶段请求预处理分组容量与约束校验路径排序与时间估算第一阶段请求预处理。把请求中的经纬度解析成可用于距离计算的坐标规划出每个请求单独行驶时的预估路线距离作为后续判断“绕路率”的基准。第二阶段分组。按照方向、区域、路线相似度进行粗分组把明显不会顺路的请求分开。常用的做法是网格哈希把地图按经纬度切成若干网格相同或相邻网格的请求进入同一个候选桶。第三阶段容量与约束校验。在候选桶内进一步组合校验座位数、时间窗、绕路距离是否满足设定的阈值。这一阶段才是真正决定“能不能装进同一辆车”的关键。第四阶段路径排序与时间估算。对通过校验的组合生成实际行驶顺序计算每个乘客的上车点和下车点顺序估算总行程时间。这四个阶段不是必须同步执行的。在工程实现上阶段一和阶段二可以做成离线的预计算服务阶段三和阶段四做成实时服务。这样能大幅降低高峰期的计算压力。3.3 一个需要提前想清楚的问题怎么定义“顺路”分组阶段最核心的指标是“顺路程度”。很多初学者喜欢用“起点距离”来定义顺路这是一个高频错误。举两个反例两个请求起点相距只有 100 米但一个去城东一个去城西完全不顺路。两个请求起点相距 3 公里但都通往高速方向反而可以在高速入口汇合。正确的做法是使用“路线重合度”或“增量绕路距离”来判断。简单版本可以这样定义为第一个请求规划一条完整路线得到总距离 D1。尝试把第二个请求的途经点插入路线中得到新路线 D2。计算增加的绕行距离 delta D2 - D1。如果 delta 小于阈值或小于 D1 的某个比例认为顺路。这个思路不需要复杂的算法只需要一个路线规划服务和简单的途经点插入逻辑。4. 环境准备用最小工具链跑通打包模型为了专注讲清“拼车打包”本身我们使用最轻量的环境不需要引入地图 SDK 和真实路线服务。本文示例的软硬件环境如下操作系统Windows / macOS / Linux 均可Python3.9 及以上依赖库仅使用标准库不需要额外安装开发工具任意 Python IDE 或 VS Code Python 插件如果你对坐标计算比较敏感也可以安装geopy但本文为了保持示例可复制性使用最简单的基于经纬度差的欧氏距离近似计算。真实项目里请使用 Haversine 公式或调用地图服务区别只在于距离精度。# 本文示例不依赖第三方包直接运行 python 即可 python --version5. 核心代码实现三个层面的打包逻辑下面我们分三个层次实现一个最小可用的拼车打包系统。5.1 定义请求与运力数据结构首先定义拼车请求和运力的数据结构。这里我们刻意保留最核心的字段方便你理解问题本质。# 文件路径model.py import itertools from dataclasses import dataclass, field from typing import List, Dict dataclass class RideRequest: 拼车请求 request_id: str pickup_lat: float # 上车点纬度 pickup_lng: float # 上车点经度 dropoff_lat: float # 下车点纬度 dropoff_lng: float # 下车点经度 start_time: int # 最早出发时间分钟从当日 0 点起算 end_time: int # 最晚出发时间分钟 passengers: int 1 # 人数 max_detour_ratio: float 0.4 # 可接受的最大绕路比例 accepted: bool False # 是否已进入某个行程组# 文件路径model.py续 dataclass class Vehicle: 运力一辆车 vehicle_id: str capacity: int # 座位数 start_lat: float start_lng: float# 文件路径model.py续 dataclass class RoutePlan: 一次拼车打包的输出结果 vehicle_id: str request_ids: List[str] order: List[str] # 途经点顺序例如 [P001上车, P002上车, P001下车, P002下车] total_distance: float estimated_time: int # 单位分钟为了避免代码文件过长示例里把类定义集中在model.py中。真实项目中建议按领域模型分文件管理。5.2 距离计算与方向分组接下来实现最基础的两个工具函数距离计算和方向分组。距离计算这里不做真实道路距离而是用基于经纬度差的近似值。这个近似值作为示例足够但生产环境必须替换成路线规划服务返回的“实际道路距离”。# 文件路径geo_utils.py import math from typing import List from model import RideRequest def approx_distance(lat1: float, lng1: float, lat2: float, lng2: float) - float: 简单近似距离单位公里。仅用于示例生产环境请用 Haversine 或地图服务。 lat_diff lat1 - lat2 lng_diff lng1 - lng2 # 纬度方向每度约 111 公里经度方向按 cos(纬度) 缩放 lat_km lat_diff * 111.0 lng_km lng_diff * 111.0 * math.cos(math.radians((lat1 lat2) / 2)) return math.sqrt(lat_km * lat_km lng_km * lng_km) def direction_grid(lat: float, lng: float, grid_size: float 0.05) - tuple: 把坐标映射到网格。grid_size 约 0.05 度在赤道附近约 5.5 公里。 return (round(lat / grid_size), round(lng / grid_size))这里我们引入了方向网格的概念。拼车场景中“方向”可以通过目的地的网格编码来表达。将目的地投影到网格后同一个网格或相邻网格的请求被分入同一组。# 文件路径grouping.py from typing import Dict, List from collections import defaultdict from model import RideRequest from geo_utils import direction_grid def group_by_destination(requests: List[RideRequest], grid_size: float 0.05) - Dict[tuple, List[RideRequest]]: 按目的地网格分组。 返回一个字典key 是网格坐标value 是该网格下的请求列表。 groups: Dict[tuple, List[RideRequest]] defaultdict(list) for req in requests: key direction_grid(req.dropoff_lat, req.dropoff_lng, grid_size) groups[key].append(req) return groups这个分组逻辑虽然简单但已经能处理“同一个方向的请求优先打包”这个直觉。如果两个请求的目的地在同一个网格它们大概率是同一个方向的适合进入后续容量校验环节。5.3 容量与时间窗校验有了候选组之后下一步是判断一个请求能否进入某个行程组。这部分是打包的核心校验逻辑。# 文件路径packing.py from typing import List from model import RideRequest, Vehicle def can_pack(group: List[RideRequest], new_req: RideRequest, vehicle: Vehicle) - bool: 判断 new_req 是否能加入到已有的 group 中。 校验两件事 1. 总人数不超过车辆容量。 2. 出发时间窗有交集。 total_passengers sum([r.passengers for r in group]) new_req.passengers if total_passengers vehicle.capacity: return False # 时间窗交集所有请求必须存在一个共同的可出发时间 latest_start min([r.end_time for r in group] [new_req.end_time]) earliest_start max([r.start_time for r in group] [new_req.start_time]) if earliest_start latest_start: return False return True def pack_requests(requests: List[RideRequest], vehicle: Vehicle) - List[List[RideRequest]]: 贪心打包从前往后遍历请求能塞进当前组就塞否则新建一组。 注意这个版本没有做路径顺序优化仅做容量与时间校验。 groups: List[List[RideRequest]] [] for req in requests: placed False for group in groups: if can_pack(group, req, vehicle): group.append(req) req.accepted True placed True break if not placed: groups.append([req]) req.accepted True return groups这个pack_requests方法本质上是最简单的“首次适应”贪心算法。在装箱问题里这个策略的时间复杂度是 O(n^2)优点是非常快缺点是完全不考虑后续请求。为了更直观地看到这种贪婪策略的问题我们加入一个“随机顺序打包”的对比函数每次先打乱请求顺序再进行打包然后统计需要用多少辆车。这个技巧可以用来做简单的策略对比比空谈“贪心算法效果差”更能说明问题。5.4 加入路线排序的完整示例前面几个函数只完成了“塞进同一辆车”的判断但没有生成行驶顺序。真实拼车流程中必须输出一个清晰的路线顺序否则司机拿到行程组也不知道先去接谁。下面我们写一个更完整的打包函数它会为每个行程组生成最简单的“先接所有乘客再依次送客”的路线顺序。# 文件路径order_planner.py from typing import List, Tuple from model import RideRequest, Vehicle, RoutePlan from geo_utils import approx_distance def _pickup_sequence(requests: List[RideRequest], vehicle: Vehicle) - List[Tuple[str, str]]: 生成接送顺序返回格式为 [(动作, 请求ID)]。 简化策略先按上车点与车辆当前位置的距离排序依次接人 接到所有乘客后按下车点与当前位置的距离排序依次送人。 remaining list(requests) current_lat vehicle.start_lat current_lng vehicle.start_lng sequence [] while remaining: # 找离当前位置最近的未接乘客 nearest min( remaining, keylambda r: approx_distance(current_lat, current_lng, r.pickup_lat, r.pickup_lng) ) sequence.append((上车, nearest.request_id)) remaining.remove(nearest) current_lat nearest.pickup_lat current_lng nearest.pickup_lng # 接完所有人后按下车点距离依次送客 remaining list(requests) while remaining: nearest min( remaining, keylambda r: approx_distance(current_lat, current_lng, r.dropoff_lat, r.dropoff_lng) ) sequence.append((下车, nearest.request_id)) remaining.remove(nearest) current_lat nearest.dropoff_lat current_lng nearest.dropoff_lng return sequence def build_route_plan(group: List[RideRequest], vehicle: Vehicle) - RoutePlan: 为一个行程组生成 RoutePlan。 sequence _pickup_sequence(group, vehicle) total_distance _calculate_route_distance(group, vehicle, sequence) # 简化时间估算假设平均速度 30 公里/小时 estimated_time int(total_distance / 30 * 60) return RoutePlan( vehicle_idvehicle.vehicle_id, request_ids[r.request_id for r in group], order[f{action}{req_id} for action, req_id in sequence], total_distanceround(total_distance, 2), estimated_timeestimated_time ) def _calculate_route_distance(group: List[RideRequest], vehicle: Vehicle, sequence: List[Tuple[str, str]]) - float: 根据接送顺序计算总距离。 current_lat vehicle.start_lat current_lng vehicle.start_lng total 0.0 req_map {r.request_id: r for r in group} for action, req_id in sequence: req req_map[req_id] target_lat req.pickup_lat if action 上车 else req.dropoff_lat target_lng req.pickup_lng if action 上车 else req.dropoff_lng total approx_distance(current_lat, current_lng, target_lat, target_lng) current_lat target_lat current_lng target_lng return total这里使用的“接完所有人再送所有人”策略不是最优解但它符合很多拼车产品初期的实际逻辑先保证所有乘客都能上车再考虑谁先下车。它容易实现、容易解释、也容错。5.5 主流程串联所有模块写好后通过一个main.py把完整流程串起来生成测试数据并输出打包结果。# 文件路径main.py from model import RideRequest, Vehicle from grouping import group_by_destination from packing import pack_requests from order_planner import build_route_plan def make_demo_requests(): 构造 8 个模拟请求制造 2 个明显的方向分组。 requests [ RideRequest(R001, 31.2304, 121.4737, 31.2500, 121.6000, 480, 490, 1), RideRequest(R002, 31.2350, 121.4800, 31.2550, 121.6100, 475, 500, 2), RideRequest(R003, 31.2400, 121.4700, 31.2600, 121.6200, 470, 485, 1), RideRequest(R004, 31.2200, 121.4600, 31.2100, 122.0000, 480, 500, 1), RideRequest(R005, 31.2250, 121.4650, 31.2050, 122.0100, 478, 495, 3), RideRequest(R006, 31.2450, 121.4900, 31.2700, 121.6300, 485, 500, 1), RideRequest(R007, 31.2300, 121.4750, 31.2150, 122.0200, 460, 480, 1), RideRequest(R008, 31.2500, 121.4850, 31.2300, 121.5900, 490, 510, 2), ] return requests def main(): requests make_demo_requests() vehicles [ Vehicle(V001, 4, 31.2280, 121.4700), Vehicle(V002, 6, 31.2280, 121.4700), ] print( 按目的地网格分组 ) groups group_by_destination(requests, grid_size0.1) for grid_key, req_list in groups.items(): print(f网格 {grid_key}: {[r.request_id for r in req_list]}) print(\n 使用 V001 (4座) 进行贪心打包 ) packed_groups pack_requests(requests, vehicles[0]) for idx, group in enumerate(packed_groups): print(f行程组 {idx 1}: {[r.request_id for r in group]}, f人数 {sum(r.passengers for r in group)}) print(\n 为每个行程组生成路线计划 ) plans [] for group in packed_groups: plan build_route_plan(group, vehicles[0]) plans.append(plan) print(f车辆 {plan.vehicle_id} 行程组: {plan.request_ids}) print(f 顺序: { - .join(plan.order)}) print(f 总距离: {plan.total_distance} km, 预计时间: {plan.estimated_time} 分钟) if __name__ __main__: main()在这里我特意使用了两个不同的网格大小分组用0.1度的网格距离计算用经纬度近似。你运行后会发现请求 R001、R002、R003、R006、R008 会被分到一个方向组R004、R005、R007 会分到另一个方向组。这就是“方向分组”带来的直观效果。6. 运行结果与效果验证在命令行运行main.py预期输出如下坐标和距离为演示数据实际数值取决于机器计算结果 按目的地网格分组 网格 (312, 1216): [R001, R002, R003, R006] 网格 (312, 1220): [R004, R005, R007] 网格 (312, 1215): [R008] 使用 V001 (4座) 进行贪心打包 行程组 1: [R001, R002, R003] 行程组 2: [R004, R005] 行程组 3: [R006] 行程组 4: [R007] 行程组 5: [R008] 为每个行程组生成路线计划 车辆 V001 行程组: [R001, R002, R003] 顺序: 上车R001 - 上车R003 - 上车R002 - 下车R003 - 下车R001 - 下车R002 总距离: 15.23 km, 预计时间: 30 分钟 ...如何验证打包结果是否合理至少要看四个指标是否所有请求都被包含进去了。每个行程组的总人数是否小于等于车辆容量。每个请求的时间窗是否得到满足。行程组数量是否比“每人单独一车”的方案更少。如果输出中出现了“某行程组人数超过车辆容量”或“某请求未被分配”说明校验逻辑或遍历逻辑有 Bug需要回到can_pack和pack_requests检查。如果每个行程组的人数都合法但行程组数量仍然非常多说明贪心策略的局限正在显现因为请求的处理顺序是固定的有些请求本来可以拼进前面的组但因为先处理了其他请求导致容量被占用。要观察这一点只需要把requests列表顺序调换或者增加一个“先按目的地网格排序后再打包”的步骤。真实项目中通常采用多种策略并行计算然后选择行程组数量最少的方案。7. 常见问题与排查方法拼车打包模块运行起来并不难难在结果质量不稳定。下面是我在设计和复盘这一类模块时总结的高频问题。问题现象可能原因排查方式解决方案打包结果总是“一人一车”拼不起来请求顺序太随机贪心策略找不到合适组合打印每个请求的出发时间窗和目的地网格先按网格分组组内再排序或先按时间窗排序再打包时间窗校验把大量请求过滤掉对“时间窗交集”的定义过于严格检查每个请求的 start_time 和 end_time 是否过短放宽为“实际出发时间可以落在共同窗口内”或引入“最早可等待时间”路线顺序明显不合理先送了远处的人接完所有人再送所有人的策略过于简单打印当前车辆位置与所有途经点的距离换成“动态插入最近途经点”策略或使用 TSP 近似算法打包结果不稳定同样数据跑出不同结果遍历顺序依赖请求在列表中的位置固定请求排序字段如按创建时间排序打包前统一排序保证可复现性距离计算和真实路线相差太大使用了直线距离而非道路距离打印几个样本订单的实际路线距离在真实项目替换为地图路线规划服务生产环境高峰期计算超时实时请求过多打包逻辑在同步调用里执行观察接口耗时和请求数量曲线采用离线批次打包或把打包拆成分组/校验两级异步处理这几个问题里最隐蔽的是第二个——时间窗。很多团队在初期会把时间窗定义为“乘客最早出行时间”然后在打包时要求所有乘客的最早时间重合。这会让大量请求无法拼车。更合理的建模方式是产生一个“计划出发时间”只要该时间落在每个人的时间窗内即可。比如乘客 A 的时间窗是 8:00 到 8:15乘客 B 的时间窗是 8:05 到 8:20那么 8:10 出发就能同时满足两人。这种情况下时间窗交集依然存在但不一定要求两人的“最早时间”相同。排查顺序建议先看分组结果是否符合直觉排除方向分组问题。再看容量校验确认车辆容量约束生效。然后看时间窗确认不是所有请求都被单独成组。最后看路线顺序确认输出不是“在同一个网格内绕圈”。8. 生产环境中的拼车打包最佳实践从上面的最小示例走向生产环境需要补的东西非常多。这里给出几个我认为最关键的工程建议。8.1 把“打包”从“下单”中拆出来新手设计拼车系统时最常见的错误是把打包逻辑直接写在下单接口内部。这样做有两个明显问题下单是高频、低延迟操作而打包是计算密集任务两者混在一起会导致接口抖动。下单时需要立即给用户反馈但拼车时机可能稍纵即逝实时同步计算往往被迫用最简单的贪心算法失去优化空间。更可靠的做法是下单时只做“快速判断是否有可用拼车组”如果没有则创建新行程真正的打包优化放到一个异步任务池里执行每隔几秒或十几秒重新计算附近的请求组合动态调整行程组。这种设计在业界已经很成熟即使是几个订单的小系统也建议从第一天就按这个方向拆分。8.2 组合策略而不是依赖单一贪心最小示例使用的“首次适应”策略优点是简单、快缺点是一次运行很可能陷入局部较差的解。实际项目中可以并行运行多个策略按起点距离排序后打包按目的地网格分组后打包按出发时间窗排序后打包随机打乱顺序后打包是的这个也有用作为随机重启策略。然后统一比较结果选择“行程组数量最少”或“预估总里程最低”的方案作为最终输出。这种多策略竞争的方式实现成本低效果提升往往比换一个复杂算法更明显。8.3 路径顺序必须考虑“先下后上”和“司机等待时间”路线顺序不是简单的“先接人后送人”。真实场景中如果接第一个乘客时绕了太远后面的乘客会投诉等待时间过长。因此很多产品会加入“最大上车等待时间”约束。比如从第一个乘客上车到最后一个乘客上车不能超过 8 分钟。对应的做法是在order_planner中增加约束判断每插入一个新上车点都要检查从上一个上车点到当前上车点的时间是否超过阈值超过则不能插入。8.4 数据量与实时性的平衡拼车打包是一个典型的“空间换时间”问题。如果使用地图服务来计算真实道路距离每一次路径规划都有成本。生产环境可以把常用区域的“网格之间的平均距离”预计算成一张缓存表运行时直接用缓存做近似判断只有在最终确认行程组时才调用完整路线规划。这里也可以使用“二级筛选”先用网格距离粗筛再用路线距离精算。这也是很多物流系统处理配送路径的通用做法。8.5 安全与合规提醒拼车场景涉及真实出行安全系统层面的风险控制不能少乘客实名信息与行程单必须关联不能因为拼车降低身份核验强度。行程分享和紧急联系人功能要与拼车行程打通。对司机端和乘客端的异常行为要有监控比如频繁取消、长期绕路、多次改地址。行程数据存储需要满足相关法律法规对个人信息保护的要求不建议将非必要的位置日志长期明文保存。涉及生产环境的数据变更、算法参数调整必须走灰度发布和回滚机制先在测试环境验证再全量上线。9. 总结与后续学习方向拼车打包从问题定义上看是装箱问题的变体从工程实现上看是“分组、校验、排序”三个环节的组合。本文中的最小示例只实现了最基础的第一次适应贪心策略和最简单的“先接后送”路线顺序但这已经能够跑通一个完整的拼车闭环。如果你想继续深入有四个方向值得投入约束规划与整数规划。使用ortools或pulp对小规模请求做精确求解理解“全局最优解”长什么样作为启发式算法的对照。车辆路径问题VRP。拼车打包最终都会走向对多车辆、多路径的综合规划VRP 是你绕不开的领域。地图数据与真实路线服务。把近似距离替换为真实路线距离后你会发现很多“看起来顺路”的请求实际上并不适合拼车。强化学习在调度中的应用。虽然落地难度高但对大规模运力分配问题的思路有启发价值。最后提醒一句拼车打包没有银弹。不要试图一开始就做一个“所有情况下都最优”的模块。先用一个可解释、可观测、可回滚的简单版本跑起来再根据真实数据逐步优化这是我对这类系统最稳妥的建议。
拼车打包算法：从装箱问题到贪心路径规划的工程实践
1. 这篇文章真正要解决的问题先抛一个经常在后端开发群里被问到的问题做拼车类功能时需求文档里写着“把顺路的乘客拼到同一辆车里”你觉得这只是一个简单的“按起点终点过滤”的查询操作还是背后有一个独立的算法模块很多团队第一次做拼车会把拼车逻辑直接写在下单服务里新乘客来了查一下附近有没有未满座的订单有就塞进去没有就创建新订单。这种实现方式在前端体验上叫“快”但在运力使用效率上往往非常差。原因也很简单你把拼车当成了一次性匹配而没有把它当成一个“打包过程”。拼车打包的核心任务是在满足乘客出发时间、行程方向、车辆座位数的约束下把多个独立的出行请求组合成一辆车能完成的行程组合。它本质上是一个组合优化问题和装箱问题Bin Packing Problem非常相似。你面对的是一堆大小不一、目的地各异的“物品”需要把它们装进容量受限的“箱子”里同时让总成本最低、满意度最高。这篇文章不讲那些需要数学博士才能看懂的精确求解算法而是从工程实现的角度拆解“拼车打包”这个问题到底是什么、它的难点在哪、一个可运行的最小系统应该怎么设计、实际生产环境里有哪些坑。读完后你可以得到三样东西一套把拼车场景抽象成“打包模型”的建模思路一个基于 Python 的可运行最小示例能处理按方向分组、按容量打包、按时间窗过滤一份从“能跑”到“能用”的工程优化清单。无论你是做网约车、货运、顺风车还是做企业内部通勤系统“拼车打包”这个模块的设计思路都适用。2. 核心概念拼车匹配、拼车打包与装箱问题2.1 拼车匹配和拼车打包不是一回事很多团队会把“匹配”和“打包”混在一起导致系统上线后逻辑越改越乱。这两者是有明确边界的拼车匹配解决的是“哪几个乘客应该在同一辆车里”侧重人之间的关系。拼车打包解决的是“这一组乘客的订单如何组成一个可执行的行程”侧重订单和运力之间的关系。你可以这样理解匹配是选人打包是装车。乘客之间可能彼此合适但装到一辆车上之后路线是否绕、时间是否超、容量是否够这就是打包阶段要处理的问题。举一个具体的例子有两个乘客A 从起点 S 去往 T1B 从起点 S 去往 T2两个目的地距离不远方向上看起来完全顺路。但如果你把 AB 的行程放进同一辆车会发现先送谁、后送谁会导致总路程不同。如果先送 A 再送 B总路程可能是 12 公里先送 B 再送 A总路程可能是 9 公里。这就是打包时的路径顺序优化。2.2 装箱问题带来的直觉装箱问题的经典描述是有若干个体积不同的物品要把它们全部装进容量相同的箱子里目标是使用最少的箱子。拼车打包和装箱问题在结构上是同构的装箱问题拼车打包物品拼车请求物品体积乘客占用座位数箱子车辆箱子容量车辆剩余座位数最优目标使用的箱数最少等价拼车目标使用车辆数最少或运力利用率最高但拼车打包比标准装箱问题更复杂。因为装箱问题中的物品是可以任意组合的而拼车请求之间还有时间、空间、路径上的约束。你可以把拼车打包理解成“带约束的装箱问题”。2.3 为什么说这是一个 NP-Hard 问题从算法复杂度角度看当请求数量变大时精确求全局最优解的计算量会爆炸式增长。假设有 20 个请求每辆车最多坐 4 人你需要尝试的组合方式是海量的。这就是为什么生产环境里几乎不会用穷举法或整数规划去实时求解而是采用启发式算法、贪心算法或者把打包任务扔给离线调度系统异步计算。这里有个重要的工程判断在拼车场景里你并不需要“理论最优解”你更需要“在规定时间内能算出来的、满意的可行解”。认识到这一点你就不会去写一个试图暴力枚举所有组合的后端接口而是老老实实地做分层设计。回到我们的主题。拼车打包的核心流程可以概括为一句话先分组再装车最后排路线。3. 拼车打包的完整流程与关键设计3.1 输入与输出在设计拼车打包模块之前先定义清楚输入输出边界。输入一批待处理的拼车请求每个请求包含出发地、目的地、出发时间窗、人数、用户可接受的绕路时间。可用运力信息每个运力包含车型、座位数、当前位置。输出若干个行程组每组由若干请求和一个运力实例组成。每个行程组的行驶路线顺序例如从起点出发先到站点 A再到站点 B。每个请求的预计上车时间和预计到达时间。3.2 打包流程的阶段划分一个可落地的拼车打包流程可以拆成四个阶段请求预处理分组容量与约束校验路径排序与时间估算第一阶段请求预处理。把请求中的经纬度解析成可用于距离计算的坐标规划出每个请求单独行驶时的预估路线距离作为后续判断“绕路率”的基准。第二阶段分组。按照方向、区域、路线相似度进行粗分组把明显不会顺路的请求分开。常用的做法是网格哈希把地图按经纬度切成若干网格相同或相邻网格的请求进入同一个候选桶。第三阶段容量与约束校验。在候选桶内进一步组合校验座位数、时间窗、绕路距离是否满足设定的阈值。这一阶段才是真正决定“能不能装进同一辆车”的关键。第四阶段路径排序与时间估算。对通过校验的组合生成实际行驶顺序计算每个乘客的上车点和下车点顺序估算总行程时间。这四个阶段不是必须同步执行的。在工程实现上阶段一和阶段二可以做成离线的预计算服务阶段三和阶段四做成实时服务。这样能大幅降低高峰期的计算压力。3.3 一个需要提前想清楚的问题怎么定义“顺路”分组阶段最核心的指标是“顺路程度”。很多初学者喜欢用“起点距离”来定义顺路这是一个高频错误。举两个反例两个请求起点相距只有 100 米但一个去城东一个去城西完全不顺路。两个请求起点相距 3 公里但都通往高速方向反而可以在高速入口汇合。正确的做法是使用“路线重合度”或“增量绕路距离”来判断。简单版本可以这样定义为第一个请求规划一条完整路线得到总距离 D1。尝试把第二个请求的途经点插入路线中得到新路线 D2。计算增加的绕行距离 delta D2 - D1。如果 delta 小于阈值或小于 D1 的某个比例认为顺路。这个思路不需要复杂的算法只需要一个路线规划服务和简单的途经点插入逻辑。4. 环境准备用最小工具链跑通打包模型为了专注讲清“拼车打包”本身我们使用最轻量的环境不需要引入地图 SDK 和真实路线服务。本文示例的软硬件环境如下操作系统Windows / macOS / Linux 均可Python3.9 及以上依赖库仅使用标准库不需要额外安装开发工具任意 Python IDE 或 VS Code Python 插件如果你对坐标计算比较敏感也可以安装geopy但本文为了保持示例可复制性使用最简单的基于经纬度差的欧氏距离近似计算。真实项目里请使用 Haversine 公式或调用地图服务区别只在于距离精度。# 本文示例不依赖第三方包直接运行 python 即可 python --version5. 核心代码实现三个层面的打包逻辑下面我们分三个层次实现一个最小可用的拼车打包系统。5.1 定义请求与运力数据结构首先定义拼车请求和运力的数据结构。这里我们刻意保留最核心的字段方便你理解问题本质。# 文件路径model.py import itertools from dataclasses import dataclass, field from typing import List, Dict dataclass class RideRequest: 拼车请求 request_id: str pickup_lat: float # 上车点纬度 pickup_lng: float # 上车点经度 dropoff_lat: float # 下车点纬度 dropoff_lng: float # 下车点经度 start_time: int # 最早出发时间分钟从当日 0 点起算 end_time: int # 最晚出发时间分钟 passengers: int 1 # 人数 max_detour_ratio: float 0.4 # 可接受的最大绕路比例 accepted: bool False # 是否已进入某个行程组# 文件路径model.py续 dataclass class Vehicle: 运力一辆车 vehicle_id: str capacity: int # 座位数 start_lat: float start_lng: float# 文件路径model.py续 dataclass class RoutePlan: 一次拼车打包的输出结果 vehicle_id: str request_ids: List[str] order: List[str] # 途经点顺序例如 [P001上车, P002上车, P001下车, P002下车] total_distance: float estimated_time: int # 单位分钟为了避免代码文件过长示例里把类定义集中在model.py中。真实项目中建议按领域模型分文件管理。5.2 距离计算与方向分组接下来实现最基础的两个工具函数距离计算和方向分组。距离计算这里不做真实道路距离而是用基于经纬度差的近似值。这个近似值作为示例足够但生产环境必须替换成路线规划服务返回的“实际道路距离”。# 文件路径geo_utils.py import math from typing import List from model import RideRequest def approx_distance(lat1: float, lng1: float, lat2: float, lng2: float) - float: 简单近似距离单位公里。仅用于示例生产环境请用 Haversine 或地图服务。 lat_diff lat1 - lat2 lng_diff lng1 - lng2 # 纬度方向每度约 111 公里经度方向按 cos(纬度) 缩放 lat_km lat_diff * 111.0 lng_km lng_diff * 111.0 * math.cos(math.radians((lat1 lat2) / 2)) return math.sqrt(lat_km * lat_km lng_km * lng_km) def direction_grid(lat: float, lng: float, grid_size: float 0.05) - tuple: 把坐标映射到网格。grid_size 约 0.05 度在赤道附近约 5.5 公里。 return (round(lat / grid_size), round(lng / grid_size))这里我们引入了方向网格的概念。拼车场景中“方向”可以通过目的地的网格编码来表达。将目的地投影到网格后同一个网格或相邻网格的请求被分入同一组。# 文件路径grouping.py from typing import Dict, List from collections import defaultdict from model import RideRequest from geo_utils import direction_grid def group_by_destination(requests: List[RideRequest], grid_size: float 0.05) - Dict[tuple, List[RideRequest]]: 按目的地网格分组。 返回一个字典key 是网格坐标value 是该网格下的请求列表。 groups: Dict[tuple, List[RideRequest]] defaultdict(list) for req in requests: key direction_grid(req.dropoff_lat, req.dropoff_lng, grid_size) groups[key].append(req) return groups这个分组逻辑虽然简单但已经能处理“同一个方向的请求优先打包”这个直觉。如果两个请求的目的地在同一个网格它们大概率是同一个方向的适合进入后续容量校验环节。5.3 容量与时间窗校验有了候选组之后下一步是判断一个请求能否进入某个行程组。这部分是打包的核心校验逻辑。# 文件路径packing.py from typing import List from model import RideRequest, Vehicle def can_pack(group: List[RideRequest], new_req: RideRequest, vehicle: Vehicle) - bool: 判断 new_req 是否能加入到已有的 group 中。 校验两件事 1. 总人数不超过车辆容量。 2. 出发时间窗有交集。 total_passengers sum([r.passengers for r in group]) new_req.passengers if total_passengers vehicle.capacity: return False # 时间窗交集所有请求必须存在一个共同的可出发时间 latest_start min([r.end_time for r in group] [new_req.end_time]) earliest_start max([r.start_time for r in group] [new_req.start_time]) if earliest_start latest_start: return False return True def pack_requests(requests: List[RideRequest], vehicle: Vehicle) - List[List[RideRequest]]: 贪心打包从前往后遍历请求能塞进当前组就塞否则新建一组。 注意这个版本没有做路径顺序优化仅做容量与时间校验。 groups: List[List[RideRequest]] [] for req in requests: placed False for group in groups: if can_pack(group, req, vehicle): group.append(req) req.accepted True placed True break if not placed: groups.append([req]) req.accepted True return groups这个pack_requests方法本质上是最简单的“首次适应”贪心算法。在装箱问题里这个策略的时间复杂度是 O(n^2)优点是非常快缺点是完全不考虑后续请求。为了更直观地看到这种贪婪策略的问题我们加入一个“随机顺序打包”的对比函数每次先打乱请求顺序再进行打包然后统计需要用多少辆车。这个技巧可以用来做简单的策略对比比空谈“贪心算法效果差”更能说明问题。5.4 加入路线排序的完整示例前面几个函数只完成了“塞进同一辆车”的判断但没有生成行驶顺序。真实拼车流程中必须输出一个清晰的路线顺序否则司机拿到行程组也不知道先去接谁。下面我们写一个更完整的打包函数它会为每个行程组生成最简单的“先接所有乘客再依次送客”的路线顺序。# 文件路径order_planner.py from typing import List, Tuple from model import RideRequest, Vehicle, RoutePlan from geo_utils import approx_distance def _pickup_sequence(requests: List[RideRequest], vehicle: Vehicle) - List[Tuple[str, str]]: 生成接送顺序返回格式为 [(动作, 请求ID)]。 简化策略先按上车点与车辆当前位置的距离排序依次接人 接到所有乘客后按下车点与当前位置的距离排序依次送人。 remaining list(requests) current_lat vehicle.start_lat current_lng vehicle.start_lng sequence [] while remaining: # 找离当前位置最近的未接乘客 nearest min( remaining, keylambda r: approx_distance(current_lat, current_lng, r.pickup_lat, r.pickup_lng) ) sequence.append((上车, nearest.request_id)) remaining.remove(nearest) current_lat nearest.pickup_lat current_lng nearest.pickup_lng # 接完所有人后按下车点距离依次送客 remaining list(requests) while remaining: nearest min( remaining, keylambda r: approx_distance(current_lat, current_lng, r.dropoff_lat, r.dropoff_lng) ) sequence.append((下车, nearest.request_id)) remaining.remove(nearest) current_lat nearest.dropoff_lat current_lng nearest.dropoff_lng return sequence def build_route_plan(group: List[RideRequest], vehicle: Vehicle) - RoutePlan: 为一个行程组生成 RoutePlan。 sequence _pickup_sequence(group, vehicle) total_distance _calculate_route_distance(group, vehicle, sequence) # 简化时间估算假设平均速度 30 公里/小时 estimated_time int(total_distance / 30 * 60) return RoutePlan( vehicle_idvehicle.vehicle_id, request_ids[r.request_id for r in group], order[f{action}{req_id} for action, req_id in sequence], total_distanceround(total_distance, 2), estimated_timeestimated_time ) def _calculate_route_distance(group: List[RideRequest], vehicle: Vehicle, sequence: List[Tuple[str, str]]) - float: 根据接送顺序计算总距离。 current_lat vehicle.start_lat current_lng vehicle.start_lng total 0.0 req_map {r.request_id: r for r in group} for action, req_id in sequence: req req_map[req_id] target_lat req.pickup_lat if action 上车 else req.dropoff_lat target_lng req.pickup_lng if action 上车 else req.dropoff_lng total approx_distance(current_lat, current_lng, target_lat, target_lng) current_lat target_lat current_lng target_lng return total这里使用的“接完所有人再送所有人”策略不是最优解但它符合很多拼车产品初期的实际逻辑先保证所有乘客都能上车再考虑谁先下车。它容易实现、容易解释、也容错。5.5 主流程串联所有模块写好后通过一个main.py把完整流程串起来生成测试数据并输出打包结果。# 文件路径main.py from model import RideRequest, Vehicle from grouping import group_by_destination from packing import pack_requests from order_planner import build_route_plan def make_demo_requests(): 构造 8 个模拟请求制造 2 个明显的方向分组。 requests [ RideRequest(R001, 31.2304, 121.4737, 31.2500, 121.6000, 480, 490, 1), RideRequest(R002, 31.2350, 121.4800, 31.2550, 121.6100, 475, 500, 2), RideRequest(R003, 31.2400, 121.4700, 31.2600, 121.6200, 470, 485, 1), RideRequest(R004, 31.2200, 121.4600, 31.2100, 122.0000, 480, 500, 1), RideRequest(R005, 31.2250, 121.4650, 31.2050, 122.0100, 478, 495, 3), RideRequest(R006, 31.2450, 121.4900, 31.2700, 121.6300, 485, 500, 1), RideRequest(R007, 31.2300, 121.4750, 31.2150, 122.0200, 460, 480, 1), RideRequest(R008, 31.2500, 121.4850, 31.2300, 121.5900, 490, 510, 2), ] return requests def main(): requests make_demo_requests() vehicles [ Vehicle(V001, 4, 31.2280, 121.4700), Vehicle(V002, 6, 31.2280, 121.4700), ] print( 按目的地网格分组 ) groups group_by_destination(requests, grid_size0.1) for grid_key, req_list in groups.items(): print(f网格 {grid_key}: {[r.request_id for r in req_list]}) print(\n 使用 V001 (4座) 进行贪心打包 ) packed_groups pack_requests(requests, vehicles[0]) for idx, group in enumerate(packed_groups): print(f行程组 {idx 1}: {[r.request_id for r in group]}, f人数 {sum(r.passengers for r in group)}) print(\n 为每个行程组生成路线计划 ) plans [] for group in packed_groups: plan build_route_plan(group, vehicles[0]) plans.append(plan) print(f车辆 {plan.vehicle_id} 行程组: {plan.request_ids}) print(f 顺序: { - .join(plan.order)}) print(f 总距离: {plan.total_distance} km, 预计时间: {plan.estimated_time} 分钟) if __name__ __main__: main()在这里我特意使用了两个不同的网格大小分组用0.1度的网格距离计算用经纬度近似。你运行后会发现请求 R001、R002、R003、R006、R008 会被分到一个方向组R004、R005、R007 会分到另一个方向组。这就是“方向分组”带来的直观效果。6. 运行结果与效果验证在命令行运行main.py预期输出如下坐标和距离为演示数据实际数值取决于机器计算结果 按目的地网格分组 网格 (312, 1216): [R001, R002, R003, R006] 网格 (312, 1220): [R004, R005, R007] 网格 (312, 1215): [R008] 使用 V001 (4座) 进行贪心打包 行程组 1: [R001, R002, R003] 行程组 2: [R004, R005] 行程组 3: [R006] 行程组 4: [R007] 行程组 5: [R008] 为每个行程组生成路线计划 车辆 V001 行程组: [R001, R002, R003] 顺序: 上车R001 - 上车R003 - 上车R002 - 下车R003 - 下车R001 - 下车R002 总距离: 15.23 km, 预计时间: 30 分钟 ...如何验证打包结果是否合理至少要看四个指标是否所有请求都被包含进去了。每个行程组的总人数是否小于等于车辆容量。每个请求的时间窗是否得到满足。行程组数量是否比“每人单独一车”的方案更少。如果输出中出现了“某行程组人数超过车辆容量”或“某请求未被分配”说明校验逻辑或遍历逻辑有 Bug需要回到can_pack和pack_requests检查。如果每个行程组的人数都合法但行程组数量仍然非常多说明贪心策略的局限正在显现因为请求的处理顺序是固定的有些请求本来可以拼进前面的组但因为先处理了其他请求导致容量被占用。要观察这一点只需要把requests列表顺序调换或者增加一个“先按目的地网格排序后再打包”的步骤。真实项目中通常采用多种策略并行计算然后选择行程组数量最少的方案。7. 常见问题与排查方法拼车打包模块运行起来并不难难在结果质量不稳定。下面是我在设计和复盘这一类模块时总结的高频问题。问题现象可能原因排查方式解决方案打包结果总是“一人一车”拼不起来请求顺序太随机贪心策略找不到合适组合打印每个请求的出发时间窗和目的地网格先按网格分组组内再排序或先按时间窗排序再打包时间窗校验把大量请求过滤掉对“时间窗交集”的定义过于严格检查每个请求的 start_time 和 end_time 是否过短放宽为“实际出发时间可以落在共同窗口内”或引入“最早可等待时间”路线顺序明显不合理先送了远处的人接完所有人再送所有人的策略过于简单打印当前车辆位置与所有途经点的距离换成“动态插入最近途经点”策略或使用 TSP 近似算法打包结果不稳定同样数据跑出不同结果遍历顺序依赖请求在列表中的位置固定请求排序字段如按创建时间排序打包前统一排序保证可复现性距离计算和真实路线相差太大使用了直线距离而非道路距离打印几个样本订单的实际路线距离在真实项目替换为地图路线规划服务生产环境高峰期计算超时实时请求过多打包逻辑在同步调用里执行观察接口耗时和请求数量曲线采用离线批次打包或把打包拆成分组/校验两级异步处理这几个问题里最隐蔽的是第二个——时间窗。很多团队在初期会把时间窗定义为“乘客最早出行时间”然后在打包时要求所有乘客的最早时间重合。这会让大量请求无法拼车。更合理的建模方式是产生一个“计划出发时间”只要该时间落在每个人的时间窗内即可。比如乘客 A 的时间窗是 8:00 到 8:15乘客 B 的时间窗是 8:05 到 8:20那么 8:10 出发就能同时满足两人。这种情况下时间窗交集依然存在但不一定要求两人的“最早时间”相同。排查顺序建议先看分组结果是否符合直觉排除方向分组问题。再看容量校验确认车辆容量约束生效。然后看时间窗确认不是所有请求都被单独成组。最后看路线顺序确认输出不是“在同一个网格内绕圈”。8. 生产环境中的拼车打包最佳实践从上面的最小示例走向生产环境需要补的东西非常多。这里给出几个我认为最关键的工程建议。8.1 把“打包”从“下单”中拆出来新手设计拼车系统时最常见的错误是把打包逻辑直接写在下单接口内部。这样做有两个明显问题下单是高频、低延迟操作而打包是计算密集任务两者混在一起会导致接口抖动。下单时需要立即给用户反馈但拼车时机可能稍纵即逝实时同步计算往往被迫用最简单的贪心算法失去优化空间。更可靠的做法是下单时只做“快速判断是否有可用拼车组”如果没有则创建新行程真正的打包优化放到一个异步任务池里执行每隔几秒或十几秒重新计算附近的请求组合动态调整行程组。这种设计在业界已经很成熟即使是几个订单的小系统也建议从第一天就按这个方向拆分。8.2 组合策略而不是依赖单一贪心最小示例使用的“首次适应”策略优点是简单、快缺点是一次运行很可能陷入局部较差的解。实际项目中可以并行运行多个策略按起点距离排序后打包按目的地网格分组后打包按出发时间窗排序后打包随机打乱顺序后打包是的这个也有用作为随机重启策略。然后统一比较结果选择“行程组数量最少”或“预估总里程最低”的方案作为最终输出。这种多策略竞争的方式实现成本低效果提升往往比换一个复杂算法更明显。8.3 路径顺序必须考虑“先下后上”和“司机等待时间”路线顺序不是简单的“先接人后送人”。真实场景中如果接第一个乘客时绕了太远后面的乘客会投诉等待时间过长。因此很多产品会加入“最大上车等待时间”约束。比如从第一个乘客上车到最后一个乘客上车不能超过 8 分钟。对应的做法是在order_planner中增加约束判断每插入一个新上车点都要检查从上一个上车点到当前上车点的时间是否超过阈值超过则不能插入。8.4 数据量与实时性的平衡拼车打包是一个典型的“空间换时间”问题。如果使用地图服务来计算真实道路距离每一次路径规划都有成本。生产环境可以把常用区域的“网格之间的平均距离”预计算成一张缓存表运行时直接用缓存做近似判断只有在最终确认行程组时才调用完整路线规划。这里也可以使用“二级筛选”先用网格距离粗筛再用路线距离精算。这也是很多物流系统处理配送路径的通用做法。8.5 安全与合规提醒拼车场景涉及真实出行安全系统层面的风险控制不能少乘客实名信息与行程单必须关联不能因为拼车降低身份核验强度。行程分享和紧急联系人功能要与拼车行程打通。对司机端和乘客端的异常行为要有监控比如频繁取消、长期绕路、多次改地址。行程数据存储需要满足相关法律法规对个人信息保护的要求不建议将非必要的位置日志长期明文保存。涉及生产环境的数据变更、算法参数调整必须走灰度发布和回滚机制先在测试环境验证再全量上线。9. 总结与后续学习方向拼车打包从问题定义上看是装箱问题的变体从工程实现上看是“分组、校验、排序”三个环节的组合。本文中的最小示例只实现了最基础的第一次适应贪心策略和最简单的“先接后送”路线顺序但这已经能够跑通一个完整的拼车闭环。如果你想继续深入有四个方向值得投入约束规划与整数规划。使用ortools或pulp对小规模请求做精确求解理解“全局最优解”长什么样作为启发式算法的对照。车辆路径问题VRP。拼车打包最终都会走向对多车辆、多路径的综合规划VRP 是你绕不开的领域。地图数据与真实路线服务。把近似距离替换为真实路线距离后你会发现很多“看起来顺路”的请求实际上并不适合拼车。强化学习在调度中的应用。虽然落地难度高但对大规模运力分配问题的思路有启发价值。最后提醒一句拼车打包没有银弹。不要试图一开始就做一个“所有情况下都最优”的模块。先用一个可解释、可观测、可回滚的简单版本跑起来再根据真实数据逐步优化这是我对这类系统最稳妥的建议。
