首页|基于量子计算的城市轨道交通网络末班车衔接优化

基于量子计算的城市轨道交通网络末班车衔接优化

扫码查看
原文链接
  • NETL
  • NSTL
  • 万方数据
针对城市轨道交通网络化运营下,各条线路运营时间存在差异性而导致乘客无法成功换乘的问题,本文开展面向城市轨道交通末班车衔接优化问题的研究,选取末班车到发时间为决策变量,以最小化失败换乘乘客数量为目标,构建了混合整数线性规划模型.考虑到线网规模扩大导致模型复杂度高的问题,本文率先将量子计算应用于上述优化模型求解中.首先将原始模型重构为计算规模更小的两阶段问题;进而将第一阶段优化模型转换为可以运行在量子计算机上的二次无约束二值化优化问题(quadratic unconstrained binary optimization,QUBO)模型,并基于相干伊辛机的光量子计算技术完成了算法开发和真机实测.为了验证所提方法的有效性,以北京地铁为例,将量子计算结果与商业求解器进行比较,验证了本文提出模型转换方法和量子计算方法的可行性,为进一步应用量子计算解决轨道交通行业复杂优化问题提供了技术支撑.
Quantum Computing-Based Optimization for the Last-Train Connection Planning Problem in Urban Rail Transit Networks
Aiming at the optimization problem of last-train connection planning in urban rail transit networks,which often brings difficulties in successful transfers,this study selects the arrival times of the last trains as decision variables and constructs a mixed-integer linear programming model to minimize the number of failed passenger transfers.To address the high model complexity caused by the expansion of the network scale,a quantum computing method is adopted to solve the proposed model.First,the original model is reconstructed into a two-stage problem with a smaller computation scale.Then,the first-stage optimization model is transformed into a quadratic unconstrained binary optimization(QUBO)model that can run on a quantum computer.Algorithm development and experimental testing are conducted based on the optical quantum computing technology of the coherent Ising machine.To verify the effectiveness of the proposed method,we consider the Beijing subway network as an example.The quantum computing results are compared with those from commercial solvers,confirming the feasibility of both the model transformation method and the quantum computing approach proposed in this study.These findings provide technical support for the further application of quantum computing in solving complex optimization problems in rail transit.

urban rail transitnetwork operationlast-train connection optimizationmixed-integer programming,quantum computing,quadratic unconstrained binary optimization model

袁也、徐皓、王悉、王振明、魏艳、徐辉章

展开 >

北京城市轨道交通咨询有限公司,北京 100068

北京交通大学自动化与智能学院,北京 100044

北京玻色量子科技有限公司,北京 100016

城市轨道交通 网络化运营 末班车衔接优化 混合整数规划 量子计算 QUBO模型

国家自然科学基金国家自然科学基金中国国家铁路集团有限公司科技研究开发计划

U236820462073024P2022X013

2024

10.3969/j.issn.1672-6073.2024.02.020

都市快轨交通
北京交通大学,北京城建设计研究总院有限责任公司

都市快轨交通

CSTPCD北大核心
影响因子：0.785
ISSN：1672-6073
年,卷(期)：2024.37(2)
  • 11