新闻
南美国际空运-疫情期间如何让快递送得更快？菜鸟网络AAAI论文用深度学习驱动MIP求解
新闻 | 2020-02-27 22:54机器之心
机器之心发布
机器之心编辑部
疫情期间，绍兴物流 ，道路受阻、货车资源有限等问题影响着快递网的正常运行，但快递网算法的优化却可以帮我们省出一些时间。在今年 AAAI 的接收论文中，来自菜鸟人工智能部大快递算法团队的一篇论文设计实现了深度学习驱动的 MIP 求解加速方法，在 8 类经典运筹问题上将 SCIP 可行解获取带来平均意义下 10 倍以上的计算加速，且有较好的泛化能力。
然而，快递网络规划问题通常规模很大，包含的决策变量和约束条件非常多，求解非常耗时，很难在短时间内求解完并应用到线上。而且，快递网络每天都在运转，而相似的组合优化问题也需要反复求解。当前学术圈与工业界尚无处理相似 MIP 问题求解的通用方法，每天计算时通常将其视为全新的求解任务，从而导致历史求解的过程数据损失其价值。如果能从历史求解过程中，采用机器学习的方法学习到相似 MIP 问题的结构特点，则有望大幅提速求解效率。
基于这一观察，菜鸟人工智能部大快递算法团队基于其在运筹优化、机器学习以及物流行业的积累，设计实现了深度学习驱动的 MIP 求解加速方法：MIP-OSP，最新研究成果论文《Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction》发表在人工智能顶级会议 AAAI-2020 上，并受邀做口头报告。本文将对这一运筹优化与机器学习学科的交叉应用论文进行深入解读，并介绍该方法在菜鸟快递网络路由优化问题中的实际应用。
应用场景
混合整数线性规划 (MIP) 是求解组合优化问题最为常见的建模与优化手段，在菜鸟网络的很多运筹优化相关应用中 (例如快递网络、车辆排线、人员排班、库存管理、服务器分配等) 都可以采用 MIP 方法进行建模求解。MIP 模型中的整数变量为其赋予了描述现实世界中离散决策的能力。以 0-1 整数决策变量为例，我们可以用它来描述生产调度问题中某个工件是否在某个机器上加工的决策问题、车辆路径规划问题中某两个门店是否进行串线运输的决策问题等等。在大量实际应用中（例如图 1 所示），相似的 MIP 被会被反复求解，且求解时长随着问题规模的增大呈指数增长。本文提出的 MIP-OSP 算法希望从这类相似 MIP 问题的历史求解过程中「学习经验」，不断加速新问题的求解。
方法简介
MIP 模型可以统一表述为标准形式：
， 其中
为包含整数的决策变量，A，b，c为模型的输入参数。针对不同场景的实际优化问题，MIP 模型的基本数学结构保持不变，但模型参数 A，b，c 以及决策变量定义域
会有不同的具体表征。如果能针对这类通用的数学模型挖掘出问题特征并与最优解进行关联，将大幅提升该思路的通用化能力，有着巨大的应用前景。研究者所设计的 MIP-OSP 方法基于 MIP 模型的抽象参数 A，b，c 建立图模型，进而通过预测 MIP 问题的最优解实现求解加速，其整体框架如图 2 所示。
图 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 模型：
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
| 千航国际 |
| 国际空运 |
| 国际海运 |
| 国际快递 |
| 跨境铁路 |
| 多式联运 |