都市快轨交通

换乘站	编号	换乘方式	换乘数量/人次
西单	1217	1 号线换乘 4 号线	100
西单	1217	4 号线换乘 1 号线	150
东单	167	1 号线换乘 5 号线	30
东单	167	5 号线换乘 1 号线	80

换乘站	编号	换乘方式	换乘数量/人次
西单	1217	1 号线换乘 4 号线	100
西单	1217	4 号线换乘 1 号线	150
东单	167	1 号线换乘 5 号线	30
东单	167	5 号线换乘 1 号线	80

参数	取值
初始 $\lambda$	1.0 + rand(-10, 10)
初始 $\mu$	1.0
增加系数 $\rho$	1.005
最大迭代次数	1000

参数	取值
初始 $\lambda$	1.0 + rand(-10, 10)
初始 $\mu$	1.0
增加系数 $\rho$	1.005
最大迭代次数	1000

参数	取值
初始温度	1000
降温系数	0.99
最低温度	0.001
每个温度迭代次数	10

参数	取值
初始温度	1000
降温系数	0.99
最低温度	0.001
每个温度迭代次数	10

参数	换乘站	线路	换乘线	取值
$\lambda$	1217	4 号线	-	533.1
${\lambda 1}$	1217	1 号线	4 号线	3.0
${\lambda 1}$	1217	1 号线	5 号线	-7.0
${\lambda 1}$	167	4 号线	1 号线	4.0
${\lambda 1}$	167	5 号线	1 号线	-8.0
${\lambda 2}$	1217	1 号线	4 号线	-3.0
${\lambda 2}$	1217	1 号线	5 号线	2.0
λ2	167	4 号线	1 号线	10.0
${\lambda 2}$	167	5 号线	1 号线	4.0
$\mu$	-	-	-	4.835 9

参数	换乘站	线路	换乘线	取值
$\lambda$	1217	4 号线	-	533.1
${\lambda 1}$	1217	1 号线	4 号线	3.0
${\lambda 1}$	1217	1 号线	5 号线	-7.0
${\lambda 1}$	167	4 号线	1 号线	4.0
${\lambda 1}$	167	5 号线	1 号线	-8.0
${\lambda 2}$	1217	1 号线	4 号线	-3.0
${\lambda 2}$	1217	1 号线	5 号线	2.0
λ2	167	4 号线	1 号线	10.0
${\lambda 2}$	167	5 号线	1 号线	4.0
$\mu$	-	-	-	4.835 9

变量	线路	换乘/始发站	最优解/(10s)
$R$	1	1217	263
$R$	1	167	63
$R$	4	1217	266
$R$	5	167	62
$S$	1	1217	6
$S$	1	167	6
$S$	1	1	6
$S$	4	1217	3
$S$	4	1	6
$S$	5	167	3
$S$	5	1	3

变量	线路	换乘/始发站	最优解/(10s)
$R$	1	1217	263
$R$	1	167	63
$R$	4	1217	266
$R$	5	167	62
$S$	1	1217	6
$S$	1	167	6
$S$	1	1	6
$S$	4	1217	3
$S$	4	1	6
$S$	5	167	3
$S$	5	1	3

求解模型	求解方法	求解时间/s	目标函数
原整数规划模型	Gurobi	0.3	130
QUBO 模型	Gurobi	102	130
简化模型 ALM 求解	CIM	0.516	130

求解模型	求解方法	求解时间/s	目标函数
原整数规划模型	Gurobi	0.3	130
QUBO 模型	Gurobi	102	130
简化模型 ALM 求解	CIM	0.516	130

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

PDF下载

袁也 ¹ , 徐皓 ¹ , 王悉 ² , 王振明 ³ , 魏艳 ² , 徐辉章 ³

都市快轨交通 | 运营管理 2024,37(2): 138-145

收起

都市快轨交通 | 运营管理 2024, 37(2): 138-145

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

全屏

袁也¹, 徐皓¹, 王悉², 王振明³, 魏艳², 徐辉章³

作者信息

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

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

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

袁也，男，硕士，工程师，主要从事轨道交通全过程咨询管理工作，yuanye@bii.com.cn

通讯作者:

王悉，男，博士，副教授，主要从事轨道交通列车运行控制与优化研究，xwang@bjtu.edu.cn

Quantum Computing-Based Optimization for the Last-Train Connection Planning Problem in Urban Rail Transit Networks

Ye YUAN¹, Hao XU¹, Xi WANG², Zhenming WANG³, Yan WEI², Huizhang XU³

Affiliations

¹ Beijing Urban MTR Consulting Co., Ltd. Beijing 100068

² School of Automation and Intelligence Beijing Jiaotong University Beijing 100044

³ Beijing Bose Quantum Technology Co., Ltd. Beijing 100016

doi: 10.3969/j.issn.1672-6073.2024.02.020

文章导航

摘要

收起

针对城市轨道交通网络化运营下,各条线路运营时间存在差异性而导致乘客无法成功换乘的问题,本文开展面向城市轨道交通末班车衔接优化问题的研究,选取末班车到发时间为决策变量,以最小化失败换乘乘客数量为目标,构建了混合整数线性规划模型。考虑到线网规模扩大导致模型复杂度高的问题,本文率先将量子计算应用于上述优化模型求解中。首先将原始模型重构为计算规模更小的两阶段问题;进而将第一阶段优化模型转换为可以运行在量子计算机上的二次无约束二值化优化问题(quadratic unconstrained binary optimization,QUBO)模型,并基于相干伊辛机的光量子计算技术完成了算法开发和真机实测。为了验证所提方法的有效性,以北京地铁为例,将量子计算结果与商业求解器进行比较,验证了本文提出模型转换方法和量子计算方法的可行性,为进一步应用量子计算解决轨道交通行业复杂优化问题提供了技术支撑。

关键词

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

Abstract

收起

Aiming at the optimization problem of lasttrain 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 mixedinteger 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 twostage problem with a smaller computation scale. Then, the firststage 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.

Key words

urban rail transit / network operation / last-train connection optimization / mixed-integer programming / quantum computing / quadratic unconstrained binary optimization model

引用本文

袁也, 徐皓, 王悉, 王振明, 魏艳, 徐辉章. 基于量子计算的城市轨道交通网络末班车衔接优化. 都市快轨交通, 2024 , 37 (2) : 138 -145 . DOI: 10.3969/j.issn.1672-6073.2024.02.020

Ye YUAN, Hao XU, Xi WANG, Zhenming WANG, Yan WEI, Huizhang XU. Quantum Computing-Based Optimization for the Last-Train Connection Planning Problem in Urban Rail Transit Networks[J]. Urban Rapid Rail Transit, 2024 , 37 (2) : 138 -145 . DOI: 10.3969/j.issn.1672-6073.2024.02.020

正文

收起

0 引言

收起

城市轨道交通以其大运量、低能耗、安全、快速等特点,成为缓解地面交通压力的重要手段之一 ^{[ 1 - 2 ]} 。随着轨道交通网络规模的快速扩大, 在末班车时段, 各条线路运营时间存在差异性, 经常有乘客无法换乘至相交线路末班车的情况。因此, 制定衔接良好的网络末班车时刻表具有重要的现实意义。

近年来, 国内外学者针对城市轨道交通网络末班车衔接优化问题展开了研究。CHEN 等 ^{[ 3 ]} 为末班车时刻表优化问题构建了混合整数规划模型, 以最大化城市轨道交通在末班车时段的网络可达性为目标, 使用遗传算法对问题进行求解; GUO 等 ^{[ 4 ]} 针对末班车时刻表优化问题设计了一种基于排序的启发式算法; ZHANG 等 ^{[ 5 ]} 拓展了优化时域以实现末班车和非末班车时刻表的综合协同；郑亚晶等 ^{[ 6 ]} 建立了以换乘人数最大化为目标的末班车衔接优化模型,并设计了遗传算法求解；通过考虑乘客换乘走行时间差异,袁振洲等 ^{[ 7 ]} 以全网乘客换乘感知费用总和最小为目标, 建立了末班车时段多趟列车的时刻表衔接优化模型；卢亚菡等 ^{[ 8 ]} 为末班车衔接优化问题建立了一种分布鲁棒机会约束规划模型以最小化换乘失败乘客数量。

对于城市轨道交通网络末班车衔接优化问题, 已有文献主要基于传统优化算法进行求解。然而, 随着线网规模的增大,传统的优化算法很难实现对大规模问题的快速高效求解。因此, 开展基于量子计算技术的网络末班车衔接优化问题研究, 探索数学模型转换方法并验证应用量子计算解决复杂网络优化问题的可行性, 具有重要的理论意义和现实价值。

1 问题描述

收起

本文考虑一个包含若干条线路的城市轨道交通网络。 $L$ 代表研究网络中的线路集合, ${I}_{l}$ 代表线路 $l$ 的站点集合, ${U}_{l}$ 代表线路 $l$ 的换乘站集合, ${X}_{l, i}$ 代表线路 $l$ 在换乘站 $i$ 相交的线路集合。聚焦于不同线路末班车在换乘站的到发衔接情况, 着重研究列车及乘客在换乘站的行为。

为便于建模, 考虑以下假设: ①乘客在同一换乘站相同线路间的换乘走行时间为常量；②末班列车有充足的运输能力；③乘客路径通过换乘路径和换乘站的选择提前给定。本研究没有将换乘路径(最短路约束) 和换乘站的选择寻优纳入到末班车时刻表衔接模型中, 而是利用这些要素来计算换乘乘客需求, 并将其作为模型输入。具体来说, 依据自动售检票系统(AFC) 提供的乘客始发地一目的地的计数信息, 以及乘客路径来反推换乘乘客的数量。而这些乘客路径的确定是由所需乘坐距离和换乘次数决定的, 涉及换乘路径和换乘站的选择寻优。

2 数学模型

收起

2.1 列车运行动态建模

公式(1)和(2)描述列车的到发时间:

(1) ${a}_{l, i}= {d}_{l, i - 1}+ {r}_{l, i - 1},\;\forall l \in L, i \in {I}_{l}\smallsetminus \{ 1\}$

(2) ${d}_{l, i}= {a}_{l, i}+ {s}_{l, i},\;\forall l \in L, i \in {I}_{l}$

式中, ${a}_{l, i},{d}_{l, i},{s}_{l, i}$ 分别表示线路 $l$ 末班车在车站 $i$ 的到达、出发及停站时间; ${r}_{l, i}$ 指线路 $l$ 末班车在车站 $i$ 到 $i + 1$ 的运行时间。

在列车运行过程中, 列车区间运行时间应控制在上下限范围内, 即:

(3) ${r}_{l, i}^{\min }\leq {r}_{l, i}\leq {r}_{l, i}^{\max },\forall l \in L, i \in {I}_{l}\smallsetminus \left\{{I}_{l}\right\}$

式中, ${r}_{l, i}^{\min }$ 表示线路 $l$ 末班车在车站 $i$ 到车站 $i + 1$ 的最短运行时间; ${r}_{l, i}^{\max }$ 表示线路 $l$ 末班车在车站 $i$ 到车站 $i + 1$ 的最长运行时间。

列车停站时间应控制在上下限范围内,即:

(4) ${s}_{l, i}^{\min }\leq {s}_{l, i}\leq {s}_{l, i}^{\max },\forall l \in L, i \in {I}_{l}$

式中, ${s}_{l, i}^{\min }$ 表示线路 $l$ 末班车在车站 $i$ 的最短停站时间; ${s}_{l, i}^{\max }$ 表示线路 $l$ 末班车在车站 $i$ 的最长停站时间。

为保证列车运行安全, 相邻车次间的发车间隔需要大于或等于最小发车间隔, 即:

(5) ${d}_{l, i}- {d}_{l, i}^{- }\geq {h}_{l}^{\min },\forall l \in L, i \in {I}_{l}$

式中, ${h}_{l}^{\min }$ 表示线路 $l$ 的最短发车间隔; ${d}_{l, i}^{- }$ 为线路 $l$ 末班车的前一列车在车站 $i$ 的出发时间。

2.2 乘客换乘行为建模

为了清晰地描述乘客换乘行为, 图 1 给出了末班车衔接示意。线路 1 末班车(即列车 1)进站, 换乘乘客下车, 通过一段时间的走行抵达换乘线路 2 列车所在站台。此时, 若列车还未到站 (即列车 3 情况), 则等待其到站后乘客上车, 并随列车一同离站; 若列车已经离站 (即列车 2 情况), 则从列车 1 下车的乘客将没有机会换乘至该列车。

基于上述描述, 乘客换乘过程建模为:

(6) ${d}_{l, i}- \left({{a}_{{l}^{\prime }, i}+ {o}_{l, i}^{{l}^{\prime }}}\right)\geq M\left({{y}_{l, i}^{{l}^{\prime }}- 1}\right),\;\forall l \in L, i \in {U}_{l},{l}^{\prime }\in {X}_{l, i}$

(7) ${d}_{l, i}- \left({{a}_{{l}^{\prime }, i}+ {o}_{l, i}^{{l}^{\prime }}}\right)\leq M{y}_{l, i}^{{l}^{\prime }},\;\forall l \in L, i \in {U}_{l},{l}^{\prime }\in {X}_{l, i}$

(8) ${y}_{l, i}^{{l}^{\prime }}= \{ 0,1\},\;\forall l \in L, i \in {U}_{l},{l}^{\prime }\in {X}_{l, i}$

式中, ${y}_{l, i}^{{l}^{\prime }}$ 是 0-1 决策变量,若线路 ${l}^{\prime }$ 末班车换出的乘客在车站 $i$ 可以成功换乘至线路 $l$ ,则 ${y}_{l, i}^{{l}^{\prime }}= 1$ ,否则为 $0;{o}_{l, i}^{{l}^{\prime }}$ 表示乘客在车站 $i$ 由线路 ${l}^{\prime }$ 换出走行至线路 $l$ 站台的时间； $M$ 为充分大的正数。

2.3 目标函数

为了提高末班车时段乘客换乘效率, 目标设置为最小化换乘失败的乘客数量,即:

(9) $ J =\mathop{\sum }\limits_{{l \in L}}\mathop{\sum }\limits_{{i \in {U}_{l}}}\mathop{\sum }\limits_{{{l}^{\prime }\in {X}_{l, i}}}{p}_{l, i}^{{l}^{\prime }}\left({1 -{y}_{l, i}^{{l}^{\prime }}}\right)$

式中, ${p}_{l, i}^{{l}^{\prime }}$ 表示在车站 $i$ 由线路 ${l}^{\prime }$ 末班车换乘至线路 $l$ 的客流需求。另外, 考虑成功换乘乘客等待时间最小化的目标有助于提升乘客出行体验,增加用户满意度。然而, 建模换乘乘客等待时间会涉及非线性项, 并且将其线性化处理需要引入更多的约束, 这会导致问题变得更复杂, 从而影响求解的效率。鉴于此, 为了简化问题并确保高效的求解, 我们目前的研究只关注失败换乘乘客数量的最小化。

2.4 优化模型

根据上述描述, 构建混合整数线性规划模型如下:

(10) $\min J =\mathop{\sum }\limits_{{l \in L}}\mathop{\sum }\limits_{{i \in {U}_{l}}}\mathop{\sum }\limits_{{{l}^{\prime }\in {X}_{l, i}}}{p}_{l, i}^{{l}^{\prime }}\left({1 -{y}_{l, i}^{{l}^{\prime }}}\right)\\\begin{array}{l}\text{ s.t.}\left\{{{a}_{l, i}= {d}_{l, i - 1}+ {r}_{l, i - 1},\;\forall l \in L, i \in {I}_{l}\smallsetminus \{ 1}\right\}\\{d}_{l, i}= {a}_{l, i}+ {s}_{l, i}+ {s}_{l, i}+ \forall l \in L, i \in {I}_{l}\\{d}_{l, i}- {d}_{l, i}^{- }\geq {s}_{l, i}^{\min },\;\forall l \in L, i \in {I}_{l}\\{d}_{l, i}- \left({{a}_{l, i}+ {c}_{l, i}^{\prime }}\right)\geq M\left({{y}_{l, i}^{\prime }- 1}\right)\;\forall l \in L, i \in {U}_{l},{l}^{\prime }\in {X}_{l, i}\\{d}_{l, i}- \left({{a}_{l, i}+ {c}_{l, i}^{\prime }}\right)\leq M{y}_{l, i}^{\prime \prime },\;\forall l \in L, i \in {U}_{l},{l}^{\prime }\in {X}_{l, i}\\{y}_{l, i}^{\prime }= \left\{\begin{array}{l} 0,1\},\;\forall l \in L, i \in {I}_{l},{l}^{\prime }\in {X}_{l, i}\\{x}_{l, i}^{\min }\leq {x}_{l, i}\leq {x}_{l, i}^{\max },\;\forall l \in L, i \in {I}_{l}\smallsetminus \{\{{I}_{l}\}\\\end{array}\right.\\\end{array}$

3 模型重构

收起

考虑到末班车衔接优化模型(10)涉及不同线路的列车时刻表变量、运行安全约束以及换乘衔接耦合约束, 随着线网规模的增大, 计算耗时将随之迅速增加。因此, 本节对模型(10)简化处理, 将问题拆分成两阶段优化, 其中阶段 1 为换乘站的到发时刻优化, 阶段 2 为其他普通车站到发时刻的递推优化。后续研究仅需对阶段 1 的模型进行求解, 阶段 2 利用贪心算法快速生成一组可行解。阶段 1 模型如下:

定义合并的区间从 $i - 1$ 站出发到达 $i$ 站对应的运行时间为 ${R}_{l, j}$ ; 定义换乘站/始发站 $i$ 的停站时间为 ${S}_{l, i}$ , 则有

(11) $\mathop{\sum }\limits_{{j \in {J}_{l, i - 1\cup \{ i - 1\}}}}{r}_{l, j}^{\min }+ \mathop{\sum }\limits_{{j \in {J}_{l, i - 1\cup \{ i - 1\}}}}{s}_{l, j}^{\min }\leq {R}_{l, j},\forall l \in L, i \in {U}_{l}$

(12) $\mathop{\sum }\limits_{{j \in {J}_{l, i - 1\cup \{ i - 1\}}}}{r}_{l, j}^{\max }+ \mathop{\sum }\limits_{{j \in {J}_{l, i - 1\cup \{ i - 1\}}}}{s}_{l, j}^{\max }\geq {R}_{l, j},\forall l \in L, i \in {U}_{l}$

(13) ${s}_{l, i}^{\min }\leq {S}_{l, i}\leq {s}_{l, i}^{\max },\forall l \in L, i \in {U}_{l}\cup 1 $

将模型改为适配量子计算的二值模型,将 ${S}_{l, i}$ 和 ${R}_{l, j}$ 定义为一系列二值变量 ${S}_{l, i, n}$ 和 ${R}_{l, j, n}$ 的表达,式中 $n = 0,1,\cdots , N + 1$ 为需要的二进制变量位数,即可满足 $S$ 和 $R$ 上下界约束。

(14) ${S}_{l, i}= {s}_{l, i}^{\min }+ \mathop{\sum }\limits_{{n = 0}}^{N}{2}^{n}{S}_{l, j, n}+ $

(15) $\left({{s}_{l, i}^{\max }- {s}_{l, i}^{\min }- {2}^{N + 1}+ 1}\right){S}_{l, j, N + 1}\\{R}_{l, j}= \left({\mathop{\sum }\limits_{{j \in {J}_{l, i - 1 \cup \{ i - 1\}}}}{\eta }_{l, j}^{\min }+ \mathop{\sum }\limits_{{j \in {J}_{l, i - 1 \cup \{ i - 1\}}}}{s}_{l, j}^{\min }}\right)\mathop{\sum }\limits_{{n = 0}}^{N}{2}^{n}{R}_{l, j, n}+ \left({\mathop{\sum }\limits_{{j \in {J}_{l, i - 1 \cup \{ i - 1\}}}}{\eta }_{l, j}^{\max }+ \mathop{\sum }\limits_{{j \in {J}_{l, i - 1 \cup \{ i - 1\}}}}{s}_{l, j}^{\max }}\right){R}_{l, j, N + 1}+ \\\left({\mathop{\sum }\limits_{{j \in {J}_{l, i - 1 <\lfloor i - 1\rfloor }}}{r}_{l, j}^{\min }+ \mathop{\sum }\limits_{{j \in {J}_{l, i - 1 <\lfloor i - 1\rfloor }}}{s}_{l, j}^{\min }- {2}^{N + 1}+ 1}\right){R}_{l, j, N + 1}$

换乘站的到发时间表示为

(16) ${a}_{li}= {a}_{l1}+ \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{l, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{l, j}$

(17) ${d}_{li}= {d}_{l1}+ \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{l, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{l, j}$

式中, $i - 1$ 为换乘站 $i$ 之前的换乘站; 1 为始发站。

模型总结如下:

(18) $\min J =\mathop{\sum }\limits_{{l \in L}}\mathop{\sum }\limits_{{i \in {U}_{l}}}\mathop{\sum }\limits_{{{l}^{\prime }\in {X}_{l, i}}}{p}_{l, i}^{{l}^{\prime }}\left({1 -{y}_{l, i}^{{l}^{\prime }}}\right)\\ S.t.\begin{cases}{a}_{l1}+ &\mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{l, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{l, j}- \left({{a}_{{l}^{\prime }1}+ \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{{l}^{\prime }, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{{l}^{\prime }, j}- {o}_{li}^{{l}^{\prime }}}\right)\\& \geq M\left({{y}_{li}^{{l}^{\prime }}- 1}\right),\;\forall l \in L, i \in {U}_{l},{l}^{\prime }\in {X}_{li}\\{a}_{l1}+ &\mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{l, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{l, j}- \left({{a}_{{l}^{\prime }1}+ \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{{l}^{\prime }, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{{l}^{\prime }, j}- {o}_{li}^{{l}^{\prime }}}\right)\\& \leq M{b}_{l1}^{{l}^{\prime }}\;\forall l \in L, i \in {U}_{l},{l}^{\prime }\in {X}_{l1},\end{cases}$

式中, ${R}_{l, j}$ 和 ${S}_{l, i}$ 为满足上下界(11)(12)(13)的二进制变量表示之和(14)(15)。

鉴于量子计算机可用比特数和精度限制, 本文对该模型的求解借鉴了增广拉格朗日算法(augmented lagrangian method, ALM), 将问题迭代求解, 对每次求解更新系数, 直到找到理论最优解且各约束得到满足。算法如下:

输入: 初始化 $\mu > 0$ ,初始化 $\lambda$ ,初始化增加系数 $\rho > 1$ 。

输出: 最终的 $\mu ,\lambda$ 以及增广拉格朗日函数

while $c\left( x\right)> 0$ or 遍历次数未达上限

$x \leftarrow \arg \mathop{\min }\limits_{x}\left({f\left( x\right)+ {\lambda }^{T}c\left( x\right)+ \frac{x}{2}\parallel c\left( x\right){\parallel }^{2}}\right)$ 可用量子计算机求解

$\text{for}i = 1,\cdots , n\text{, do}\\\text{if}c\left( x\right)> 0 \\{\lambda }_{i}\leftarrow {\lambda }_{i}+ {\mu c}\left( x\right)\\\mu \leftarrow {\rho \mu }$

在每一步求解中, 只需要关注原问题的不等式约束,将其表示为 $c\left( x\right)\leq 0$ 形式。ALM 每一次迭代求解模型如下:

(19) $\mathop{\min }\limits_{y}\mathop{\sum }\limits_{{l \in L}}\mathop{\sum }\limits_{{i \in {U}_{l}}}\mathop{\sum }\limits_{{{l}^{\prime }\in {X}_{li}}}{p}_{li}^{{l}^{\prime }}\left({1 -{y}_{li}^{{l}^{\prime }}}\right)+ \mathop{\sum }\limits_{{l \in L}}\mathop{\sum }\limits_{{i \in {U}_{l}}}{\lambda }_{l, i}\left({-{a}_{l1}- \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{l, j}- \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{l, j}+ {d}_{l, i}^{- }+ {h}_{\min }^{l}}\right)+ \\\mathop{\sum }\limits_{{l \in L}}\mathop{\sum }\limits_{{i \in {U}_{l}}}\mathop{\sum }\limits_{{{l}^{\prime }\in {X}_{li}}}\lambda {1}_{{il}{l}^{\prime }}\left({-{a}_{l1}- \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{l, j}- \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{l, j}+ \left({{a}_{{l}^{\prime }1}+ \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{{l}^{\prime }, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{{l}^{\prime }, j}- {o}_{li}^{{l}^{\prime }}}\right)+ M\left({{y}_{li}^{{l}^{\prime }}- 1}\right)}\right)+ \\\mathop{\sum }\limits_{{l \in L}}\mathop{\sum }\limits_{{i \in {U}_{l}}}\mathop{\sum }\limits_{{{l}^{\prime }\in {X}_{li}}}\lambda {2}_{{il}{l}^{\prime }}\left({{a}_{l1}+ \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{l, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{l, j}- \left({{a}_{{l}^{\prime }1}+ \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{{l}^{\prime }, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{{l}^{\prime }, j}- {o}_{li}^{{l}^{\prime }}}\right)- M{y}_{li}^{{l}^{\prime }}}\right)+ \\\frac{\mu }{2}{\left(-{a}_{l1}- \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{l, j}- \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{l, j}+ {d}_{l, i}^{- }+ {h}_{\min }^{l}\right)}^{2}+ \\\mathop{\sum }\limits_{{l \in L}}\mathop{\sum }\limits_{{i \in {U}_{l}}}\mathop{\sum }\limits_{{{l}^{\prime }\in {X}_{li}}}{\left(-{a}_{l1}- \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{l, j}- \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{l, j}+ \left({a}_{{l}^{\prime }1}+ \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{{l}^{\prime }, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{{l}^{\prime }, j}- {o}_{li}^{{l}^{\prime }}\right)+ M\left({y}_{li}^{{l}^{\prime }}- 1\right)\right)}^{2}+ \\\mathop{\sum }\limits_{{l \in L}}\mathop{\sum }\limits_{{i \in {U}_{l}}}\mathop{\sum }\limits_{{{l}^{\prime }\in {X}_{li}}}{\left({a}_{l1}+ \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{l, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{l, j}- \left({a}_{{l}^{\prime }1}+ \mathop{\sum }\limits_{{j = 1}}^{{i - 1}}{S}_{{l}^{\prime }, j}+ \mathop{\sum }\limits_{{j = 2}}^{i}{R}_{{l}^{\prime }, j}- {o}_{li}^{{l}^{\prime }}\right)- M{y}_{li}^{{l}^{\prime }}\right)}^{2}$

在阶段 1 问题求解完成后, 已知末班车在换乘站到发时刻等信息, 需要递推出列车在每一个非换乘站的到发时刻, 阶段 2 问题可等价为求解一组多元线性方程。阶段 2 方程组如下:

(20) $\left\{\begin{array}{l}{a}_{l, i}\geq {d}_{l, i - 1}+ {r}_{l, i - 1}^{\min },\;\forall l \in L, i \in {I}_{l}\smallsetminus \{ 1\}\\{a}_{l, i}\leq {d}_{l, i - 1}+ {r}_{l, i - 1}^{\max },\;\forall l \in L, i \in {I}_{l}\smallsetminus \{ 1\}\\{d}_{l, i}\geq {d}_{l, i}+ {s}_{l, i}^{\min },\;\forall l \in L, i \in {I}_{l}\\{d}_{l, i}\leq {a}_{l, i}+ {s}_{l, i}^{\max },\;\forall l \in L, i \in {I}_{l}\\{d}_{l, i}= {d}_{l, i}- {s}_{l, i}^{\min },\;\forall l \in L, i \in {I}_{l}\\{r}_{l, i}\leq {d}_{l, i},\;\forall l \in L, i \in {I}_{l}\smallsetminus \{ 1, l\}\\{s}_{l, i}^{\min }\leq {s}_{l, i}\leq {r}_{l, i}^{\max },\;\forall l \in L, i \in {I}_{l}\smallsetminus \{\left|{I}_{l}\right|\}\\{s}_{l, i}^{\min }\leq {s}_{l, i}\leq {r}_{l, i}^{\max },\;\forall l \in L, i \in {I}_{l}\smallsetminus \{ 1\}\end{array}\right.$

4 量子计算方法

收起

量子计算以量子比特为基本单元,利用量子叠加、纠缠、干涉等物理特性进行高速运算, 可对组合优化问题进行指数级求解加速。其中, 基于光量子系统的相干伊辛计算架构(coherent ising machine, CIM)在全连通 100000 节点的最大割问题中的算法优势已经得到了证明 ^{[ 9 ]} 。

本文使用的光量子计算机是基于测量反馈的CIM ^{[ 10 ]} 。作为一种混合量子计算系统, 测量反馈型 CIM 的光学部分采用飞秒脉冲光纤激光器, 形成简并光学参数振荡(degenerate optical parametric oscillators, DOPO)在光纤环路中传输 ^{[ 11 ]} 。

CIM 可被用作求解优化 Ising 模型的专用计算机。 Ising 模型的自旋变量取值 $\pm 1$ ,哈密顿量表示为:

(21) ${H}_{\text{Ising }}\left(\sigma \right)= -\mathop{\sum }\limits_{{i, j}}{J}_{ij}{\sigma }_{i}{\sigma }_{j}+ \mathop{\sum }\limits_{i}{h}_{i}{\sigma }_{i}$

式中, ${J}_{ij}$ 和 ${h}_{i}$ 分别为二次系数和线性系数。

QUBO 模型变量 $x$ 取值 0 或 1, QUBO 模型可以表示为:

(22) ${f}_{\text{QUBO }}\left( x\right)= -\mathop{\sum }\limits_{{i \leq j}}{q}_{ij}{x}_{i}{x}_{j}$

基于 ${x}_{i}= \left({1 +{\sigma }_{i}}\right)/2$ 关系,将目标问题的 QUBO 模型映射到全连通 Ising 哈密顿量, 将 Ising 模型中的系数输入 CIM,通过可控的量子相变过程使哈密顿量最小化, 问题即可被 CIM 有效求解。

5 算例分析

收起

为验证所提出模型和方法的有效性, 本节选取北京地铁部分网络作为仿真背景, 如图 2 所示。设置最短停站时间为 ${30}\mathrm{\;s}$ ,最长停站时间为 ${60}\mathrm{\;s}$ ,换乘走行时间为 ${120}\mathrm{\;s}$ ,三条线路的最小运行间隔分别设置为 ${110}\mathrm{\;s}$ 、 ${120}\mathrm{\;s}$ 和 ${120}\mathrm{\;s}$ 。区间运行时间在初始值前后 ${20}\mathrm{\;s}$ 范围内浮动。各换乘站的乘客换乘需求量如表 1 所示。使用 ALM 对案例求解的参数设定如表 2 所示。每次迭代用模拟退火求解, 模拟退火参数如表 3 所示。模型平均迭代约 129 次得到最优解。迭代次数分布见图 3 。

以其中一次为例, 迭代次数 316 次。在得到最优解的最后一次迭代中, $\lambda$ 和 $\mu$ 参数取值如表 4 所示。

对最终找到最优解的一次迭代使用真机测试。在第 371 圈找到原问题的最优解,一圈运行时间是 ${10.91\mu }\mathrm{s}$ , 量子计算机在 $4\mathrm{\;{ms}}$ 求到最优解。

相比模拟退火算法, CIM 真机在求解的过程中可以更快地找到原问题的最优解。对最后一次迭代对应的问题分别用 CIM 和模拟退火求解 100 次, 其中最快找到原问题最优解的哈密顿量演化对比如图 4 所示。

算例模型的时间相关参数以 ${10}\mathrm{\;s}$ 为单位,1号线、 4 号线、 5 号线的初始站到达时间分别设置为 100、200、 300 个时间单位。对于 CIM 的求解结果可以验证, 在换乘站 1217,1 号线到达时间为 369 个时间单位,出发时间为 375 个时间单位； 4 号线到达时间为 292 个时间单位,出发时间为 295 个时间单位,乘客从 4 号线可以成功换乘至1号线。在换乘站167,1号线到达时间为 438 个时间单位,出发时间为 444 个时间单位； 5 号线到达时间为 365 个时间单位, 出发时间为 368 个时间单位,乘客从 5 号线可以成功换乘至 1 号线。列车在换乘站的运行和停站时间如表 5 所示。

量子计算与商业求解器 Gurobi 计算效率对比如表 6 所示。Gurobi 在 ${0.3}\mathrm{\;s}$ 内得到了模型(10)的最优解, 相比之下,量子计算方法的单次迭代可以在更短时间内得到最优解, 平均迭代 129 次能够找到最优解, 则期望的求解时间为 $4\mathrm{{ms}}* {129}= {0.516}\mathrm{\;s}$ ,在这个问题上的总体计算时间略长于原整数规划问题的求解器求解。进一步,比较使用 Gurobi 和量子计算方法来求解转换后的 QUBO 模型,可以发现 Gurobi 需要接近 ${102}\mathrm{\;s}$ 才能搜索到最优解,而 CIM 方法仅用 0.516 s 就可以完成求解, 说明当模型规模变大时 CIM 方法更有效率。

6 结论与展望

收起

目前轨道交通领域多使用传统的优化算法以及商业解法器进行求解。这些算法和求解器都是基于 CPU/ GPU 等经典计算机研发的, 而量子计算机利用了量子系统的物理能量演化实现优化计算, 两种计算机的实现原理不同导致目前的优化模型和算法无法直接平移到量子计算机上进行使用。本文对现有数学模型进行重构并转换到量子模型, 进一步开发对应的量子算法来实现优化问题的求解, 从而验证了应用量子计算解决复杂网络优化问题的可行性。

6.1 结论

1) 以最小化末班车换乘失败乘客人数为优化目标, 构建了面向末班车衔接的混合整数线性规划模型。将原始模型重构为计算规模更小的两阶段模型, 并将第一阶段优化模型转化为 QUBO 模型, 提出了面向量子计算的模型重构方法。

2) 基于 QUBO 模型完成了量子计算算法开发和真机实测, 从而率先验证了量子计算用于轨道交通优化问题的可行性。考虑到算法具有一定的通用性, 这意味着一旦量子计算机硬件成熟, 本方法为应用于更大规模和复杂的问题提供了技术支撑。

6.2 展望

在未来的研究中, 可以进一步把乘客换乘路径和换乘站的选择优化纳入到末班车时刻表衔接模型中, 使模型能够更准确地识别不同时间段内的换乘需求, 并基于此制定更合理的末班车时刻表衔接方案。

此外, 受当今量子计算机的硬件规模限制, 无法进行更大规模的算例验证。考虑到量子计算的原理, 随着问题规模的增加, 求解速度优势就会逐步体现出来, 考虑到量子计算时间的稳定性, 应用量子计算解决轨道交通网络优化问题的算力优势将会不断显现。

基金

收起

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

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

米保伟, 王术明, 张强. 城市轨道交通工程安全监控平台建设及应用[J]. 都市快轨交通, 2023, 36(3): 10-15.

Baowei

, WANG

Shuming

, ZHANG

Qiang

. Construction and application of safety risk monitoring platform for urban rail transit projects[J]. Urban rapid rail transit, 2023, 36(3): 10-15.

[2]

侯秀芳, 冯晨, 左超, 等. 2022年中国内地城市轨道交通线路概况[J]. 都市快轨交通, 2023, 36(1): 9-13.

HOU

Xiufang

, FENG

Chen

, ZUO

Chao

, et al. Statistical analysis of urban rail transit in Chinese mainland in 2022[J]. Urban rapid rail transit, 2023, 36(1): 9-13.

[3]

CHEN

Yao

, MAO

Baohua

, BAI

Yun

, et al . Timetable synchronization of last trains for urban rail networks with maximum accessibility[J]. Transportation research part C: emerging technologies, 2019, 99: 110-129.

[4]

GUO

Xin

, WU

Jianjun

, SUN

Huijun

, et al . Scheduling synchronization in urban rail transit networks: trade-offs between transfer passenger and last train operation[J]. Transportation research part A: policy and practice, 2020, 138: 463-490.

[5]

ZHANG

Quan

, LI

Xuan

, YAN

Tao

, et al . Last train time-tabling optimization for minimizing passenger transfer failures in urban rail transit networks: a time period based approach[J]. Physica A: statistical mechanics and its applications, 2022, 605: 128071.

[6]

郑亚晶, 李耀辉, 靳文舟. 考虑换乘客流的城市轨道交通网络末班车衔接优化研究[J]. 华南理工大学学报(自然科学版), 2022, 50(5): 32-39.

ZHENG

Yajing

, LI

Yaohui

, JIN

Wenzhou

. Connection scheme optimization of last trains of urban mass transit network based on considering the transfer passengers[J]. Journal of South China University of Technology (Natural Science Edition), 2022, 50(5): 32-39.

[7]

袁振洲, 魏来, 吴玥琳, 等. 基于差异化换乘感知的轨道交通末班车衔接优化[J]. 北京交通大学学报, 2020, 44(1): 12-19.

YUAN

Zhenzhou

, WEI

Lai

, WU

Yuelin

, et al. Connecting optimization of last train in rail transit based on differential transfer perception[J]. Journal of Beijing Jiaotong University, 2020, 44(1): 12-19.

[8]

卢亚菡, 杨凯, 杨立兴, 等. 基于分布鲁棒优化的城市轨道交通网络末班车衔接研究[J]. 控制与决策, 2023, 38(1): 248-256.

Yahan

, YANG

Kai

, YANG

Lixing

, et al. Distributionally robust optimization for the last-train connection planning problem in urban rail transit networks[J]. Control and decision, 2023, 38(1): 248-256.

[9]

WANG

Zhe

, MARANDI

, WEN

Kai

, et al . Coherent Ising machine based on degenerate optical parametric oscillators[J]. Physical review A, 2013, 88(6): 063853.

[10]

HONJO

, SONOBE

, INABA

, et al . 100,000-spin coherent Ising machine[J]. Science advances, 2021, 7(40 ): eabh0952 .

[11]

YAMAMOTO

, AIHARA

, LELEU

, et al . Coherent Ising machines-optical neural networks operating at the quantum limit[J]. NPJ quantum information, 2017, 3: 49.

2024年第37卷第2期

PDF下载

381

157

引用本文

BibTeX

文章信息

doi: 10.3969/j.issn.1672-6073.2024.02.020

接收时间：2023-09-04
首发时间：2025-07-09

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2023-09-04
修回日期：2024-01-05

基金

国家自然科学基金(U2368204, 62073024)

中国国家铁路集团有限公司科技研究开发计划(P2022X013)

作者信息

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

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

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

通讯作者:

王悉，男，博士，副教授，主要从事轨道交通列车运行控制与优化研究，xwang@bjtu.edu.cn

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/dskgjt/CN/10.3969/j.issn.1672-6073.2024.02.020

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

换乘站	编号	换乘方式	换乘数量/人次
西单	1217	1 号线换乘 4 号线	100
西单	1217	4 号线换乘 1 号线	150
东单	167	1 号线换乘 5 号线	30
东单	167	5 号线换乘 1 号线	80

换乘站

编号

换乘方式

换乘数量/人次

西单

1217

1 号线换乘 4 号线

100

西单

1217

4 号线换乘 1 号线

150

东单

167

1 号线换乘 5 号线

东单

167

5 号线换乘 1 号线

参数	取值
初始 $\lambda$	1.0 + rand(-10, 10)
初始 $\mu$	1.0
增加系数 $\rho$	1.005
最大迭代次数	1000

参数

取值

初始 $\lambda$

1.0 + rand(-10, 10)

初始 $\mu$

1.0

增加系数 $\rho$

1.005

最大迭代次数

1000

参数	取值
初始温度	1000
降温系数	0.99
最低温度	0.001
每个温度迭代次数	10

参数

取值

初始温度

1000

降温系数

0.99

最低温度

0.001

每个温度迭代次数

参数	换乘站	线路	换乘线	取值
$\lambda$	1217	4 号线	-	533.1
${\lambda 1}$	1217	1 号线	4 号线	3.0
${\lambda 1}$	1217	1 号线	5 号线	-7.0
${\lambda 1}$	167	4 号线	1 号线	4.0
${\lambda 1}$	167	5 号线	1 号线	-8.0
${\lambda 2}$	1217	1 号线	4 号线	-3.0
${\lambda 2}$	1217	1 号线	5 号线	2.0
λ2	167	4 号线	1 号线	10.0
${\lambda 2}$	167	5 号线	1 号线	4.0
$\mu$	-	-	-	4.835 9

参数

换乘站

线路

换乘线

取值

$\lambda$

1217

4 号线

533.1

${\lambda 1}$

1217

1 号线

4 号线

3.0

${\lambda 1}$

1217

1 号线

5 号线

-7.0

${\lambda 1}$

167

4 号线

1 号线

4.0

${\lambda 1}$

167

5 号线

1 号线

-8.0

${\lambda 2}$

1217

1 号线

4 号线

-3.0

${\lambda 2}$

1217

1 号线

5 号线

λ2

167

4 号线

1 号线

10.0

${\lambda 2}$

167

5 号线

1 号线

$\mu$

4.835 9

变量	线路	换乘/始发站	最优解/(10s)
$R$	1	1217	263
$R$	1	167	63
$R$	4	1217	266
$R$	5	167	62
$S$	1	1217	6
$S$	1	167	6
$S$	1	1	6
$S$	4	1217	3
$S$	4	1	6
$S$	5	167	3
$S$	5	1	3

变量

线路

换乘/始发站

最优解/(10s)

$R$

1217

263

$R$

167

$R$

1217

266

$R$

167

$S$

1217

$S$

167

$S$

1217

$S$

167

$S$

求解模型	求解方法	求解时间/s	目标函数
原整数规划模型	Gurobi	0.3	130
QUBO 模型	Gurobi	102	130
简化模型 ALM 求解	CIM	0.516	130

求解模型

求解方法

求解时间/s

目标函数

原整数规划模型

Gurobi

0.3

130

QUBO 模型

Gurobi

102

130

简化模型 ALM 求解

CIM

0.516

130