近些年，以机器学习为代表的人工智能技术逐渐被大家认识并在很多方面得到普及，深度学习技术在学术界和工业界取得了广泛的成功，受到高度重视，并掀起新一轮的人工智能热潮。运筹学作为一个看似古老的学科，科学家和工程师在过去开发了各种启发式或精确的求解方法，能够在有限的时间内返回一个尽可能好的结果。值得注意的是，上述算法均诞生于这轮AI大爆发之前，在AI时代，如何将最新的机器学习技术应用在运筹和组合优化，正在受到越来越多的关注。在芯片设计、求解器等“卡脖子”领域，基于机器学习的组合优化方法很可能成为将来的基础性技术。本博客以路径规划为例，探讨了传统的优化方法、深度强化学习类方法的研究现状和交叉融合趋势，分析了各自的特点以及在实际落地亟需解决的若干问题，也希望能探索相关算法在得物供应链场景的落地实践。运筹学（Operations Research）作为数学、计算机科学、管理学的交叉学科，最早起源于一战中的防空作战系统，由钱学森先生引入中国，最开始的用途是优化航空／军工等领域。如今广泛应用在企业的生产、运营、物流环节，通过算法指导和辅助人类管理者进行决策。在本博客中，我们将运筹优化概括为，通过求解一个最优化问题，在满足约束的条件下，最小化完成某件事所花费的成本。最优化问题常描述为一个数学规划问题，根据决策变量是连续或离散，可以分为两类：连续最优化问题与组合优化。
连续最优化问题的标准形式是：
![]()
这里x是决策变量，f(x)是目标函数，g(x)是不等式约束条件，h(x)是等式约束条件，且有m≥0, p≥0。若有m=p=0，则问题转化为无约束优化问题。函数f,g,h可以是线性或非线性，经典的求解算法有：牛顿法、梯度下降法、共轭法等等。而当决策变量取值是（或部分是）整数，则是离散优化问题，常称为组合优化（Combinatorial Optimization），是运筹优化的一个重要分支，其标准形式是：而当决策变量取值是（或部分是）整数，则是离散优化问题，常称为组合优化（Combinatorial Optimization），是运筹优化的一个重要分支，其标准形式是：![]()
一般描述为混合整数规划（mixed integer programming，MIP），所有的参数(c_j,d_k,a_{ij},g_{ik},b_i)取值是任意实数，只考虑线性表达式。$$m$$是约束条件的数量，$$n$$是连续变量数，$$p$$是整数变量数。若n=0则上述MIP转化为纯整数规划，若$$p=0$$则上述MIP转化为线性规划；特别的，若y_k∈{0，1}，全称量词k，则转化为二元（binary）规划问题。组合优化问题（如资源调度、生产排产、路径优化、运营排班等）是企业经营决策所面临的最常见的优化问题类型，覆盖商业决策优化的大部分流程，因此也是运筹学的主要研究对象之一。从航班和工厂的调度、金融资产配置、仓库货物存储到运输路线的设计，很多都可以建模成组合优化问题。本文讨论的对象是组合优化问题。组合优化问题的离散特性为问题求解引入了特别的挑战，因为求解空间是随问题规模呈指数级增长的，其中有不少是NP-complete的。也就是说目前还找不到多项式时间复杂度的算法。NP-complete问题有很多，如经典的satisfiability（SAT）问题，minimum vertex cover（MVC）问题，max cut（MC）问题等等。它们之间可以在多项式复杂度内相互归约，也就是说其中一个被证明有多项式复杂度解法的话，所有的都有多项式复杂度解法。
2.1 常见的组合优化问题
NP-complete问题中最经典的问题之一要属旅行商问题（Traveling Salesman Problem，TSP），它是车辆路径问题（Vehicle Routing Problem, VRP）的一个特例。其迷人之处可能就在于看似描述很简单，日常生活中可能还常用到，但想要找到通用的高效解法却发现非常难。其可行解是所有点的全排列，随着点数的增加，会产生组合爆炸，暴力求解的复杂度O(n!)。问题描述为由n个城市组成的完全图，两个城市间有整数代价；有一个旅行商要走遍所有城市，每个城市只走一次且最后回到原点（即Hamilton回路），求所有城市的访问路径的顺序，且该路径的代价和最小。
![]()
很多时候对于中大规模TSP，尚无找到最优解的有效算法，其能找到的最好解与真正最优解的距离称为optimality gap。这也是评估很多TSP算法的重要指标，用来说明它的解接近最优的程度。自被提出后的几十年里，该问题在组合优化领域被反复地研究，从而衍生出基于精确算法、近似算法、启发式算法几大类成熟的方法。TSP问题在交通运输、电路板线路设计、物流配送等场景有着广泛的应用。
组合优化中的另一经典问题是车辆路径规划问题（Vehicle Routing Problem, VRP），描述为一定数量的客户，各自有不同数量的货物需求，从仓库向客户提供货物，由一个车队负责分送。需要组织适当的分配方案和行车路线，目标是使得客户的需求得到满足，并在一定的约束（时间窗、装载率）下，达到诸如路程最短、成本最小、耗费时间最少等目标。一个简单的有着16个客户（编号为1-16）、1个仓库（编号为0）的示意图如下所示，共需要4辆车完成配送（以不同颜色标识），每辆车服务4个客户，所有车均从仓库出发，服务完所有的客户之后，再返回仓库。![]()
根据不同的问题特征，可以附加各种约束，得到不同的VRP问题变形，如下图所示。TSP是VRP的特例，即不考虑车辆的约束，用一辆车服务完所有的客户。而若车辆有容量（装载量上限），就构成了CVRP，再考虑时间窗（Time Window）就是VRPTW；若为同时取送货（Pickup and Delivery），则构成了VRPPD。一般的城市配送问题都可以描述为CVRP，一般的预约安装类问题都可以抽象为VRPTW，而外卖配送、打车等O2O范围类的问题都可以用VRPPD来描述。因此，VRP在物流配送中有着广泛的应用场景，在过去50年来是研究热点。传统的优化方法（启发式、精确算法等）专注于研究各种各样的问题变形，甚至拓展到了uncertainty、robust、stochastic、two-echelon等场景，而深度强化学习类的方法则主要专注于求解TSP、CVRP等简单情形，并常用优化方法得到的解作为比较对象。下文将详细介绍。![]()
2.2 组合优化问题的常见求解方法
2.2.1 近似算法
这类算法找的不是最优解，而是次优（sub-optimal）解，或者说近优（near-optimal）解，其优点是会有某种程度上的最优性保证。具体地，它能保证最坏情况下给出的解不次于最优解的一定倍数，这个倍数称为近似比（approximation ratio）。对于NP完全问题，虽然求最优解没有多项式复杂度的算法，但求近优解却存在不少多项式复杂度的算法。这类方法包含如贪心算法、原始-对偶法、动态规划法等。对于一个最小化的组合优化问题，假设全局最优解的目标函数为100，那么近似比为2的近似算法收敛求得的解一定在[100，200]，最坏情况是200。对于TSP问题，在满足三角不等式（triangle inequality）时，Christofides algorithm 通过计算最小生成树和最小权完全匹配来求解，其时间复杂度为O(n3)，近似比为1.5。2.2.2 启发式算法
启发式算法是指通过对经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观判断或试探的方法。其本质上也是找一个近似解，但与上面的近似算法相比，差别在于启发式算法没有最优性的理论保证，即不能保证解的质量。但一般来说，它比上面的近似算法能找到更好的解。可以分为以下两类。一类是可以根据问题相关的heuristic构造解，如最近邻，或者最小生成树；另一种是local search，即根据heuristic来对中间解进行局部修改，以迭代的方式在解空间中进行搜索。这类算法通常是以问题为导向的即Problem Specific，没有一个通用的框架，每个不同的问题通常设计一个不同的启发式算法，更多是快速寻求局部最优。还有一类是应用元启发式搜索框架，耳熟能详的有禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、粒子群优化算法、人工鱼群算法、人工蜂群算法等；它们以生物的行为方式或者物质的运动形态为背景，对社会性昆虫的群体行为的研究基础上，群居性生物通过协作表现出的宏观智能行为特征，又称群智能优化算法。元启发式算法可以针对普遍的问题，即Problem Independent，可以作为一个black box操作，适用性广，但还是要根据问题特点来调节算法的各种参数；有随机优化的机制，适合于寻求全局最优。对于TSP问题，这类方法中的SOTA算法为Lin-Kernighan-Helsgaun (LKH)，可解决的规模可以达到上万级别。对于VRP问题，根据求解过程，可分为 construction heuristic 和 improvement heuristic 两类。construction heuristic 用于构造一个初始可行解，常用的方法包括 Solomon I1 以及 saving heuristic （节约算法），后者的示意图如下所示。基本思想是将各客户点均与depot相连，构成若干条只含有一个配送点的线路；然后通过贪心规则，计算将点 i和点 j 连接在一条线路上距离的节约值；重复这个步骤，对线路进行合并。
![]()
improvement heuristic用于对初始解进行改进提升，常用的方法如下图所示。基本思想是通过交换点、边的位置或顺序，常作为元启发式算法中构造邻域解的中间算子，再嵌套迭代不断优化求解效果。![]()
![]()
![]()
2.2.3 精确算法
精确算法是指能够求出问题最优解的算法。对于难解的组合优化问题，当问题的规模较小时，精确算法能够在可接受的时间内找到最优解；当问题的规模较大时，精确算法一方面可以提供问题的可行解，另一方面可以为启发式方法提供初始解，以便能搜索到更好的解。精确算法主要包括分支定界法、割平面法、列生成算法、动态规划法等。精确算法，顾名思义，就是搜索整个解空间，能够保证找到最优解。当然由于搜索空间太大，实际当中会通过剪枝等方法来减小搜索空间。常见的做法是建模成整数规划（Integer programming，IP）或混合整数规划问题（Mixed-integer programming，MIP），然后通过对偶理论，寻找问题的下界和上界（对于最小化问题，就是可行解），然后不断逼近。![]()
![]()
该模型是典型的MIP，决策变量x{ijk}是二元变量，取值为 0 或 1；s{ik}是连续变量，代表车辆k到达客户 i的时间。原问题的下界，可以很容易地通过求解其线性松弛来得到，但是往往非常弱，因此常通过添加割平面来提升下界的值；给定的source和sink，会存在很多条满足资源约束的最短路径，因此常通过列生成法，先通过少数可行路径构造一个主问题，再求解一个定价子问题，逐步加入能使目标得到改进的新变量（列）；而为了保证得到可行解，还需要对分数变量进行分支。具体的，分支定界（Branch and Bound）本质上就是将搜索空间构造成树的形式，通过不断地选取和分裂节点，配合剪枝来有效地找寻最优整数解。至于如何挑选节点和如何对其赋值对于找到解的速度有很大影响，是门很大的学问，因此衍生出不少启发式（Heuristic）策略。割平面法（Cutting Plane）从松弛问题的一个非整数的最优解出发，序贯地添加一个新的线性不等式（其对应线性方程所代表的超平面即称为割平面），求解新的松弛问题的算法。列生成算法（Column Generation）运用分解的思想和单纯形法的特点，不是直接同时处理所有的候选方案，而是基于当前生成列的子集，通过限制主问题进行优化求解；其余的候选方案（变量）可以改善限制主问题当前最优解时，才会进入该子集。![]()
![]()
![]()
在实际MIP的求解中，这些方法往往是进行组合，构成 branch and cut、branch and price、branch and cut and price （BCP）方法等，而BCP方法就是求解TSP和VRP的最有效的精确算法。求解器是用来实现在可行域中找到最优解的工具，其本质上是一个专业的数学/计算软件，用于实现复杂的数学算法。目前市面上主要分商用求解器、开源求解器两类。商用求解器主要有IBM CPLEX、GUROBI、FICO XPRESS等；开源求解器主要有SCIP、COIN-OR、Google OR-Tools等。商用求解器的效率一般是开源求解器的5-7倍。以VRPTW benchmark C101为例，上述模型通过Gurobi在3s内即可得到最优解。正因为有了优化求解器的存在，只需将以上整数规划模型的系数矩阵输入到优化求解器中，它就能够快速求出最优解或可行解（除了分支定界法还集成了各种启发式和割平面算法）。如前所述，混合整数规划在工业、经济、国防、医疗等各行各业应用十分广泛。目前，仅有少数几个发达国家拥有自己的整数规划求解器，如美国有GUROBI、CPLEX、SAS、MATLAB、CBC、SYMPHONY，德国有SCIP，俄罗斯有MIPCL和GLPK，英国有XPRESS（后被美国FICO公司收购），芬兰有LPSOLVE。商业求解器三大厂 CPLEX、GUROBI 与 XPRESS 凭借丰富的商业开发经验，以及较好的性能，在国际市场上占了超过90%的份额。目前号称SOTA的数学规划求解器是Gurobi Optimization，由 Zonghao Gu、Ed Rothberg和Robert Bixby 于 2008 年创立， 自 2009 年首次发布以来，Gurobi 一直在求解器性能（通过实现平均每年 60% 的速度提高）和适用性（通过将其应用扩展到 40 多个不同行业的 2,400 多家公司）方面不断设定新标准。求解器在工业发展中的意义非凡。例如，我国战略布局上面临的难题 EDA （电子设计自动化）需要用到SAT求解器进行快速验证，而制造、物流与供应链优化等则需要用到整数规划求解器（尤其是线性规划求解器）。在几年前，凡是需要用到求解器的企业，都是直接购买美国的 CPLEX、GUROBI 与 XPRESS。好消息是，近年来，国内一些有着领先科技能力的新锐公司和互联网大厂，也开始研发自己的优化求解器，布局相关研究。首款“国产”求解器于2018年发布，虽然处在起步阶段，但也实现了从0到1的突破。3.1 国内数学规划求解器
3.1.1 中科院CMIP混合整数规划求解器
中科院数学与系统科学院戴彧虹研究员带领CMIP团队从2015年开始，历经30个月，自主研发了我国第一个具有国际水平的整数规划求解器CMIP，并于2018年3月确定版本为CMIP 1.0版本。CMIP代码总量已经超过五万行，涵盖国际现有求解器预处理、启发式、割平面、分支、节点选择、域传播等各种功能模块，并已经较好地具备了求解大规模整数规划的能力。3.1.2 LEAVES优化求解器和COPT
LEAVES优化求解器是上海财经大学与杉数科技联合建设的一个运筹学与人工智能基础算法平台，也是第一个成规模的华人运筹学优化算法求解器。LEAVES求解器可以解决线性规划、半正定规划、几何规划、线性约束凸规划等常见的大规模优化问题，现已在社区开源。杉数科技开发的商业求解器COPT，同时具备大规模混合整数规划、线性规划（单纯形法和内点法）、二阶锥规划、半定规划以及凸二次规划和凸二次约束规划问题求解能力的综合性能数学规划求解器。其1.0版本于2019年5月发布，现迭代更新到6.5版。据2022年6月19日Mittlemann测试榜单（http://plato.asu.edu/bench.html，亚利桑那州立大学Hans Mittelmann教授负责维护的数学规划求解器测试平台，是目前世界上公认的最知名的、具有权威性和代表性的独立第三方测试平台）数据，COPT在线性规划的单纯形法、内点法、凸二次规划、半定规划均排名第一。3.1.3 达摩院Mind-Opt
Mind-Opt出自阿里达摩院决策智能实验室，是求解优化问题的专业计算软件。可广泛应用于云计算、零售、金融、制造、交通、能源等领域，号称每年在弹性计算资源调度优化场景里为阿里云节省数亿成本。过去两年，杉数、阿里与Gurobi在线性规划权威榜单 Mittlemann 测试上竞争激烈。据2023年3月24日数据，MindOpt和COPT在Mittelmann测试集的LPopt榜单（http://plato.asu.edu/ftp/lpopt.html）上均居榜首。3.1.4 华为天筹
华为云天筹（OptVerse）AI求解器将运筹学和AI相结合，突破业界运筹优化极限，支持求解混合整数线性规划问题和线性规划问题，寻求最优解。其特点是AI赋能求解，基于历史数据和问题特征自适应选择最优参数，支持基于拓扑感知的分布式并行加速，充分利用华为云分布式并行能力。据2023年3月24日数据，天筹AI求解器在Mittelmann测试集的大规模网络线性规划榜单（http://plato.asu.edu/ftp/network.html）中位列TOP1。如今深度学习在自然语言处理、视觉、语音、推荐等领域的应用已经非常广泛；在深度学习任务中，我们会为模型定义一个损失函数，称作优化问题的目标函数，损失函数表征的是预测值和实际值之间的差距，再通过一定的优化算法（如SGD）减小这个差距。多数情况下，损失函数十分复杂，很难得到确定、唯一的解析解，而是一般通过优化迭代的方法去逼近一个数值解。机器学习算法和经典的运筹优化算法的对比如下：
| 优点 | 不足 |
运筹优化算法 | 鲁棒、稳定：具有时间复杂度、最坏情况近似的理论保证 | 对于一个新的问题，需要领域专家知识来设计problem specific heuristic |
机器学习算法 | 自适应、数据驱动：能够根据特定业务数据分布提升算法性能，为应用于大规模问题提供可能 | 缺乏optimality ratio的保证 |
结合两者的优点，这两大类算法的交叉融合也逐渐成为一个研究热点，相结合的方式主要有以下两种：（此处借鉴大佬Yoshua Bengio论文中的图示，分别见Fig 7 和Fig 9）- 以end-to-end的方式用机器学习直接根据给定问题输出解（辅以相应的后处理）
- 将机器学习与传统的算法相结合，比如使用机器学习帮助选取参数或者启发式策略
![]()
![]()
下文将以路径规划问题（TSP、VRP）为例，从这两方面来介绍近年来的一些交叉研究。以基于机器学习的组合优化为主线，前后引入了RNN、注意力机制、Transformer、GNN等，从而发展成今天的众多分支。这个方向正随着机器学习的蓬勃发展而快速演进，随着更多的想法被吸收和融入到组合优化中，会成为传统算法的有力补充。
4.1 End-to-End 方法
4.1.1 早期研究
用机器学习来求解组合优化问题，在早些年就已有尝试和萌芽。1985年，Hopfield和Tank的论文《"Neural" computation of decisions in optimization problems》尝试用Hopfield-network来求解小型的TSP实例，其缺点是对超参和参数初始化敏感；1995年，Zhang和Dietterich在论文《A Reinforcement Learning Approach to Job-Shop Scheduling》中将强化学习应用到NP-hard的车间调度问题；1999年，论文《Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research》综述了早期神经网络用于组合优化问题的研究。鉴于当时数据、算力等的局限，这些尝试大多都只限于研究探索，没有展现出比传统算法更优异的效果。4.1.2 Pointer Network-开端
2014年提出的sequence-to-sequence（Seq2Seq）模型、注意力机制（Attention mechanism）以及后来的Transformer，已被广泛用于翻译、聊天机器人、文本生成等序列数据的任务处理上，取得了不错的效果。但是，传统的 Seq2Seq 模型无法解决输出序列的词汇表会随着输入序列长度的改变而改变的问题，因为其decoder 输出的目标数量是固定的，例如翻译时输出的向量长度往往等于字典的大小，且忽略了输出只能从输入中选择这个先验信息。这导致 Seq2Seq 不能用于一些组合优化的问题，例如凸包问题、TSP 等。这些问题的特征是输出往往是输入集合的子集（输出严重依赖于输入），而这个长度是变化的。如TSP的输出是输入的全排列，对于每个问题实例而言，其输入的数量，即城市的数量是不一样的。2015年Google和UC Berkeley的《Pointer Networks》将深度神经网络应用到了组合优化领域，Ptr-Net 可以解决输出字典大小可变的问题并修改了 Attention 的方法，根据 Attention 的值从 Encoder 的输入中选择一个作为 Decoder 的输出。![]()
Ptr-Net 的点睛之笔是改动了注意力机制。传统的带有注意力机制的seq2seq模型中，先使用encoder部分对输入序列进行编码，然后对编码后的向量做attention，最后使用decoder部分对attention后的向量进行解码从而得到预测结果。但在Ptr-Net中，得到预测结果的方式便是输出一个概率分布，逻辑上就像一个指针指向输入中的某个节点，也即所谓的指针。即传统带有注意力机制的seq2seq模型输出的是针对输出词汇表的一个概率分布，而Ptr-Net 输出的则是针对输入文本序列的概率分布。4.1.2 引入强化学习
前面提到的主要是监督学习的方法，这成为了一个比较大的局限，因为对于监督学习来说算法质量很大程度上取决于训练集的质量。这意味着要训练这个网络，需要先求解出训练集中问题的高质量解。在计算机视觉中的物体检测、图片分类，肉眼即可打标。但如果训练集中每个样本是TSP这样的NP完全问题，那么求其最优解或高质量的可行解，复杂度太高。为了克服监督学习的局限，引入了强化学习。因为强化学习不需要显式的带标签的数据集，而是通过与环境不断交互中得到的反馈来学习。2018年 Lehigh University 的论文《Reinforcement Learning for Solving the Vehicle Routing Problem》将 Ptr-Net拓展到求解VRP。相较于TSP，VRP的难点在于，问题输入是动态变化的。如当一个客户访问后，其需求可能就会被清零（或减少，对于split delivery）。而Ptr-Net结构存在的问题在于，当输入序列中的动态元素发生变化时，要对整个encoder进行更新才能进行下一个节点的预测，增加了计算量。![]()
这篇文章指出，输入集合中元素之间的顺序，如单词之间的相对关系，在文本翻译等场景很重要；而在组合优化问题如TSP、VRP中，输入是客户的位置和他们的需求量，其相互顺序并没有意义。因此去掉了encoder部分，只保留了decoder部分。具体的，在Embedding layer，直接把静态元素（坐标）映射为一个$$D$$维的向量空间，不同时刻的输入共享同一个输入结构；在 Attention layer，RNN的输出和动态元素（需求量）输入给attention机制，然后形成下一个可行决策点的概率分布。模型训练采用了经典的policy gradient方法。另外，为了加速训练和产生可行解，它用了masking scheme会将不可行解的log prob设为负无穷。有两种后处理方式：Greedy与Beam search。对于新的问题实例，只要它是来自于同一问题实例分布，则无需重新训练。在中等规模VRP（50，100个客户）中，该方法在解的质量上相较经典heuristic方法（Clarke-Wright savings heuristic，Sweep heuristic）以及Google OR Tools有一定优势。在结合beam search后，对比OR Tools有60%以上的胜率。4.1.3 Transformer结构
2017年Google的论文《Attention Is All You Need》引起了业界的巨大反响，这篇文章提出了Transformer模型，使用了（多头）注意力机制；该模型准确率更高，而且易并行，训练也更快。其网络结构也被借鉴到求解路径优化问题上。如2019年阿姆斯特丹大学的论文《Attention: Learn to solve routing problems!》，与原Transformer模型相比，encoder部分中没有使用位置编码，这样便使node embedding与输入顺序无关；之后节点的embedding通过N个堆叠的注意力层来更新，每层包括多头注意力层(Multi-Head Attention, MHA)、全连接前馈层(Feed Forward, FF)、跳跃链接（ship connection）和批量归一化层（Batch Normalization，BN）。多头注意力机制允许节点从不同的邻居接收不同类型的消息，前馈子层使用512维的隐藏层和ReLU激活函数。![]()
decoder采用了经典的自回归模式，按顺序执行，在时间步t∈{1，...,n}时，根据来自encoder的embedding和decoder在时间步t之前的输出Πt'，t'输出节点Πt。在解码过程中，用一个特殊的context node（c）来表征解码上下文。这个context node加上其它的embedding信息通过MHA层（与encoder中的MHA相比，这里为了高效没有skip-connection, BN和FF子层）得到输出向量。最后，decoder结构有一个single attention head（即M=1的MHA），通过softmax输出即为当前步的输出。![]()
训练采用基于policy-based的强化学习方法，baseline function通过基于当前最好的策略模型进行deterministic greedy rollout得到。实验部分主要考虑了多种路径问题，如TSP和VRP的多种变体，在部分case中，与构造类heuristic（Nearest、Random and Farthest Insertion和Nearest Neighbor），OR Tools等方法相比能得到更优的解。其实验数据是在单位正方形内随机均匀采样得到。
4.1.4 Graph Embedding与GNN
对于组合优化问题，一个困境是对于同样类型，但数据不同的问题，我们常常需要一遍遍地重新去求解。那么给定一个图优化问题和一个问题实例的分布，有没有办法可以让heuristic泛化到那些不曾见过的问题实例？引入机器学习的期望之一就是提高其泛化能力，即训练完的模型可以有效地应用于未曾见过的问题实例。为了提高泛化能力，对于图这种非欧几里得数据来说，通过图嵌入（Graph embedding）来抽取数据中的有效特征，通过低维的向量来表征图的节点及拓扑结构等信息，再作为后面机器学习算法的输入。而图神经网络（Graph neural network，GNN）是将深度神经网络模型应用于解决图相关任务的方法，其中重要的一种是结合了卷积的图卷积网络（Graph Convolutional Network，GCN）。2020年菜鸟网络在KDD上的一篇论文《Efficiently solving the practical vehicle routing problem: A novel joint learning approach》提出了基于点序列预测和边分类的图卷积网络GCN-NPEC。模型遵循的是经典的encoder-decoder框架。在encoder部分，采用GCN网络生成图中点和边的representation。采用的GCN编码器同时考虑点和边两种输入，将实际路网的交通可达性作为edge embedding。
在decoder阶段，共有两个decoder：点序列预测解码器和边分类解码器。Π其中，点序列预测解码器以点特征作为输入，生成VRP的解序列，边分类模型以边特征作为输入，输出一个代表边是否存在的概率矩阵。边分类解码器需要标签来指导分类训练，但由于精确算法很难在合理的时间内生成VRP的精确解，尤其当问题规模很大（如大于100）时。作为一种折中，论文中将点序列预测解码器得到的Π作为边概率矩阵的ground-truth（label）。在训练过程中，采用结合强化学习（点序列预测解码器）和监督学习（边分类解码器）的联合学习策略。
![]()
在实验分析阶段，论文选取了真实的配送数据和实际路网矩阵，对比实验证明了边缘特征的重要性，联合学习策略可以加速训练的融合并最终提高解的质量。4.1.5 RLHF
在VRP中，优化目标常是最小化总运输成本、行驶时间/距离、所需车辆数、时间窗违反量等等。这些目标有清晰、可量化的计算公式，而在工业实际中，常常需要车辆的行驶轨迹（路线）看起来 visual attractiveness，如路线之间没有覆盖或者交集（not overlapping、not crossing）。如下图，就分别示例了考虑 visual attractiveness（左图）、将总成本（右图）作为最小化目标的两个解决方案。显然，当考虑 visual attractiveness时，线路之间的交叉较少，看起来更加优美，更加易于算法方案的落地。在这种情况下，每个司机都集中在一个小区域内进行服务，意味着更高的操作效率，因为司机会更加熟悉片区内的交通、停车点、商户营业时间等。![]()
但是，路线看起来优美、没有交叉，只是主观、定性的描述，很难定义明确的计算公式。诚然，可以通过计算几何的方法，先计算每个route的最小外接圆、外接凸多边形，然后最小化这些多边形之间的重叠区域或交叉点，但和visual attractiveness也不直接等价。这样的方案在落地时，仍然会受到调度员（生产实际中，由调度员手动调车和排路线）的挑战。另一种方案是，通过统计学的方法，挖掘调度员的经验，可在一定程度上，学习到“司机对片区熟悉”这一信息。幸运的是，TMS中沉淀的调度员派车方案、车辆行驶轨迹，可以用来指导算法的寻优。这一点和LLM的进步轨迹很类似。LLM可以生成多样性的文本内容，然而对生成结果的评估是主观和依赖上下文的。通过预测下一个单词的方式和简单的损失函数（如交叉熵）来建模，没有显示地引入人的偏好和主观意见。而RLHF通过使用强化学习的方式来直接优化带有人类反馈的语言模型，用生成文本的人工反馈作为衡量标准，再进一步用该反馈作为损失来优化模型，使得ChatGPT类的模型大放异彩。RLHF 使得在一般文本数据语料库上训练的语言模型能和复杂的人类价值观对齐。再回到路径规划的落地应用上，一开始使用监督学习进行训练，基于TMS中积累的调度员派车方案（visual beautiful solutions），通过调度员（人类训练者）提供正确的标记示例，模型学习根据输入预测正确的动作或输出；在RM（Reword Model）训练奖励值方面，需要调度员对模型生成的回答进行排名，比较多个输出并构建更好的规范数据集，从而创建强化学习的奖励信号。总之，利用RLHF将人类专家的知识和经验融入到智能体的学习过程中，可以提高学习的效率和性能，通过人类经验，加速visual beautiful solutions 这类难以量化方案的落地，是一个值得探索的方向。4.2 搜索与后处理
如前所述，基于深度学习的方法已经在组合优化问题中取得还不错的成绩。另一方面，我们也可以看到，这些方法大多数还需要结合一些后处理操作，可分为如下几类。
在不少工作中，对于机器学习模型表示概率的输出，需要经过一些后处理算法得到最终的解。包括 1）Greedy：每次选取输出概率最高的节点。2）Beam search：本质上是宽度受限的广度优先搜索。3）Sampling：采样一定数量的解，取最优。
机器学习部分已经得到了一个完整的解，再结合一些局部搜索方法（如2-OPT、3-OPT等操作）对这个解进行修改来试图进行提升。2019年蒙特利尔综合理工学院等机构的论文《How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem》通过实验说明了搜索过程对于机器学习方法的影响巨大，一些基于机器学习的方法得到的解在经过如2-OPT，3-OPT和LK等方法refine后其optimality gap能够显著降低。融合树搜索或蒙特卡洛树搜索（MCTS）的思想，如基于GCN输出节点属于最优解的概率，用来在树搜索中以迭代的方式构造解。这个概率分布可能是多峰的，这样就可以生成很多候选解，有利于后面树搜索中更好的探索。在训练和推理中都加入MCTS，在训练中可以促进探索，增强泛化能力；在推理时可以改进效果，增强稳定性。4.3 与传统方法的结合
将机器学习引入用于解决组合优化问题，上面提到的方法主要是end-to-end的方式，而另一种重要的方式是与传统的OR方法相结合。
如前所述，解决组合优化的传统方法中比较经典的就是建模成混合整数规划问题，在精确求解器如Gurobi、SCIP等中，规划算法的实现涉及到大量超参数，如开源MIP求解器中性能最为强劲的SCIP求解器提供了2617个超参数，其中超过2000个超参数与求解过程中的决策强相关。通常，这些超参数由求解器开发者依据人工经验整定，面向通用问题提供一套适用性最为广泛的参数作为默认值。但面向细分行业特定场景，首先，默认参数难以发挥求解器的最佳性能。第二，求解器使用门槛相对较高，要求用户对组合优化、数学规划算法和场景问题本身有较为深入的理解。第三，即使是行业领域的专家，在求解器的海量参数组合中为特定场景问题选择最佳参数的过程中，也存在着人工调参耗时耗力的挑战。
这里需要提及的是NeurlPS 的ML4CO（The Machine Learning for Combinatorial Optimization）基于机器学习的组合优化比赛。2021年的比赛由加拿大蒙特利尔理工大学和蒙特利尔大学机器学习研究所 (Mila) 主办。Mila是全球领先的深度学习研究中心，由Yoshua Bengio教授创立。本次挑战赛的重点是通过机器学习方法替代现有组合优化求解器（开源求解器 SCIP 和它的Python封装 Ecole）中的启发式组件，针对混合整数线性规划问题（MILP）进行优化，探索机器学习在求解器参数整定、参数推荐上的应用，来达到提升现有的组合优化求解器求解性能的目的。主办方提供了三个 MILP 数据集，它们来自完全不同的现实问题，如 Dual Task 赛道研究如何更快收紧 MILP 问题的约束边界，征集SCIP求解器的最佳参数推荐方案，从而帮助提升通用求解器在细分行业特定场景问题上的性能。![]()
具体的，求解器内置有分支定界、割平面、列生成等算法的求解框架，涉及一些决策过程，如分支变量的选择、树搜索时的节点选取策略和节点裁剪策略、有效不等式的选择、非负列进基的选择等等，求解器内部常是一些启发式选择策略。引入机器学习，就是从大量的数据中自主学习启发式规则，对决策进行引导。如分支定界方法会将解空间递归地切分，形成搜索树，期间会计算bound并裁剪掉肯定不包含最优值的子树。He et al. (2014 ) 以监督学习的方式得到自适应的节点搜索策略，Liberto et al. (2016) 提出DASH方法，针对搜索过程中的子问题动态切换并选取最合适的启发算法，Gasse et al. (2019) 结合了模仿学习和GCN来学习变量选择策略等等。此外，Tang et al. (2020)使用强化学习用于自适应地选择割平面，也证明了对于分支切割算法的价值；Ding et al. (2020) 使用三部图来预测初始二元变量的取值，用于构造 local branching cut。这些都是采用深度学习算法来辅助决策传统OR方法中启发式选择策略的有力尝试。
应用深度强化学习来求解传统的组合优化问题，随着机器学习的蓬勃发展而快速演进，学术上掀起了一波热潮，但在业界的推广使用，还有一段距离。学术研究上的问题都是有着明确清晰定义的标准问题，而在真实的业务场景中，问题定义常是模糊的，需要通过trial and error来确定约束条件和目标函数。再以路径优化为例，业务关心的目标可能是距离最短、每辆车的服务区域尽量集中，考虑的约束可能有车辆的载重、容积上限、每趟服务的点数上限等等，特别是在POC的场景。机器学习类算法在问题定义改变（如新增/删减某个约束条件），需要重新训练模型，存在很大的试错成本；而数学规划类的方法，能真正做到开箱即用。另一方面，学术研究上的实验数据（包括仓库位置、客户节点位置、需求量等）基本都是在一个区间内随机均匀采样得到的，所以机器学习类的算法依据同样的生成规则，可以得到大量的训练数据。而在真实场景上，客户分布、下单频率，往往没有明显的数学统计特征。这样就造成了机器学习类的算法在按照某种分布生成的数据集上表现较好，但是在实际算例上表现欠佳。
如某供应链企业中AI部门所承接的算法问题，各业务线、各行业线，都有大量的决策优化、深度学习的场景。在干支线路由、传站、城配、末端揽派，都存在上文所述的路径规划问题。在决策优化的场景，目前普遍使用的还是传统的优化方法，机器学习类方法仅作为上游的销量预测、体积预测环节，二者互为补充。目前尚在探索使用机器学习类算法端到端支撑某个优化决策类场景。但是在机器视觉（CV）和自然语言处理（NLP）的场景，则大不相同。在CV和NLP领域，深度学习已较为成熟，出现了许多开源的代码和框架，在业界应用也较为广泛。相信随着研究的深入，随着大模型在各行各业的落地实践，深度强化学习和组合优化方法的交叉融合，一定会带来更为卓越的成果和应用；再借助分布式算力、海量数据的优势，在业界真正落地，产生价值。
参考文献
Di Liberto, Giovanni, et al. "Dash: Dynamic approach for switching heuristics." European Journal of Operational Research 248.3 (2016): 943-953.
He, He, Hal Daume III, and Jason M. Eisner. "Learning to search in branch and bound algorithms." Advances in neural information processing systems 27 (2014).
Gasse, Maxime, et al. "Exact combinatorial optimization with graph convolutional neural networks." Advances in Neural Information Processing Systems 32 (2019).
Tang, Yunhao, Shipra Agrawal, and Yuri Faenza. "Reinforcement learning for integer programming: Learning to cut." International conference on machine learning. PMLR, 2020.
Ding, Jian-Ya, et al. "Accelerating primal solution findings for mixed integer programs based on solution prediction." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 02. 2020.
Hopfield, John J., and David W. Tank. "“Neural” computation of decisions in optimization problems." Biological cybernetics 52.3 (1985): 141-152.
Zhang, Wei, and Thomas G. Dietterich. "A reinforcement learning approach to job-shop scheduling." IJCAI. Vol. 95. 1995.
Smith, Kate A. "Neural networks for combinatorial optimization: a review of more than a decade of research." Informs journal on Computing 11.1 (1999): 15-34.
Vinyals, Oriol, Meire Fortunato, and Navdeep Jaitly. "Pointer networks." Advances in neural information processing systems 28 (2015).
Nazari, Mohammadreza, et al. "Reinforcement learning for solving the vehicle routing problem." Advances in neural information processing systems 31 (2018).
Kool, Wouter, Herke Van Hoof, and Max Welling. "Attention, learn to solve routing problems!." arXiv preprint arXiv:1803.08475 (2018).
Duan, Lu, et al. "Efficiently solving the practical vehicle routing problem: A novel joint learning approach." Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020.
Bengio, Y. , A. Lodi , and A. Prouvost . "Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon." (2018).
Rossit, Diego Gabriel, Daniele Vigo, Fernando Tohmé, and Mariano Frutos. "Visual attractiveness in routing problems: A review." Computers & Operations Research 103 (2019): 13-34.
https://www.ecole.ai/2021/ml4co-competition/
微信公众号“运筹帷幄”相关内容
*文/有竹
如有任何疑问，或想要了解更多技术资讯，请添加小助手微信：
关注得物技术，每周一、三、五晚18:30更新技术干货未经得物技术许可严禁转载，否则依法追究法律责任。