运筹学学报（中英文）

Select

1. k-均值问题的差分隐私算法综述

袁藩, 徐大川, 张冬梅

运筹学学报 2022, 26 (3): 1-16. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.001

摘要（8345）

HTML （849）

PDF（pc）（993KB）（1654）

$k$-均值问题是机器学习和组合优化领域十分重要的问题。它是经典的NP-难问题, 被广泛的应用于数据挖掘、企业生产决策、图像处理、生物医疗科技等领域。随着时代的发展, 人们越来越注重于个人的隐私保护:在决策通常由人工智能算法做出的情况下, 如何保证尽可能多地从数据中挖掘更多信息，同时不泄露个人隐私。近十年来不断有专家学者研究探索带隐私保护的$k$-均值问题, 得到了许多具有理论指导意义和实际应用价值的结果, 本文主要介绍关于$k$-均值问题的差分隐私算法供读者参考。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

2. 以商圈为中心的O2O动态外卖配送路径优化模型与算法

周成昊, 吕博轩, 周翰宇, 鲁海燕

运筹学学报 2022, 26 (3): 17-30. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.002

摘要（8339）

HTML （555）

PDF（pc）（1042KB）（1491）

针对线上到线下(Online to Offline，O2O) 外卖路径优化问题，综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件，将商圈看作配送中心，将快递员数量与快递员总行驶时间作为最小化目标，提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题，设计了一种分阶段启发式实时配送路径优化算法框架，并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上，以商圈为中心生成测试算例，对本文算法进行仿真实验，并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送，并优化其配送路径，有效减少了快递员数量与快递员总行驶时间。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

3. 一个基于张量火车分解的张量填充方法及在图像恢复中的应用

谢文蕙, 凌晨, 潘晨健

运筹学学报 2022, 26 (3): 31-43. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.003

摘要（8024）

HTML （74）

PDF（pc）（3899KB）（1030）

低秩张量填充在数据恢复中有广泛应用, 基于张量火车(TT) 分解的张量填充模型在彩色图像和视频以及互联网数据恢复中应用效果良好。本文提出一个基于三阶张量TT分解的填充模型。在模型中, 引入稀疏正则项与时空正则项, 分别刻画核张量的稀疏性和数据固有的块相似性。根据问题的结构特点, 引入辅助变量将原模型等价转化成可分离形式, 并采用临近交替极小化(PAM) 与交替方向乘子法(ADMM) 相结合的方法求解模型。数值实验表明, 两正则项的引入有利于提高数据恢复的稳定性和实际效果, 所提出方法优于其他方法。在采样率较低或图像出现结构性缺失时, 其方法效果较为显著。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

4. 布德施恩运筹策怀瑾握瑜滋蕙兰——庆祝姚恩瑜教授八十华诞

运筹学学报 2022, 26 (3): 0-0.

摘要（2067）

HTML （392）

PDF（pc）（1750KB）（992）

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

5. 机器学习驱动的多智能体路径搜寻算法综述

王祥丰, 李文浩

运筹学学报 2023, 27 (4): 106-135. DOI: 10.15960/j.cnki.issn.1007-6093.2023.04.006

摘要（731）

HTML （23）

PDF（pc）（3514KB）（831）

多智能体路径搜寻(Multi-agent Path Finding, MAPF)问题是多智能体系统中的核心基本问题, 被广泛应用于自动化智能仓储、自动驾驶、群体机器人等实际场景。从问题属性来看, 其关键难点在于多个智能体能够同时沿着路径行驶, 同时保证不发生碰撞, 属于NP-难组合优化问题。然而, 上述现实世界应用需要算法能够在较短的计算时间内为大量智能体搜索高质量的无碰撞路径, 更短的路径将导致更高的系统吞吐量以及更低的操作成本, 给经典MAPF运筹算法带来了极大挑战。因此, 近年来大量工作开始聚焦于使用机器学习方法赋能多智能体路径搜寻问题的研究, 以期加快求解速度、提升求解质量。本文综述内容包括三部分, 包括MAPF问题的核心概念、优化目标、基准任务, 经典MAPF算法的问题建模、核心思想、算法优劣, 并从机器学习赋能程度从低到高分别介绍一系列机器学习赋能的MAPF算法, 并给出具体的示意图和伪代码。本文还总结了机器学习驱动的多智能体路径搜寻算法目前面临的主要挑战, 并提出未来潜在研究方向, 以期可帮助领域内的研究者, 并促进机器学习方法在经典多智能体路径搜寻领域的发展。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

6. 面向城市交通信号优化的多智能体强化学习综述

华贇, 王祥丰, 金博

运筹学学报 2023, 27 (2): 49-62. DOI: 10.15960/j.cnki.issn.1007-6093.2023.02.003

摘要（1379）

HTML （20）

PDF（pc）（3398KB）（656）

随着近年来国民经济水平的快速提高, 人民的出行需求快速增长, 给当前由传统非智能信号控制主导的道路交通信号系统带来了日趋严峻的压力。交通路网复杂程度的显著提升促使交通信号控制从单点问题向系统工程问题发展, 而人工智能技术的兴起, 使得城市交通信号优化有了更多的处理手段。以多智能体强化学习为代表的群体智能方法在最近几年被广泛应用于交通信号控制与优化, 其中包括交通信号灯控制、自动驾驶、车路协同等。多智能体强化学习方法相比于传统方法, 可以赋予交通信号系统智能化的同时实现大规模交通信号系统协作, 以提升城市交通运行效率。未来智慧城市交通愿景下, 参与城市交通的各个部分互相协作是至关重要的, 多智能体强化学习在城市交通信号优化具有极大研究价值。本文将系统介绍面向城市交通信号优化的多智能体强化学习的基本理论及其应用于城市交通信号优化领域的现状, 从智能体协作的角度对已有方法进行归纳, 并分析各类方法优缺点。此外, 本文总结多智能体强化学习方法在城市交通信号优化领域所面临的挑战, 并指出该领域未来潜在研究方向, 以促进多智能体强化学习方法在智能城市交通信号优化领域的发展。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

7. 单位无穷范数下边权有界的最小支撑树逆最优值问题

张斌武, 关秀翠

运筹学学报 2022, 26 (3): 44-56. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.004

摘要（7782）

HTML （53）

PDF（pc）（888KB）（635）

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

8. 城市交通流量估计的运筹学方法

邵虎, 卓越, 刘鹏杰, 邵枫

运筹学学报 2023, 27 (2): 27-48. DOI: 10.15960/j.cnki.issn.1007-6093.2023.02.002

摘要（1255）

HTML （23）

PDF（pc）（1215KB）（614）

随着社会经济的发展和人类生产方式的进步, 交通管理系统为运筹学提供一系列研究课题。运筹学方法在交通网络建模领域有着广泛应用, 其在智能交通管理系统中亦占有重要位置。充分应用运筹学的各个分支方法去解决交通系统中存在的问题, 可有效保障生活中交通的高效、有序运行。本文首先介绍交通问题中一些基本概念和交通流量问题的若干基本模型, 然后从线性规划、整数规划、动态规划、图论、统计方法、启发式方法和机器学习七个方面综述现有的相关研究成果。最后, 探讨了交通流量模型及相关问题的发展方向, 提出其尚需研究和解决的问题, 以期为交通运输管理者与研究者提供更多参考。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

9. 拍卖机制设计在区块链中的应用与挑战

陈宏崟, 程郁琨, 邓小铁, 姚章豪

运筹学学报 2023, 27 (1): 1-29. DOI: 10.15960/j.cnki.issn.1007-6093.2023.01.001

摘要（2907）

HTML （99）

PDF（pc）（1261KB）（607）

区块链是新一代信息技术的重要组成部分，是分布式网络、加密技术、智能合约等多种技术集成的新型数据库软件。过去的十多年，区块链技术在全球范围内产生广泛影响。如今的区块链技术，已从最初的关注于解决货币和支付的去中心化问题，转入到解决市场的去中心化问题。智能合约的出现使得基于区块链技术的去中心化金融进入高速发展状态，也涌现出区块链环境下的各类拍卖场景。本文首次从机制设计角度，以区块链交易费机制，非同质化代币(Non-Fungible Token，NFT)拍卖和矿工可提取价值(Miner-Extractable Value，MEV)交易位置拍卖为主要对象，总结和剖析近些年来区块链上特有的拍卖机制；并针对区块链特性，提出区块链上拍卖机制设计所面临的挑战和未来亟待解决的问题。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

10. 谱图理论中的未解决问题

刘乐乐, 宁博

运筹学学报 2023, 27 (4): 33-60. DOI: 10.15960/j.cnki.issn.1007-6093.2023.04.003

摘要（839）

HTML （29）

PDF（pc）（779KB）（494）

谱图理论是图论中一个迷人的领域, 其利用与图相关的矩阵的特征值和特征向量来研究图的性质.本文收集了谱图理论中的若干公开问题和猜想, 按照内容的相关性将其分为20个主题.本文主要关注图的邻接矩阵中的相关问题, 并对这些问题和猜想的研究进展做了简要的梳理.

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

11. 随机二阶锥二次规划逆问题的SAA方法

王博, 初丽, 张立卫, 张宏伟

运筹学学报 2022, 26 (2): 31-44. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.003

摘要（2932）

HTML （61）

PDF（pc）（829KB）（489）

本文讨论一类随机的二阶锥二次规划逆问题, 该模型是一个含有二阶锥互补约束的随机二次规划模型, 对解释部分实际问题有着一定的优势。为了求解该模型, 本文引入了随机抽样技术和互补约束光滑化近似技术, 得到问题的近似子问题。本文证明, 只要子问题的解是存在且收敛的, 则该极限以概率一是原问题的C-稳定点; 若严格互补条件和二阶必要性条件成立, 则该极限以概率1是原问题的M-稳定点。一个简单的数值实验验证了该算法具有一定的可行性。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

12. 基于递归型神经网络动力学求解时变凸二次规划

廖伍代, 周军

运筹学学报 2023, 27 (1): 103-114. DOI: 10.15960/j.cnki.issn.1007-6093.2023.01.007

摘要（2445）

HTML （11）

PDF（pc）（1226KB）（476）

为了在线求解时变凸二次规划问题，实现误差精度更高、求解时间更短和收敛速度更快的目标。本文采用了求解问题更快的时变网络设计参数，选择了有限时间可以收敛的Sign-bi-power激活函数，构造了一种改进的归零神经网络动力学模型。其后，分析了模型的稳定性和收敛性，得到其解能够在有限时间内收敛。最后，在仿真算例中，与传统的梯度神经网络和归零神经网络模型相比，所提模型具有更高的误差精度、更短的求解时间和更快的收敛速度，优于前两种网络模型。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

13. 修正PRP共轭梯度方法求解无约束最优化问题

张慧玲, 赛·闹尔再, 吴晓云

运筹学学报 2022, 26 (2): 64-72. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.006

摘要（3154）

HTML （24）

PDF（pc）（823KB）（472）

基于著名的PRP共轭梯度方法，利用CG_DESCENT共轭梯度方法的结构，本文提出了一种求解大规模无约束最优化问题的修正PRP共轭梯度方法。该方法在每一步迭代中均能够产生一个充分下降的搜索方向，且独立于任何线搜索条件。在标准Wolfe线搜索条件下，证明了修正PRP共轭梯度方法的全局收敛性和线性收敛速度。数值结果展示了修正PRP方法对给定的测试问题是非常有效的。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

14. 最小化碳排放的共享单车迁移问题

苏兵, WyattCarlson, 范佳彬, GAO Arthur, 邵艳君, 林国辉

运筹学学报 2022, 26 (3): 75-91. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.006

摘要（2347）

HTML （56）

PDF（pc）（1155KB）（440）

本文考虑共享单车迁移问题, 它可看作是经典旅行售货商问题的一个新颖变形, 不同的是其目标函数为最小化碳排放。其中, 碳排放利用单车负载与其行驶路程的乘积进行刻画。我们提出了两个启发式算法：贪心和基于TSP的算法, 每个算法的核心思想均是优先减少单车负载。从理论上证明算法的可行性并给出数据实验以验证算法的实际性能。数据实验结果表明贪心算法优于基于TSP的算法, 这为共享单车企业进行日常单车分配提供了理论依据。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

15. 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用

吕袈豪, 罗洪林, 杨泽华, 彭建文

运筹学学报 2022, 26 (2): 16-30. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.002

摘要（2889）

HTML （61）

PDF（pc）（895KB）（437）

针对具有多块可分结构的非凸优化问题提出了一类新的随机Bregman交替方向乘子法，在周期更新规则下, 证明了该算法的渐进收敛性; 在随机更新的规则下, 几乎确定的渐进收敛性得以证明。数值实验结果表明, 该算法可有效训练具有离散结构的支持向量机。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

16. 一种求解二次约束二次规划问题的自适应全局优化算法

黄小利, 高岳林, 张博, 刘霞

运筹学学报 2022, 26 (2): 83-100. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.008

摘要（3009）

HTML （15）

PDF（pc）（871KB）（430）

为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

17. 双层规划在城市交通领域研究与应用的系统综述

魏贺, 刘昊飞, 许丹丹, 韩雪华, 王良, 张晓东

运筹学学报 2023, 27 (2): 1-26. DOI: 10.15960/j.cnki.issn.1007-6093.2023.02.001

摘要（1204）

HTML （47）

PDF（pc）（14197KB）（405）

双层规划是约束条件中含有优化问题，具有上下双层递阶结构的非凸优化问题，是典型的NP-Hard问题。本文系统性综述双层规划在城市交通领域的研究与应用，聚焦交通网络设计和OD(origin destination)反推调整两类问题。首先，利用文献计量法概述国内外研究主题与演变历程。其次，以开创性研究为线索溯源首次系统综述、首篇博士论文、首个TR-B专题和首篇中文综述关键研究。再次，梳理道路、公交、多模式网络设计问题与静态、动态OD反推问题的近期发展。从次，总结通用求解方法，讨论求解方法发展动向，阐述双层规划与平衡约束数学规划的关系。最后，指出未来发展的机遇与挑战：智慧交通探索揭示、建模架构模式优选和计算平台互动共享。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

18. 双边配给问题的Shapley解及其在博物馆通票问题中的应用

宫豆豆, 徐根玖, 侯东爽

运筹学学报 2022, 26 (2): 45-54. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.004

摘要（2921）

HTML （19）

PDF（pc）（816KB）（400）

双边配给问题描述了现实生活中一类带有二部图结构的稀缺资源配置问题, 例如, 在自然灾害期间救援物资的配给; 电力和天然气等自然资源按需分配; 高校引进人才调配等。本文通过求解线性规划, 并从联盟边际贡献的角度出发定义了双边配给问题的一个Shapley解。之后, 通过合作对策模型和解的公理化方法说明新解的合理性。首先, 建立双边配给问题的合作对策模型, 论证了新解与双边配给合作对策的Shapley值一致; 其次, 证明了Shapley解是唯一满足优先一致性的有效配给方案。最后, 将Shapley解应用于博物馆通票问题的研究, 探讨了博物馆合作制定通票后所得单票和通票收益的分配方式。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

19. 非负正交约束优化问题的理论、算法及应用

姜波

运筹学学报 2023, 27 (4): 136-152. DOI: 10.15960/j.cnki.issn.1007-6093.2023.04.007

摘要（417）

HTML （10）

PDF（pc）（947KB）（390）

非负正交约束优化问题是同时带有非负约束和正交约束的优化问题, 该类问题在机器学习和数据科学中有着重要的应用。常见的非负正交约束优化问题包括二次指派问题、图匹配问题、非负正交矩阵分解问题、非负主成分分析和K-指示模型等。由于非负约束和正交约束的共同作用, 该类问题具有一定的组合结构, 一般是NP-难的。本文主要介绍非负正交约束优化问题的基本理论性质、求解算法以及相关的应用模型。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

20. 最优控制问题的直接法综述

邵梦真, 余长君

运筹学学报 2023, 27 (4): 81-105. DOI: 10.15960/j.cnki.issn.1007-6093.2023.04.005

摘要（581）

HTML （25）

PDF（pc）（992KB）（376）

最优控制是控制理论的一个重要分支, 其目标是确定一种控制策略, 在满足动态系统和约束条件的前提下, 最优化系统性能指标。最优控制在工程、经济学、金融学、机器人技术、航空航天等各个领域都有着广泛的应用。直接法是解决最优控制问题的一类常用方法, 该方法通过直接离散化控制和状态函数, 从而将连续的最优控制问题转化为有限维优化问题。当前, 直接法主要包括直接配点法和控制参数化方法。直接配点法利用特定函数形式同时近似状态和控制函数, 控制参数化方法则使用基函数的线性组合来近似控制函数, 从而使控制空间离散化。两种方法的目的均为将连续的最优控制问题转化为有限维的非线性规划问题, 进而选择合适的优化算法求解。得益于其灵活性和处理约束的能力, 近年来直接法成为实际应用中需要实时控制的重要方法。本文主要介绍直接法的相关成果与最新进展供读者参考, 并讨论直接法的研究趋势和潜在研究方向。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

全文下载排行