1、智能运筹创新应用中国科学院自动化研究所群体决策智能团队杨宁邮箱：目录智能运筹研究背景1智能运筹算法应用3智能优化算法研究2外卖配送智能交通排产系统供应链建筑设计智能运筹研究背景应用场景金融决策求解时间长无法在大规模问题使用速度比精确求解快，但求解精度低需要大量对具体问题的研究和试错很难获得最优的标签可行性、自适应性、可泛化性智能运筹研究背景运筹优化问题求解方法智能运筹研究背景强化学习在运筹优化中的应用智能运筹研究背景代表性研究 Manchanda,et al.Learning Heuristics over Large Graphs via Deep Reinforcement Learnin

2、g,NeurIPS,2020.Stooke,et al.Responsive Safety in Reinforcement Learning by PID Lagrangian Methods,PMLR,2020.Tang Y,et al.Reinforcement Learning for Integer Programming:Learning to Cut,PMLR,2020 Li B,et al.Large language models for supply chain optimizationJ.arXiv,2023.目录智能运筹研究背景1智能运筹算法应用3智能优化算法研究2智能

3、优化算法研究智能优化算法评测数学模型应用问题求解器AI方法线性整数规划TSP,TSPTWConcorde,GurobiCNN-Transformer,Pointerformer,bab-dqn,Safe RL(PDO,PPOLag,CPO)VRP,VRPTW,CVRPORTools,SCIP,COPTNeuRewriter混合整数规划库存Gurobi,SCIPDNN-SMEIO割平面问题,set coveringhierarchical sequence model(HEM)Retro Branching，Hybrid-learn2branchProfit for Portfoliobab-d

4、qn00000eil51berlin52 kroA100求解距离ConcordeGurobitsp50_CNNtsp100_CNNPointerformer_50Pointerformer_10000.511.52eil51berlin52 kroA100求解时间GurobiBeamsearch_50Beamsearch_100Pointerformer_50Pointerformer_100横坐标：数据集纵坐标：求解的最小距离横坐标：数据集纵坐标：求解的时间智能优化算法研究TSP,CVRP问题055求解时间OR-toolsSCIPCOPT02000

5、400060008000400016000求解距离OR-ToolsSCIPCOPT横坐标：数据集纵坐标：求解的最小距离横坐标：数据集纵坐标：求解的时间CVRP问题TSP问题在TSP问题上，每种算法的求解性能相似，Gurobi的收敛速度远远大于其他算法。在CVRP问题上，OR-Tools的收敛性和收敛速度均优于其他算法，SCIP和COPT的均达到最大求解时间横坐标：数据集纵坐标：求解的最小距离横坐标：数据集纵坐标：求解的时间智能优化算法研究VRPTW,割平面问题横坐标：数据集纵坐标：求解时间横坐标：数据集纵坐标：求解时间割平面问题VRPTW问题020040060080010

6、0012001400C101C201R101R201R202求解时间OR-ToolsSCIPCOPT0200400600800016001800C101C201R101R201R202求解距离OR-ToolsSCIPCOPT00MIPLIB2017输入量1000*输出量1000Retro BranchingHybrid-learn2branch传统方法010203040MIPLIB2017输入量500*输出量1000Retro BranchingHybrid-learn2branch传统方法在VRPTW问题上，OR-Tools的收敛性和收敛速度均优于

7、其他算法，对于R201数据集，SCIP和COPT求解器无解对于R202数据集，SCIP求解器无解在割平面问题上，Retro Branching收敛速度大于Hybrid-learn2branch大于传统算法。智能优化算法研究大语言模型在运筹学中的应用 求解时间和求解质量 评估不同求解器或算法运筹优化的关注点 模型构建时的语音理解和推理能力 准确辨别问题并部署合适的Python库 prompt设计（建模、求解、纠错等）AI agent 设计 数学建模的Fine-tuning运筹优化大语言模型的关注点评估大模型解决运筹学问题能力的算法流程智能优化算法研究大语言模型在运筹学中的应用生成7种运筹学问题G

8、PT-4 and New Bing无约束优化问题（UOP）二次规划问题（QPP）线性规划问题（LPP）整数规划问题（IPP）旅行商问题（TSP）背包问题（KP）车辆路径问题（VRP）聚类优化问题编码可视化智能优化算法研究大语言模型在运筹学中的应用GPT-3.5 和 GPT-4 准确度对比分析GPT-4 和 GPT-3.5 在数学建模中的表现GPT 在运筹学建模与求解中的应用GPT-4 和 GPT-3.5 在程序生成中的表现智能优化算法研究大语言模型在运筹学中的应用智能优化算法研究Multi-ORGPT 解决困难运筹学问题实例多智能体协作系统目录智能运筹研究背景1智能运筹算法应用3智能优化算法研

9、究2智能运筹算法应用移动边缘计算(MEC)系统云基础设施边缘服务器云台微云智能交换机应用服务器智能路由器移动设备智能手机笔记本电脑传感器网络平板电脑智能载具智能健康检测设备智能运筹算法应用移动边缘计算系统AoI最小化在MEC系统中信息新鲜度最小化问题的挑战：1.长时间内的最优卸载决策难以获得2.MDP和DP算法受到维度诅咒的困扰3.信息新鲜度与两个因素有关：任务产生时间、任务处理持续时长我们算法的贡献：1.建模成多智能体Restless Multi-Arm Bandit问题，并构建了多层MDP2.证明多层MDP满足Intra-indexability，并提出了nested index策略3.理

10、论和仿真均证明提出算法的渐近最优性系统模型特点：1.考虑多个用户和多个边缘服务器2.每个任务都可以卸载到任意服务器3.未完成的任务可以被丢弃或发送到另一个服务器继续计算1 Chen S,Yang N,Zhang M,et al.Minimizing Age of Information for Mobile Edge Computing Systems:A Nested Index ApproachJ.IEEE WiOpt,2023.智能运筹算法应用多层MDP框架 将问题重新构造为Restless Multi-Arm Bandit问题，并建立了一个分层马尔可夫决策过程（MDP）来描述MEC系统

11、的AoI的更新嵌套索引和多层阈值类型1 Chen S,Yang N,Zhang M,et al.Minimizing Age of Information for Mobile Edge Computing Systems:A Nested Index ApproachJ.IEEE WiOpt,2023.智能运筹算法应用Nested Index 策略1 Chen S,Yang N,Zhang M,et al.Minimizing Age of Information for Mobile Edge Computing Systems:A Nested Index ApproachJ.IEEE

12、WiOpt,2023.Intra-indexability特性保证了门限的唯一性Nested index衡量了不同层不同状态，被改变的紧急程度智能运筹算法应用渐进最优性问题规模：1000个用户，200个服务器1 Chen S,Yang N,Zhang M,et al.Minimizing Age of Information for Mobile Edge Computing Systems:A Nested Index ApproachJ.IEEE WiOpt,2023.理论和实验上都验证了nested index policy 不断逼近松弛问题的最优解智能运筹算法应用多目标任务卸载任务卸载

13、在MEC系统中的难点：1.MEC网络环境具有动态性和不确定性2.不同MEC网络中用户可能对延迟和能耗有不同的偏好我们的贡献：1.设计了多目标强化学习（MORL）网络架构2.设计一个状态编码方法来构建特征（状态空间至少缩小10倍）3.设计了一个新型的奖励函数，用于准确计算延迟和能耗的效用1 Yang N,Wen J,Zhang M,et al.Multi-objective Deep Reinforcement Learning for Mobile Edge ComputingJ.IEEE WiOpt,2023.智能运筹算法应用MORL问题描述找到帕累托前沿上的一点调整偏好以找到多个点偏好动作

14、 卸载决策状态 任务、队列和传输信息环境智能体目标1：延迟目标2：能量消耗最小化黄色区域，或最大化蓝色区域寻找帕累托最优策略以最小化长期成本期望1 Yang N,Wen J,Zhang M,et al.Multi-objective Deep Reinforcement Learning for Mobile Edge ComputingJ.IEEE WiOpt,2023.智能运筹算法应用MORL算法框架多目标强化学习框架状态信息：1.任务量2.数据速率3.CPU频率4.执行任务数量5.边缘服务器数量6.任务直方图向量奖励函数：1.能量消耗2.传输延迟1 Yang N,Wen J,Zhang

15、M,et al.Multi-objective Deep Reinforcement Learning for Mobile Edge ComputingJ.IEEE WiOpt,2023.智能运筹算法应用MORL算法表现训练集：包含50个偏好，间隔为0.02测试集：包含100个偏好，间隔为0.01多边缘服务器我们考虑一个系统平衡算力和任务要求1 Yang N,Wen J,Zhang M,et al.Multi-objective Deep Reinforcement Learning for Mobile Edge ComputingJ.arXiv preprint arXiv:2307.1

16、4346,2023.智能运筹算法应用MORL算法表现边缘服务器数量E=8，任务容量L=20Mbits算法性能评价：MORL：80.7 LinUCB：69.9启发式方法：63.9 随机策略：24.2我们的MORL方案分别提高了帕累托前沿的超体积15.5%，26.3%和233.1%1 Yang N,Wen J,Zhang M,et al.Multi-objective Deep Reinforcement Learning for Mobile Edge ComputingJ.arXiv preprint arXiv:2307.14346,2023.快速建设阶段高效运营阶段生产计划型市场导向型我国

17、高速铁路正在经历转变对列车运行图编制效率和编制质量提出了更高要求，亟需在编制理论和应用技术层面寻找突破口编图频次增多，四季度+春暑运“4+2”编制模式列车运行图编制质量和经济评价为满足客流需求，提出“一日一图”的模式能力充分利用，精细化程度提升体现信息化智能化需求智能运筹算法应用铁路运行图技术背景 影响因素复杂且调整频繁 各作业环节相互交互、依次推进，列车运行图一体化铺画困难 本线列车运行线与跨线列车运行线的协调优化难题手工编制与调整技术自身的困难 列车运行图的编制与调整问题是一个超大规模的、多目标组合优化的“NP-难”问题，具有组合“爆炸”特性，既有模型方法/计算技术在基本原理框架上难以胜任

18、既有计算技术实现自动编制与调整的困难智能运筹算法应用铁路运行图技术背景 构建并运用数学优化模型算法和智能化算法去自动地、高效地对一张列车运行初始方案进行调整、以达到指标优化的目的基于列车运行初始方案的智能调整 优化目标：最小化运行图冲突个数 冲突图生成：大约60辆列车；5个站；大约50个冲突 基础动作集:增加列车、取消列车、增加停站、取消停站、向左平移、向右平移设计基础动作集设计冲突消解算子集设计强化学习算法停站时间超出范围运行时间超出范围间隔时间不足超车运行图智能调整需消解的四类冲突智能运筹算法应用算法流程在冲突列车左右各 max 的时间范围内逐站搜索前 个最大的间隔时间；从这些站中挑选约束

19、最强的站，这里用间隔时间的均值评估，均值越小约束越强（图中站）；模拟将冲突列车 插入挑选的站的前 个最大的间隔时间内，并保证满足最小约束时间；根据最终目标函数的大小决定冲突列车 最后的位置。参数包括冲突列车，搜索时间范围 max，每站挑选备用的最大间隔时间数量。智能运筹算法应用复杂冲突消解算子集环境状态集合S策略集合奖励R把线路区段内运行的所有列车分布（也即一张可能的但不一定可行的运行图图面）定义为一个环境状态定义动作：41个算子（即41个动作）策略集合需要通过对相关数据的采样和训练得到动作集合A奖励R主要用来对策略集合进行训练和估计 复杂冲突消解算子的单步减少的冲突数量除以复杂冲突消解算子一

20、次当中调用过基本动作的次数作为复杂冲突消解算子的单步回报；其他算子采用后减少的冲突数量；无效算子，加入惩罚。智能运筹算法应用强化学习算法设计将熵加入算法中，提高算法的探索力度，防止过早收敛；利用启发式算法对模型进行监督学习作为前期参数训练；采用模型预热策略，对测试时遇到的新环境进行若干轮预训练，进行模型参数的微调；多策略群体决策。将多个不同环境难度训练得到的不同策略组合到一起，从最终结果中选取最好的一个作为此时的测试环境的调图方案。PPOPPO算法改进策略智能运筹算法应用算法改进陷入局部最优解的概率成功消解所有冲突的概率在500次扰动的情况下RL可完全消解所有冲突的概率为74%智能运筹算法应用

21、算法表现60辆列车左右；5个站；4类冲突；训练时间一两天；测试时间5分钟以内；5分钟消解完所有冲突冲突图生成的方式是按照一定的比例选择基础动作集，进行部分线的调整来制造一部分冲突智能运筹算法应用优化结果可视化智能运筹算法应用优化结果可视化油田集合采购节点集合销售节点1销售节点2销售节点3加工混油汽油1 1汽油2 2汽油3 3柴油2 2柴油1 1加工方案存储上限存储下限安全上限安全下限原油中转集合炼厂集合成品油中转集合省库集合运输量加工量智能运筹算法应用原油业务链模型大规模230多个节点2100多条道路复杂性节点间相互影响节点类型多不确定性供应量需求量加工量多目标库存量运输成本多约束流量平衡约束

22、(节点)汽柴油存储约束发运量约束时空性路径跨天运行智能运筹算法应用问题难点核心思想通过建立运筹算子层，进行中层决策，较少上层强化学习的优化难度，运筹算子经过了专家策略设计，易于得到局部最优解，通过序列决策选择算子，能够组合出更好的解决方案。优缺点1、进一步减少了求解空间。2、能够快速得到较好的解决方案。3、运筹算子组需要手动设计，设计的好坏对性能影响大。原因通过强化学习-数学规划双层框架能有效降低学习维度，从更高的角度决策，指导算法得到方案，但是双层框架仍需要决策较多连续变量，强化学习仍需要面对较大的动作空间。通过强化学习-运筹算子-数学规划三层框架，能够把连续动作空间转化为离散动作空间，进一

23、步将问题简化。智能运筹算法应用分层框架二提高库存到安全线、减低库存到安全线、维持库存满足5天需求、提高库存到安全线保持储量在安全库存线内自下而上的顺序优化：首先优化成品油库存，以满足需求。成品油库存决定了加工量，牵动着炼厂的原油库存，因此第二项考虑原油优化，以维持运营。炼厂的原油量关系到供应或转运节点的运输调配，由此第三优化项为转运节点的库存（目前供应节点不考虑库存）。最后考虑运费优化，以得到在预警最小的前提下降低运费的方案炼厂成品油库存炼厂原油库存转运节点库存运费1、优先级 算子编号 对炼厂成品油的目标对炼厂原油库存的目标对转运节点的目标优化方法是否考虑运费1提高库存到安全线满足5天需求保持

24、在安全库存内分段线性优化是2降低库存到安全线满足5天需求保持在安全库存内分段线性优化是3维持库存满足5天需求保持在安全库存内分段线性优化是4提高库存到安全线提高库存到安全线保持在安全库存内分段线性优化是5降低库存到安全线提高库存到安全线保持在安全库存内分段线性优化是6维持库存提高库存到安全线保持在安全库存内分段线性优化是7提高库存到安全线满足5天需求保持在安全库存内多目标序列优化是8降低库存到安全线满足5天需求保持在安全库存内多目标序列优化是9维持库存满足5天需求保持在安全库存内多目标序列优化是10提高库存到安全线提高库存到安全线保持在安全库存内多目标序列优化是11降低库存到安全线提高库存到安

25、全线保持在安全库存内多目标序列优化是12维持库存提高库存到安全线保持在安全库存内多目标序列优化是智能运筹算法应用分层框架二库存量距离目标库存越近，惩罚值越小。库存超出上下限时，惩罚值的增长率会提升。系数法：在使用分段线性优化方法的算子中，优先级越高的项目拥有越高的权重（相邻优先级的权重差距为1001000倍），所有优化项的加权求和为总优化目标值。序列法：Gurobi求解器中内置了多目标序列优化方法，该方法优先优化高优先级的目标，然后在最优解集中选择下一优先级目标的最优解。2、库存与惩罚值关系图：3、优先级实现方法：智能运筹算法应用分层框架二0523456789527282930预警数天东北区域预警数量分层框架一-PPO分层框架一-SAC分层框架三-PPO分层框架三-SAC方法分层框架一-PPO分层框架一-SAC分层框架三-PPO分层框架三-SACSAC求解质量(预警数)641571180 0求解时间(s)6.766.0675.0369.6869.68全产业链东北区域下游分牌号的业务场景下，采用分层框架三和PPO算法得到的求解质量最好，可将预警数降为0.0.因次在全国范围采用分层框架三。智能运筹算法应用全产业链下游算法结果-东北区域智能运筹算法应用原油供应链智能决策算法谢谢！