馬 琳 ，鄭 勇 ，金成日

（1.北京交通大學(xué) 電子信息工程學(xué)院，北京 100044；2.中國(guó)航天科工飛航技術(shù)研究院，北京 100044）

黨的十九大報(bào)告把“交通強(qiáng)國(guó)”作為建設(shè)科技強(qiáng)國(guó)的重要組成部分，指出要瞄準(zhǔn)世界科技前沿，實(shí)現(xiàn)前瞻性基礎(chǔ)研究、引領(lǐng)原創(chuàng)性成果重大突破［1］.何華武院士提出，低真空管道超高速磁懸浮鐵路是未來(lái)軌道交通的發(fā)展方向.中國(guó)工程院于2018 年正式啟動(dòng)《低真空管（隧）道磁懸浮鐵路戰(zhàn)略研究》重大咨詢(xún)項(xiàng)目，圍繞我國(guó)發(fā)展低真空管道超高速磁懸浮鐵路的戰(zhàn)略需求和定位、針對(duì)速度目標(biāo)值、真空度和合理運(yùn)距以及常導(dǎo)制式、高溫超導(dǎo)制式、電動(dòng)制式、低真空管道、車(chē)輛裝備、無(wú)線(xiàn)通信、運(yùn)行控制等關(guān)鍵技術(shù)開(kāi)展了方案研究.同期，中國(guó)航天科工公司也正式宣布啟動(dòng)最高時(shí)速4 000 km/h“超高速磁浮列車(chē)”的低真空管道交通系統(tǒng)研發(fā)項(xiàng)目［2］.低真空管道超高速磁懸浮列車(chē)作為一種利用低真空環(huán)境和超聲速外形減小空氣阻力，通過(guò)磁懸浮減小摩擦阻力實(shí)現(xiàn)超聲速運(yùn)行的管道運(yùn)輸系統(tǒng)［3］，它的研制將助力交通強(qiáng)國(guó)戰(zhàn)略的實(shí)施與推進(jìn)，對(duì)于促進(jìn)經(jīng)濟(jì)社會(huì)高質(zhì)量發(fā)展具有重大而深遠(yuǎn)的意義.

超高速磁浮列車(chē)的運(yùn)營(yíng)在效率和服務(wù)上具有更高的要求.作為衡量公眾運(yùn)輸服務(wù)滿(mǎn)意度和列車(chē)運(yùn)力資源使用情況的重要指標(biāo)，超高速磁浮的線(xiàn)路設(shè)計(jì)能力備受關(guān)注.超高速磁浮列車(chē)的運(yùn)行過(guò)程主要由車(chē)輛、牽引供電系統(tǒng)和列車(chē)運(yùn)行控制系統(tǒng)共同完成，基本運(yùn)動(dòng)采用直線(xiàn)電機(jī)控制原理，通過(guò)供電系統(tǒng)控制供電電能大小，進(jìn)而控制列車(chē)運(yùn)行，供電系統(tǒng)與列車(chē)運(yùn)行控制系統(tǒng)的關(guān)系進(jìn)一步加強(qiáng)［4］.為了降低供電系統(tǒng)的負(fù)載，保證行車(chē)安全，超高速磁浮列車(chē)一般以供電分區(qū)作為閉塞分區(qū)運(yùn)行，采用準(zhǔn)移動(dòng)閉塞模式曲線(xiàn)控車(chē)方式，每個(gè)供電分區(qū)至多只能有一列車(chē)運(yùn)行［5］.因此閉塞（供電）分區(qū)的劃分不僅是線(xiàn)路設(shè)計(jì)能力的重要影響因素之一，也與牽引供電設(shè)備成本密切相關(guān)［6］.由于供電分區(qū)的工程造價(jià)遠(yuǎn)高于輪軌交通閉塞分區(qū)的造價(jià)，設(shè)計(jì)人員期望最小的供電分區(qū)成本獲得最大的能力.因此，閉塞分區(qū)的優(yōu)化設(shè)計(jì)對(duì)指導(dǎo)超高速磁浮列車(chē)經(jīng)濟(jì)、合理、科學(xué)的系統(tǒng)設(shè)計(jì)及規(guī)劃具有重要意義.

目前有關(guān)超高速磁懸浮列車(chē)閉塞分區(qū)的合理規(guī)劃問(wèn)題暫未檢索發(fā)現(xiàn).國(guó)內(nèi)外眾多學(xué)者主要以城市軌道交通、干線(xiàn)鐵路或中低速磁懸浮為對(duì)象展開(kāi)了閉塞分區(qū)合理劃分的相關(guān)研究.文獻(xiàn)［7-9］主要基于公式法建立了有關(guān)能力計(jì)算的目標(biāo)函數(shù)，提供了一個(gè)初步的區(qū)間閉塞分區(qū)的結(jié)果估計(jì).該方法建立的模型較簡(jiǎn)單，未對(duì)信號(hào)系統(tǒng)進(jìn)行精確建模.相比于公式法計(jì)算列車(chē)追蹤間隔時(shí)間，文獻(xiàn)［10］認(rèn)為基于閉塞時(shí)間的建模方法可以準(zhǔn)確刻畫(huà)列車(chē)的占用特性，精確計(jì)算列車(chē)間隔，因其靈活、拓展性強(qiáng)、結(jié)果清晰明確等優(yōu)點(diǎn)，已經(jīng)成為國(guó)際上能力計(jì)算方法的發(fā)展趨勢(shì).文獻(xiàn)［11］基于閉塞時(shí)間壓縮的方法構(gòu)建了中速磁浮列車(chē)最小追蹤間隔的單目標(biāo)函數(shù)，并采用遺傳算法求解，最后得到了滿(mǎn)足列車(chē)最小運(yùn)行間隔的分區(qū)劃分方案.針對(duì)多目標(biāo)優(yōu)化模型的求解，文獻(xiàn)［12-13］通過(guò)線(xiàn)性加權(quán)法將兩個(gè)目標(biāo)轉(zhuǎn)換成單目標(biāo)問(wèn)題，然后采用相應(yīng)的智能優(yōu)化算法如粒子群算法、遺傳算法等求解.線(xiàn)性加權(quán)分解法過(guò)程簡(jiǎn)單便捷，但無(wú)法精準(zhǔn)確定權(quán)重，解的優(yōu)劣程度難以保證.由于超高速磁懸浮列車(chē)的閉塞分區(qū)優(yōu)化設(shè)計(jì)中不同目標(biāo)函數(shù)重要性或優(yōu)先級(jí)尚不明確，采用傳統(tǒng)的優(yōu)化思路具有一定的局限性.

為了給決策者提供所有非支配最優(yōu)解和多目標(biāo)之間的權(quán)衡分析，本文作者提出一種基于閉塞時(shí)間窗和極大自動(dòng)機(jī)理論相結(jié)合構(gòu)建能力計(jì)算模型的方法.在對(duì)線(xiàn)路基礎(chǔ)設(shè)施、超高速磁懸浮列車(chē)動(dòng)力學(xué)特性及列車(chē)超速防護(hù)系統(tǒng)（Automatic Train Protection，ATP）建模的基礎(chǔ)上，首先根據(jù)進(jìn)路屬性、聯(lián)鎖條件和信號(hào)系統(tǒng)工作流程，分別對(duì)車(chē)站和區(qū)間區(qū)域的不同類(lèi)型分區(qū)進(jìn)行劃分，建立相應(yīng)的閉塞時(shí)間模型.其次，通過(guò)異步仿真輸出基于列車(chē)運(yùn)行計(jì)劃的速度-距離、時(shí)間-距離曲線(xiàn)；然后，通過(guò)調(diào)用閉塞時(shí)間模型計(jì)算各分區(qū)的閉塞時(shí)間，并引入極大自動(dòng)機(jī)理論構(gòu)建能力計(jì)算模型計(jì)算列車(chē)平均發(fā)車(chē)間隔.最后，在滿(mǎn)足信號(hào)系統(tǒng)設(shè)計(jì)規(guī)范和相關(guān)安全準(zhǔn)則的約束條件下，基于能力計(jì)算模型構(gòu)建以設(shè)計(jì)能力最大化和分區(qū)建設(shè)成本最小化為目標(biāo)的多目標(biāo)優(yōu)化模型，將閉塞分區(qū)合理劃分問(wèn)題轉(zhuǎn)化為混合整數(shù)非線(xiàn)性規(guī)劃問(wèn)題，采用非支配排序遺傳算法（NSGA-Ⅱ）對(duì)問(wèn)題進(jìn)行求解，求解效果與基于線(xiàn)性加權(quán)方法的多目標(biāo)遺傳算法（VEGA）進(jìn)行對(duì)比，通過(guò)設(shè)計(jì)仿真測(cè)試案例，評(píng)估了該方法及NSGA-Ⅱ算法的可行性和優(yōu)越性.

1 超高速磁懸浮列車(chē)能力計(jì)算

超高速磁懸浮列車(chē)能力計(jì)算需要對(duì)基礎(chǔ)設(shè)施、列車(chē)和信號(hào)系統(tǒng)等數(shù)據(jù)進(jìn)行建模.基礎(chǔ)設(shè)施采用雙點(diǎn)拓?fù)浣Y(jié)構(gòu)進(jìn)行描述，主要包括軌道線(xiàn)路、坡度、曲率、靜態(tài)限速、道岔及車(chē)站.列車(chē)根據(jù)靜態(tài)參數(shù)如最高速度、編組、列車(chē)長(zhǎng)度等，以及動(dòng)態(tài)參數(shù)如牽引性能、制動(dòng)性能等，建立列車(chē)動(dòng)力學(xué)模型.信號(hào)系統(tǒng)包括ATP 控車(chē)模型、聯(lián)鎖進(jìn)路以及信號(hào)系統(tǒng)相關(guān)的處理、反應(yīng)和延遲時(shí)間.

在此基礎(chǔ)上，根據(jù)分區(qū)的定義及劃分原則，建立各類(lèi)型分區(qū)的閉塞時(shí)間模型；然后，通過(guò)異步仿真輸出基于列車(chē)運(yùn)行計(jì)劃的速度-距離、時(shí)間-距離曲線(xiàn)，并計(jì)算各分區(qū)的閉塞時(shí)間；最后引入極大自動(dòng)機(jī)（Max-plus Automata）理論構(gòu)建能力計(jì)算模型.

1.1 閉塞時(shí)間模型

分區(qū)是指列車(chē)運(yùn)行時(shí)，同一時(shí)刻僅允許一列列車(chē)占用，具有獨(dú)占性的區(qū)段，如區(qū)間的一個(gè)閉塞分區(qū)、車(chē)站的一個(gè)道岔區(qū)段或一個(gè)停車(chē)股道［14］.根據(jù)文獻(xiàn)［14］提出的分區(qū)劃分原則，建立各類(lèi)型分區(qū)閉塞時(shí)間模型如圖1 所示.

圖1 超高速磁懸浮列車(chē)閉塞時(shí)間模型Fig.1 Block time model of ultra-high-speed maglev train

結(jié)合超高速磁懸浮列車(chē)運(yùn)行控制系統(tǒng)工作流程，圖1 中各時(shí)間參數(shù)的含義如下所示［15］：

1）進(jìn)路建立時(shí)間Ts：接/發(fā)車(chē)/股道分區(qū)為中央控制系統(tǒng)排列下一列車(chē)的接/發(fā)車(chē)進(jìn)路（包含道岔動(dòng)作時(shí)間），中央控制系統(tǒng)向分區(qū)控制系統(tǒng)發(fā)送進(jìn)路狀態(tài)的時(shí)間；區(qū)間分區(qū)為車(chē)地通信設(shè)備接收來(lái)自分區(qū)控制系統(tǒng)的分區(qū)狀態(tài)信息后，處理信息并發(fā)送給下一列車(chē)的時(shí)間.

2）反應(yīng)時(shí)間Tr：超高速磁懸浮列車(chē)控車(chē)模式為列車(chē)自動(dòng)駕駛模式（Automatic Train Operation，ATO），反應(yīng)時(shí)間指列車(chē)接收到地車(chē)通信設(shè)備的實(shí)時(shí)反饋信息并做出處理的時(shí)間.

3）接近時(shí)間Ta：區(qū)間/股道/接車(chē)分區(qū)為列車(chē)車(chē)頭從接近點(diǎn)運(yùn)行至分區(qū)入口點(diǎn)的時(shí)間，其中區(qū)間分區(qū)的接近點(diǎn)為列車(chē)移動(dòng)授權(quán)（Movement Authority，MA）首次延伸到分區(qū)入口點(diǎn)時(shí)車(chē)頭所在的位置，股道/接車(chē)分區(qū)的接近點(diǎn)為列車(chē)移動(dòng)授權(quán)MA 首次延伸到接車(chē)咽喉區(qū)道岔防護(hù)點(diǎn)時(shí)車(chē)頭所在的位置；發(fā)車(chē)分區(qū)為列車(chē)從停車(chē)點(diǎn)運(yùn)行至分區(qū)入口點(diǎn)的時(shí)間.

4）占用時(shí)間To：本車(chē)車(chē)頭從分區(qū)入口點(diǎn)運(yùn)行至分區(qū)出口點(diǎn)所需時(shí)間.

5）出清時(shí)間Tc：列車(chē)車(chē)頭從分區(qū)出口點(diǎn)運(yùn)行一個(gè)車(chē)長(zhǎng)所需時(shí)間.

6）解鎖時(shí)間Tu：分區(qū)控制系統(tǒng)采集分區(qū)出清狀態(tài)并釋放進(jìn)路的時(shí)間.

根據(jù)異步仿真輸出的基于運(yùn)行計(jì)劃的速度-距離曲線(xiàn)和時(shí)間-距離曲線(xiàn)，可計(jì)算各分區(qū)的閉塞時(shí)間組成.

1.2 能力計(jì)算模型

能力計(jì)算借鑒國(guó)際鐵路聯(lián)盟標(biāo)準(zhǔn)（International Union of Railways 406，UIC406）中時(shí)刻表壓縮的思想，通過(guò)平移鋪畫(huà)好的各列車(chē)路徑的閉塞時(shí)間階梯圖直至兩兩列車(chē)達(dá)到無(wú)沖突運(yùn)行的最小列車(chē)間隔［16］.由于列車(chē)路徑在各分區(qū)上形成的閉塞時(shí)間窗視為帶有上界和下界的堆模型，能力計(jì)算的過(guò)程類(lèi)似堆模型不斷堆積的過(guò)程，因此本文引入極大自動(dòng)機(jī)理論建立能力計(jì)算模型.

1.2.1 極大自動(dòng)機(jī)理論

極大自動(dòng)機(jī)理論結(jié)合了堆模型和Max-plus 代數(shù)［17］.堆模型可定義為一個(gè)五元組C=(P，B，M，S，F(xiàn))，其 中：P為任務(wù)集合；B為資源集合；M為的態(tài)射，大小|B|×|B|維的矩陣；S為堆模型的上界集合；F為堆模型的下界集合.Max-plus 代數(shù)由(Rmax，⊕，?)共同組成，其中域Rmax=R∪{-∞}，⊕、?為在域上定義的兩個(gè)運(yùn)算.對(duì)于?a，b∈Rmax，定義ε=-∞，e=0，二元運(yùn)算規(guī)則如下

為簡(jiǎn)化計(jì)算，通常省略?符號(hào).

1.2.2 能力計(jì)算

假設(shè)一個(gè)列車(chē)運(yùn)行計(jì)劃周期已知，分區(qū)b1的起點(diǎn)為車(chē)站停車(chē)點(diǎn)，基于閉塞時(shí)間窗的各列車(chē)路徑在空間上占用不同的分區(qū)，在時(shí)間上依據(jù)其各分區(qū)占用開(kāi)始和占用結(jié)束時(shí)刻，不斷堆積，形成一個(gè)運(yùn)行計(jì)劃周期的堆模型示意圖，如圖2 所示.通過(guò)極大自動(dòng)機(jī)的代數(shù)運(yùn)算得到堆積后運(yùn)行計(jì)劃周期的基礎(chǔ)設(shè)施占用時(shí)間［18］，從而進(jìn)一步計(jì)算平均發(fā)車(chē)間隔.

圖2 堆模型Fig.2 Heap model

圖2 中，堆模型五元組中P={p1，p2，...，pk，...，pK，pK+1}為一個(gè)運(yùn)行計(jì)劃周期的列車(chē)路徑集合，pk為第k條列車(chē)路徑，前K條列車(chē)路徑互不重復(fù)，最后一條列車(chē)路徑pK+1與第一條列車(chē)路徑p1相同；B(pk)={b1，b2，...，bn，...，bN}為 第k條列車(chē) 路徑的分區(qū)集合，bn為第n個(gè)分區(qū)，N為分區(qū)總數(shù)；S，F(xiàn)為每條列車(chē)路徑從0 時(shí)刻開(kāi)始發(fā)車(chē)形成的閉塞時(shí)間窗上界集合 和下界集合，Sk，n，F(xiàn)k，n為第k條列車(chē)路徑在第n個(gè)分區(qū)的閉塞時(shí)間窗的上界和下界，如下

定義“堆模型”的態(tài)射矩陣

式中：若i=j，為分區(qū)i的堆模型高度.

首先，根據(jù)式（2）的矩陣運(yùn)算規(guī)則計(jì)算基于一個(gè)列車(chē)運(yùn)行計(jì)劃周期下P的能力占用矩陣為

其次，根據(jù)能力占用矩陣M(P)計(jì)算一個(gè)列車(chē)運(yùn)行計(jì)劃周期在堆積后形成的大小為1×|B|維的向量y(pK)，表示堆積前K條列車(chē)路徑后形成的所有分區(qū)下界，如下

式中：y(e)={e，...，e}是一個(gè)1×|B|維的向量，對(duì)應(yīng)一個(gè)空運(yùn)行計(jì)劃；y(P)n為堆積K條列車(chē)路徑后第n個(gè)分區(qū)的下界.

然后，根據(jù)堆積后的列車(chē)路徑結(jié)果，計(jì)算基礎(chǔ)設(shè)施占用時(shí)間為

式 中：（FK+1，1-SK+1，1）為重復(fù) 計(jì)算第K+1 列車(chē)在第1 個(gè)分區(qū)的堆模型高度.

一個(gè)列車(chē)運(yùn)行計(jì)劃周期的總發(fā)車(chē)間隔H為

由于第1 條列車(chē)路徑和第K+1 條列車(chē)路徑相同，（總發(fā)車(chē)間隔H和基礎(chǔ)設(shè)施占用時(shí)間λ(P)的值相同）.

最后，直接通過(guò)基礎(chǔ)設(shè)施占用時(shí)間計(jì)算一個(gè)列車(chē)運(yùn)行計(jì)劃周期的平均列車(chē)發(fā)車(chē)間隔為

2 閉塞分區(qū)優(yōu)化問(wèn)題建模

基于第1 節(jié)超高速磁懸浮列車(chē)能力計(jì)算模型建立分區(qū)長(zhǎng)度合理劃分的優(yōu)化模型.分區(qū)劃分范圍從車(chē)站發(fā)車(chē)點(diǎn)開(kāi)始到下一車(chē)站停車(chē)點(diǎn)結(jié)束，發(fā)車(chē)、接車(chē)以及車(chē)站股道分區(qū)的劃分長(zhǎng)度是由道岔防護(hù)點(diǎn)設(shè)置決定的，故本文主要考慮區(qū)間分區(qū)的合理劃分問(wèn)題，如圖3 所示.假設(shè)兩站區(qū)間分區(qū)個(gè)數(shù)為N，第n個(gè)分區(qū)的長(zhǎng)度為ln，n∈{1，2，...，N}，dn為對(duì)應(yīng)分區(qū)節(jié)點(diǎn)位置.其中d0、dN已知，分別為出站咽喉區(qū)防護(hù)點(diǎn)位置和進(jìn)站咽喉區(qū)防護(hù)點(diǎn)的位置.

圖3 分區(qū)劃分示意圖Fig.3 Schematic diagram of block division

2.1 優(yōu)化目標(biāo)

分區(qū)優(yōu)化問(wèn)題是在確保列車(chē)安全運(yùn)行的前提下，從“效率”和“經(jīng)濟(jì)”兩個(gè)方面優(yōu)化分區(qū)長(zhǎng)度和數(shù)量.

1）“效率”目標(biāo).

“效率”目標(biāo)是指在滿(mǎn)足列車(chē)安全運(yùn)行的前提下最大化設(shè)計(jì)能力，即單位時(shí)間內(nèi)不考慮緩沖時(shí)間下可以計(jì)劃的最多列車(chē)路徑數(shù)量［19］.本文以平均發(fā)車(chē)間隔為指標(biāo)衡量設(shè)計(jì)能力，目標(biāo)函數(shù)為

式中：目標(biāo)函數(shù)輸入變量為分區(qū)長(zhǎng)度(l1，l2，…，ln).結(jié)合第1 節(jié)中超高速磁懸浮列車(chē)能力計(jì)算方法，目標(biāo)函數(shù)計(jì)算步驟如下.

算法1：平均發(fā)車(chē)間隔計(jì)算方法

輸入：列車(chē)路徑數(shù)K，分區(qū)個(gè)數(shù)N，分區(qū)長(zhǎng)度ln，n∈{1，2，…，N}，線(xiàn)路，列車(chē)和信號(hào)系統(tǒng)相關(guān)輸入數(shù)據(jù).

步驟1：初始化操作，對(duì)線(xiàn)路、列車(chē)和信號(hào)系統(tǒng)進(jìn)行數(shù)據(jù)建模，異步仿真輸出每條列車(chē)路徑的安全間距集合，存放每一時(shí)刻下列車(chē)車(chē)頭所在位置，列車(chē)速度以及列車(chē)移動(dòng)授權(quán)延伸的最大位置.

步驟2：根據(jù)分區(qū)長(zhǎng)度計(jì)算閉塞分區(qū)節(jié)點(diǎn)位置dn=d0+，采用遍歷算法計(jì)算每條列車(chē)路徑下在各個(gè)分區(qū)的閉塞時(shí)間組成部分.

步驟2.1：令列車(chē)路徑k=1，分區(qū)個(gè)數(shù)n=1；

步驟2.2：調(diào)用第k條列車(chē)路徑下的安全間距表集合，搜索定位表中第n個(gè)分區(qū)的入口點(diǎn)位置dn-1、出口點(diǎn)位置dn，出清點(diǎn)位置dn+ltrain，列車(chē)移動(dòng)授權(quán)延伸至分區(qū)入口點(diǎn)時(shí)的對(duì)應(yīng)列車(chē)時(shí)刻；

步驟2.3：根據(jù)1.1 節(jié)的閉塞時(shí)間模型含義，判斷第n個(gè)分區(qū)的分區(qū)類(lèi)型，計(jì)算并賦值第k列車(chē)在第n個(gè)分區(qū)的進(jìn)路以及

步驟2.4：令n=n+1，如果滿(mǎn)足n＞N，繼續(xù)步驟2.5，反之跳轉(zhuǎn)至步驟2.2；

步驟2.5：令k=k+1，n=1，如果k＞K，則遍歷結(jié)束，繼續(xù)步驟3，否則跳轉(zhuǎn)至步驟2.2.

步驟3：根據(jù)1.2.2 節(jié)計(jì)算一個(gè)列車(chē)運(yùn)行計(jì)劃下的堆模型五元組C.計(jì)算堆模型上界和下界集合S、F，M(pk)，M(P).

步驟4：根據(jù)列車(chē)路徑堆積的結(jié)果分別計(jì)算y(P)，

2）“經(jīng)濟(jì)”目標(biāo).

“經(jīng)濟(jì)”目標(biāo)是指滿(mǎn)足約束的前提下，最小化分區(qū)建設(shè)成本.本文直接以分區(qū)劃分?jǐn)?shù)量為指標(biāo)衡量建設(shè)成本，其目標(biāo)函數(shù)為

2.2 約束條件

作為一個(gè)復(fù)雜的多目標(biāo)規(guī)劃問(wèn)題，除了目標(biāo)函數(shù)外，分區(qū)的實(shí)際劃分需考慮多個(gè)約束條件，本文根據(jù)約束條件的性質(zhì)，分為幾何約束和性能約束.

1）幾何約束.

考慮基本分區(qū)長(zhǎng)度和分區(qū)個(gè)數(shù)的限制，構(gòu)建幾何約束為

式中：lmin、lmax分別為工程人員由現(xiàn)場(chǎng)實(shí)際情況確定的分區(qū)的最小長(zhǎng)度和最大長(zhǎng)度.

2）性能約束.

除了基本長(zhǎng)度約束，從信號(hào)系統(tǒng)設(shè)計(jì)的角度進(jìn)一步構(gòu)建性能約束函數(shù).首先，相鄰列車(chē)運(yùn)行過(guò)程中應(yīng)符合安全原則，即分區(qū)劃分的結(jié)果滿(mǎn)足只有當(dāng)?shù)趉列車(chē)出清并解鎖第n個(gè)分區(qū)，第k+1 列車(chē)才可排列第n個(gè)分區(qū)進(jìn)路的條件.其次，為了符合能力最優(yōu)設(shè)計(jì)原則，前車(chē)出清并解鎖第1 個(gè)區(qū)間分區(qū)后，后車(chē)立即排列發(fā)車(chē)進(jìn)路，該性能約束如下

3 求解算法

針對(duì)分區(qū)劃分優(yōu)化問(wèn)題，采用NSGA-Ⅱ算法進(jìn)行求解，并與VEGA 算法的求解效果進(jìn)行對(duì)比.NSGA-Ⅱ算法基本流程圖如圖4 所示［20］.

圖4 NSGA-Ⅱ算法流程圖Fig.4 Flow chart of NSGA-Ⅱ algorithm

結(jié)合NSGA-Ⅱ算法的流程圖進(jìn)一步設(shè)計(jì)超高速磁懸浮列車(chē)分區(qū)的劃分過(guò)程，具體如下：

1）解的編碼.

染色體采用xi=(xi(0)，xi(1)，xi(2)，…，xi(N))的形式表示分區(qū)優(yōu)化至第i代的一種劃分方案，其中：N=xi(0)；xi(0)表示當(dāng)前劃分方案下的分區(qū)個(gè)數(shù)；(n)表示第j條染色體中第n個(gè)分區(qū)的長(zhǎng)度，染色體的維度與分區(qū)個(gè)數(shù)有關(guān).本文采用具有優(yōu)化精度高、搜索方便等特點(diǎn)的實(shí)數(shù)編碼.

2）初始化種群.

初始化種群的質(zhì)量對(duì)優(yōu)化結(jié)果具有重要影響，為了提高算法性能，本文針對(duì)初始化的過(guò)程進(jìn)行以下處理：①盡可能快速均勻分布初始解，避免陷入局部最優(yōu)；②通過(guò)簡(jiǎn)單篩選剔除質(zhì)量較差的部分個(gè)體，具體種群初始化算法如下

算法2：種群初始化算法

輸入：分區(qū)劃分優(yōu)化模型，種群規(guī)模Np，站間距L.

輸出：種群初始解.

步驟1：令迭代次數(shù)j=1.

步驟2：隨機(jī)生成分區(qū)個(gè)數(shù)N，記錄第j次迭代的時(shí)間tj.

步驟3：判斷當(dāng)前迭代的時(shí)間tj是否大于10 s，若小于10 s，則跳轉(zhuǎn)步驟3.1，反之跳轉(zhuǎn)步驟3.2.

步驟3.1：隨機(jī)生成各個(gè)分區(qū)的長(zhǎng)度，跳轉(zhuǎn)步驟4；

步驟3.2：將區(qū)間分區(qū)長(zhǎng)度N等分后l=，每個(gè)分區(qū)長(zhǎng)度在[l-100，l+100]的范圍內(nèi)隨機(jī)取值，跳轉(zhuǎn)步驟4；

步驟4：判斷當(dāng)前染色體是否符合所有約束條件，若符合，則跳轉(zhuǎn)步驟5，反之，則轉(zhuǎn)入跳轉(zhuǎn)步驟3.

步驟5：j=j+1，如果j＞Np，算法終止，否則跳轉(zhuǎn)至步驟2 繼續(xù)初始化染色體.

3）適應(yīng)度函數(shù)構(gòu)建.

為了提高優(yōu)化效率，針對(duì)諸多約束條件引入外點(diǎn)懲罰函數(shù)，進(jìn)一步構(gòu)建無(wú)約束的適應(yīng)度函數(shù)，目標(biāo)的適應(yīng)度函數(shù)如下

式中：Fu，u=1，2 分別為兩個(gè)目標(biāo)下的適應(yīng)度函數(shù)；為迭代過(guò)程中呈遞增正數(shù)列的罰因子；g(x)和h(x)分別為優(yōu)化模型中的不等式約束和等式約束.在迭代過(guò)程中，若一組染色體滿(mǎn)足所有約束時(shí)，適應(yīng)度函數(shù)值等于目標(biāo)函數(shù)值；反之，若不滿(mǎn)足約束，則后兩項(xiàng)取值增大，適應(yīng)度函數(shù)值也將增大.

4）新解的產(chǎn)生：選擇、交叉、變異［21］.

①選擇：假設(shè)父代種群記為Pg，首先通過(guò)二元錦標(biāo)賽策略，每次從當(dāng)前種群中取出兩個(gè)個(gè)體，取其中適應(yīng)度值較優(yōu)的染色體放入子代種群，重復(fù)該操作直到子代種群規(guī)?；謴?fù)為Np，選擇操作后的子代種群記為.

② 交叉：為了增強(qiáng)算法的局部搜索能力，將種群中的染色體進(jìn)行長(zhǎng)度分類(lèi)，選擇相同長(zhǎng)度的染色體采用模擬二進(jìn)制交叉算法進(jìn)行單點(diǎn)交叉操作.假設(shè)選取個(gè)體，進(jìn)行交叉，其交叉后的個(gè)體為

式中：β與隨機(jī)數(shù)μ∈[0，1]有關(guān).

式中：η1為交叉分布參數(shù)，取值越大，子代個(gè)體與父代個(gè)體差異越小.

③變異：模擬二進(jìn)制交叉后的種群，隨機(jī)選擇要變異的基因位，通過(guò)多項(xiàng)式變異操作生成子代種群為

式中：xmax，xmin分別為相應(yīng)決策變量的上下邊界；η2為變異分布參數(shù)，可根據(jù)實(shí)際進(jìn)化情況進(jìn)行調(diào)整.若變異的基因位置在第一位，染色體長(zhǎng)度改變，重新初始化該條染色體.

5）非支配排序.

將種群Qg進(jìn)行非支配排序，產(chǎn)生一系列非支配集Zi并計(jì)算擁擠度.個(gè)體擁擠度的計(jì)算與適應(yīng)度函數(shù)值有關(guān)，如下

式中：jd為第j點(diǎn)的擁擠度分別為第j+1點(diǎn)和第j-1 點(diǎn)的適應(yīng)度函數(shù)值.

6）精英策略.

將子代種群Qg和父代種群Pg合并形成規(guī)模為2Np的新種群Rg，根據(jù)快速非支配排序結(jié)果和擁擠度的值對(duì)個(gè)體進(jìn)行篩選合并后的種群Rg，直到選出種群規(guī)模為Np的新父代種群Pg+1.

7）終止條件判斷.

判斷是否滿(mǎn)足迭代終止條件，若當(dāng)前迭代次數(shù)滿(mǎn)足最大迭代次數(shù)，則停止迭代，輸出最優(yōu)解，否則，通過(guò)交叉變異產(chǎn)生新的子代種群Qg+1，將Pg+1和Qg+1合并形成新的種群Rg，重復(fù)3）到6）的操作.

4 仿真案例

4.1 參數(shù)設(shè)置

以?xún)烧镜膮^(qū)間為例，假設(shè)始發(fā)站停車(chē)點(diǎn)絕對(duì)公里標(biāo)為2.14 km，區(qū)間站停車(chē)點(diǎn)絕對(duì)公里標(biāo)為302.14 km，道岔防護(hù)點(diǎn)d0和dN的位置分別為3.18、301.258 km，一個(gè)列車(chē)運(yùn)行計(jì)劃周期最大列車(chē)數(shù)量為3 列，基礎(chǔ)設(shè)施、列車(chē)、信號(hào)系統(tǒng)和運(yùn)營(yíng)組織相關(guān)輸入數(shù)據(jù)如表1所示.

表1 仿真參數(shù)設(shè)置Tab.1 Simulation parameter setting

本文基于Matlab 編程實(shí)現(xiàn)超高速磁懸浮列車(chē)的分區(qū)優(yōu)化設(shè)計(jì)，并采用NSGA-Ⅱ算法進(jìn)行求解.配置為：計(jì)算機(jī)內(nèi)存8 G，處理器主頻1.60 GHz，操作系統(tǒng)為windows 10（64 位）.根據(jù)經(jīng)驗(yàn)及大量實(shí)際仿真，NSGA-Ⅱ算法中最優(yōu)個(gè)體前端個(gè)體系數(shù)取值0.3，個(gè)體交叉概率為0.95，個(gè)體變異概率為0.1，交叉分布參數(shù)為20，變異分布參數(shù)為20，初始種群規(guī)模200 個(gè)，最大迭代次數(shù)200 次，選擇操作基于序值和擁擠距離［22-24］.

為分析本文所提出模型與算法的效果，將其與VEGA 算法進(jìn)行結(jié)果對(duì)比，相關(guān)參數(shù)設(shè)置與NSGA-Ⅱ算法保持一致.VEGA 算法通過(guò)線(xiàn)性加權(quán)的方式將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題，適應(yīng)度評(píng)價(jià)函數(shù)如下

式中：fitness 為適應(yīng)度評(píng)價(jià)函數(shù)；a、b分別為兩個(gè)目標(biāo)的權(quán)重，滿(mǎn)足a+b=1.C1、C2為常數(shù)，將兩個(gè)目標(biāo)的適應(yīng)度值調(diào)節(jié)在一定的范圍內(nèi)，與初始化種群的目標(biāo)均值有關(guān)，如下

4.2 仿真分析

基于以上輸入數(shù)據(jù)和多目標(biāo)優(yōu)化模型分別運(yùn)行NSGA-Ⅱ算法和VEGA 算法.本文首先輸出了NSGA-Ⅱ算法下的兩個(gè)目標(biāo)收斂曲線(xiàn)，并結(jié)合曲線(xiàn)趨勢(shì)分析NSGA-Ⅱ的收斂性，多樣性的特點(diǎn)；其次，通過(guò)調(diào)整VEGA 算法的權(quán)重系數(shù)形成一組可行解，與NSGA-Ⅱ算法下的Pareto 前沿解作對(duì)比，從計(jì)數(shù)指標(biāo)、收斂性指標(biāo)、多樣性指標(biāo)定性分析兩種算法的性能及解集的質(zhì)量［25］，并且進(jìn)一步引入超體積評(píng)價(jià)指標(biāo)（Hypervolume，HV）量化分析不同算法的綜合性能；最后，選取列出了NSGA-Ⅱ算法求解結(jié)果中具有代表性的三組Pareto 最優(yōu)解.

NSGA-Ⅱ的目標(biāo)收斂曲線(xiàn)如圖5 所示，包含迭代過(guò)程中種群最大、平均和最小的適應(yīng)度值變化信息.

圖5 NSGA-Ⅱ目標(biāo)收斂曲線(xiàn)圖Fig.5 Target convergence curve of NSGA-Ⅱ

由圖5可知：

1）NSGA-Ⅱ算法中兩個(gè)目標(biāo)下的均值收斂曲線(xiàn)在局部范圍內(nèi)波動(dòng)存在一定的相關(guān)性，即當(dāng)在一個(gè)目標(biāo)保持不變或者增大時(shí)另一個(gè)目標(biāo)快速減小，表明兩個(gè)目標(biāo)在進(jìn)化過(guò)程中不斷地相互均衡取舍.而“效率”目標(biāo)的最大值曲線(xiàn)存在一定的波動(dòng)，表明算法在迭代過(guò)程中仍然具有較強(qiáng)的持續(xù)搜索能力，最大值的適當(dāng)保留維持了各代種群的多樣性，能夠提高迭代過(guò)程的進(jìn)化空間，有效的避免陷入局部最優(yōu).

2）NSGA-Ⅱ算法在迭代前期兩個(gè)優(yōu)化目標(biāo)的進(jìn)化曲線(xiàn)都在迅速減小并逐漸收斂，算法性能優(yōu)良.隨著迭代次數(shù)的增加，各代種群的目標(biāo)平均適應(yīng)度值于160 代之后分別收斂于314 和16.2 左右，并且目標(biāo)的均值收斂曲線(xiàn)更偏向于最小值，表明種群中的可行解分布集中在最小值附近，解的質(zhì)量得到較好保證.

VEGA 算法通過(guò)調(diào)整權(quán)重系數(shù)可形成一組可行解，與NSGA-Ⅱ算法下的Pareto 解集作對(duì)比，實(shí)驗(yàn)結(jié)果如圖6 所示，包含了目標(biāo)空間兩個(gè)目標(biāo)的值.

從圖6 對(duì)比可知：

圖6 NSGA-Ⅱ算法和VEGA 算法解集對(duì)比Fig.6 Comparison between solution sets of NSGA-Ⅱ and VEGA

1）計(jì)數(shù)指 標(biāo)：VEGA 算法共生成6 組最優(yōu) 解，NSGA-Ⅱ算法共生成9 組Pareto 最優(yōu)解，NSGA-Ⅱ算法下求解數(shù)量更多；

2）收斂性指標(biāo)：圖6 中紅色曲線(xiàn)整體位于藍(lán)色曲線(xiàn)下方，說(shuō)明NSGA-Ⅱ算法的收斂效果優(yōu)于VEGA 算法；

3）多樣性指標(biāo)：多樣性指標(biāo)包括解集的延展性和分布性.NSGA-Ⅱ算法和VEGA 算法解集的延展均從（387.3，9）到（285.8，21），延展性幾乎一致，但是NSGA-Ⅱ解集的分布更均勻，故NSGA-Ⅱ算法的多樣性?xún)?yōu)于VEGA 算法；

4）超體積評(píng)價(jià)指標(biāo)HV［26］：超體積評(píng)價(jià)指標(biāo)通過(guò)一個(gè)標(biāo)量值可同時(shí)反映多目標(biāo)進(jìn)化算法的收斂性和多樣性，其計(jì)算為

式中：λ為勒貝格測(cè)度；vi為參考點(diǎn)和非支配個(gè)體pi構(gòu)成的超體積；S為算法求解的非支配集.HV 值越大，算法的綜合性能越好.以非支配解集每維上的最大值組成的向量（387，21）為參考點(diǎn)［27］，由式（22）計(jì)算可得，NSGA-Ⅱ算法下HV 為0.119 1，VEGA 算法下HV 為0.084 5，故NSGA-Ⅱ算法的綜合性能優(yōu)于VEGA 算法.

綜上分析，從解的質(zhì)量方面，NSGA-Ⅱ算法的解集分布更均衡且收斂效果更好，求解效果顯著優(yōu)于VEGA 算法.VEGA 算法通過(guò)線(xiàn)性加權(quán)的方法將兩個(gè)目標(biāo)轉(zhuǎn)化為單目標(biāo)問(wèn)題，指標(biāo)對(duì)評(píng)價(jià)結(jié)果的影響僅靠改變權(quán)重?zé)o法完全體現(xiàn)，并且迭代過(guò)程中難以維持種群的多樣性，相關(guān)參數(shù)選擇和適應(yīng)度函數(shù)設(shè)計(jì)也會(huì)影響解的品質(zhì).而NSGA-Ⅱ算法直接基于原始目標(biāo)函數(shù)和值進(jìn)行操作，不會(huì)丟失目標(biāo)函數(shù)和解的信息，得到一系列最優(yōu)的解集，解的優(yōu)劣可以較好保證，能為決策者提供更多的選擇范圍.

選取NSGA-Ⅱ算法求解結(jié)果中有代表性的三組Pareto 最優(yōu)解，劃分結(jié)果保留一位小數(shù)，分區(qū)劃分方案如表2 所示.

表2 Pareto 最優(yōu)解集Tab.2 Optimal solution set of Pareto

NSGA-II 算法中，Pareto 最優(yōu)解1 的經(jīng)濟(jì)目標(biāo)值最小，Pareto 最優(yōu)解9 的效率目標(biāo)值最小.決策者選擇最優(yōu)設(shè)計(jì)方案時(shí)，若更加看重線(xiàn)路建設(shè)的經(jīng)濟(jì)性，則最佳決策方案更可能為 Pareto 最優(yōu)解1；反之若更加注重線(xiàn)路的設(shè)計(jì)能力，則最佳決策方案更可能為Pareto 最優(yōu)解9；若兩者之間相對(duì)平衡，可選擇中間的其他方案.

5 結(jié)論

1）在對(duì)基礎(chǔ)設(shè)施、超高速磁懸浮列車(chē)動(dòng)力學(xué)特性及信號(hào)系統(tǒng)ATP 建模的基礎(chǔ)上，提出一種基于閉塞時(shí)間窗和Max-plus 自動(dòng)機(jī)理論相結(jié)合構(gòu)建能力計(jì)算模型的方法，通過(guò)引用分區(qū)概念及劃分原則建立不同類(lèi)型分區(qū)的閉塞時(shí)間模型，在此基礎(chǔ)上引入極大自動(dòng)機(jī)理論構(gòu)建了能力計(jì)算函數(shù).針對(duì)設(shè)計(jì)能力最大化和分區(qū)建設(shè)成本最小化多目標(biāo)優(yōu)化問(wèn)題，以平均發(fā)車(chē)間隔最小和閉塞分區(qū)建設(shè)成本最小化為目標(biāo)，建立列車(chē)運(yùn)行控制系統(tǒng)的性能約束條件.由此，將閉塞分區(qū)合理劃分問(wèn)題轉(zhuǎn)化為混合整數(shù)非線(xiàn)性規(guī)劃問(wèn)題，并采用NSGA-Ⅱ算法對(duì)問(wèn)題進(jìn)行求解，最后通過(guò)仿真案例將其與VEGA 算法從求解質(zhì)量方面進(jìn)行了對(duì)比，驗(yàn)證了該方法及優(yōu)化算法的優(yōu)勢(shì).相比于基于公式法建立的分區(qū)優(yōu)化模型，基于閉塞時(shí)間窗和Max-plus 自動(dòng)機(jī)理論相結(jié)合構(gòu)建能力計(jì)算模型的方法和優(yōu)化算法具有建模精確、運(yùn)算速度高、結(jié)果清晰準(zhǔn)確的優(yōu)點(diǎn).

2）基于超高速磁懸浮列車(chē)相關(guān)數(shù)據(jù)進(jìn)行了仿真測(cè)試，結(jié)果表明：NSGA-Ⅱ算法的算法性能和求解效果從計(jì)數(shù)指標(biāo)、收斂性指標(biāo)、多樣性指標(biāo)和超體積評(píng)價(jià)指標(biāo)上均優(yōu)于VEGA 算法.NSGA-Ⅱ算法在求解超高速磁懸浮列車(chē)閉塞分區(qū)劃分優(yōu)化設(shè)計(jì)過(guò)程中，具有運(yùn)行速度快，解集收斂性好的優(yōu)點(diǎn)，輸出結(jié)果共得到9 組Pareto 最優(yōu)解，解決了傳統(tǒng)多目標(biāo)規(guī)劃問(wèn)題將多目標(biāo)轉(zhuǎn)化為單目標(biāo)問(wèn)題后每次求解帶來(lái)的只有單一解的問(wèn)題.仿真結(jié)果精確滿(mǎn)足各項(xiàng)約束，可為決策者在管理決策過(guò)程中提供使多個(gè)目標(biāo)都達(dá)到滿(mǎn)意結(jié)果的閉塞分區(qū)布置方案.

后續(xù)的研究中，可以對(duì)閉塞時(shí)間模型增加時(shí)間裕量，進(jìn)一步考慮列車(chē)擾動(dòng)情況下模型和算法的優(yōu)化.