疫情期如何让快递送得更快?菜鸟网络AAAI论文深度学习驱动MIP求解

疫情期如何让快递送得更快?菜鸟网络AAAI论文深度学习驱动MIP求解
2020年02月24日 18:30 机器之心Pro

机器之心发布

机器之心编辑部

疫情期间,道路受阻、货车资源有限等问题影响着快递网的正常运行,但快递网算法的优化却可以帮我们省出一些时间。在今年 AAAI 的接收论文中,来自菜鸟人工智能部大快递算法团队的一篇论文设计实现了深度学习驱动的 MIP 求解加速方法,在 8 类经典运筹问题上将 SCIP 可行解获取带来平均意义下 10 倍以上的计算加速,且有较好的泛化能力。

在本次疫情中,快递物流在新冠抗疫物资运输中起了非常关键的作用。面对受到影响的运输网络,如何规划路由与车线,利用有限的货车资源尽快将积压的包裹送达目的地,这是物流领域典型的组合优化问题,该问题可建模为混合整数规划问题 (Mixed Integer Programing, MIP),并利用求解器进行求解。

然而,快递网络规划问题通常规模很大,包含的决策变量和约束条件非常多,求解非常耗时,很难在短时间内求解完并应用到线上。而且,快递网络每天都在运转,而相似的组合优化问题也需要反复求解。当前学术圈与工业界尚无处理相似 MIP 问题求解的通用方法,每天计算时通常将其视为全新的求解任务,从而导致历史求解的过程数据损失其价值。如果能从历史求解过程中,采用机器学习的方法学习到相似 MIP 问题的结构特点,则有望大幅提速求解效率。

基于这一观察,菜鸟人工智能部大快递算法团队基于其在运筹优化、机器学习以及物流行业的积累,设计实现了深度学习驱动的 MIP 求解加速方法:MIP-OSP,最新研究成果论文《Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction》发表在人工智能顶级会议 AAAI-2020 上,并受邀做口头报告。本文将对这一运筹优化与机器学习学科的交叉应用论文进行深入解读,并介绍该方法在菜鸟快递网络路由优化问题中的实际应用。

论文地址:https://arxiv.org/abs/1906.09575

应用场景

混合整数线性规划 (MIP) 是求解组合优化问题最为常见的建模与优化手段,在菜鸟网络的很多运筹优化相关应用中 (例如快递网络、车辆排线、人员排班、库存管理、服务器分配等) 都可以采用 MIP 方法进行建模求解。MIP 模型中的整数变量为其赋予了描述现实世界中离散决策的能力。以 0-1 整数决策变量为例,我们可以用它来描述生产调度问题中某个工件是否在某个机器上加工的决策问题、车辆路径规划问题中某两个门店是否进行串线运输的决策问题等等。在大量实际应用中(例如图 1 所示),相似的 MIP 被会被反复求解,且求解时长随着问题规模的增大呈指数增长。本文提出的 MIP-OSP 算法希望从这类相似 MIP 问题的历史求解过程中「学习经验」,不断加速新问题的求解。

图 1. 应用场景示例。场景描述:在分拨中心到站点的传站车辆调度问题中,智能调度引擎每天制定车辆的运输计划,决策车货匹配关系并优化车辆路径。此问题可以建模为 MIP 模型进行求解,由于运输计划基于每天不同的订单进行更新,系统中每天都要对相似的 MIP 模型进行求解。

方法简介

MIP 模型可以统一表述为标准形式:

, 其中

为包含整数的决策变量,A,b,c为模型的输入参数。针对不同场景的实际优化问题,MIP 模型的基本数学结构保持不变,但模型参数A,b,c以及决策变量定义域

会有不同的具体表征。如果能针对这类通用的数学模型挖掘出问题特征并与最优解进行关联,将大幅提升该思路的通用化能力,有着巨大的应用前景。研究者所设计的 MIP-OSP 方法基于 MIP 模型的抽象参数A,b,c建立图模型,进而通过预测 MIP 问题的最优解实现求解加速,其整体框架如图 2 所示。

图 2. MIP-OSP 方法流程

图 2 中左半部分为最优解预测模型的训练过程,右半部分为模型的应用过程。仍以传站车辆调度问题为例,假设调度引擎已经完成了连续 n-1 天的模型求解,并将计算过程与计算结果存储到数据库中。该方法首先基于这 n-1 天的 MIP 模型基本信息以及求解过程数据训练出最优解预测的模型,并将其用于第 n 天 MIP 问题的最优解预测。令

表示基于模型对第 n 天最优解的预测,基于这一预测结果可以将 MIP 问题的搜索空间大幅减小,从而加速第 n 天 MIP 问题的计算。显然,随着系统运行时间增加,模型训练的数据逐步累积,使得最优解预测的准确率越来越高,求解新的 MIP 问题时速度也越来越快。

整体算法框架

研究者提出了一类基于图卷积神经网络 (GCN) 的最优解预测算法 (MIP-OSP),通过收集 MIP 的结构特征以及根节点线性松弛特征,预测 MIP 模型中 0-1 整数变量在最优解中的取值。整体流程如下:

  • 首先针对通用 MIP 模型设计了一类三部图的表征方式;
  • 而后基于该三部图设计 Attention GCN 预测模型进行变量取值预测;
  • 最后根据模型预测结果,生成 local branching 形式的约束加入到原模型中,加速 MIP 求解。

考虑如下通用的 MIP 模型:

其中变量的索引集合

划分为 3 个子集

, 分别对应于 0-1 整数变量,一般整数变量以及连续变量的索引集合。算法的核心任务是预测任意 0-1 整数变量

在最优解中取 1(或取 0) 的概率,并基于这一预测结果加速 MIP 求解。

MIP 模型的三部图表征

对于任意给定的 MIP 问题算例

,设计了一类三部图

对其进行表征。建图的基本思想是根据

中基础信息,即系数矩阵A,右边项系数向量b(right-hand-side, RHS) 以及目标函数系数向量c来建图。图中节点和边的构建方式如下:

图 3. MIP 的三部图表征示例

MIP 最优解预测

算法 1 中给出了最优解预测的详细流程,预测算法分为 3 个阶段:

1.嵌入层 (第 1-3 行): 将变量、约束、目标函数节点通过嵌入操作映射到同一维度 (设定为 64 维向量);

2.带有注意力机制的图卷积层 (第 4-10 行): 进行不同类型节点之间的信息传递;

3.全连接层 (第 11 行),用于预测变量节点对应的输出取值。

该算法的直观解释如下:在图卷积中的每一步,三类节点都增量地从它的邻接节点更新全局信息,这些邻接节点恰恰对应于原 MIP 模型中与该节点相关的变量、约束以及目标函数。通过迭代地传递与更新,将 MIP 模型中的连接关系嵌入到三部图中,用于 MIP 模型的表征。三部图中卷积过程的信息传递采用如下 4 步策略(如下所示):

图 4. 三部图卷积层的信息传递过程

注意力机制: 文中三部图的一个独特特性在于节点、边之间的异质性。三类节点以及三类连接边在原问题空间中对应的对象不尽相同,因此在设计注意力机制时需要将这一异质性的图结构考虑进来。常用的图注意力机制设计方案中,对于不同节点间的注意力采用共享的权重矩阵;研究者设计的注意力机制中,针对不同类别的节点之间分别引入共享的权重矩阵以反映一类节点在另一类节点上特征重要性的影响。具体地,给定类别为

的节点

以及其类别为

的邻居节点节点

,反映节点i的特征对于节点j影响重要性的注意力系数可计算如下:

其中

分别表示节点

以及边

的图嵌入向量,而

表示类型

与类型

节点之间的共享注意力权重矩阵。对于每个节点

,注意力权重系数通过 softmax 函数在其邻接节点

中进行标准化。基于这一注意力机制,MIP 的系数矩阵具体数值就被应用于反应图中边连接的重要性上。

基于预测结果加速 MIP 求解

完成最优解预测后,下面介绍如何基于这一预测结果加速 MIP 求解。这里介绍一类 local branching 形式的割平面方法来降低可行解的探索空间。该方法旨在基于最优解预测结果,首先识别出稳定可预测的 0-1 整数变量,从而将分支定界树的搜索方向引导到那些难以预测的决策变量上,从而加速计算。令

表示 0-1 整数变量的最优解预测值,令 表示 0-1 变量索引集合的一个子集,则 local branching 形式的割平面定义如下:

其中

是控制一个新的可行解x到预测最优解

距离的参数。对于

这一特殊情形,等价于将索引集合S所对应的决策变量固定为其预测最优解的取值

实验效果

为了对 MIP-OSP 的加速效果进行评测,通过在目前性能最佳的开源 MIP 求解器 SCIP 中添加插件以实现数据采集与求解加速实验。

算例

为了验证 MIP-OSP 框架的可行性与通用性,研究者实现了 8 类经典的 MIP 问题模型并生成算例。对于每类问题,他们生成了 200 个算例用于模型训练与预测,并生成另外 50 个算例用于评价求解速度提升。8 类问题分别是:

• 固定费用网络流问题 (Fixed Charge Network Flow, FCNF)

• 设施选址问题 (Capacitated Facility Location, CFL)

• 广义分配问题 (Generalized Assignment, GA)

• 最大独立集合问题 (Maximal Independent Set, MIS)

• 多维背包问题 (Multidimensional Knapsack, MK)

• 集合覆盖问题 (Set Covering, SC)

• 旅行商问题 (Traveling Salesman Problem, TSP)

• 车辆路径问题 (Vehicle Routing Problem, VRP).

这 8 类问题是 OR 领域非常常见的组合优化问题且具有在模型结构以及最优解结构上有较大的差别,因此很具有代表性。特别值得一提的是,这些经典优化问题,与菜鸟的多项算法应用有着密切的关联:网络流问题与设施选址问题与仓配网络的选址、流量规划密切相关;广义分配问题与末端小件员分配问题密不可分;而旅行商、车辆路径问题则是配送路径优化问题的底层问题。

MIP 求解效果提升

研究者将基于 MIP-OSP 的求解流程与求解器的默认配置方案下的性能进行对比,采用可行解间隙 (primal gap) 和间隙积分 (primal integral) 指标刻画不同求解方法的效果对比。其中可行解间隙表示可行解x目标函数值与已知的最佳可行解

之间的相对差距,而间隙积分则表示求解过程中的平均可行解间隙。

从表中对比结果可以看出:给定相同运行时长,MIP-OSP 方法(GCN 列)都相较于求解器默认设置(DEF1 列)有着显著优势。即使与求解器 10 倍运行时长 (DEF10 列) 相比,MIP-OSP 的求解效果也在平均意义下有着更好的性能表现,这表明本文提出的方法在测试问题上可以带来 SCIP 求解器可行解获取能力 10 倍以上的性能提升。

泛化能力

图嵌入模型的优势是在不同规模的问题上有一定的泛化能力,考虑到通常大规模 MIP 问题的求解非常困难,因此这一泛化能力对于 MIP 求解显得尤为重要。为了探究模型的泛化能力,研究者在小规模 MIP 算例上进行模型训练,而后将训练的模型在大规模的 MIP 模型的预测和求解中进行应用,对比结果如下表所示。由下表可见,小规模 MIP 算例上训练的模型在大规模算例上预测准确率下降不多,且最优解预测结果可用于大规模 MIP 的求解,相较于 SCIP 默认设置有显著提高,因此该方法在超大规模 MIP 问题处理上有着巨大的潜力。

MIP-OSP 在快递网络优化中的应用

快递网络的路由优化

快递网络的规划和优化分两步,第一是网络中点和边的设计和优化,比如哪些地方要建立转运中心 (点),哪些转运中心之间要开通线路 (边);第二是在基础网络之上决定货物如何运输,车辆资源需要多少,运输班次如何定。由于快递网络的规模性和复杂性,依靠人工经验对网络进行规划和优化是非常浩大的工程,需要耗费巨大的人力和时间,而且这个过程难免出现结果的错误和滞后性。具体来说货,规模上,一般快递公司全网会有几百个转运中心,上千条运输线路,几千辆运输车线以及上万个运输需求,这里需要决策的变量规模巨大;复杂性上,在规划过程中,需要充分考虑不同地区间的快递时效、往返选择,以及每个转运中心具备的的地区特性等,这里需要考虑的约束量也是极其庞大且复杂。研究者针对快递网络路由优化进行优化建模,建模后的 MIP 问题包含了千万级别的变量和百万级别的约束。这是个非常庞大的问题,一般商业求解器很难在有效时间内对该问题进行求解。

MIP-OSP 在快递路由优化上的应用

研究者试用了一些求解器,即使运行 10 个小时也仍有 1.8% 左右的最优解间隙。而这 1.8% 的间隙对应的日均运输成本损失可能在数十万的级别,累计到全年就是近亿元的成本。因此如果能加速该问题的求解,在有限计算时间内得到更优的可行解,则可带来运输成本的显著下降。

图 6. MIP-OSP 算法与 SCIP 默认算法求解效率对比

如图所示,在快递网络优化问题中,采用 MIP-OSP 这一加速方法,可以在运行时长 2000 秒时达到 SCIP 默认方法 20000 秒的求解效果。这说明虽然该优化问题十分复杂,但 MIP-OSP 算法仍能对其进行高效处理。此外,当算法运行收敛时,优化结果带来了 0.8% 的目标函数值下降,这将带来快递运输成本的显著下降。

结束语

本文是将机器学习方法与运筹优化问题相结合的一次成功尝试。在很多工业应用中,同类型的运筹优化问题需要周期性地反复求解,采用机器学习方法识别这些反复求解问题之间的共性并合理利用,可以大幅加速优化的求解。沿着这一思路,本文讨论了对 MIP 问题的三部图表征,以及基于该表征的 Attention GCN 预测方法,并利用预测解生成 local branching 形式的约束加入到原模型中加速 MIP 的求解。文中的计算实验与菜鸟快递网络优化的实际应用表明,该解决方案对于求解同质 MIP 问题有较强的通用性,在 8 类经典运筹问题上将 SCIP 可行解获取带来平均意义下 10 倍以上的计算加速,且有较好的泛化能力,在处理超大规模 MIP 问题处理上有着巨大的潜力。

财经自媒体联盟

新浪首页 语音播报 相关新闻 返回顶部