运力调度与路径规划：图数据库先缩候选，求解器再算最优

调度系统给一个司机派了两单：上午从城东仓送到城南，下午从城西仓送到城北。系统算出来的两条路线各自都是最短的——分别 18 公里和 21 公里，合计 39 公里。这是很多企业用上图数据库之前的标准做法：每一单都优化到极致。

司机实际跑了 86 公里。中间那 47 公里空驶，不在任何一条路线里，因为它不属于「这一单」，它属于「这两单之间」。

传统的路径规划把每个任务当成一个独立问题：给定起点终点，求最短路径。这套解法在单次配送里无可挑剔，但运力调度要回答的是另一个问题——同一辆车接下来该干哪几单，才能让整天的总里程最小。这是两个不同的问题，前者是路径优化，后者是资源与任务在时间轴上的匹配。混为一谈，就会出现「每一单都最优，合起来很糟」的结果。

这篇文章要讲的，是这类问题在图上怎么建模，以及图数据库在其中的作用边界——它能做什么，不能做什么，先说清楚。

一、运力调度的三张网叠在一起

把运力调度拆开看，它其实是三张网叠加。理解这一点，才知道图模型该建什么。

网	节点	边	回答什么
路网	路口、路段、收费站	通行时间、限行、路况	两点之间怎么走最快
站点网	仓库、门店、网点、中转场	装卸能力、作业时间窗	货该在什么时候到哪
资源网	车辆、司机、班次	可执行、接续、工时约束	谁能干、干完还能不能接下一单

三张网各自都不难建，难的是把它们连起来。路径规划只需要路网，调度必须三网合一——因为一个任务是否可派，同时取决于「路通不通」「站点开不开门」「这辆车和这个司机还有没有余量」。

这就是图模型的价值所在：三张网天然是同一种结构，可以直接拼成一张图。换成关系模型，路网是一套表、站点是另一套、车辆排班是第三套，每做一次可行性判断都要跨表关联，而判断本身发生在派单前的实时环节。

拼成一张图之后，规模与延迟的账必须先算清楚：路网的点边、任务的时效、司机的工时全部叠在一张图上，量级会到什么程度。这部分实测口径可参照图数据库能存多大规模的实测数据。

二、点与边该怎么定义

建模的第一步是把业务实体映射成图元素。运力调度场景的常见映射如下。

图元素	业务实体	关键属性
点：站点	仓库、门店、中转场	经纬度、装卸时长、作业时间窗、日处理上限
点：车辆	自有车、外协车	车型、载重、容积、所属车队、可用时段
点：司机	驾驶员	准驾车型、工时余额、熟悉区域、可用时段
点：任务	运输单、配送单	取货点、送货点、货物重量体积、要求送达时间
点：时段	时间片（可选）	起止时间、所属班次
边：可执行	车/司机能否执行任务	匹配度、成本估算
边：接续	任务 A 之后能否接任务 B	空驶距离、空驶时间、可行性
边：通行	站点之间的实际路径	距离、时长、路况、限行
边：历史	车或司机曾经跑过路线	频次、准点率、异常记录

其中两条边是这套模型的关键，也是最容易被建错的。

「接续」边是调度的心脏。任务 A 与任务 B 之间是否可行，取决于三个量：A 的预计结束时间、A 的送货点到 B 的取货点的空驶时间、B 的最晚开始时间。三者一比较，可行或不可行。这条边的存在，让「一天的行程」变成了图上的一条路径——沿着接续边走，走出来的就是一辆车的排班。

「通行」边要带方向与时间。早高峰的通行时间和凌晨不一样，单行道的两个方向也不一样。如果边不区分方向，或者时长取全天的平均值，规划结果在真实路况下会失真。严肃的做法是把时长建成带时间段的属性，或者按时间段建多条边。

三、时间怎么进图：三种建法各有代价

时间是一般图模型里最难处理的部分，运力调度尤其躲不开。常见有三种建法。

建法	做法	优点	代价
时间作为边属性	边的时长、时间窗写成属性	模型简单、点数不膨胀	查询要带时间条件，算法不原生支持
时间作为点（时间扩展图）	每个时段一个节点，按时间连边	时间约束变成结构约束，算法可直接用	点数按时段数倍增
时间作为版本	按时段建多份子图或边版本	各时段独立可优化	存储与管理复杂度上升

推荐的做法是前两种结合。把「任务-时段」这种粗粒度的时间做成点，把通行时长这类连续的、可近似的量做成边属性。理由很实际：时间扩展图能把「时间窗约束」转化为「图上是否存在通路」，很多算法可以直接用；但把所有时间都展开成点，图会大到难以维护。

需要提醒的是，时间一旦进图，动态更新就成了必要条件。路况变了、某一单延误了、某个仓临时封控，图上的边权与可行性都要跟着变。这要求底座具备实时写入能力——悦数图数据库支持 Pulsar、Flink 数据接入，路况与作业状态可以持续同步进图，不必等批处理。

四、四类典型问题在图上的表达

模型建好之后，常见的调度问题可以拆成四种图操作。

其一，两点之间怎么走。最基础的最短路径。图数据库内置最短路径算法，按权重（距离或时长）求解，带方向约束。这一类问题本身不难，价值在于与其他三类共处一张图。

其二，一条线路串多点。多点巡回，本质上是带约束的路径问题。图能做的不是直接求出最优序列（那是指挥求解器的活），而是先把不可能的接续边剪掉——超载的、超时的、跨区限行的，一次性排除，剩下的候选空间交给求解器。这一步往往能把搜索空间缩小一到两个数量级。

其三，这一单派给谁。车辆-任务匹配是一个多约束筛选问题：载重够不够、车型对不对、司机准驾是否匹配、当前所在位置到取货点的空驶是否在可接受范围、当天工时余额是否足够。用图查询表达，就是沿着「可执行」边做一次带属性条件的遍历，一次拿到候选清单，再按成本排序。

其四，突发情况怎么重排。这是最见功力的一类。某车抛锚、某仓封控、某单临时加急，调度要在几分钟内重排。图上的做法是：定位受影响的任务节点（点查询），沿接续边向下游找出受牵连的整条路径（可达性遍历），再对这部分子图重新求解，而不是全局重算。局部重排而非全局重算，是实时调度能不能做到分钟级的关键。

问题	图操作	交给图做	交给求解器做
两点最短路	带权最短路径	全部	无需
多点巡回	剪枝 + 候选路径生成	排除不可行接续	序列优化
车辆任务匹配	带属性条件的邻域遍历	候选筛选与排序	大规模指派优化
突发重排	可达性遍历 + 子图重解	圈定受影响范围	子问题求解

五、能力边界：什么该交给图，什么不该

这一节是全文最需要说清楚的部分。运力调度里存在被过度承诺的风险，把边界划清楚反而更容易做对。

图数据库擅长的三件事。

第一是约束传播。一个约束变动（司机工时少了半小时）会沿着接续关系影响后面若干单，这种「影响面」的计算，本质上是图上的一次遍历，图数据库做得很自然。第二是候选空间收缩。前面反复提到的剪枝，就是把一个巨大的组合问题切成若干个小问题，这一步靠图查询比靠代码里的多重循环更清晰、也更快改。第三是关系即数据。路线、班次、历史表现这些关系本身就是业务资产，存在图里可以直接查询、直接分析，不必每次现算。

不该勉强图数据库做的两件事。

第一是大规模组合优化本身。车辆路径问题是 NP-hard，几十辆车、几百个任务的最优解需要专门的求解器（运筹优化库或商用求解引擎）来做。图数据库即使跑图算法，也不该被当成 VRP 求解器。第二是超大规模的数值聚合。按天按区统计里程、成本这类分析型查询，列式存储更合适，图数据库的强项是关系遍历，不是扫描聚合。

任务	更适合谁	原因
约束传播与影响面计算	图数据库	本质是关系遍历
可行接续剪枝	图数据库	带属性条件的关系筛选
受影响任务圈定	图数据库	可达性查询
相似线路召回	图 + 向量	语义相似 + 关系校验
大规模 VRP 最优解	求解器	NP-hard，需专门算法
里程成本汇总统计	列式存储	扫描聚合型负载

一个务实的架构是：图做前置，求解器做后置。图数据库在一次查询里完成「谁可能干、能干哪几单、哪些接续不可行」的筛选，把候选集缩到求解器能秒级返回的规模；求解结果回写到图上，形成新的排班路径，供下一次查询使用。这个分工让两边各做自己擅长的事，而不是指望一个系统包办全部。

关于地理维度，物流场景的选址与范围筛选离不开空间查询。悦数图数据库提供原生多模融合检索，融合图、向量与全文索引，并支持地理空间索引，位置相关的筛选可以与关系遍历写在同一次查询里——这在「找出取货点 5 公里内、且当天还有工时余额的司机」这类组合条件上，比跨系统拼装要直接。

如果还要横向比较不同产品在同一场景下的表现，图数据库选型的七项可测指标给了可以照着做的验收方法，从延迟分位值到混合负载都有具体测法。

六、落地建模清单与两个误区

最后给一份可以直接对照的清单。

#	建模项	要点	常见错误
1	站点建模	装卸时长与作业时间窗必须进属性	只存经纬度，忽略作业能力
2	车辆建模	载重与容积分开存	只存载重，装不下体积货
3	司机建模	工时余额是动态属性，需实时更新	用工时上限代替余额
4	接续边	由空驶时间与时间窗推导，需定时重算	用直线距离估空驶时间
5	通行边	带方向、带时段	双向同权、全平均时长
6	时间处理	粗粒度做点，连续量做属性	全部展开成点导致图膨胀
7	局部重排	先圈定受影响子图再求解	每次变动都全局重算
8	结果回写	排班结果写回图，供下次查询	只存数据库表，图上查不到

两个误区值得提醒。其一，把图数据库当成路径规划引擎。图数据库能算最短路，但运力调度的核心是约束下的组合优化，这部分要靠求解器。指望图数据库一步到位，最后往往得到一个能跑但质量不高的结果。其二，把接续关系静态化。接续的可行性随路况、工时、装卸进度实时变化，如果这张边表一天只重算一次，调度给出的方案在半天之后就已经失真。接续边必须是动态的，这也是这套模型对底座实时写入能力有要求的原因。

开头那位司机多跑的 47 公里，本质上是一次信息缺失：系统的视野只到「单」这一层，看不到「单与单之间」。把这一层补上，不需要换掉求解器，只需要在它前面加一张能表达时间与约束的图。

相关阅读

常见问题（FAQ）

Q1：悦数图数据库是一款什么样的产品？

A：悦数图数据库是杭州悦数科技自主研发的企业级原生分布式 GQL 图数据库，100% 国产自研、自主可控，原生支持 ISO-GQL 国际标准，融合图、向量与全文索引能力，可支撑千亿点万亿边规模。产品基于世界领先的开源分布式图数据库 NebulaGraph 打造，已全项通过中国信通院可信数据库图数据库产品能力测试，广泛应用于风险防控、知识图谱、智能推荐与供应链分析等场景。

Q2：运力调度已经有成熟的路径规划算法和求解器，为什么还要引入图数据库？

A：两者解决的问题不同。求解器擅长在给定候选集内求出最优组合，但候选集本身的构造——哪些车能接哪些单、哪些接续在时间窗内可行、某个变动会牵连哪些任务——是关系问题。图数据库的价值在于把车、任务、站点、时段建成一张可遍历的图，用一次查询完成候选筛选与影响面计算，把问题规模缩到求解器能秒级求解的范围，两者是前后衔接而非相互替代。

Q3：悦数图数据库在实时数据接入与大规模图计算上有哪些技术积累？

A：悦数图数据库支持 Pulsar、Flink 等流式数据接入，可将路况、作业状态等实时数据持续同步进图，并支持导出至 HDFS 与多源数据导入。平台内置图算法库与图计算引擎，相比 Spark GraphX 有 6 至 10 倍提速，资源占用降低 80%，开发效率提升 80%；底座采用 Shared-Nothing 与存算分离架构，支持千亿点万亿边规模。公司累计拥有 60 余项发明专利，据 IDC 2024 年报告，悦数在中国图数据库市场份额位居第二，并连续两年获评中国信通院「领航者」案例。