达尔文派单局：遗传算法实现自动派单

• 1 引言
• 2 业务背景
• 3 问题模型
• 4 算法选择
• 5 遗传算法介绍
• 5.1 遗传算法原理
• 5.2 遗传算法应用
• 5.3 收敛过程演示
• 6 总结
• 6.1 业务收益
• 6.2 技术选型

1 引言

假设有4位上门工程师和24个待派订单，如何分配订单，使得：

• 工程师同一时间段只能履约一个订单，即订单时间窗口不能重复。
• 工程师通行总通行时间最低。
• 工程师订单尽量均衡。

如下图，红色点为工程师，蓝色点为用户订单，蓝色点上方数字为上门时间，例：14-16表示该订单履约时间为14点到16点。

派单之后，每个工程师路线图：

每位工程师的订单数量分配比较均衡，且订单地理位置集中在工程师服务半径内，使得通行成本得到控制。

2 业务背景

奢侈品回收业务的初期，上门订单的派发完全依赖人工。开放的十多个上门城市都是人工规划路线。

人工派单需要综合考量多种因素，主要包括：

• 准时履约确保工程师能在每个订单开始时间前到达，并且订单结束时，有足够时间到达下一单。
• 路线最优尽量保证工程师整体的通行成本是最低的。
• 订单均衡尽量保证工程师分配的订单数量均衡。

基于上述因素，人工决策和主观判断需要反复尝试、调整派单方案，不仅效率低下，而且容易陷入局部最优，难以实现全局最优的派单方案。

另外，奢侈品上门回收派单方式有两种：

实时派单通过规则的方式实现，这里不再赘述。接下来，将重点对批量派单进行详细介绍。

3 问题模型

要通过算法求解最优的派单方案，首先需要确定问题模型，自动派单可以被认为是VRPTW模型（带时间窗口的车辆路径问题，VRP变种问题）。

在VRPTW模型中，约束条件如下：

• 时间窗约束工程师必须在履约时间范围内到达并完成服务。
• 订单约束一个工程师可以分配多个订单，一个订单只属于一个工程师。
• 起始约束工程师从起点出发，最终回到起点。
• 顺序约束工程师按照订单的开始时间顺序履约。

基于以上约束条件，问题模型的目标是：

• 最低通行成本确保工程师的总体通行成本最小化。
• 订单均衡均衡分配每位工程师的订单数量。

解决这类问题的核心是在解空间搜索不同的组合方式，通过尝试不同组合并打分，可以确定最优或近似最优的派单方案。

4 算法选择

确定问题模型之后，下一步选择合适的算法或方案。

我们分析一下不同算法模型的优劣。

精确算法

• 优势暴力搜索全量解空间，枚举所有组合，能得到理论最优解。
• 劣势计算复杂度指数级增长（NP-Hard问题），m个工程师n个订单， 时间复杂度为O(mⁿ)。
• 使用场景用于验证其他算法的有效性。适合小规模订单派发。

经过实验，在5名工程师和30个订单的场景下，即使CPU资源被完全占用，耗时10分钟，最终也未能搜索到最优解。

近似算法

• 优势计算速度快，实现简单。
• 劣势每次只关注下一单的最优分配，无法关注到整体最优，短视问题导致解的质量差，易陷入局部最优解。
• 使用场景配合其他算法做初始解生成。一般和派单规则结合，适合小规模流式订单派发。

目前，我们的实时派单功能就是结合近似算法与派单规则的方式实现。

强化学习

• 优势通过试错自主学习，奖励函数反馈不断优化派单方案。适合高维复杂问题（多目标、多动态约束）。
• 劣势初期缺乏数据支撑，有冷启动问题。派单方案解释性差，对业务来说是”黑盒“。依赖高算力，成本高。
• 使用场景拥有海量的历史派单数据可用于训练。适合订单量级大、实时要求较高、能投入高成本的场景。

美团、Uber等公司实时调度系统采用强化学习。

元启发式算法

• 优势既能避免组合爆炸的问题，又能够全面兼顾全局搜索能力。适合高维复杂问题（多目标、多动态约束）。耗时低，秒级结果输出。无需高算力。
• 劣势不一定能搜索到绝对最优解，但能搜索到近似最优解（最优解的95%~100%）。算法参数调优依赖实验验证。
• 使用场景不需要追求绝对最优解的组合优化。无需额外成本。

在综合考虑业务体量与人效成本的情况下，就批量派单方式而言，元启发式算法是最佳的选择。

5 遗传算法介绍

遗传算法是一种模拟自然选择和遗传机制的优化算法。它通过模拟生物进化过程中的选择、交叉和变异等操作产生子代，逐步淘汰劣势个体，保留优势个体。经过多轮迭代和优胜劣汰，最终存活的个体往往是较为优秀的，这些个体即可视为问题的最优解或近似最优解。

5.1 遗传算法原理

前置

了解染色体中交叉、变异操作。

• 交叉交叉是指通过将两个父代个体的部分基因进行交换，生成新的子代个体的过程。
• 变异变异是指通过随机改变个体基因序列，为种群引入新的多样性。

交叉和变异操作的核心在于，在保留父代优良基因的基础上，进一步探索更优的个体。

举例

为了更好的理解思想，这里举个浅显的例子，假设我们要组建一支『闪电小队』。

这个简单案例揭示了遗传算法的基本原理：通过多代选择适应度较高的个体，使这些优势个体在遗传过程中保留优良基因，并通过交叉、变异等操作产生更加优秀的后代，从而逐步逼近问题的最优解，最终收敛到最优解。

5.2 遗传算法应用

遗传算法思想平移到自动派单，该如何设计呢？接下来会重点讲解核心步骤：

初始化种群

首先说明个体和种群的概念和关系。

• 个体一种派单方案被认为是一个个体，例如，有工程师A和B，有订单1、2、3、4，那么一个个体可以表示为：

工程师A：订单1、订单3工程师B：订单2、订单4

也可以是：

工程师A：订单1工程师B：订单2、订单3、订单4

• 种群

若干个个体组成种群。

• 初始化

种群初始化是遗传算法的首要步骤，核心是生成具有多样性的初始解集合。

可以根据问题规模设置种群大小，比如种群大小设置100，即初始化100个个体。

适应度函数

适应度函数是遗传算法中评估个体优劣的关键指标。在自动派单中，我们设计的适应度函数主要优化两个目标：最短工程师通行时间和最均衡订单分配。表现越好的个体（派单方案），其适应度评分越高。

归一化之后的适应度函数：

• ：当前个体的工程师通行总时间
• ：种群中最大通行总时间
• ：订单分配均衡性的标准差
• ：成功派单数
• ：订单总数
• , , 为优化目标权重系数，通过业务诉求和实验确定具体值。

选择

在遗传算法的选择阶段，系统会根据适应度函数评估结果，采用特定的选择策略从当前种群中筛选出优质个体作为父代。这些被选中的父代个体将通过后续的交叉和变异操作产生新一代子代，从而推动种群向更优解进化。

列举两种最常用的选择策略：

建议两种方式组合使用，只选择精英保留可能会导致“近亲繁殖”问题，种群多样性快速下降，陷入局部最优；只选择轮盘赌，可能会存在适应度相近时选择压力不足。

交叉

交叉是遗传算法中最关键的进化操作，它通过模拟生物染色体片段交换的方式，将父代个体的优良特征传递给子代。

常见交叉策略有：

这里以多点交叉举例，假设从种群中选择了两个个体作为父代。(A:1 2 3 代表工程师A分配了订单[1,2,3])

• 父代1A:1 2 3 4 5 6

• 父代2A:6 4 5 2 1 3

• 片段选择从父代1中选定基因片段[3,4,5]。

• 基因重组移除父代2中与选定片段冲突的基因[3,4,5]。将父代1的片段[3,4,5]插入父代2的末端。

• 产生子代

• 子代A:6 2 1 3 4 5

示例仅展示基因重组原理，实际还需要考虑订单时间窗口冲突问题。

变异

如果交叉理解为在解空间中大踏步寻找最优解，那么变异就是在解空间小踏步寻找最优解。

上述通过交叉操作产生的子代，采用保守的变异概率（推荐5%±2%），在保持种群多样性和保护优良基因之间取得平衡。

变异操作最常用的是打乱重组的基因片段，例如，将[3,4,5]打乱得到[5,3,4],则经过交叉、变异后得到的子代是：

• 子代A:6 2 1 5 3 4

优胜劣汰

优胜劣汰模拟生物进化中的自然选择过程，其核心原则是保留适应度较高的个体，同时淘汰掉适应度较低的个体，从而推动种群整体向更优解方向进化。

至此，种群完成一次进化（迭代），整体解的质量要高于上一代。

5.3 收敛过程演示

工程师严格按照预约开始时间履约，所以最终收敛的路线规划结果不可避免地会出现折返情况。

6 总结

6.1 业务收益

算法代替人工后，单日人力耗时从6人时/日降至10分钟/日，效率提升约97.22%，释放2人力。

6.2 技术选型

最终采用遗传算法实现自动派单系统，其优势包括：

• 鲁棒性即使问题规模扩大，计算量仍能保持合理增长，能规避组合爆炸风险。
• 秒级响应中、大规模批量派单场景下仍能实现秒级响应。
• 业务匹配精准适配当前业务体量与派单模式，以最优成本实现效率最大化。

关于作者

蒋韬，转转回收技术部的后端工程师