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

电梯群控系统调度问题(EDP)是具有非线性目标函数、较短求解时间要求的一类组合优化问题,针对此问题,提出一种基于时空状态网络的EDP问题线性化方法,并构建对应的线性0-1整数规划模型.为高效求解上述模型,在ADMM分解算法框架的基础上,为拉格朗日乘子次梯度迭代过程引入空间膨胀法(space dilation)应对算法迭代时间较短的问题,为二次项乘子设计基于迭代时间的更新形式,进而给出更加适配短时求解的改进ADMM分解算法.数值实验结果表明,在实际问题规模与500ms系统响应时间要求下,所提出的方法相较既有启发式算法具有更好的求解效果,相较商用求解器Gurobi-9.0.1提供的分支定界算法具有更短的求解时间,能够稳定高效地求解EDP问题.

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

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 500ms 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.