Beijing Transportation University
电梯群控系统调度问题(Elevator Dispatch Problem,EDP)是具有非线性目标函数、较短求解时间要求的一类组合优化问题,本文提出了一种基于时空状态网络的EDP问题线性化方法,并构建了对应的线性0-1整数规划模型。为高效求解上述模型,在ADMM分解算法框架的基础上进行改进,为拉格朗日乘子次梯度迭代过程引入空间膨胀法(Space Dilation)应对算法迭代时间较短的问题,并为二次项乘子设计基于迭代时间的更新形式,进而给出了更加适配短时求解的改进ADMM分解算法。数值实验结果表明,在实际问题规模与500ms系统响应时间要求下,所提出的方法相较既有启发式算法有更好的求解效果、相较商用求解器Gurobi 9.0.1提供的分支定界算法有更短的求解时间,能够稳定高效地求解EDP问题。
Elevator dispatch problem (EDP) is a kind of combinatrial optimization problem with nonlinear objective function and short solving time request. In this paper, we propose a linearization method of EDP based on time-space-state network togather with the corresponding linear 0-1 integer programming model. In order to solve the model efficiently, we introduce space dilation method into the subgradient iterative process of lagrange multiplier to make up for the defect of short solving time and design an update form based on iteration time for augmented multiplier, which could make the improved ADMM decomposition algorithm more suitable for short-time solving. The results of numerical experiment under the 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 could solve EDP problems stably and efficiently.