电梯群控系统调度模型及其改进ADMM分解算法  

A dispatching model and improved ADMM decomposition algorithm for elevator group control system

作　　者：张家瑞 李海鹰[2] 苗建瑞[2] 王莹[1] 张红亮[1] ZHANG Jia-rui;LI Hai-ying;MIAO Jian-rui;WANG Ying;ZHANG Hong-iang(School of Trafic and Transportation,Bejing Jiaotong University,Beijing 100044,China;State Key Laboratory of Rail Traffic Control and Safety,Beijing Jiaotong University,Bejing 100044,China)

机构地区：[1]北京交通大学交通运输学院,北京100044 [2]北京交通大学轨道控制与安全国家重点实验室,北京100044

出　　处：《控制与决策》2023年第1期39-48,共10页Control and Decision

摘　　要：电梯群控系统调度问题(EDP)是具有非线性目标函数、较短求解时间要求的一类组合优化问题,针对此问题,提出一种基于时空状态网络的EDP问题线性化方法,并构建对应的线性0-1整数规划模型.为高效求解上述模型,在ADMM分解算法框架的基础上,为拉格朗日乘子次梯度迭代过程引入空间膨胀法(space dilation)应对算法迭代时间较短的问题,为二次项乘子设计基于迭代时间的更新形式,进而给出更加适配短时求解的改进ADMM分解算法.数值实验结果表明,在实际问题规模与500ms系统响应时间要求下,所提出的方法相较既有启发式算法具有更好的求解效果,相较商用求解器Gurobi-9.0.1提供的分支定界算法具有更短的求解时间,能够稳定高效地求解EDP问题.The elevator dispatch problem(EDP)is a kind of combinatorial optimization problem with the nonlinear objective function and short solving time request.Therefore,we propose a linearization method of the EDP based on the time-space-state network together with the corresponding linear 0-1 integer programming model.In order to solve the model efficiently,we introduce the space dilation method into the sub-gradient iterative process of the Lagrange multiplier and an augmented multiplier update method based on iteration time to make up for the defect of short solving time.The result of a numerical experiment under 500 ms respond time shows that the proposed method has better solution quality than the existing heuristic algorithm,shorter solving time than the branch and bound algorithm provided by Gurobi-9.0.1,and can solve the EDP stably and efficiently.

关 键 词：电梯群控系统调度问题 整数规划 时空状态网络 多商品流 ADMM分解算法 空间膨胀 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]