盧特爾，陳軍華，陳昂揚(yáng)，鄭 漢

（北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044)

0 引言

自20 世紀(jì)90 年代以來，經(jīng)過幾十年的發(fā)展，我國針對(duì)不同的區(qū)域環(huán)境和線路條件，研發(fā)了應(yīng)用于高寒地區(qū)、沙漠地區(qū)、長(zhǎng)大干線、城際線路等不同速度等級(jí)、不同運(yùn)用條件的高速鐵路動(dòng)車組，已經(jīng)基本形成了自主創(chuàng)新的高速動(dòng)車組體系結(jié)構(gòu)[1]。高速鐵路動(dòng)車組有很多不同的型號(hào)，但是大多為8輛、16 輛或17 輛車廂固定編組，且在運(yùn)營過程中編組不可改變，導(dǎo)致動(dòng)車組的載運(yùn)能力無法很好地適應(yīng)需求的波動(dòng)。此外，動(dòng)車組檢修、熱備等環(huán)節(jié)均需要整列同時(shí)進(jìn)行，動(dòng)車組運(yùn)用缺乏靈活性，運(yùn)用效率不高。國外鐵路可變編組列車的發(fā)展起步較早，應(yīng)用范圍更廣，如德國研發(fā)的ICE4 于2017年投入運(yùn)營，可實(shí)現(xiàn)5 ～ 14 輛靈活編組[2]。荷蘭采用3 輛或4 輛客車形成列車單元，以實(shí)現(xiàn)3 ～ 15 輛編組。我國研發(fā)的CRH3X 型可變編組動(dòng)車組樣車可以實(shí)現(xiàn)多種車型的靈活拆解、組合[3]。2018 年，中車唐山機(jī)車車輛有限公司首次發(fā)布最高運(yùn)行速度500 km/h 的可變編組動(dòng)車組概念車，同時(shí)展出運(yùn)行速度350 km/h 的可變編組動(dòng)車組樣車模型。2019年2 月，我國首列可變編組動(dòng)車組完成全部60 余項(xiàng)廠內(nèi)試驗(yàn)，具備出廠條件[4]，可根據(jù)客流變化實(shí)現(xiàn)2 ～ 16 輛靈活編組。

在可變編組動(dòng)車組的運(yùn)行計(jì)劃研究方面，陶若冰等[5]綜合運(yùn)用熵值法、變異系數(shù)法和BP 神經(jīng)網(wǎng)絡(luò)，研究可變編組列車不同座席的客流預(yù)測(cè)模型。姜安培[6]以運(yùn)行圖為輸入?yún)?shù)，建立動(dòng)車組運(yùn)用優(yōu)化模型。付建軍等[7]提出可變編組動(dòng)車組運(yùn)用計(jì)劃與檢修計(jì)劃一體化的思路，建立相應(yīng)的混合整數(shù)規(guī)劃模型，用改進(jìn)的非支配排序遺傳算法求解，采用帕累托前沿分析模型的2 個(gè)目標(biāo)值。此外，還有一些學(xué)者研究城市軌道交通可變編組列車開行方案設(shè)計(jì)問題[8-10]。但是，目前我國針對(duì)可變編組高速鐵路列車的開行計(jì)劃優(yōu)化研究較少。隨著可變編組高速鐵路動(dòng)車組的研發(fā)、生產(chǎn)技術(shù)的完善，可變編組高速鐵路列車將在更大的范圍內(nèi)應(yīng)用，需要更新與變革相應(yīng)運(yùn)輸組織工作。因此，研究高速鐵路可變編組列車的開行計(jì)劃優(yōu)化問題，構(gòu)建優(yōu)化模型，設(shè)計(jì)分支定界算法，以確定列車需要進(jìn)行組合、拆解作業(yè)的車站，以及各區(qū)段、各時(shí)段可變編組列車的編組內(nèi)容，實(shí)現(xiàn)列車開行成本和乘客出行時(shí)間的最小化。

1 高速鐵路可變編組列車開行計(jì)劃優(yōu)化模型

1.1 符號(hào)說明

高速鐵路可變編組列車開行計(jì)劃優(yōu)化是在給定列車運(yùn)行圖和客流需求的條件下，確定各列車在各車站是否進(jìn)行組合、拆解作業(yè)，以及各列車在各個(gè)區(qū)間運(yùn)行時(shí)的具體編組內(nèi)容[11]。高速鐵路可變編組列車運(yùn)行圖為G= (I，A)或G= (I，P)，運(yùn)行圖示意圖如圖1 所示。其中I= {1，2，…，R}，是車站集合；1，2，…，R依次表示運(yùn)行圖下行方向車站編號(hào)，R為車站總數(shù)。A= {a1，a2，…，am…，aM}是區(qū)間運(yùn)行線集合，P= {p1，p2，…，pn…，pN}是完整列車運(yùn)行線集合，一條完整列車運(yùn)行線由多條區(qū)間運(yùn)行線組成。為了方便表述，將同一列車區(qū)間運(yùn)行線am的后續(xù)緊鄰的區(qū)間運(yùn)行線定義為a′m，如p1= {a1，a2，a3}，a′1=a2，a′2=a3。列車Wn表示在完整列車運(yùn)行線pn上開行的列車。列車單元是由若干動(dòng)車與拖車組成的不可拆分的列車組成單位，同類型及不同類型的列車單元之間均可進(jìn)行組合或拆解以調(diào)整列車編組。列車單元與列車示意圖如圖2 所示。以2 種類型的列車單元U1和U2為例進(jìn)行說明，U1列車單元由3 個(gè)車輛組成，U2列車單元由4 個(gè)車輛組成。模型集合與參數(shù)如表1所示。

圖1 運(yùn)行圖示意圖Fig.1 Train operation diagram

模型的決策變量xe(am)為正整數(shù)變量，表示區(qū)間運(yùn)行線am上開行列車單元e的數(shù)量；yi(Wn) ∈ {0，1}表示列車Wn在車站i是否進(jìn)行組合拆解，yi(Wn) =1 表示進(jìn)行組合拆解，yi(Wn) = 0 表示不進(jìn)行組合拆解。

圖2 列車單元與列車示意圖Fig.2 Diagram of train unit and train

表1 模型集合與參數(shù)Tab.1 Sets and parameters of the model

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

高速鐵路可變編組列車開行計(jì)劃優(yōu)化模型以動(dòng)車組開行成本（包括固定成本和變動(dòng)成本）最小和組合拆解作業(yè)時(shí)間最短為優(yōu)化目標(biāo)，其中動(dòng)車組開行成本是各區(qū)間運(yùn)行線上各類型列車單元開行成本之和，固定成本是列車單元運(yùn)行必須產(chǎn)生的成本，變動(dòng)成本則與列車單元運(yùn)行單位距離費(fèi)用、列車單元數(shù)量和運(yùn)行距離有關(guān)。目標(biāo)函數(shù)為

模型具有以下約束條件。

（1）供給需求約束。在任一區(qū)間運(yùn)行線am上開行列車單元所提供的一等座、二等座數(shù)量必須大于或等于相應(yīng)的客流需求。

（2）站臺(tái)容車約束。每個(gè)區(qū)間任何1 列車完成編組后的長(zhǎng)度不可以超過站臺(tái)長(zhǎng)度。

（3）車站改編能力約束。每個(gè)車站每日安排的需要進(jìn)行組合、拆解的列車不能超過車站的改編能力。

（4）決策變量關(guān)系約束。當(dāng)同一列車在前、后緊鄰區(qū)間的編組列車單元e數(shù)量不相等時(shí)，列車在這2 個(gè)區(qū)間的銜接車站i需要進(jìn)行組合或拆解作業(yè)，反之則不需要組合拆解作業(yè)。

1.3 求解算法

以上模型是非線性整數(shù)規(guī)劃模型，直接求解存在困難，因而采用分支定界算法并分兩階段進(jìn)行求解。分支定界算法的基本思想是把原問題線性松弛后的可行域分解為范圍越來越小的子域，并檢查某子域內(nèi)整數(shù)解的情況，直至證實(shí)整數(shù)解不存在或求出最優(yōu)的整數(shù)解。令M1 (Xj)表示模型的1 個(gè)分支子問題，Xj為該分支上的子可行域。求解的步驟如下。

第一階段：只考慮開行成本最小的目標(biāo)及約束式(1)—(3)。

步驟1：初始化。先松弛問題的整數(shù)約束條件，求解其對(duì)應(yīng)的線性松弛問題，如果線性松弛問題的最優(yōu)解是整數(shù)解，則該整數(shù)解即為原問題的最優(yōu)解。據(jù)此得出各車次在各區(qū)段、各時(shí)段所需要各類型列車單元的最小數(shù)量xe(am)；否則，則將該線性規(guī)劃解作為最優(yōu)整數(shù)解的初始下界z-，并且設(shè)置初始上界z-為+∞。

步驟2：分支。分支是為整數(shù)解的出現(xiàn)創(chuàng)造條件。從任1 個(gè)子問題M1 (Xj)的不滿足整數(shù)限制的變量中挑選1 個(gè)進(jìn)行分析，通過加入1 對(duì)約束使子問題變?yōu)? 個(gè)帶進(jìn)一步約束條件的子問題。子問題的解若不滿足整數(shù)解則繼續(xù)進(jìn)行分支，各分支可形成1 個(gè)倒立的分支樹，分支樹的根節(jié)點(diǎn)就是對(duì)應(yīng)的線性規(guī)劃松弛問題，它后面有2 個(gè)子節(jié)點(diǎn)，每個(gè)子節(jié)點(diǎn)后面可能又會(huì)有2 個(gè)節(jié)點(diǎn)，以此類推，直至此節(jié)點(diǎn)不可行或找到了1 個(gè)整數(shù)節(jié)點(diǎn)。各節(jié)點(diǎn)表示各子問題，若此問題已被求解過，則稱此節(jié)點(diǎn)為封閉節(jié)點(diǎn)，未被求解則稱為開放節(jié)點(diǎn)。

步驟3：定界與剪枝。定界是制定“過濾篩選條件”，剪枝就是根據(jù)“過濾篩選條件”來剔除不好的解。下界根據(jù)各開放節(jié)點(diǎn)中的最小目標(biāo)函數(shù)值來確定，上界根據(jù)已找到的最優(yōu)的整數(shù)解來確定，由此不斷更新z-和z-。

步驟4：搜索迭代。每一次的分支過程即為一次搜索過程，在每次搜索中當(dāng)上界被更新后，檢查所有開放節(jié)點(diǎn)并封閉那些目標(biāo)值大于新上界的節(jié)點(diǎn)。這一剪枝過程可以明顯降低搜索和計(jì)算量。當(dāng)所有節(jié)點(diǎn)被封閉時(shí)，則標(biāo)志著所有搜索已完成，搜索過程中得到的最好整數(shù)解即為編組內(nèi)容結(jié)果xe(am)。

第二階段：根據(jù)第一階段求解的結(jié)果，結(jié)合約束式(5)來判斷組合拆解情況yi(Wn)。如果符合改編能力約束式(4)，則算法結(jié)束，計(jì)算否則進(jìn)入步驟5調(diào)整。

步驟5：對(duì)于不符合約束式(4)的yi(Wn)及相應(yīng)的xe(am)進(jìn)行調(diào)整，即如果某個(gè)車站每日安排的需要進(jìn)行組合、拆解的列車超過了車站的改編能力，則取消該車站適當(dāng)次數(shù)的改編作業(yè)(值最大的先取消)，取消后相應(yīng)的yi(Wn) = 1 變?yōu)閥i(Wn) = 0，相 應(yīng) 的xe(a′m) -xe(am) = 0，?e∈ {1，2，…，E}，返回步驟1。

2 案例分析

2.1 基礎(chǔ)數(shù)據(jù)

京滬高速鐵路全長(zhǎng)1 318 km，共有24 個(gè)車站?？紤]客流量情況，濟(jì)南西、徐州東、南京南是京滬線上的3 個(gè)重要節(jié)點(diǎn)[12]，因而重點(diǎn)考慮可變編組動(dòng)車組在這3 個(gè)技術(shù)站進(jìn)行站內(nèi)組合拆解作業(yè)。因此，將北京南、濟(jì)南西、徐州東、南京南、上海虹橋站這5 個(gè)車站作為本案例的研究對(duì)象，共形成4 個(gè)區(qū)段，4 個(gè)區(qū)段(按下行方向)的距離分別為406 km 和286 km，331 km 和295 km。在本案例中，考慮運(yùn)行有種類型的列車單元，類型一是由2 動(dòng)車1 拖車組成，類型二是由2 動(dòng)車2 拖車組成，2 動(dòng)車分別位于列車單元的首尾兩端，設(shè)動(dòng)車和拖車的長(zhǎng)度相等。案例共設(shè)計(jì)29 個(gè)車次(98 條區(qū)間運(yùn)行線)，其中下行15 個(gè)車次(51 條區(qū)間運(yùn)行線)，上行14 個(gè)車次(47 條區(qū)間運(yùn)行線)。根據(jù)可變編組客流預(yù)測(cè)研究結(jié)論[5]，各車次及區(qū)間對(duì)座位的需求量(部分)如表2 所示。

2.2 求解步驟

設(shè)置站臺(tái)長(zhǎng)度約束下的所允許編組的最多車輛數(shù)量l= 16 輛；1 個(gè)類型一可變編組列車單元提供的一等座座位數(shù)sI1= 38 個(gè)；1 個(gè)類型一可變編組列車單元提供的二等座座位數(shù)sII2= 163 個(gè)；1 個(gè)類型二可變編組列車單元提供的一等座座位數(shù)sI2= 65 個(gè)；1 個(gè)類型二可變編組列車單元提供的二等座座位數(shù)sII2= 218 個(gè)。某車次列車在某區(qū)段某時(shí)段的一、二等座座位需求量dI和dII如表2 所示。車站的改編能力gi= 50 列/d。列車在車站的最短、最長(zhǎng)組合或拆解時(shí)間分別為αi= 3 min，βi= 10 min。組合拆解作業(yè)時(shí)間按τi= 5 min 計(jì)算[13]。在開行成本方面，按車底數(shù)量比例進(jìn)行折算，得到開行1 個(gè)類型一列車單元的固定成本和變動(dòng)成本（即單位公里費(fèi)用）分別為c1= 37 500 元，為c′1= 112.5 元，開行1 個(gè)類型二列車單元的固定成本和變動(dòng)成本分別為c2=50 000 元，c′2= 150 元[14]。

將參數(shù)值代入模型，用分支定界算法求解得出各車次及區(qū)間需要的類型一和類型二列車單元的最小數(shù)量。以時(shí)間段6 : 35—13 : 57 為例，設(shè)計(jì)已知時(shí)刻表下可變編組列車編組情況(部分)如表3 所示。在列車的到、發(fā)時(shí)刻下方標(biāo)出上文計(jì)算得出的所需2 種列車單元的數(shù)量。

將客座利用率(座位需求量/定員數(shù))作為指標(biāo)之一，分別計(jì)算可變編組下行和上行方向的客座利用率，并與固定編組進(jìn)行比較分析(這里主要以二等座為例進(jìn)行對(duì)比)，得到可變編組與固定編組二等座客座利用率比較如表4 所示。固定編組列車即在列車運(yùn)行全程不進(jìn)行組合拆解作業(yè)。計(jì)算時(shí)，固定編組列車的編組內(nèi)容由該車次運(yùn)行線上客流量最大區(qū)間的客流需求決定，以保證供給滿足需求。

可變編組與固定編組客座利用率對(duì)比如表5 所示。由表5 計(jì)算可得客座利用率優(yōu)化的平均百分比為8.47%。

表2 各車次及區(qū)段對(duì)座位的需求量(部分) 個(gè)Tab.2 Demand of seats for each train in each section (Excerpts)

3 結(jié)束語

基于可變編組的高速鐵路列車開行計(jì)劃優(yōu)化，對(duì)于提升高速鐵路客運(yùn)供需匹配和服務(wù)品質(zhì)、提高動(dòng)車組的運(yùn)用效率、減少動(dòng)車組的運(yùn)用成本等方面都有著重要的理論和現(xiàn)實(shí)意義。針對(duì)可變編組的列車單元運(yùn)用模式，構(gòu)建可變編組高鐵列車開行計(jì)劃優(yōu)化模型，在京滬高速鐵路案例中應(yīng)用上述模型，采用分支定界算法，求解得出可變編組列車在哪些站進(jìn)行組合拆解作業(yè)以及各區(qū)段各時(shí)段的列車編組內(nèi)容，并根據(jù)運(yùn)行時(shí)刻繪制可變編組運(yùn)行圖，計(jì)算得出可變編組客座利用率相比同等條件下固定編組列車有較為顯著的提高。但是，目前列車開行計(jì)劃與運(yùn)行圖以及動(dòng)車組運(yùn)用計(jì)劃尚未實(shí)現(xiàn)完全的一體化自動(dòng)化編制，這也是未來的一個(gè)努力方向。

表3 已知時(shí)刻表下可變編組列車編組情況(部分)Tab.3 Marshalling content of variable configuration trains under the given timetable (Excerpts)

表4 可變編組與固定編組二等座客座利用率比較Tab.4 Comparison of load factor ratios for economy class between variable and fixed configuration train

表5 可變編組與固定編組客座利用率對(duì)比 %Tab.5 Comparison of load factor ratios between variable and fixed configuration train