成網(wǎng)條件下城市軌道交通車底運用問題研究

李潔，何世偉，何必勝

(北京交通大學交通運輸學院，北京100044)

為緩解日益嚴重的城市交通擁堵問題，我國一些特大城市大力開展軌道交通建設(shè)，在較短時期內(nèi)由單一線路形成網(wǎng)絡(luò)。由于路網(wǎng)規(guī)模的快速擴大，原有的單線運營管理模式不能完全適應網(wǎng)絡(luò)化運營，迫切要求研究新方法以應對這種快速變化的新局面。成網(wǎng)條件，即總控制中心負責多條線路的運行控制和協(xié)調(diào)調(diào)度，線路采用相同類型的信號系統(tǒng)和供電制式，更新的車輛及運營設(shè)備類型保持統(tǒng)一和兼容，可實現(xiàn)維修、配件和技術(shù)資源的充分共享。而城市軌道車輛價格昂貴，在固定設(shè)備投資中占較大比重，車底運用計劃又是城市軌道交通運營規(guī)劃中重要的內(nèi)容之一，因此運營效益最大化要求投入適當數(shù)量的車輛，合理地安排列車接續(xù)和檢修，縮短列車非生產(chǎn)時間，提高利用率，降低運營成本。

軌道交通運營問題一直是國內(nèi)外學者研究的重點內(nèi)容。Tomoshi Otsuki等［1］將機車車輛配置問題定義為多商品流問題，并提出基于搜索的啟發(fā)式算法。Luis Cadarso等［2］分析了在發(fā)車頻率高、站間距短的快速公交網(wǎng)絡(luò)中，建立模型解決不同線路間的能力與車輛共享問題。王彥棟［3］建立了以接續(xù)時間和維修時間最少為目標函數(shù)的車底運用計劃模型。繆道平［4］分別從車底使用數(shù)量最少和均衡性最好的角度建立模型。徐瑞華等［5］提出“運行圖周期分析法”，建立多種交路條件下城市軌道交通通過能力和車底數(shù)量的數(shù)學模型。吳濤［6］推演出共線運行圖不同行車間隔時間條件下的運行圖周期和車底運用列數(shù)的計算方法。陶志祥［7］從客流特征、運營管理、基礎(chǔ)設(shè)施及設(shè)備兼容等方面分析了區(qū)域城際鐵路與城市軌道交通跨線運行的兼容性。可見，國外的研究工作主要集中在列車的編組方案、通過能力等方面，以靈活的編組結(jié)合對行車密度的調(diào)節(jié)來適應不同時期和不同時段客流量變化的要求，雖然研究較成熟，但不符合我國城市軌道交通固定編組的情況，不能直接應用，但其建模思路與方法可作為借鑒經(jīng)驗。而我國城市軌道交通大多以單線運營為基礎(chǔ)，研究多以單線路條件為背景，或以成網(wǎng)條件下的客流情況和運輸能力為研究方向，較少涉及到成網(wǎng)條件下的車底運用計劃。

本文給出成網(wǎng)條件下城市軌道交通車底運用問題的優(yōu)化方法，即基于網(wǎng)絡(luò)流模型的單車場與多車場車底運用模型，以構(gòu)建最優(yōu)任務(wù)序列(即行車計劃)，節(jié)省車底使用數(shù)，降低運營成本。最后采用ILOG CPLEX 12.5優(yōu)化軟件，結(jié)合算例對模型求解分析，并與啟發(fā)式算法進行了比較，驗證了求解方法的高效性。

1 成網(wǎng)條件下城市軌道交通車底運用問題研究

1.1 問題描述

城市軌道交通車底運用問題可以描述為:給定時刻表等相關(guān)信息，在滿足相關(guān)約束條件下，調(diào)度車輛執(zhí)行時刻表給定任務(wù)(中間可插入空駛班次以減少車輛需求)，使每一任務(wù)均有唯一車輛執(zhí)行，從而構(gòu)建車輛執(zhí)行的任務(wù)序列(行車計劃)。其最主要的優(yōu)化目標是在現(xiàn)有車輛水平下安排車輛調(diào)度方案使運用車輛數(shù)或費用最少。

與公交可靈活地進行區(qū)域調(diào)度不同，城市軌道車輛只能在既定軌道上行駛，交路形式略顯單一，可以從公交的行車計劃編制中汲取經(jīng)驗。為研究城市軌道交通車底運用問題從單線向網(wǎng)絡(luò)化運營的變化情況，本文以單車場車底運用問題和多車場車底運用問題為理論基礎(chǔ)。

單車場車底運用問題指一條線路只配備有一個車場，該線路上的所有收發(fā)車任務(wù)均由此車場的車底完成。我國多數(shù)城市的軌道交通路網(wǎng)為單線疊加而成，這種調(diào)度方案可以很好的滿足客流成網(wǎng)的運營組織需求，而且組織模式簡單，易于操作，穩(wěn)定性強。針對單車場車底運用問題，提出最小總成本的優(yōu)化目標和約束條件。

隨著軌道交通的迅速發(fā)展，路網(wǎng)不斷升級，車場建設(shè)增多，線路間聯(lián)系緊密，單車場車底運用模式轉(zhuǎn)變?yōu)槎嘬噲鲕嚨走\用模式，包含以下兩種情況:(1)一條線路配備多個車場，即單線路多車場;(2)每條線路配備車場不唯一，可以實現(xiàn)車輛在線路間的跨線運營，即多線路多車場。多車場車底運用模式研究解決區(qū)域內(nèi)多個場站的車輛整合調(diào)度問題，指定最佳的執(zhí)行車輛(分布于多個車場)使區(qū)域內(nèi)所需的車輛數(shù)最少。

成網(wǎng)條件下的城市軌道交通車底運用問題涉及單車場和多車場兩種情況，需根據(jù)線路和車場的具體形式進行具體分析。

1.2 網(wǎng)絡(luò)構(gòu)建與符號描述

n∈N表示任務(wù)集合;rk∈R表示出發(fā)車場節(jié)點集合，tk∈T表示到達車場節(jié)點集合;Vk=N∪R∪T為車場中節(jié)點集合;A={r×N，N×t}為單車場中弧段集合，Ak={rk×N，N×tk}為多車場中弧段集合。

車底調(diào)度網(wǎng)絡(luò)可以定義為:單車場時有網(wǎng)絡(luò) G=(V，A)，多車場時對每一車場 k∈K有網(wǎng)絡(luò)Gk∈(Vk，Ak)。其中，該網(wǎng)絡(luò)中從r到t路徑表示一輛車的可行調(diào)度方案。可行調(diào)度方案集合就是能覆蓋所有任務(wù)的從r到t的路徑集合。

m∈M表示單車場中的車輛集合，m∈Mk表示車場k的車輛集合;

cij表示連接弧(i，j)∈A的成本，一般設(shè)置為行程時間(不包括車次任務(wù)時間)，本文中以秒為計量單位;對于(i，j)∈N駛出駛?cè)胲噲龅幕《?r，i)(j，t)，其成本為車輛使用的固定成本，換算為秒計量;

tij表示連接任務(wù)i，j的最小折返時間，此處指同一車站的折返時間;

nij表示連接任務(wù)i，j的列車編組數(shù);

l為所用車輛長度;

Lij為任務(wù)i，j所在線路上的最小站臺長度;

ymij為單車場車底運用模型的0-1決策變量，ykmij為多車場車底運用模型的0-1決策變量，表示第m輛車在完成了任務(wù)i后是否接續(xù)任務(wù)j。

1.3 建立模型

構(gòu)造單車場車底運用網(wǎng)絡(luò)G。

圖1中，節(jié)點包括任務(wù)節(jié)點(任務(wù)a、任務(wù)b、任務(wù)c、任務(wù)d，如表1所示)和車場節(jié)點(分別用r，t代表起始點和終止點)。(a，b)，(a，c)，(a，d)，(b，c)(b，d)，(c，d)為 6 條連接弧，其余為車場駛?cè)腭偝龌?。具體假設(shè)該車場存在3輛車。路徑r-a-c-t即為1輛車的調(diào)度方案，而r-a-c-t和r-b-d-t組成的路徑集合即為一可行調(diào)度方案。該可行的調(diào)度方案對應的決策變量值如下:y1ra=1，y1ac=1，y1ct=1，y2rb=1，y2bd=1，y2dt=1，第 3 輛車空閑。

圖1 單車場車底運用網(wǎng)絡(luò)Fig.1 Single-depot rolling stock assignment network

表1 任務(wù)時間表Table 1 Task scheduling table

單車場車底運用模型如下:

式(1)表示成本最小;約束(2)，(3)表示每一任務(wù)都必須被一輛車完成;約束(4)表示連接的兩任務(wù)間要滿足最小折返時間;約束(5)為變量約束。

構(gòu)造多車場車底運用網(wǎng)絡(luò)，如圖2所示。

圖2 多車場車底運用網(wǎng)絡(luò)Fig.2 Multi-depot rolling stock assignment network

式(6)表示成本最小;約束(7)保證每一任務(wù)由一輛車完成;約束(8)流量守恒約束;約束(9)表示連接的兩任務(wù)要滿足最小折返時間;約束(10)表示完成i，j任務(wù)的列車長度應符合站臺長度要求;約束(11)為變量約束。

在實際調(diào)度過程中，很多車場要求車輛回歸本段停放，即車輛從哪個車場出發(fā)，結(jié)束任務(wù)后必須回到原始車場，這樣就方便了車輛的管理與維修。其中約束(8)在保證流量守恒的同時，也要求車輛回段，該約束對模型的影響將在后文中進一步分析。

車場調(diào)度問題的求解方法主要有以下3類:精確算法、啟發(fā)式方法以及模擬方法。本文選擇ILOG CPLEX 12.5作為求解方法，ILOG CPLEX 12.5提供靈活的高性能優(yōu)化程序，在應用程序開發(fā)和部署過程中，開發(fā)者可以使用多種不同的方法與ILOG CPLEX 12.5進行交互，即可以通過大多數(shù)編程環(huán)境來訪問ILOG CPLEX 12.5，并在多個平臺上對其進行使用，實現(xiàn)了可移植性，多用于模擬實際問題。同時，本文還將免疫克隆算法作為對比算法，此算法相比于其他智能優(yōu)化算法，具有克隆、超變異、免疫記憶等特色功能，而且收斂速度快、易于編程實現(xiàn)，在保證收斂速度的同時又能維持抗體的多樣性，算法參見文獻［8］。但是該算法迭代后期容易出現(xiàn)停滯現(xiàn)象，導致搜索精度不高，對初始解有較強的依賴性，容易陷入局部最優(yōu)。當數(shù)據(jù)規(guī)模較小時，ILOG CPLEX 12.5收斂速度快;當規(guī)模較大時，收斂速度慢，可能會出現(xiàn)內(nèi)存溢出現(xiàn)象，無法獲得可行解。

2 算例分析

2.1 案例背景

本研究選取上海地鐵2號線與7號線為例進行分析計算。表2為案例分析所涉及的參數(shù)。

表2 參數(shù)介紹Table 2 Parameter introduction

各停車場及車輛段位置如圖3所示。

每條線路開通初期，兩車場并非同時投入運營，建設(shè)時間有先后，在第2個車場投入使用前，單線路車底運用問題可由單車場模型解決。隨著2號線與7號線的其余車場建成投用后，形成多車場局面。龍陽路停車場共同用于2號線與7號線列車的停放與養(yǎng)護，但是兩條線路車輛仍然獨立使用，未形成網(wǎng)絡(luò)化運營。假設(shè)將來隨著客流量的不斷增多，7號線擴大為8節(jié)編組，兩條線路統(tǒng)一調(diào)度，即可實現(xiàn)車輛的跨線行駛。川沙停車場主要用于4節(jié)編組的列車停放，在廣蘭路站以西形成一個擁有3個車場、兩條線路的小型區(qū)域網(wǎng)絡(luò)，以此為研究對象展開進一步分析。

2.2 計算結(jié)果

以列車間隔為基礎(chǔ)，選取周一至周四的早高峰時段(7:00～9:00)，編制行車計劃表，將所有車次的任務(wù)按照發(fā)車時間先后順序從1開始排列，利用ILOG CPLEX 12.5軟件輸出任務(wù)序列和總成本費用。不考慮折返線數(shù)量的限制。

(1)2號線獨立運營(圖4)。選取兩個車場:北翟路車輛段、龍陽路停車場，兩個車站:廣蘭路站、淞虹路站，為單線路多車場，符合多車場車底運用模型。計算得總成本費用為14 472 s(即連接弧的時間費用總和，由于任務(wù)固定，故未包括車底執(zhí)行車次過程的時間費用，下面計算方法相同)，使用車輛25列。

(2)7號線獨立運營(圖5)。選取2個車場:陳太路停車場、龍陽路停車場，2個車站:上海大學站、花木路站，為單線路多車場，符合多車場車底運用模型。計算得總成本費用為11 040 s，使用車輛32列。

(3)網(wǎng)絡(luò)化運營(圖6)。選取3個車場:北翟路車輛段、陳太路停車場、龍陽路停車場，4個車站:上海大學站、花木路站、廣蘭路站、淞虹路站，為多線路多車場，符合多車場車底運用模型。計算得總成本費用為22 512 s，使用車輛55列。

圖3 二號線及七號線停車場及車輛段位置示意圖Fig.3 Illustration of parking lot and depot location for lines 2 and 7

圖6 實行網(wǎng)絡(luò)化運營后列車運行圖Fig.6 Train timetable for transit network

2.3 結(jié)果分析

通過3組數(shù)據(jù)的對比可以看出，當實現(xiàn)2號線與7號線的跨線運營后，總成本費用相對于兩線獨立運營的成本費用之和降低了近12%，運用總車輛數(shù)也同時減少。城市軌道交通車輛價格昂貴，這樣一來大大減少了投資成本與維修費用，可將節(jié)省的列車當作備用車輛，有積極的現(xiàn)實意義。這說明成網(wǎng)條件下，車底資源得到了有效配置，達到預期目標。

若執(zhí)行完一天的開行計劃后要求車輛回歸本段停放，增加這一約束，重新求解得到另一組數(shù)據(jù)，見表3。

表3 車輛是否回歸本段運算結(jié)果Table 3 Results of entering a depot or not

從表3中可以看出，當要求車輛回歸本段停放時，得到的總成本費用大于或等于第一組數(shù)據(jù)，這是因為車輛執(zhí)行完所有載客任務(wù)后，部分車輛必須空駛回原始車場，增加了一部分費用。從結(jié)果來看，總體上該約束對任務(wù)節(jié)點的接續(xù)情況影響不大。若車型相同，只要盡量保證各車場車輛數(shù)的均衡，以便順利執(zhí)行開行方案，即可在完成所有任務(wù)后，車輛不要求回到原始車輛段，從而減少空駛。

本文采取免疫克隆算法與軟件ILOG CPLEX 12.5對模型進行求解，最終求解結(jié)果中的總成本費用與使用車輛數(shù)二者保持一致，但免疫克隆算法求解模型的平均運行時間為5.1 s，平均迭代次數(shù)為227次，而ILOG CPLEX 12.5平均運行時間為1.59 s，平均迭代次數(shù)75次。兩種算法的求解關(guān)系迭代圖如圖7所示。當求解數(shù)據(jù)規(guī)模較小時，相比于免疫克隆算法，ILOG CPLEX 12.5在求解模型上運行時間更短，收斂性更強，驗證了ILOG CPLEX 12.5求解模型的高效性。

圖7 ILOG與免疫克隆算法求解模型關(guān)系曲線Fig.7 Relationship curves of the solution model of ILOG and immune clone algorithms

當數(shù)據(jù)規(guī)模較大時，再運用ILOG CPLEX 12.5與免疫克隆算法進行求解，得到表4所示對比結(jié)果。當任務(wù)數(shù)由130變?yōu)?04時，ILOG的求解時間仍然低于免疫克隆算法。任務(wù)數(shù)擴大到292時，ILOG求解時間明顯增大，再增至460時求解時間已經(jīng)達到16 832.7 s，遠遠超過免疫克隆算法的19.0 s。而執(zhí)行全天的896個任務(wù)時，免疫克隆算法只需37.4 s，ILOG雖能獲得可行解，但求解時間太長，效率較低，當線路增加任務(wù)數(shù)更多時，該方法不可行。由此可見，ILOG CPLEX 12.5雖然能獲得優(yōu)化解，但是隨著問題規(guī)模的擴大，其求解速度變慢，免疫克隆算法求解質(zhì)量相對差一些，卻能有相對較快的求解速度。因此，在實際的生產(chǎn)工作中，應該將ILOG CPLEX 12.5與免疫克隆算法配合使用，當對計算的求解質(zhì)量要求較高時，采用ILOG CPLEX 12.5，而對時效性要求較高時，選擇免疫克隆算法。

3 結(jié)論

本文主要研究了成網(wǎng)條件下城市軌道交通車底運用問題。隨著地鐵網(wǎng)絡(luò)化的發(fā)展，單車場調(diào)度模型存在一定的局限性，在此基礎(chǔ)上構(gòu)建了多車場調(diào)度模型，建立了使總成本費用最少的目標函數(shù)，約束中考慮了折返時間、站臺長度等現(xiàn)實條件，并新增是否回場的約束。采用ILOG CPLEX 12.5和免疫克隆算法對該問題進行了求解分析，并結(jié)合算例驗證了模型和求解方法的有效性，為成網(wǎng)條件下的城軌車底運用問題提供了較好的決策參考依據(jù)。

［1］OTSUKI T，AISU H，TANAKA T.A search-based approach to the railway rolling stock allocation problem［J］.Lecture Notes in Computer Science，2010，6509:131-143.

［2］CADARSO L，MARIN á .Robust rolling stock in rapid transit networks［J］.Computers and Operations Research，2011，38(8):1131-1142.

［3］彥棟.城市軌道交通車體運用計劃編制模型研究［J］.物流技術(shù)，2011，30(12):98-100.

［4］繆道平.城市軌道交通車體運用計劃自動編制及優(yōu)化研究［D］.北京:北京交通大學，2009.

［5］徐瑞華，陳菁菁，杜世敏.城軌交通多種列車交路模式下的通過能力和車底運用研究［J］.鐵道學報，2005，27(4):6-10.

［6］吳濤.城市軌道交通共線運行圖車底運用研究［J］.鐵道運輸與經(jīng)濟，2011，33(9):83-85，90.

［7］陶志祥.區(qū)域城際鐵路與城市軌道交通跨線運行的兼容性分析［J］.城市軌道交通研究，2008，11(1):6-10.

［8］李代坤，何世偉，申永生，等.基于免疫克隆算法的綜合交通樞紐布局優(yōu)化研究［J］.武漢理工大學學報，2012，36(2):382-386.