?；菝?/p>

(蘭州交通大學(xué)，交通運(yùn)輸學(xué)院，蘭州730070)

0 引言

努力向旅客提供高質(zhì)量的空間位移服務(wù)，并以列車時(shí)刻表的形式向社會(huì)公布，是軌道交通運(yùn)輸組織的核心。在軌道交通內(nèi)部，列車時(shí)刻表的時(shí)空?qǐng)D示形式又稱為列車運(yùn)行圖，它規(guī)定了列車占用區(qū)間的次序，以及在每一個(gè)車站的到達(dá)、出發(fā)和通過(guò)時(shí)刻。列車運(yùn)行圖是軌道運(yùn)營(yíng)企業(yè)最重要的技術(shù)文件，是協(xié)調(diào)不同部門、環(huán)節(jié)進(jìn)行運(yùn)輸生產(chǎn)活動(dòng)的基礎(chǔ)，以及軌道線路能力查定的依據(jù)[1-3]。對(duì)于社會(huì)而言，列車時(shí)刻表則是連接運(yùn)營(yíng)商和出行者的橋梁，以及乘客安排出行活動(dòng)的依據(jù)。

其他公共交通方式，如城市公交、民用航空、客運(yùn)輪渡、城際道路客運(yùn)等，都涉及時(shí)刻表問(wèn)題。當(dāng)公共交通系統(tǒng)的基礎(chǔ)設(shè)施(如線路、車站、碼頭、航站等)、或運(yùn)輸裝備(牽引、制動(dòng)、通訊、容量等)產(chǎn)生了變化、或客流需求(大小、時(shí)空分布)出現(xiàn)了較大波動(dòng)時(shí)，都需要根據(jù)變化的運(yùn)營(yíng)環(huán)境或客流需求，重新設(shè)計(jì)新的運(yùn)營(yíng)時(shí)刻表。相比較而言，由于軌道交通特有的封閉性和排他性約束，使得列車時(shí)刻表問(wèn)題更加復(fù)雜。軌道列車時(shí)刻表的設(shè)計(jì)，是一類具有廣泛應(yīng)用背景的調(diào)度優(yōu)化問(wèn)題。

列車時(shí)刻表問(wèn)題(Train Timetabling Problem)，最大的困難是如何處理不同列車占用軌道資源引發(fā)的時(shí)空沖突，這種時(shí)空沖突與列車運(yùn)行追蹤、越行、交匯耦合在一起，構(gòu)成了復(fù)雜的約束條件。該類問(wèn)題的優(yōu)化，是在特定的時(shí)空網(wǎng)絡(luò)中，為每個(gè)列車確定一條合理的運(yùn)行路徑，使基于用戶的度量指標(biāo)(如乘客候車時(shí)間)、或企業(yè)的度量指標(biāo)(如運(yùn)營(yíng)費(fèi)用)等實(shí)現(xiàn)最優(yōu)，并滿足嚴(yán)格的運(yùn)行安全要求。軌道列車時(shí)刻表的優(yōu)化，數(shù)學(xué)上是典型的大規(guī)模、多目標(biāo)、強(qiáng)耦合的整數(shù)或0-1規(guī)劃問(wèn)題，其中加入需求因素并嵌入旅客行為，將使問(wèn)題變得異常復(fù)雜。根據(jù)不同的運(yùn)營(yíng)環(huán)境和實(shí)踐要求，構(gòu)建列車時(shí)刻表合理的數(shù)學(xué)模型、設(shè)計(jì)有效可靠的求解算法，是一類非常具有挑戰(zhàn)性的科學(xué)難題。

廣泛的應(yīng)用場(chǎng)景和復(fù)雜的計(jì)算挑戰(zhàn)，使得軌道列車時(shí)刻表問(wèn)題，多年來(lái)一直是國(guó)際交通運(yùn)輸及運(yùn)籌管理學(xué)界的熱點(diǎn)研究問(wèn)題[4-10]。特別值得一提的是，該問(wèn)題具有表述簡(jiǎn)單明確、不需要太多的專門知識(shí)；包容性強(qiáng)、可以融合多個(gè)子問(wèn)題，如列車停站、動(dòng)車組調(diào)度、客流控制等；數(shù)學(xué)模型是典型的大規(guī)模NP問(wèn)題，可以結(jié)合問(wèn)題背景，設(shè)計(jì)求解模型的多種啟發(fā)式方法。正是由于這些原因，在一些著名的國(guó)際交通運(yùn)輸類期刊上，如Transportation Research Part B、Part C、Transportation Science 等，以及運(yùn)籌管理類期刊，如Operations Research、European Journal of Operational Research等，經(jīng)?？梢砸?jiàn)到研究列車時(shí)刻表問(wèn)題的論文。

1 研究問(wèn)題

1.1 列車時(shí)刻表問(wèn)題

按照荷蘭學(xué)者Goossens等[11]的觀點(diǎn)，列車時(shí)刻表設(shè)計(jì)是整個(gè)軌道交通運(yùn)營(yíng)規(guī)劃的一個(gè)子問(wèn)題，向上是線路規(guī)劃問(wèn)題(Line Planning Problem)，向下則是動(dòng)車組調(diào)度問(wèn)題(Rolling Stock Scheduling Problem)。

單純的列車時(shí)刻表問(wèn)題，是在一條軌道交通線路或走廊上，確定所有列車在每一個(gè)車站的到達(dá)、出發(fā)和通過(guò)時(shí)刻，也稱為基于線路的列車時(shí)刻表(Line-Based Train Timetable)。在直角坐標(biāo)平面內(nèi)，以時(shí)間為橫軸、空間為縱軸，可以組成二維時(shí)空平面。在時(shí)空平面中，按照一定的比例關(guān)系，將列車運(yùn)行軌跡用若干條線段連接起來(lái)，就可得到相應(yīng)的列車運(yùn)行線。對(duì)于所考慮的軌道線路，全體列車運(yùn)行線的總體，稱為該線路的列車運(yùn)行圖。

需要特別指出的是，在研究軌道列車時(shí)刻表及相關(guān)問(wèn)題時(shí)，為了直觀地展示所研究的內(nèi)容，通常會(huì)畫(huà)出列車運(yùn)行圖的簡(jiǎn)化形式。其中仍然以時(shí)間和空間為維度，但不必硬性規(guī)定橫軸與縱軸的具體所指(時(shí)間、空間)；最重要的是，不深究各類對(duì)象的準(zhǔn)確坐標(biāo)，而重點(diǎn)關(guān)注它們之間的時(shí)空邏輯關(guān)系，如兩個(gè)節(jié)點(diǎn)之間相對(duì)的左右、上下位置，這樣得到的列車運(yùn)行時(shí)空?qǐng)D示，稱為列車運(yùn)行時(shí)空網(wǎng)絡(luò)(Space-Time Network)。

線路規(guī)劃問(wèn)題，就是具體確定列車運(yùn)行區(qū)段、種類、停站方案、時(shí)段發(fā)車頻率、編組長(zhǎng)度等，這些內(nèi)容大部分和旅客需求相關(guān)。換言之，線路規(guī)劃是根據(jù)客流需求特征，確定的列車輪廓運(yùn)行計(jì)劃，體現(xiàn)了客流需求對(duì)列車服務(wù)的基本訴求。在隨后的列車時(shí)刻表階段，則把線路規(guī)劃中的內(nèi)容作為給定的輸入，使待求解問(wèn)題在相對(duì)簡(jiǎn)單的環(huán)境下進(jìn)行。在我國(guó)學(xué)術(shù)和企業(yè)界，線路規(guī)劃常用另一個(gè)含義基本相同的概念“列車開(kāi)行方案”所代替。

動(dòng)車組調(diào)度問(wèn)題，是在已經(jīng)設(shè)計(jì)好的列車時(shí)刻表上，為每條列車運(yùn)行線(或稱為任務(wù))指派一個(gè)動(dòng)車組(或車底)，要求每個(gè)任務(wù)有且只有一個(gè)動(dòng)車組來(lái)完成，該問(wèn)題也稱為動(dòng)車組運(yùn)用問(wèn)題或車底交路問(wèn)題。動(dòng)車組運(yùn)用所產(chǎn)生的費(fèi)用，是軌道交通運(yùn)營(yíng)階段所耗費(fèi)的主要支出。因此，當(dāng)所研究問(wèn)題涉及企業(yè)運(yùn)營(yíng)成本時(shí)，則一般需要考慮動(dòng)車組使用情況。通過(guò)在時(shí)空網(wǎng)絡(luò)上進(jìn)行適當(dāng)?shù)淖儞Q，動(dòng)車組調(diào)度問(wèn)題等價(jià)于多車場(chǎng)車輛調(diào)度問(wèn)題(Multiple-Depot Vehicle Scheduling Problem)。

在列車時(shí)刻表問(wèn)題中，通過(guò)把線路規(guī)劃中的某些內(nèi)容松弛為決策變量，或者在構(gòu)模階段直接考慮客流需求，可以生成更高質(zhì)量的列車服務(wù)產(chǎn)品；此外，也可以在列車時(shí)刻表優(yōu)化階段，同步考慮動(dòng)車組調(diào)度問(wèn)題，以獲得運(yùn)營(yíng)成本更低的方案。目前列車時(shí)刻表領(lǐng)域的研究選題，大部分都是這樣融合的結(jié)果。

1.2 新增列車運(yùn)行線問(wèn)題

這個(gè)問(wèn)題來(lái)自于現(xiàn)實(shí)。由于旅客需求發(fā)生了明顯變化，或線路基礎(chǔ)設(shè)施如信號(hào)聯(lián)鎖系統(tǒng)進(jìn)行了改造，既有的列車時(shí)刻表不再滿足新環(huán)境的要求，需要在現(xiàn)有的列車運(yùn)行圖中，增加新的列車運(yùn)行線，并對(duì)已有的運(yùn)行線進(jìn)行同步調(diào)整。在已有的運(yùn)行圖中插入新的列車運(yùn)行線，這一思想在我國(guó)有著廣泛的應(yīng)用。時(shí)至今日，我國(guó)客貨共線的列車運(yùn)行圖，都是先編制旅客列車運(yùn)行圖，然后插入盡可能多的貨物列車運(yùn)行線。然而，該問(wèn)題在理論研究層面，卻是歐洲學(xué)者的工作更有系統(tǒng)性，其中意大利學(xué)者的研究成果最有影響。

新增列車運(yùn)行線問(wèn)題，包含新列車運(yùn)行線插入和既有列車運(yùn)行線調(diào)整，兩部分內(nèi)容關(guān)聯(lián)在一起，使得問(wèn)題十分復(fù)雜。博洛尼亞大學(xué)Caprara 教授等[8]針對(duì)一條鐵路走廊，在固定列車停站和越行模式、允許部分列車調(diào)整到發(fā)時(shí)刻及停站時(shí)間的條件下，構(gòu)建了線性整數(shù)規(guī)劃模型，用以解決新增列車運(yùn)行線的問(wèn)題。隨后，Caprara等[12]進(jìn)一步考慮了信號(hào)系統(tǒng)、車站能力、運(yùn)營(yíng)維修等因素對(duì)該問(wèn)題的影響，開(kāi)發(fā)了相應(yīng)的計(jì)算機(jī)軟件系統(tǒng)，在意大利鐵路(RFI)的運(yùn)能分配和時(shí)刻表編制中得到了廣泛應(yīng)用。2009年，昆士蘭理工大學(xué)Burdett 等[13]將新增列車運(yùn)行線問(wèn)題刻畫(huà)為一個(gè)帶有時(shí)間窗約束的車間作業(yè)調(diào)度(Job-shop Scheduling)問(wèn)題，以保證即有和新增運(yùn)行線的有效融合，并在特制的分離圖上運(yùn)用元啟發(fā)式算法求解模型。2010年，博洛尼亞大學(xué)Cacchiani 等[14]考慮了在旅客列車時(shí)刻表中插入貨物列車運(yùn)行線的問(wèn)題，其中旅客列車運(yùn)行線固定，目標(biāo)是優(yōu)化貨物列車時(shí)刻表和停站方案，模型對(duì)每個(gè)貨物列車預(yù)先指定理想時(shí)刻表，然后在迭代過(guò)程中不斷修改調(diào)整。最近，Jiang等[15]以我國(guó)京滬高鐵為背景，根據(jù)客流需求的特征，研究了如何在現(xiàn)有列車運(yùn)行圖中插入新的列車運(yùn)行線，特別考慮了優(yōu)化過(guò)程中允許部分列車增加停站、取消停站、延長(zhǎng)停站時(shí)間等問(wèn)題。

1.3 列車實(shí)時(shí)調(diào)度問(wèn)題

列車實(shí)時(shí)調(diào)度，是指當(dāng)前的列車運(yùn)行受到非正常或隨機(jī)干擾后，計(jì)劃的列車時(shí)刻表不再可行，需要對(duì)部分或全部列車的運(yùn)行計(jì)劃進(jìn)行實(shí)時(shí)調(diào)整，以獲得新的列車運(yùn)行方案。從本質(zhì)上講，列車實(shí)時(shí)調(diào)度就是根據(jù)變化的運(yùn)營(yíng)環(huán)境，重新設(shè)計(jì)或修改一個(gè)新的列車時(shí)刻表。研究該問(wèn)題，可以將原有的計(jì)劃列車時(shí)刻表作為理想時(shí)刻表，并將當(dāng)前與理想時(shí)刻表之間的偏差最小作為優(yōu)化目標(biāo)。長(zhǎng)期以來(lái)，軌道列車實(shí)時(shí)調(diào)度調(diào)整，始終是本領(lǐng)域一個(gè)熱門研究選題，引起了眾多學(xué)者的關(guān)注。

列車運(yùn)行必須受限于當(dāng)前車站、線路的狀態(tài)，是研究實(shí)時(shí)調(diào)度問(wèn)題的基本要求，荷蘭代爾夫特理工大學(xué)Corman等[16]針對(duì)時(shí)空網(wǎng)絡(luò)中存在的瓶頸路徑，提出了基于“綠波”實(shí)時(shí)控制策略的替代圖模型，采用分支定界算法進(jìn)行求解，該方法在運(yùn)營(yíng)區(qū)段稍短、列車速度差較小、車站能力充足條件下具有很強(qiáng)的適用性。Lusby等[17]以最小化現(xiàn)實(shí)與計(jì)劃之間的列車運(yùn)行偏離為目標(biāo)，將樞紐站列車實(shí)時(shí)調(diào)度描述為集合覆蓋問(wèn)題。2011年，孟令云和周學(xué)松[18]以單線鐵路為背景，在列車運(yùn)行時(shí)間及干擾持續(xù)時(shí)間不確定的情況下，基于不同的干擾場(chǎng)景建立隨機(jī)優(yōu)化模型，采用滾動(dòng)時(shí)域算法求解列車實(shí)時(shí)調(diào)度問(wèn)題。挪威學(xué)者Lamorgese等[19]把列車調(diào)度調(diào)整問(wèn)題分解為線路列車運(yùn)行調(diào)整及車站列車運(yùn)行調(diào)整兩個(gè)子問(wèn)題，前者在保證列車不同時(shí)占用不兼容線路的前提下，最小化與計(jì)劃列車時(shí)刻表之間的偏差；后者優(yōu)化列車在車站的路徑和到發(fā)時(shí)刻，建立混合整數(shù)規(guī)劃模型，利用近似Benders 方法進(jìn)行求解，所研發(fā)的列車時(shí)刻表優(yōu)化系統(tǒng)于2014年在挪威J?rbane鐵路線上開(kāi)始應(yīng)用。

1.4 列車時(shí)刻表和停站協(xié)同優(yōu)化

在列車時(shí)刻表問(wèn)題中融入線路規(guī)劃的某些內(nèi)容，可以產(chǎn)生許多延伸問(wèn)題，最著名的是列車時(shí)刻表與停站協(xié)同優(yōu)化問(wèn)題。表面上看，列車停站應(yīng)嵌套于時(shí)刻表問(wèn)題中，因?yàn)楦鶕?jù)列車在一個(gè)站的到達(dá)和出發(fā)時(shí)刻，就可以決定列車是否在該站停車。但從分層規(guī)劃的視角看，列車停站屬于上層的線路規(guī)劃問(wèn)題，而在單純的時(shí)刻表問(wèn)題中，總是假設(shè)列車停站模式已經(jīng)給定。數(shù)學(xué)上，如需在時(shí)刻表問(wèn)題中考慮列車停站，則在構(gòu)模階段，由于受列車最小停站時(shí)間的約束，必須設(shè)置新的0-1停站變量，才能構(gòu)建時(shí)刻表和停站的協(xié)同優(yōu)化模型。

北京交通大學(xué)楊立興等[20]針對(duì)一條高速鐵路走廊，把列車停站決策作為約束條件嵌入到時(shí)刻表問(wèn)題中，以總的列車停站時(shí)間和延誤時(shí)間最小為目標(biāo)函數(shù)，構(gòu)建了時(shí)刻表和停站協(xié)同優(yōu)化的多目標(biāo)線性整數(shù)規(guī)劃模型，并運(yùn)用CPLEX 求解模型。2017年，法國(guó)Altazin等[21]研究了城市軌道交通列車調(diào)整問(wèn)題，其中嵌入了列車停站選擇變量，在考慮動(dòng)車組約束條件下，通過(guò)最小化系統(tǒng)恢復(fù)時(shí)間和乘客等待時(shí)間，構(gòu)建了線性整數(shù)規(guī)劃模型。商攀等[22]在一條超擁擠的地鐵線路上，運(yùn)用多維時(shí)空網(wǎng)絡(luò)建模方法，研究了基于乘客候車公平的列車停站優(yōu)化問(wèn)題。需要特別指出的是，在列車時(shí)刻表和停站協(xié)同優(yōu)化中，只有直接或間接考慮了客流需求，才有可能得出有價(jià)值的研究成果。

1.5 列車時(shí)刻表和動(dòng)車組調(diào)度協(xié)同優(yōu)化

列車時(shí)刻表優(yōu)化目的，主要在于提高旅客服務(wù)質(zhì)量，而最小化運(yùn)營(yíng)成本則是動(dòng)車組調(diào)度的首要目標(biāo)，將兩者結(jié)合起來(lái)尋找服務(wù)與成本之間最佳妥協(xié)，是該領(lǐng)域多年來(lái)另一個(gè)熱門研究選題。2014年，荷蘭鹿特丹大學(xué)Kroon 等[23]在構(gòu)建周期化列車時(shí)刻表PESP(Periodic Event Scheduling Problem)模型時(shí)，考慮了動(dòng)車組與乘客之間的柔性接續(xù)問(wèn)題，即預(yù)先不指定兩個(gè)列車之間的鏈接關(guān)系，而是通過(guò)求解所構(gòu)建的數(shù)學(xué)模型，得到期望的列車時(shí)刻表和動(dòng)車組周轉(zhuǎn)方案，他們開(kāi)發(fā)的列車運(yùn)行圖自動(dòng)編制DONS(Designer Of Network Schedules)系統(tǒng)，成功應(yīng)用于荷蘭鐵路運(yùn)營(yíng)管理決策。2018年，丹麥理工大學(xué)Fonseca等[24]為了方便乘客在不同軌道線路上的換乘，研究了列車時(shí)刻表和動(dòng)車組調(diào)度的協(xié)同優(yōu)化，以最小化旅客換乘費(fèi)用和企業(yè)運(yùn)營(yíng)成本為目標(biāo)函數(shù)，構(gòu)建了雙目標(biāo)混合整數(shù)規(guī)劃模型，通過(guò)調(diào)整列車出發(fā)時(shí)間和延后列車停站時(shí)間，設(shè)計(jì)了求解模型的元啟發(fā)式算法。荷蘭埃因霍芬理工大學(xué)Veelenturf等[25]考慮了列車及動(dòng)車組、乘務(wù)組實(shí)時(shí)調(diào)度協(xié)同優(yōu)化問(wèn)題，在考慮動(dòng)車組能力約束的條件下，以最小化取消和延誤列車數(shù)量為目標(biāo)，構(gòu)建線性整數(shù)規(guī)劃模型。

1.6 面向需求列車時(shí)刻表優(yōu)化

實(shí)際上，客流需求是列車時(shí)刻表設(shè)計(jì)最重要的考慮因素。從本質(zhì)上講，盡可能實(shí)現(xiàn)客流需求與列車運(yùn)行線時(shí)空分布的最佳匹配，使列車服務(wù)的提供者和使用者共同受益，是列車時(shí)刻表優(yōu)化的終極目標(biāo)。然而，客流需求具有明顯的連續(xù)與時(shí)變特點(diǎn)，而列車運(yùn)行線則有離散與穩(wěn)定屬性，將兩者有效地耦合為一個(gè)整體，確實(shí)是一件非常艱巨的任務(wù)。早期列車時(shí)刻表問(wèn)題的研究，為了簡(jiǎn)化模型和求解，構(gòu)模階段不直接使用客流需求數(shù)據(jù)，而將重點(diǎn)放在如何處理股道占用沖突和列車運(yùn)行安全上，相應(yīng)的問(wèn)題常稱為面向供給的列車時(shí)刻表(Supply-Oriented Train Timetable)優(yōu)化。

值得注意的是，許多研究列車時(shí)刻表問(wèn)題的文獻(xiàn)，盡管沒(méi)有直接使用客流需求，但通過(guò)在上層線路規(guī)劃中設(shè)置相關(guān)參數(shù)，間接地考慮了客流需求。如列車在始發(fā)站的出發(fā)時(shí)間范圍、理想出發(fā)時(shí)刻，以及時(shí)段內(nèi)開(kāi)行的列車數(shù)、車站最少停站列車數(shù)等，基本上都是客流需求影響的結(jié)果。使用這些參數(shù)，就是在列車時(shí)刻表問(wèn)題中間接地考慮了客流需求。在列車時(shí)刻表問(wèn)題中，直接使用時(shí)變的OD需求，是該領(lǐng)域近年來(lái)的研究熱點(diǎn)。根據(jù)統(tǒng)計(jì)時(shí)間單位選擇的不同，可以生成不同的OD客流需求。在列車時(shí)刻表問(wèn)題中，最常用的是基于小時(shí)(Hour-Dependent)和基于分鐘(Minute-Dependent)的OD需求。

2013年，Niu 和周學(xué)松[26]研究了時(shí)變和超擁擠條件下城市軌道列車時(shí)刻表的優(yōu)化問(wèn)題，從理論上揭示了軌道列車與乘客的耦合關(guān)系，建立了動(dòng)車組數(shù)量給定條件下面向需求列車時(shí)刻表非線性整數(shù)規(guī)劃模型。加拿大蒙特利爾大學(xué)Barrena等[27]對(duì)于時(shí)變需求下的列車時(shí)刻表問(wèn)題，提出了兩種非線性規(guī)劃模型，目的是最小化每個(gè)時(shí)段旅客的平均等待時(shí)間，通過(guò)反復(fù)刪除或添加列車運(yùn)行線，建立了基于自適應(yīng)鄰域搜索的快速迭代算法。Hassannayebi等[28]在列車能力和股道資源約束下，以一條城市軌道交通線路為背景，以乘客的平均等待時(shí)間最小為目標(biāo)函數(shù)，構(gòu)建基于路徑變量的非線性整數(shù)規(guī)劃模型，設(shè)計(jì)了求解模型的拉格朗日松弛算法，得到了期望的列車時(shí)刻表。2018年，石俊剛等[29]針對(duì)超擁擠的城市軌道交通系統(tǒng)，研究時(shí)變需求環(huán)境下列車時(shí)刻表和客流控制的協(xié)同優(yōu)化問(wèn)題，目標(biāo)函數(shù)為最小化乘客在車站的候車時(shí)間，最后計(jì)算結(jié)果在得到最優(yōu)列車時(shí)刻表的同時(shí)，還給出了避免站臺(tái)擁擠的客流控制策略。

2 建模方法

2.1 決策變量

合理設(shè)置問(wèn)題的決策變量，是正確構(gòu)建列車時(shí)刻表數(shù)學(xué)模型的關(guān)鍵。在研究列車時(shí)刻表問(wèn)題時(shí)，現(xiàn)有文獻(xiàn)通常將時(shí)間軸按1 min(0.5 min或更小)進(jìn)行等間隔劃分，并假定系統(tǒng)中所有活動(dòng)都發(fā)生在這些整數(shù)分割點(diǎn)上?；谶@一事實(shí)，通過(guò)引入整數(shù)變量表示列車在車站的到達(dá)和出發(fā)時(shí)間，可以完整地刻畫(huà)列車時(shí)刻表模型，但這種方法僅適用于沒(méi)有列車越行的城市軌道交通或短距離城際鐵路。如果考慮列車越行，則需要設(shè)置用以描述列車在車站出發(fā)順序的0-1變量，才能正確地構(gòu)建模型。如在Liu等[30]、Shafia 等[31]、許紅等[62]構(gòu)建的列車時(shí)刻表模型中，均使用了表示列車出發(fā)順序的邏輯變量。當(dāng)然，如果在列車時(shí)刻表問(wèn)題考慮列車停站優(yōu)化，則需要設(shè)置列車在車站是否停站的0-1 決策變量，如Yang等[20]、Altazin等[21]研究文獻(xiàn)中均設(shè)置了這樣的邏輯變量。

利用0、1 組成的變量序列，可以表示離散、時(shí)變的事件狀態(tài)，其中在事件未發(fā)生前的時(shí)間點(diǎn)變量取值為0(或1)、而在事件發(fā)生及以后的時(shí)間點(diǎn)取值為1(或0)，這樣的變量序列稱為累積0-1 變量。運(yùn)用累積0-1 變量，可以刻畫(huà)許多復(fù)雜的時(shí)變系統(tǒng)。2013年，Niu和周學(xué)松[26]用累積0-1變量的方法刻畫(huà)面向需求的列車時(shí)刻表問(wèn)題，此后又有多篇文獻(xiàn)(Meng 等[32]，Shi 等[33])用該方法構(gòu)建軌道列車調(diào)度問(wèn)題。需要特別指出的是，當(dāng)使用商用優(yōu)化軟件(如CPLEX)求解0-1 整數(shù)規(guī)劃模型時(shí)，如果模型中0-1變量的數(shù)目過(guò)多，將嚴(yán)重降低算法求解效率。

如上文所述，軌道列車運(yùn)行線可以視為時(shí)空網(wǎng)絡(luò)中的列車運(yùn)行路徑。以此為基礎(chǔ)，通過(guò)使用0-1邏輯變量，可以構(gòu)建基于路徑的列車時(shí)刻表模型。通常有兩種變量設(shè)置方法：一種是直接設(shè)置0-1 路徑變量，如Cacchiani 等[34]、Fischetti[35]等研究文獻(xiàn)，均定義了0-1 路徑變量；另一種是不直接使用路徑變量，而用0-1 路段變量間接表示時(shí)空網(wǎng)絡(luò)中路徑的選擇結(jié)果，如Caprara 等[8,12]、Cacchiani 等[14]、江峰等[60]均利用了0-1 路段變量，構(gòu)建了相應(yīng)的列車時(shí)刻表模型。但不管是哪一種設(shè)置，后續(xù)使用算法都不直接求解所構(gòu)建的0-1 規(guī)劃問(wèn)題，而是選擇對(duì)偶分解技術(shù)，將其轉(zhuǎn)化為多列車最短路徑問(wèn)題來(lái)求解。

2.2 約束條件

軌道列車時(shí)刻表問(wèn)題，需要考慮多種復(fù)雜的約束條件，以保證列車運(yùn)行安全及不同要素間的合理耦合等，主要包括：描述單列車車站到達(dá)和出發(fā)時(shí)刻、車站停留時(shí)間、區(qū)間運(yùn)行時(shí)間的關(guān)聯(lián)方程；反映多列車車站出發(fā)、到達(dá)間隔時(shí)間約束，以及列車越行耦合約束；基于車站股道占用、列車載客人數(shù)的能力約束。面向需求的列車時(shí)刻表問(wèn)題，還要考慮客流需求和列車之間的關(guān)聯(lián)匹配約束。一般而言，如果在列車時(shí)刻表問(wèn)題中嵌入了其他問(wèn)題(如列車停站)，都需要考慮不同變量間的關(guān)聯(lián)約束。

為順利求解列車時(shí)刻表這類復(fù)雜的離散優(yōu)化問(wèn)題，約束條件中還通常包括縮小列車活動(dòng)空間的限制約束，如列車在始發(fā)站出發(fā)時(shí)間窗約束等。必須承認(rèn)的是，縮小列車的活動(dòng)范圍是一種無(wú)奈選擇，如何使這類約束設(shè)置既相對(duì)合理，又不影響隨后的模型求解，是一件非常有意義的工作，高如虎和Niu[36]對(duì)此做了新的嘗試。

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

軌道列車時(shí)刻表設(shè)計(jì)，可以從運(yùn)營(yíng)者和乘客兩個(gè)角度設(shè)置優(yōu)化目標(biāo)。從運(yùn)營(yíng)者角度來(lái)考慮，總是希望成本及消耗性指標(biāo)最小，或列車運(yùn)行盡可能接近某種理想的方案，具體的目標(biāo)函數(shù)包括，基于列車走行時(shí)間或動(dòng)車組運(yùn)用的費(fèi)用成本最小(Zhou等[47,54])，基于列車運(yùn)行和停站的能源消耗最少(Huang等[37]，Yin等[38-39])，現(xiàn)實(shí)與理想列車時(shí)刻表之間的偏離最小(Burdett等[13]，Caprara等[8,12])。從乘客角度來(lái)考慮，優(yōu)化目標(biāo)包括乘客在車站等候時(shí)間最小(Niu等[26]，Barrena等[27]，李得偉等[59])、車內(nèi)擁擠費(fèi)用最少(Niu 等[50])，以及乘客的旅行時(shí)間最小(Sparing 等[40]，田小鵬和Niu[10]，廖正文等[61]，朱宇婷等[63])等。

基于以上考慮，可以構(gòu)建列車時(shí)刻表問(wèn)題的數(shù)學(xué)模型。迄今為止，這些模型均為線性整數(shù)或0-1規(guī)劃問(wèn)題。由于某些特殊原因，模型中有時(shí)會(huì)出現(xiàn)非線性表達(dá)式，利用通常的數(shù)學(xué)轉(zhuǎn)換，可得到等價(jià)的線性模型，如石俊剛等[29]就采用這種方法處理模型中的非線性項(xiàng)。特別注意的是，如果在列車時(shí)刻表問(wèn)題中考慮了時(shí)變的OD需求，就會(huì)導(dǎo)致目標(biāo)函數(shù)中出現(xiàn)2次項(xiàng)(Niu等[46])。

3 求解算法

列車時(shí)刻表問(wèn)題優(yōu)化具有明確的應(yīng)用背景，數(shù)學(xué)模型是大規(guī)模的NP 問(wèn)題，任何無(wú)實(shí)質(zhì)性數(shù)值測(cè)算的理論研究，科學(xué)意義都非常有限。學(xué)術(shù)界的基本共識(shí)是，算法設(shè)計(jì)是列車時(shí)刻表問(wèn)題最為重要和困難的部分。以下4類算法，是目前求解列車時(shí)刻表問(wèn)題文獻(xiàn)中最常用的方法。

3.1 智能搜索方法

由于列車時(shí)刻表問(wèn)題固有的離散性，運(yùn)用智能搜索方法，如遺傳算法(GA)等，就成為解決此類問(wèn)題的首選，特別是對(duì)于不考慮越行情況的列車時(shí)刻表問(wèn)題，智能算法的求解效率非常高。

1997年，德國(guó)學(xué)者Nachtigall 等[41]在研究周期性列車時(shí)刻表時(shí)，運(yùn)用基于模糊邏輯的復(fù)合遺傳算法求解所構(gòu)建的雙目標(biāo)模型。Robenek等[42]提出面向用戶的列車時(shí)刻表，新時(shí)刻表繼承了周期運(yùn)行圖的規(guī)則性和非周期運(yùn)行圖的靈活性，用模擬退火算法求解問(wèn)題，算法的核心思想是在保持乘客滿意度最大的條件下，逐漸消除多個(gè)列車之間可能的時(shí)空沖突。2017年，Huang等[37]考慮了乘客旅行時(shí)間和列車運(yùn)行中能源消耗，構(gòu)建了列車時(shí)刻表優(yōu)化的多目標(biāo)規(guī)劃模型，設(shè)計(jì)了禁忌搜索算法求解模型。2019年，Nitisiri等[43]以最小化乘客等待時(shí)間和列車運(yùn)營(yíng)成本為目標(biāo)，構(gòu)建了非越行環(huán)境下列車調(diào)度的雙目標(biāo)整數(shù)規(guī)劃模型，提出了求解模型的并行多目標(biāo)遺傳算法，其中使用了混合抽樣策略和基于學(xué)習(xí)的變異操作。

對(duì)于包含有越行情況的列車時(shí)刻表問(wèn)題，由于不同變量之間的強(qiáng)耦合特征，使得智能搜索算法的求解效率明顯降低。此外，智能算法有一個(gè)難以克服的缺陷，就是不能準(zhǔn)確地度量當(dāng)前解與最優(yōu)解的偏離程度。需要指出的是，對(duì)于確實(shí)沒(méi)有更好方法的列車時(shí)刻表問(wèn)題，選擇智能算法仍然不失為一個(gè)明智之舉。

3.2 模型修改方法

基于模型修改的啟發(fā)式方法，始終是求解列車時(shí)刻表問(wèn)題最重要的方法。這類算法的核心是，對(duì)原始模型(或相應(yīng)架構(gòu))進(jìn)行適當(dāng)修改或簡(jiǎn)化，然后使用商用優(yōu)化求解軟件(如GAMS 等)并結(jié)合其他優(yōu)化技術(shù)，直接求解更新后的模型。

蒙特利爾大學(xué)Barrena 等[44]在求解列車時(shí)刻表問(wèn)題時(shí)，通過(guò)重新定義一組客流變量，將非線性的乘客等待時(shí)間轉(zhuǎn)化為線性表達(dá)式，得到了與原問(wèn)題等價(jià)的線性整數(shù)規(guī)劃模型，然后利用CPLEX 設(shè)計(jì)了求解模型的啟發(fā)式算法。王義惠等[45]在研究地鐵列車實(shí)時(shí)調(diào)度問(wèn)題時(shí)，針對(duì)模型中存在非光滑、非凸函數(shù)的事實(shí)，通過(guò)修改模型設(shè)計(jì)了基于梯度的2 次規(guī)劃序列迭代求解算法。2016年，楊立興等[20]在研究列車時(shí)刻表和停站協(xié)同優(yōu)化問(wèn)題時(shí)，通過(guò)引入列車出發(fā)順序的0-1 變量，來(lái)刻畫(huà)列車安全間隔及列車越行約束，通過(guò)線性加權(quán)及約束修改的方法得到了單目標(biāo)混合整數(shù)規(guī)劃模型，最后利用CPLEX優(yōu)化軟件求解模型。

列車時(shí)刻表問(wèn)題的極端復(fù)雜性，對(duì)求解算法提出了更高要求，任何在算法方面的改進(jìn)嘗試都是一件非常有意義的工作。2017年，荷蘭代爾夫理工大學(xué)Sparing 等[40]針對(duì)周期性列車時(shí)刻表設(shè)計(jì)問(wèn)題，提出了一種問(wèn)題導(dǎo)向的預(yù)處理技術(shù)用以縮減解的搜索空間，結(jié)合CPLEX 求解器設(shè)計(jì)了一種啟發(fā)式的迭代求解策略。對(duì)于列車實(shí)時(shí)調(diào)度問(wèn)題，F(xiàn)ischetti等[35]提出了對(duì)約束條件的定界策略和對(duì)決策變量的壓縮策略，以獲得更加緊湊縮減的解空間，然后利用CPLEX 求解修改后的混合整數(shù)規(guī)劃模型。Niu 等[46]對(duì)于面向需求的列車時(shí)刻表問(wèn)題，根據(jù)基于分鐘和小時(shí)的客流需求，分別構(gòu)建了問(wèn)題的2 次和擬2 次整數(shù)規(guī)劃模型，針對(duì)不同情形引入了新的變量，修改構(gòu)建了數(shù)學(xué)上嚴(yán)格、計(jì)算上易處理的非線性混合整數(shù)規(guī)劃模型，提出了基于優(yōu)化軟件GMS的求解方法。

3.3 直接分解方法

列車時(shí)刻表問(wèn)題具有明顯的離散選擇特征，數(shù)學(xué)上可以表示為整數(shù)規(guī)劃模型。從算法設(shè)計(jì)的角度講，利用一些已有的分解方法，直接將這類復(fù)雜問(wèn)題分解為容易求解的多個(gè)子問(wèn)題，然后逐步求解，最后得到期望的最優(yōu)解。分支定界和動(dòng)態(tài)規(guī)劃算法，是該領(lǐng)域兩類最常見(jiàn)的分解方法。

分支定界(Branch and Bound)是求解整數(shù)規(guī)劃問(wèn)題的常用算法，該方法是一種迭代搜索方法，主要思路是把可行解空間反復(fù)地分割為越來(lái)越小的子集，稱為分支；對(duì)每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界(最小值問(wèn)題)，稱為定界；每次分枝后，凡是界限超出已知可行解目標(biāo)值的那些子集不再進(jìn)一步分枝，從而縮小搜索范圍，稱為剪枝；反復(fù)實(shí)施上述過(guò)程直至找出最優(yōu)解。分支定界算法由于其良好的分解能力和收斂特性，在列車時(shí)刻表問(wèn)題研究中廣泛使用。2005年，亞利桑那州立大學(xué)周學(xué)松教授[47]在研究多級(jí)列車共線運(yùn)行下列車時(shí)刻表問(wèn)題時(shí)，構(gòu)建了高等級(jí)列車出發(fā)時(shí)間與理想出發(fā)時(shí)刻偏離最小，以及所有列車旅行時(shí)間最少的雙目標(biāo)模型；根據(jù)兩種優(yōu)先權(quán)規(guī)則，將第2 個(gè)目標(biāo)對(duì)應(yīng)的模型分解為單列車時(shí)刻表問(wèn)題，并將其轉(zhuǎn)化為帶有資源限制的項(xiàng)目調(diào)度問(wèn)題；提出帶有有效支配準(zhǔn)則的分支定界算法，以獲得原多目標(biāo)問(wèn)題的帕累托解；為了提高算法效率及獲得具有代表性的非支配解集，提出帶有效用評(píng)價(jià)準(zhǔn)則的束搜索策略。

代爾夫特理工大學(xué)D'Ariano 等[48]將列車實(shí)時(shí)調(diào)度抽象為車間作業(yè)調(diào)度問(wèn)題，然后利用分支定界算法消解列車之間可能的沖突，并將一系列啟發(fā)式規(guī)則嵌入到算法中以加快求解速度。挪威學(xué)者M(jìn)annino等[49]利用分支定界算法求解地鐵列車實(shí)時(shí)調(diào)度問(wèn)題，通過(guò)隱枚舉法將可行的路徑加入到活動(dòng)節(jié)點(diǎn)集合中，將每個(gè)節(jié)點(diǎn)得到的可行目標(biāo)值作為上界，同時(shí)利用最小費(fèi)用流模型求解下界。Shafia等[31]利用分支定界算法求解列車時(shí)刻表問(wèn)題，每個(gè)搜索節(jié)點(diǎn)對(duì)應(yīng)一個(gè)可能的列車時(shí)刻表，并通過(guò)節(jié)點(diǎn)選擇策略逐步更新下界。Liu等[30]建立了列車時(shí)刻表的兩階段優(yōu)化模型，設(shè)計(jì)了基于分支定界的啟發(fā)式求解框架，構(gòu)造的搜索樹(shù)節(jié)點(diǎn)表示主問(wèn)題和對(duì)應(yīng)的系列子問(wèn)題，設(shè)計(jì)了基于領(lǐng)域搜索的分支策略，并通過(guò)預(yù)定閾值對(duì)問(wèn)題定界。

動(dòng)態(tài)規(guī)劃(Dynamic Programming)算法，是求解列車時(shí)刻表問(wèn)題另一類常用的分解算法，該算法的核心思想是，根據(jù)離散及多階段特征，將待求解問(wèn)題分解為若干個(gè)子問(wèn)題，然后按順序求解子問(wèn)題，并用前一子問(wèn)題的解向后一問(wèn)題提供信息；在求解每個(gè)子問(wèn)題時(shí)，通過(guò)決策保留能夠達(dá)到最優(yōu)的局部解；依次求解子問(wèn)題，最后得到原問(wèn)題的最優(yōu)解。

Niu 等[50]在求解考慮換乘的列車時(shí)刻表時(shí)，運(yùn)用動(dòng)態(tài)規(guī)劃獲取問(wèn)題的最優(yōu)解；算法執(zhí)行過(guò)程中，視列車為決策階段，列車在始發(fā)站的出發(fā)時(shí)刻為搜索狀態(tài)，乘客在站等待時(shí)間和在車擁擠度作為狀態(tài)的評(píng)價(jià)函數(shù)。陰佳騰等[38]利用動(dòng)態(tài)規(guī)劃求解列車調(diào)度調(diào)整問(wèn)題，將列車在車站之間的移動(dòng)作為待決策階段，以乘客延誤時(shí)間、旅行時(shí)間和列車能源消耗為評(píng)價(jià)指標(biāo)函數(shù)，并通過(guò)近似化指標(biāo)函數(shù)加速問(wèn)題的求解效率。對(duì)于一個(gè)擁擠的公共交通系統(tǒng)，Chen等[51]在研究車輛車頭距和編組長(zhǎng)度優(yōu)化時(shí)，利用了動(dòng)態(tài)規(guī)劃算法，其中以離散的時(shí)間節(jié)點(diǎn)作為決策階段，乘客排隊(duì)長(zhǎng)度為狀態(tài)變量，能耗成本和等待時(shí)間為指標(biāo)函數(shù)，為避免“維數(shù)災(zāi)”的影響，迭代中不斷加入有效不等式，以縮減狀態(tài)空間、加快求解速度。

3.4 對(duì)偶分解方法

在問(wèn)題分解過(guò)程中，充分利用對(duì)偶信息，稱為對(duì)偶分解算法。拉格朗日松弛算法(Lagrangian Relaxation)是最著名的對(duì)偶分解算法，該方法被廣泛應(yīng)用于求解各類運(yùn)籌優(yōu)化問(wèn)題，如車輛路徑、設(shè)施選址、任務(wù)調(diào)度等問(wèn)題，美國(guó)賓夕法尼亞大學(xué)教授、著名運(yùn)籌學(xué)家Fisher[52]對(duì)該方法有詳細(xì)的分析和精辟的點(diǎn)評(píng)。拉格朗日方法的核心是將“多智能體耦合約束”進(jìn)行松弛，得到多個(gè)易求解的子問(wèn)題，然后應(yīng)用對(duì)偶信息進(jìn)行迭代，并隨時(shí)計(jì)算評(píng)估當(dāng)前解距離最優(yōu)解的偏離程度，直到找到問(wèn)題的滿意解為止。在列車時(shí)刻表優(yōu)化問(wèn)題中，“股道能力約束”要求相關(guān)的列車群在同一區(qū)間必須滿足最小安全間隔，用拉格朗日方法松弛該能力約束，就可以將復(fù)雜的列車時(shí)刻表問(wèn)題分解為一系列最短路徑問(wèn)題。

1998年，瑞典皇家理工學(xué)院Brannlund 等[9]在求解列車時(shí)刻表問(wèn)題時(shí)，首次應(yīng)用拉格朗日松弛方法，將一段軌道線路劃分為若干個(gè)閉塞區(qū)間，要求兩個(gè)列車在任意時(shí)刻不能占用同一區(qū)間，通過(guò)松弛區(qū)間能力約束，將原問(wèn)題分解為多個(gè)單列車路徑子問(wèn)題。由于時(shí)刻表模型中包括海量的區(qū)間能力約束，導(dǎo)致拉格朗日松弛方法難以應(yīng)對(duì)大規(guī)模問(wèn)題求解的需要?；诖?，Caprara 教授團(tuán)隊(duì)[8,12]通過(guò)構(gòu)建獨(dú)特的時(shí)空網(wǎng)絡(luò)，將列車時(shí)刻表問(wèn)題描述為一類多商品網(wǎng)絡(luò)流問(wèn)題，通過(guò)引入不兼容弧來(lái)限制股道能力約束，建立僅依賴于時(shí)空節(jié)點(diǎn)的能力約束模型，避免了拉格朗日乘子過(guò)多的影響。沿著這一思路，Cacchiani 等[14,53]應(yīng)用拉格朗日松弛方法，通過(guò)松弛股道能力約束，求解貨物及魯棒列車時(shí)刻表優(yōu)化問(wèn)題。2007年，周學(xué)松教授[54]將列車時(shí)刻表優(yōu)化描述為一個(gè)廣義資源受限調(diào)度問(wèn)題，其中區(qū)段和車站能力作為受限資源，通過(guò)松弛這兩類資源約束，將原問(wèn)題分解為一系列的單列車路徑子問(wèn)題，采用動(dòng)態(tài)規(guī)劃算法求解子問(wèn)題，其中為了得到期望的整數(shù)解，將分枝定界策略嵌入搜索過(guò)程，以生成可行的下界。

城市軌道交通一般采取相對(duì)簡(jiǎn)單的運(yùn)行模式，不需要考慮列車之間的越行，股道能力約束較為簡(jiǎn)單，在利用拉格朗日算法求解這類時(shí)刻表問(wèn)題時(shí)，可以考慮松弛其他耦合約束條件。 如Hassannayebi 等[28]在研究列車時(shí)刻表問(wèn)題時(shí)，同步考慮了動(dòng)車組運(yùn)用，通過(guò)松弛列車接續(xù)約束，將對(duì)偶問(wèn)題分解為兩類獨(dú)立的時(shí)刻表子問(wèn)題。陰佳騰等[39]在求解基于能耗的列車時(shí)刻表問(wèn)題時(shí)，利用拉格朗日方法松弛乘客加載與列車運(yùn)行耦合約束，將問(wèn)題分解為單純的列車時(shí)刻表問(wèn)題和客流分配問(wèn)題。楊立興等[55]通過(guò)構(gòu)建時(shí)空網(wǎng)絡(luò)，研究了網(wǎng)絡(luò)條件下地鐵末班列車協(xié)同優(yōu)化問(wèn)題，通過(guò)松弛乘客與列車間的關(guān)聯(lián)約束，將問(wèn)題分解為乘客路徑子問(wèn)題和列車路徑子問(wèn)題。

需要指出的是，在利用拉格朗日方法求解列車時(shí)刻表及延伸問(wèn)題時(shí)，松弛約束條件的類型和數(shù)量將嚴(yán)重影響算法效率。通常而言，總是希望松弛的約束條件越少越好，而且相互之間沒(méi)有其他可能的依賴關(guān)系，否則會(huì)導(dǎo)致不同拉格朗日算子之間互相影響并降低算法效率。為了盡量消除這一問(wèn)題的影響，Mahmoudi 和周學(xué)松[56]于2016年提出多維時(shí)空網(wǎng)絡(luò)的概念，該方法可以將一些復(fù)雜約束條件，如車輛容量、時(shí)間窗和乘客上下車約束等，自然嵌入到時(shí)空網(wǎng)絡(luò)中，從而剔除一些不必要的約束，使多商品流模型減少對(duì)應(yīng)的拉格朗日乘子，加快了模型的求解速度。近期發(fā)表的部分軌道列車調(diào)度文獻(xiàn)，如地鐵列車停站問(wèn)題[22]、動(dòng)車組維修和補(bǔ)給問(wèn)題[57]，均使用了多維時(shí)空網(wǎng)絡(luò)構(gòu)模技術(shù)。

列生成算法(Column Generation)是另一類著名的對(duì)偶分解方法，它將原問(wèn)題分解為限制主問(wèn)題和價(jià)格子問(wèn)題，通過(guò)反復(fù)求解兩類子問(wèn)題，以獲得問(wèn)題的最優(yōu)解。值得注意的是，列生成算法在大多數(shù)情況下，需要進(jìn)一步集成“分支-切割”技術(shù)以獲得期望的整數(shù)解[57]。2008年，Cacchiani教授等[34]在研究列車時(shí)刻表問(wèn)題時(shí)，用列車路徑為決策變量建立了集合覆蓋模型，通過(guò)列生成算法及分枝定界技術(shù)獲得了最后的滿意解。2020年，田小鵬和Niu[10]在基于小時(shí)的OD需求環(huán)境中，研究了含有越行的列車時(shí)刻表優(yōu)化，通過(guò)重新定制一組客流加載約束，以匹配列車停站和乘客上下車過(guò)程，并通過(guò)使用單車站代理對(duì)偶變量的方法，消除價(jià)格子問(wèn)題中的不可分割性(Indivisibility)或強(qiáng)耦合性。

4 結(jié)論與展望

本文全面總結(jié)了軌道列車時(shí)刻表問(wèn)題的研究現(xiàn)狀，基于深刻的文獻(xiàn)分析與解讀，詳細(xì)討論了國(guó)際學(xué)術(shù)界在該領(lǐng)域重點(diǎn)關(guān)注的研究選題、主要的建模方法和常用的求解算法，評(píng)述了相關(guān)研究成果的科學(xué)意義和應(yīng)用價(jià)值。必須指出的是，這些研究軌道列車時(shí)刻表的文獻(xiàn)，還存在著一些問(wèn)題和不足，主要表現(xiàn)在：

(1)理論研究和實(shí)際應(yīng)用之間缺乏深度融合。軌道列車時(shí)刻表優(yōu)化是一個(gè)有明確實(shí)踐背景和巨大理論挑戰(zhàn)的問(wèn)題，這需要所開(kāi)展的研究既能全面細(xì)致、適合應(yīng)用，又能適度簡(jiǎn)化、方便求解。然而，該領(lǐng)域現(xiàn)有的理論研究總有一些曲高和寡、偏離實(shí)際的感覺(jué)，缺少與運(yùn)營(yíng)企業(yè)深層次的信息交流及合作攻關(guān)。

(2)缺少對(duì)一些重要實(shí)踐問(wèn)題的深層次理論探索。在該領(lǐng)域的應(yīng)用層面，長(zhǎng)期存在著一些難以完成的操作任務(wù)，如需要為每個(gè)列車在始發(fā)站預(yù)先指定一個(gè)出發(fā)時(shí)間窗，對(duì)于擁擠的鐵路走廊，實(shí)踐中很難實(shí)現(xiàn)這一設(shè)置；類似這樣的具體問(wèn)題，往往背后隱藏著復(fù)雜的理論挑戰(zhàn)，現(xiàn)有研究文獻(xiàn)缺乏深入的分析和探究。

作為交通管理和運(yùn)籌優(yōu)化領(lǐng)域重要的理論和實(shí)踐問(wèn)題，軌道列車時(shí)刻表問(wèn)題的研究熱度和廣度還將持續(xù)較長(zhǎng)的時(shí)間，未來(lái)可能的研究選題包括：

(1)現(xiàn)有列車時(shí)刻表問(wèn)題的研究文獻(xiàn)，主要集中在單線路或單走廊情形，關(guān)于軌道交通網(wǎng)絡(luò)列車時(shí)刻表問(wèn)題，鮮有大影響、高亮點(diǎn)的研究成果。研究該類問(wèn)題，需要重點(diǎn)解決不同線路上列車之間的銜接及旅客的換乘問(wèn)題，這會(huì)產(chǎn)生相當(dāng)多的困難和挑戰(zhàn)，將是一個(gè)非常有意義的研究選題。

(2)將現(xiàn)有列車時(shí)刻表問(wèn)題的研究成果，通過(guò)與線路規(guī)劃、動(dòng)車組調(diào)度和其他實(shí)際需要(如維修天窗)，以及時(shí)變票價(jià)和客票分配等因素之間進(jìn)行深度融合，研究軌道列車時(shí)刻表集成優(yōu)化問(wèn)題。

(3)由于軌道列車時(shí)刻表問(wèn)題特有的大規(guī)模和NP難特性，研究該類問(wèn)題有效可靠的求解算法，始終具有重要的理論和實(shí)踐意義。利用已有求解架構(gòu)，結(jié)合不同問(wèn)題的特點(diǎn)，設(shè)計(jì)針對(duì)性的啟發(fā)式算法，或借鑒其他相關(guān)學(xué)科研究成果，構(gòu)建新的求解算法或架構(gòu)，都是值得繼續(xù)探索的研究選題。

(4)最后，根據(jù)所獲得的優(yōu)化理論和方法，通過(guò)與軌道企業(yè)的深度合作，開(kāi)發(fā)能夠完全應(yīng)用于實(shí)際運(yùn)營(yíng)、具有商業(yè)意義的系統(tǒng)軟件，將是一件非常有意義的工作。