基于量子計(jì)算的靈活編組列車大小交路混合運(yùn)行優(yōu)化方法

摘要：靈活編組模式下列車時(shí)刻表和大小交路策略的聯(lián)合優(yōu)化問題受到列車時(shí)刻表、乘客動(dòng)態(tài)方程和列車靈活編組等相關(guān)條件制約，各約束相互耦合增加了問題的復(fù)雜性和計(jì)算求解的難度，傳統(tǒng)優(yōu)化方法求解該問題將變得較為困難。本研究將量子計(jì)算應(yīng)用于該問題，以最小化線路上所有車站的滯留乘客數(shù)量為目標(biāo)，建立了混合整數(shù)非線性規(guī)劃模型，設(shè)計(jì)數(shù)值實(shí)驗(yàn)并利用相干伊辛機(jī)真機(jī)對模型進(jìn)行求解。結(jié)果表明，相干伊辛機(jī)真機(jī)在運(yùn)行效率和優(yōu)化性能上相比較于其他經(jīng)典算法具有明顯的優(yōu)勢。

關(guān)鍵詞：城市軌道交通；靈活編組；量子計(jì)算；大小交路；時(shí)刻表優(yōu)化

中圖分類號(hào)：U298.5文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1002-4026（2024）06-0094-10

隨著近年來城市規(guī)模的快速增長，城市軌道交通系統(tǒng)面臨著一些新的問題，其中之一就是如何更好地匹配乘客的動(dòng)態(tài)出行需求。由于客流需求在空間和時(shí)間維度上具有明顯的不均衡性，在早高峰時(shí)段，一些特定車站的乘客需求總是過飽和，導(dǎo)致部分乘客滯留在這些車站，而其他車站的乘客需求較少，易造成運(yùn)力資源的浪費(fèi)。為了進(jìn)一步提高城市軌道交通的服務(wù)質(zhì)量，降低運(yùn)營成本，以大小交路混合運(yùn)行和列車靈活編組為代表的動(dòng)態(tài)運(yùn)行調(diào)整策略成為近年來研究的熱點(diǎn)[1-3]。

列車大小交路混合運(yùn)行模式，指的是在既有的大交路運(yùn)行的基礎(chǔ)上，在客流需求較大的區(qū)段增加小交路的列車服務(wù)，執(zhí)行小交路服務(wù)的列車僅在這一區(qū)段內(nèi)往返運(yùn)行。該模式可以有效地滿足乘客需求的時(shí)空不均衡特征，因此許多學(xué)者對列車大小交路策略展開了研究[4-5]。Yang等[6]建立了列車時(shí)刻表優(yōu)化模型，結(jié)合一種新穎的靈活大小交路運(yùn)行模式，最小化乘客總出行時(shí)間。Zhu等[7]在考慮乘客到達(dá)的不確定性基礎(chǔ)上，構(gòu)建了結(jié)合列車時(shí)刻表和大小交路策略的優(yōu)化模型。列車靈活編組策略指的是線路上的列車可以根據(jù)動(dòng)態(tài)的乘客需求靈活調(diào)整組成列車的編隊(duì)數(shù)量，從而更好地匹配不平衡的乘客需求。近年來，如何優(yōu)化列車靈活編組策略成為城市軌道交通的熱門研究課題[8-9]。Pan等[10]提出基于列車靈活編組模式的聯(lián)合優(yōu)化模型，同時(shí)優(yōu)化列車時(shí)刻表和車輛循環(huán)計(jì)劃以更好地匹配乘客需求和提高運(yùn)輸能力。Zhou等[11]提出了一個(gè)混合整數(shù)線性規(guī)劃（MILP）模型來共同優(yōu)化列車時(shí)刻表和車輛循環(huán)計(jì)劃，其中特別考慮了靈活的列車編組模式，并且開發(fā)了一種基于可變鄰域搜索的啟發(fā)式算法來求解。

列車靈活編組與大小交路進(jìn)行聯(lián)合優(yōu)化問題中各約束條件間的相互耦合，傳統(tǒng)的優(yōu)化求解方法需要先將0-1變量進(jìn)行線性化后再進(jìn)行求解，計(jì)算的復(fù)雜性大大增加。因此需要使用更高效的計(jì)算方法對模型進(jìn)行求解。量子計(jì)算是一種利用量子力學(xué)原理的計(jì)算方法，使用量子比特（qubit）來進(jìn)行信息存儲(chǔ)和處理。與經(jīng)典計(jì)算機(jī)使用的經(jīng)典比特（bit）只能處于0或1的狀態(tài)不同，量子比特可以同時(shí)處于0和1的疊加態(tài)，這使得量子計(jì)算機(jī)在處理特定問題時(shí)具有獨(dú)特的優(yōu)勢。相干伊辛機(jī)（coherent Ising machine， CIM）是一種使用光量子的量子計(jì)算方案，是目前的研究熱點(diǎn)之一[12]。CIM利用相干光場的演化來模擬伊辛模型，通常用于解決組合優(yōu)化問題，能夠通過量子糾纏和量子并行性質(zhì)來更高效地搜索解空間。Atsushi等[13]研究了相干伊辛機(jī)在組合優(yōu)化問題中的原理與實(shí)現(xiàn)，并通過數(shù)值實(shí)驗(yàn)證實(shí)了相關(guān)的理論。文凱等[14]將光量子計(jì)算應(yīng)用在金融領(lǐng)域中，研究量子計(jì)算在信用評(píng)分場景下的應(yīng)用，改進(jìn)了金融數(shù)據(jù)預(yù)處理的方式，創(chuàng)新性地使用量子計(jì)算機(jī)來求解特征選擇的二次無約束二值優(yōu)化模型。

綜上可以看出，研究人員針對大小交路混合運(yùn)行模式下的列車時(shí)刻表優(yōu)化問題和面向靈活編組的時(shí)刻表優(yōu)化問題已經(jīng)展開了廣泛的研究[15]。但其使用的求解方法多為經(jīng)典的優(yōu)化求解方法，經(jīng)典算法通常需要較長的運(yùn)行時(shí)間，并且還會(huì)出現(xiàn)無法產(chǎn)生最優(yōu)解的情況。為了解決以上問題，本文引入量子計(jì)算的求解方法，將原模型轉(zhuǎn)化為二次無約束二值優(yōu)化模型，設(shè)計(jì)數(shù)值實(shí)驗(yàn)并利用相干伊辛機(jī)真機(jī)對問題進(jìn)行求解，驗(yàn)證該方法的可用性和高效性。

1問題描述

本文主要研究由2I個(gè)站點(diǎn)組成的城市軌道交通系統(tǒng)中的雙向線路，城市軌道交通線路的布局和列車服務(wù)方式如圖1所示，上行方向的始發(fā)站與終點(diǎn)站分別為1站和I站，下行方向始發(fā)站與終點(diǎn)站分別為I+1與2I站。小交路區(qū)域?yàn)?站到a站與b站到2I站。將車站1與車站a間的車站定義為車站集合I1，運(yùn)行在此區(qū)域的列車服務(wù)集合定義為K1，k1為列車服務(wù)索引；將車站a+1與車站b－1間的車站定義為車站集合I2，運(yùn)行在此區(qū)域的列車服務(wù)集合定義為K2，k2為列車服務(wù)索引；將車站b與車站2I間的車站定義為車站集合I3，運(yùn)行在此區(qū)域的列車服務(wù)集合定義為K3，k3為列車服務(wù)索引。列車在地鐵線路的始發(fā)站和終點(diǎn)站之間運(yùn)行并在車站為乘客提供出行需求，稱作一個(gè)列車服務(wù)，每個(gè)列車服務(wù)都需要由一個(gè)列車承擔(dān)，不同的列車服務(wù)可以由同一個(gè)列車承擔(dān)。

在通過a站之后列車根據(jù)客流情況可以選擇兩種路線執(zhí)行服務(wù)，一是小交路，即所有的車隊(duì)不解編全部駛向車站b，如圖1（a） 所示；二是列車進(jìn)行解編，解編后的前一車隊(duì)行駛向車站a+1，后一車隊(duì)行駛向車站b，如圖1（b）所示。實(shí)際運(yùn)行過程中，解編和不解編的情況會(huì)同時(shí)出現(xiàn)，此時(shí)的列車運(yùn)行狀態(tài)，如圖1（c）所示。默認(rèn)始發(fā)的列車服務(wù)由兩個(gè)車隊(duì)組成，解編之后成為兩個(gè)單獨(dú)的車隊(duì)，并標(biāo)識(shí)為兩個(gè)列車服務(wù)，列車編組方式如圖2所示。

根據(jù)以上分析，列車根據(jù)乘客的需求來決定其是否需要解編，并確定列車服務(wù)的區(qū)域。最終目標(biāo)是將客流與有限的列車資源相匹配，提高乘客滿意度，同時(shí)減少不必要的列車資源浪費(fèi)，以提高列車的服務(wù)水平。研究中已知的參數(shù)有：運(yùn)營中的列車數(shù)量、線路中的車站數(shù)量、單個(gè)車隊(duì)的最大通過能力、每個(gè)車站的乘客到達(dá)率、大小交路的區(qū)域劃分，以及相鄰車站之間的運(yùn)行時(shí)間。為建立所研究問題的數(shù)學(xué)模型，本文做了如下假設(shè)：

（1）線路上任何一個(gè)車站都不存在越行行為，每個(gè)車隊(duì)的運(yùn)力是相同的，與是否需要解編、大小交路運(yùn)行無關(guān)。

（2）乘客總是選擇直達(dá)目的地車站的列車服務(wù)，而不是在不同類型的列車服務(wù)之間轉(zhuǎn)乘。

（3）列車只允許在a站之后的道岔區(qū)域進(jìn)行解編操作。列車從a站發(fā)車后，只有上述兩種選擇，不存在運(yùn)行路線為大交路而不解編的情況。

（4）允許列車上的乘客根據(jù)列車將要執(zhí)行解編策略在列車內(nèi)移動(dòng)，以完成其出行需求。

2數(shù)學(xué)模型

2.1與時(shí)刻表相關(guān)的約束

首先建立與列車運(yùn)行相關(guān)約束，

ti，k=ti－1，k+ri－1+xi，k，i∈I1，k∈K1 or i∈I2，k∈K2 or i∈I3，k∈K3 ，（1）

其中，ti，k表示列車服務(wù)k在i站的發(fā)車時(shí)間，ri－1表示列車服務(wù)在i－1站與i站之間的運(yùn)行時(shí)間，xi，k表示列車服務(wù)k在i站的停站時(shí)間。特別地，對于在a+1站的列車服務(wù)的發(fā)車時(shí)間可以通過列車服務(wù)k2到達(dá)a+1站的時(shí)間與在其在a+1站停留的時(shí)間之和得到：

ta+1，k2=da+1，k2+xa+1，k2，k2∈K2 ，（2）

同理，可以表示b站的發(fā)車時(shí)間：

tb，k3=db，k3+xb，k3，k3∈K3 ， （3）

定義變量di，k表示列車服務(wù)k到達(dá)i站的時(shí)間，可以由公式（4）表示：

di，k=ti－1，k+ri－1，i∈I1，k∈K1 or i∈I2，k∈K2 or i∈I3，k∈K3，（4）

即列車服務(wù)k到達(dá)i站的時(shí)間由其在i－1站的發(fā)車時(shí)間以及在i－1站到i站的站間運(yùn)行時(shí)間相加得到，常量ri－1表示i－1站到i站的運(yùn)行時(shí)間。

特別地，還需要增加一些不同服務(wù)之間的銜接約束，來表明服務(wù)k1，k2，k3之間的列車承接關(guān)系。由于列車服務(wù)k2都承接自列車服務(wù)k1，因此其在a+1站的到站時(shí)間表示如下：

da+1，k2=ta，k1+ra，k1∈K1，k2∈K2，（5）

若列車服務(wù)k3承接自k1，則其到達(dá)b站時(shí)間為其承接的列車服務(wù)k1在a站的發(fā)車時(shí)間與列車在a站與b站之間的運(yùn)行時(shí)間Ta，b之和，Ta，b設(shè)置為常量。這個(gè)過程表示為：

db，k3=ta，k1+Ta，b，if ξk1，k3=1，k1∈K1，k3∈K3，（6）

其中，ξk1，k3表示列車服務(wù)k1與k3的承接關(guān)系，為1即為承接。若列車服務(wù)k3承接自k2列車服務(wù)，可以通過公式表示到站時(shí)間：

db，k3=tb－1，k2+rb－1，if ξk2，k3=1，k2∈K2，k3∈K3，（7）

其中，rb－1表示列車在車站b－1到車站b之間的運(yùn)行時(shí)間。

此外，相鄰列車在實(shí)際運(yùn)行過程中應(yīng)滿足最大和最小追蹤間隔，以保證乘客滿意度與運(yùn)行安全。使用thmin表示最小的追蹤間隔，thmax表示最大的追蹤間隔。相鄰列車服務(wù)間的追蹤間隔應(yīng)該滿足：

thmin≤ti，k－ti，k－1≤thmax，i∈I1，k，k－1∈K1 or i∈I2，k∈K2 or i∈I3，k∈K3。（8）

2.2與乘客動(dòng)態(tài)方程相關(guān)約束

基于列車時(shí)刻表建立動(dòng)態(tài)客流模型，在k－1與k列車服務(wù)之間到達(dá)i站的乘客數(shù)量與相鄰兩個(gè)服務(wù)的時(shí)間間隔以及當(dāng)前車站的乘客到達(dá)率有關(guān)，表示為：

ai，k=μi，kti，k－ti，k－1，i∈I1，k∈K1 or i∈I2，k∈K2 or i∈I3，k∈K3，（9）

其中，μi，k表示在列車服務(wù)k－1發(fā)車與列車服務(wù)k發(fā)車期間，i站的乘客到達(dá)率。定義wi，k表示在i站等待列車服務(wù)k的乘客數(shù)量，該變量可以表示為：

wi，k=si，k－1+ai，k，i∈I1，k∈K1 or i∈I2，k∈K2 or i∈I3，k∈K3。（10）

等待乘客由兩部分構(gòu)成，一部分是在k－1服務(wù)離開之后k服務(wù)到達(dá)之前這段時(shí)間到達(dá)i站的乘客ai，k，第二部分為在高峰時(shí)期，除到站乘客外，等待乘客還包括因沒有列車服務(wù)通過車站或運(yùn)力有限而未能成功登上前一趟列車的滯留乘客，定義為si，k，特別地，線路的終點(diǎn)站沒有等待乘客，即wI，k=w2I，k=0。滯留乘客用以下公式表示：

si，k=wi，k－gi，k，i∈I1，k∈K1 or i∈I2，k∈K2 or i∈I3，k∈K3，（11）

其中，gi，k表示在i站成功登上列車服務(wù)k的乘客數(shù)量。定義pi，k表示在列車服務(wù)k離開i站時(shí)，列車上的乘客數(shù)量，通過乘客上下車的行為定義車內(nèi)的乘客動(dòng)態(tài)變化過程可以表示為：

pi，k=pi－1，k+gi，k－li，k，i∈I1，k∈K1 or i∈I2，k∈K2 or i∈I3，k∈K3。 （12）

成功登車的乘客數(shù)量與列車服務(wù)k是否服務(wù)i站和到達(dá)i站時(shí)列車的剩余運(yùn)力兩個(gè)因素有關(guān)。這個(gè)過程可以表示為：

gi，k=minwi，k，εkC－pi－1，k+li，kαi，k，i∈I1，k∈K1 or i∈I2，k∈K2 or i∈I3，k∈K3，（13）

其中，εk表示組成k列車服務(wù)的車隊(duì)數(shù)量，C表示單個(gè)車隊(duì)的最大運(yùn)力，整個(gè)服務(wù)的最大運(yùn)力表示為εkC，那么可以得出εkC－pi－1，k+li，k表示在i站時(shí)列車服務(wù)k的剩余運(yùn)力情況。特別地，線路的終點(diǎn)站沒有乘客上車，即gI，k=g2I，k=0。其中，αi，k是一個(gè)二進(jìn)制變量，表示列車服務(wù)k是否通過i站，通過i站則表示能夠?yàn)閕站提供服務(wù)。具體可以表示為：

其中，變量li，k表示列車服務(wù)k停留在i站時(shí)下車的乘客數(shù)量，并且假設(shè)該數(shù)量與當(dāng)前列車服務(wù)上的乘客數(shù)量成一定的比例，使用λi，k來表示這一比例。與成功登車乘客的表述類似，對i站下車的乘客數(shù)量的計(jì)算也需要考慮列車是否服務(wù)于該站，表述如下：

li，k=λi，kpi－1，kαi，k，i∈I1，k∈K1 or i∈I2，k∈K2 or i∈I3，k∈K3。 （15）

2.3大小交路與列車編組相關(guān)的約束

建立解編和交路運(yùn)行相關(guān)約束。定義二元邏輯變量γk，用來表示列車服務(wù)k是否解編：

當(dāng)列車在道岔前發(fā)生解編時(shí)，組成列車服務(wù)的車隊(duì)數(shù)會(huì)相應(yīng)的發(fā)生變化，解編后的車隊(duì)數(shù)量為1，不解編為2，車隊(duì)數(shù)量計(jì)算遵循以下公式：

根據(jù)本文研究的場景，列車服務(wù)k1的車隊(duì)數(shù)量恒為2；列車服務(wù)k2的車隊(duì)數(shù)量與其是否解編有關(guān)，若解編則車隊(duì)數(shù)量為1，若不解編則表示沒有列車執(zhí)行大交路服務(wù)，此時(shí)車隊(duì)數(shù)量為0；列車服務(wù)k3的車隊(duì)數(shù)量需根據(jù)其來承接的服務(wù)進(jìn)行區(qū)分，若其承接于k2則車隊(duì)數(shù)與所承接的列車服務(wù)k2的車隊(duì)數(shù)量保持一致，若其承接自列車服務(wù)k1，則其車隊(duì)數(shù)量與所承接的k1是否解編有關(guān)，解編情況下車隊(duì)數(shù)量為1，不解編情況下車隊(duì)數(shù)量為2。

根據(jù)定義的站點(diǎn)的區(qū)域變量以及列車服務(wù)運(yùn)行的區(qū)段情況，可以表示列車在每個(gè)車站的?？壳闆r，即站點(diǎn)是否有列車服務(wù)經(jīng)過：

區(qū)域I1恒有列車執(zhí)行服務(wù)，即αi，k1=1；區(qū)域I2是否有列車服務(wù)與列車是否解編一致，若解編，則αi，k2=1，否則為0；對于區(qū)域I3，若其服務(wù)承接于k1則肯定有列車服務(wù)經(jīng)過，此時(shí)αi，k3=1，若其列車服承接于k2，則是否有服務(wù)情況與k2保持一致，即αi，k3=αi，k2=γk。

2.4目標(biāo)函數(shù)

在城市軌道交通系統(tǒng)中，各站點(diǎn)滯留乘客總數(shù)是評(píng)價(jià)運(yùn)營方案服務(wù)質(zhì)量的重要指標(biāo)。為了提高乘客滿意度，應(yīng)盡量減少每個(gè)車站的滯留乘客數(shù)量。當(dāng)線路客流較大時(shí)，可通過減少相鄰車站之間的發(fā)車間隔來增加列車發(fā)車次數(shù)。對于大交路區(qū)域內(nèi)的車站，可以通過確定列車是否執(zhí)行小交路區(qū)域的服務(wù)來平衡客流，以減少車站的滯留乘客數(shù)量。目標(biāo)函數(shù)可以表示為最小化線路上所有車站的滯留乘客之和：

3求解方法

3.1場景簡化

在這一部分，為使用量子計(jì)算的方式對模型進(jìn)行求解，需對研究場景進(jìn)行簡化，并對原模型進(jìn)行轉(zhuǎn)化，將其轉(zhuǎn)為（quadratic unconstrained binary optimization， QUBO）模型。在保留大小交路與靈活編組特征的前提下，將原場景簡化為上下行各3個(gè)站點(diǎn)，其中小交路區(qū)域包括a－1，a，b，b+1車站。從a－1站發(fā)出的列車服務(wù)數(shù)量為2，列車可在a站根據(jù)客流需求決定是否編組，以盡可能減少線路上的滯留乘客。簡化后的線路布局如圖3所示。車站a－1到a中的兩次列車服務(wù)記為k=1，k=2。車站a+1和b－1有兩次可能的列車服務(wù)，分別記為k=1s，k=2s。從車站b到b+1有4次可能的列車服務(wù)k=1，k=2，k=1s，k=2s，假設(shè)4列車到達(dá)b站的先后順序?yàn)閗=1，k=2，k=1s，k=2s。

3.2滯留人數(shù)分析

為更清晰表述列車編組策略及大小交路運(yùn)行方案對滯留乘客的影響，本小節(jié)結(jié)合3.1節(jié)的簡化場景對各站的滯留乘客作進(jìn)一步說明。

3.2.1b－1站的滯留人數(shù)

b－1站的滯留人數(shù)在各個(gè)車次到站時(shí)可以表示為：如果1車不解編，則為該車站的到達(dá)人數(shù); 如果1車解編，有一個(gè)車隊(duì)提供服務(wù)，滯留人數(shù)為當(dāng)前站臺(tái)人數(shù)（即自開始服務(wù)時(shí)間的到達(dá)人數(shù)）減去單車隊(duì)容量：

sb－1，1s=（1－γ1）×Ab－1，1s，prev+γ1×max（0，Ab－1，1s，prev－C），（20）

其中，各站開始服務(wù)時(shí)間對應(yīng)的索引為prev， Ab－1，1s，prev表示從列車服務(wù)k=1s發(fā)車到prev發(fā)車期間車站b－1的到達(dá)人數(shù)。

如果2車不解編，滯留人數(shù)為上一列車的滯留人數(shù)加上從列車服務(wù)k=1s到k=2s時(shí)間段內(nèi)到達(dá)的人數(shù)；如果2車解編，滯留人數(shù)為上一列車的滯留人數(shù)加上從k=1s到k=2s時(shí)間段內(nèi)到達(dá)的人數(shù)減去單車隊(duì)容量（取滯留人數(shù)≥0的部分）：

sb－1，1s=（1－γ2）×（sb－1，1s+Ab－1，2s，1s）+γ2×max（0，sb－1，1sAb－1，2s，1s－C）。（21）

3.2.2b站的滯留人數(shù)

在各列車到站時(shí)b站的滯留人數(shù)可以表示為：如果1車不解編，有兩個(gè)車隊(duì)的容量容納當(dāng)前b站滯留乘客（初始到達(dá)乘客），如果滯留乘客小于容量，則當(dāng)次車離開后滯留人數(shù)為0；如果1車解編，有一車隊(duì)的容量，如果滯留乘客小于列車容量，則該列車離開后滯留人數(shù)為0：

sb，1=γ1×max（0，Ab，1，prev－C）+1－γ1×max（0，Ab，1，prev－2C）。（22）

如果2車不解編，有兩隊(duì)車的容量容納當(dāng)前b站滯留乘客（上一列車滯留乘客加到達(dá)乘客）；如果2車解編，有一隊(duì)車的容量，如果滯留乘客小于列車容量，則當(dāng)次車離開后滯留乘客為0：

sb，2=max（0，sb，1+Ab，2，1－C×（2－γ2））。（23）

若1車不解編，滯留乘客為上一列車服務(wù)的滯留乘客加上從列車服務(wù)k=1s到該列車服務(wù)間的到達(dá)乘客；如果1車解編，為當(dāng)前站臺(tái)人數(shù)減去車內(nèi)的容量（上一站乘客上車后的車內(nèi)剩余容量加上b站下車人數(shù)）：

sb，1s=sb，2+Ab，1s，2－γ1×（max（C－Ab－1，1s，prev，0）+min（C，Ab－1，1s，prev）×DR［b］） ，（24）

其中DR[b]為在站點(diǎn)b下車比例。

如果2車不解編，滯留乘客為上一列車服務(wù)k=1s的滯留乘客加上從k=1s到k=2s期間的到達(dá)乘客；如果2車解編，滯留乘客為當(dāng)前站臺(tái)人數(shù)減去車內(nèi)的容量（上一站乘客上車后的車內(nèi)剩余容量加上b站下車人數(shù)）：

sb，2s=sb，1s+Ab，2s，1s－γ2×（max（C－（Ab－1，2s，1s+sb－1，1s），0）+（C－max（C－（Ab－1，2s，1s+sb－1，1s），0））×DR［b］）。 （25）

綜上，總的滯留乘客即為線路上各站各列車服務(wù)滯留乘客之和。

3.3模型轉(zhuǎn)化

為使用量子計(jì)算的方式對模型進(jìn)行求解，需對原模型進(jìn)行一定的轉(zhuǎn)化。首先是將原模型轉(zhuǎn)化為QUBO模型，對模型進(jìn)行一些預(yù)求解操作以降低模型的復(fù)雜度。以sb，2s為例，使用max（C－（Ab－1，2s，1s+sb－1，1s），0）表示列車剩余容量，取y∈0，1，因此：

u=y×（C－（Ab－1，2s，1s+sb－1，1s）），（26）

sb，2s=sb，1s+Ab，2s，1s－γ2（u+（C－u）×DR［b］）。 （27）

如果uup≤0，則可以令y=0，此時(shí)u恒為0；如果ulow≥0，則可令y=1，此時(shí)u為一線性項(xiàng)，sb，2s次數(shù)為2；如果ulowlt;0lt;uup，則添加以下約束：

ulow×（1－y）≤C－（Ab－1，2s，1s+sb－1，1s）≤uup×y。 （28）

此時(shí)sb，2s的表達(dá)式中次數(shù)為3，需要1個(gè)比特降階。由此即完成sb，2s的QUBO模型轉(zhuǎn)化，其他站點(diǎn)及列車的滯留乘客數(shù)QUBO轉(zhuǎn)化如以上步驟所示。

進(jìn)一步，將QUBO轉(zhuǎn)化為伊辛模型，以便能直接使用相干伊辛機(jī)真機(jī)CIM對模型求解。CIM為基于簡并光學(xué)參量振蕩器的光量子計(jì)算機(jī)，可以用來處理伊辛模型。伊辛模型描述了物質(zhì)相變的隨機(jī)過程，其數(shù)學(xué)形式為：

其中，σ為待求自旋變量，取值為{-1；+1}，H為哈密頓量，J和μ分別為二次型系數(shù)和線性項(xiàng)系數(shù)，是已知量。QUBO模型便于建模，伊辛模型便于求解，通過公式即可將QUBO模型等價(jià)轉(zhuǎn)為伊辛模型以使用相干伊辛機(jī)真機(jī)求解：

4數(shù)值實(shí)驗(yàn)

根據(jù)第3節(jié)將原模型進(jìn)行轉(zhuǎn)化后，使用圖3所示的簡化后場景進(jìn)行一組數(shù)值實(shí)驗(yàn)，該實(shí)驗(yàn)中的客流特征與早高峰客流特征保持一致，以盡可能真實(shí)地模擬城市軌道交通早高峰的運(yùn)營場景。利用基于光量子計(jì)算的相干伊辛機(jī)真機(jī)求解。各站所設(shè)置的下車率、乘客到達(dá)率以及站間運(yùn)行時(shí)間如表1所示。

真機(jī)求解的結(jié)果為兩車均不解編，目標(biāo)函數(shù)值為38.4，求解時(shí)間為0.133 9 ms。根據(jù)實(shí)驗(yàn)結(jié)果，在當(dāng)前客流需求下兩車實(shí)行均不解編的運(yùn)行策略，即均執(zhí)行小交路服務(wù)，可以最小化線路上總的滯留乘客，提高了運(yùn)行效率。在圖4中繪制了CIM真機(jī)求解過程中，解的哈密頓量隨時(shí)間變化的曲線，展示了問題求解的動(dòng)態(tài)過程。曲線呈現(xiàn)出在不同時(shí)間點(diǎn)哈密頓量的變化趨勢，揭示了相干伊辛機(jī)在搜索解空間中的演化過程。實(shí)驗(yàn)結(jié)果顯示在第103圈時(shí)真機(jī)找到了最優(yōu)解，表明相干伊辛機(jī)在非常短的時(shí)間內(nèi)成功收斂到問題的最優(yōu)解。真機(jī)每圈所需的時(shí)間為1.3 μs，總體耗時(shí)為0.133 9 ms，這顯示了相干伊辛機(jī)在高效求解列車編組問題上的強(qiáng)大性能。

圖5為真機(jī)求得的最優(yōu)解的示意圖。值得說明的是，在真機(jī)實(shí)驗(yàn)中將QUBO模型最后轉(zhuǎn)換成了對應(yīng)的最大割問題。圖5中的點(diǎn)有兩種顏色，藍(lán)色和綠色，分別代表圖中的點(diǎn)被劃分到兩個(gè)集合中，即對應(yīng)的變量取值為1和0。

通過對原問題使用相干伊辛機(jī)（CIM）， Gurobi求解器， 模擬退火（simulated annealing， SA）， 禁忌搜索（Tabu） 4種算法進(jìn)行求解，在圖6中展示了各算法的運(yùn)行時(shí)間和相應(yīng)的目標(biāo)函數(shù)值（滯留人數(shù)）。結(jié)果顯示，CIM算法表現(xiàn)出極低的運(yùn)行時(shí)間（0.133 9 ms）和最優(yōu)的目標(biāo)函數(shù)值（38.4），表明其在問題求解效率和優(yōu)化性能上具有顯著優(yōu)勢。Gurobi算法雖然在目標(biāo)函數(shù)值方面表現(xiàn)一致，但運(yùn)行時(shí)間相對較高（30 ms），比CIM真機(jī)慢了224倍。SA算法展現(xiàn)了較好的目標(biāo)函數(shù)值（38.4）和最長的運(yùn)行時(shí)間（4 240.1 ms），表明其在找到解上相對耗時(shí)較長。Tabu算法在目標(biāo)函數(shù)值上表現(xiàn)最差（48），但在運(yùn)行時(shí)間上有較好的平衡（12.99 ms）。根據(jù)實(shí)驗(yàn)結(jié)果，相比較于其他經(jīng)典算法，CIM真機(jī)在運(yùn)行效率和優(yōu)化性能具有非常大的優(yōu)勢。

5總結(jié)與展望

本文將量子計(jì)算應(yīng)用于城市軌道交通中大小交路與靈活編組的運(yùn)行場景，以全線滯留乘客最少為目標(biāo)建立了聯(lián)合優(yōu)化模型，該模型綜合考慮了列車時(shí)刻表、乘客動(dòng)態(tài)方程、列車車隊(duì)數(shù)量變化和列車大小交路等約束條件。本文設(shè)計(jì)了數(shù)值實(shí)驗(yàn)來驗(yàn)證所提方法的有效性，首先對場景進(jìn)行了簡化并對模型進(jìn)行了QUBO轉(zhuǎn)化，針對簡化后的城市軌道交通運(yùn)營場景，使用基于量子計(jì)算的相干伊辛機(jī)真機(jī)進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明所構(gòu)建模型有效減少了線路上的滯留乘客，并且對量子計(jì)算與經(jīng)典算法在求解時(shí)間與目標(biāo)值兩個(gè)維度上進(jìn)行了對比，結(jié)果表明量子計(jì)算在對該問題求解的運(yùn)行效率和優(yōu)化性能方面相比較于其他經(jīng)典算法具有顯著的優(yōu)勢。

盡管量子計(jì)算從技術(shù)原理上具有巨大的潛力優(yōu)勢，但是仍然屬于一個(gè)全新的技術(shù)，受限于硬件條件，現(xiàn)有量子計(jì)算機(jī)的比特?cái)?shù)無法直接計(jì)算大規(guī)模問題。本文驗(yàn)證了量子計(jì)算解決軌道交通行業(yè)復(fù)雜優(yōu)化問題的可行性，未來隨著量子計(jì)算技術(shù)的發(fā)展，其在求解實(shí)際問題的算力優(yōu)勢將進(jìn)一步得到發(fā)揮。

參考文獻(xiàn)：

［1］XI W， HU M Y， WANG H W， et al. Formation control for virtual coupling trains with parametric uncertainty and unknown disturbances[J]. IEEE Transactions on Circuits and Systems II： Express Briefs， 2023， 70（9）： 3429-3433. DOI： 10.1109/TCSII.2023.3262511.

[2]姜嘉偉， 趙金寶， 劉文靜， 等. 基于SSA-LSTM組合模型的城市軌道交通短時(shí)客流預(yù)測[J]. 山東科學(xué)， 2023， 36（5）： 75-84. DOI： 10.3976/j.issn.1002-4026.2023.05.010.

[3]WANG X， SU S， CAO Y， et al. Robust control for dynamic train regulation in fully automatic operation system under uncertain wireless transmissions[J]. IEEE Transactions on Intelligent Transportation Systems， 2022， 23（11）： 20721-20734. DOI： 10.1109/TITS.2022.3170950.

[4]WANG X， LI S K， TANG T， et al. Event-triggered predictive control for automatic train regulation and passenger flow in metro rail systems[J]. IEEE Transactions on Intelligent Transportation Systems， 2022， 23（3）： 1782-1795. DOI： 10.1109/TITS.2020.3026755.

[5]李傳耀， 陳依婷. 自主式交通系統(tǒng)功能架構(gòu)優(yōu)化密度峰值聚類算法[J]. 山東科學(xué)， 2023， 36（2）： 93-102. DOI： 10.3976/j.issn.1002-4026.2023.02.012.

[6]YANG L Y， YAO Y， SHI H， et al. Dynamic passenger demand-oriented train scheduling optimization considering flexible short-turning strategy[J]. Journal of the Operational Research Society， 2021， 72（8）： 1707-1725. DOI： 10.1080/01605682.2020.1806745.

[7]ZHU L， LI S K， HU Y T， et al. Robust collaborative optimization for train timetabling and short-turning strategy in urban rail transit systems[J].Transportmetrica B： Transport Dynamics， 2023， 11（1）： 147-173. DOI： 10.1080/21680566.2022.2048120.

[8]WANG X， SU S， CAO Y， et al. Robust cruise control for the heavy haul train subject to disturbance and actuator saturation[J]. IEEE Transactions on Intelligent Transportation Systems， 2023， 24（8）： 8003-8013. DOI： 10.1109/TITS.2023.3264238.

[9]張儀果， 屈云超， 尹浩東， 等. 軌道交通封站條件下應(yīng)急疏散車輛路徑優(yōu)化[J]. 山東科學(xué)， 2023， 36（4）： 80-88. DOI： 10.3976/j.issn.1002-4026.2023.04.010.

[10]PAN H C， YANG L X， LIANG Z. Demand-oriented integration optimization of train timetabling and rolling stock circulation planning with flexible train compositions： a column-generation-based approach[J]. European Journal of Operational Research， 2023， 305（1）： 184-206. DOI： 10.1016/j.ejor.2022.05.039.

[11]ZHOU H S， QI J G， YANG L X， et al. Joint optimization of train timetabling and rolling stock circulation planning： a novel flexible train composition mode[J]. Transportation Research Part B： Methodological， 2022， 162： 352-385. DOI： 10.1016/j.trb.2022.06.007.

[12]XU H Z， CHEN J H， ZHANG X C， et al. High-speed train timetable optimization based on space-time network model and quantum simulator[J]. Quantum Information Processing， 2023， 22（11）： 418. DOI： 10.1007/s11128-023-04170-3.

[13]YAMAMURA A， AIHARA K， YAMAMOTO Y. Quantum model for coherent Ising machines： discrete-time measurement feedback formulation［J］. Physical Review A， 2017， 96（5）： 053834. DOI： 10.1103/physreva.96.053834.

[14]文凱，馬寅，王鵬等.基于光量子計(jì)算的信用評(píng)分特征篩選研究報(bào)告[J]. 網(wǎng)絡(luò)安全與數(shù)據(jù)治理， 2022， 41（9）： 13-18.

[15]曹若冰， 曹成鉉， 徐猛， 等. 韌性交通樞紐中突發(fā)大客流疏散優(yōu)化研究[J]. 山東科學(xué)， 2023， 36（2）： 76-84. DOI： 10.3976/j.issn.1002-4026.2023.02.010.