網(wǎng)絡(luò)化運營下城市軌道交通列車車底運用計劃編制優(yōu)化研究

網(wǎng)絡(luò)化運營下城市軌道交通列車車底運用計劃編制優(yōu)化研究

城市軌道（以下簡稱城軌）在線運營是為了更好地滿足客運需求，提高效率，采用運營管理等技術(shù)手段將多個獨立運營的城軌線路整合成一個統(tǒng)一的運營管理整體，并在時間和空間上協(xié)調(diào)組織和指揮。網(wǎng)絡(luò)化運營下城軌列車的車底運用計劃優(yōu)化是指用最少的城軌列車車底滿足整個城軌網(wǎng)絡(luò)內(nèi)運輸需求而實現(xiàn)城軌運輸效益的最大化,它是開展城軌網(wǎng)絡(luò)化運營所涉及的主要研究內(nèi)容之一。但關(guān)于網(wǎng)絡(luò)化運營下的城軌列車車底運用計劃優(yōu)化研究還鮮見報道。然而,在地面公交領(lǐng)域?qū)τ诙嘬噲龅墓徽{(diào)度和鐵路運輸中對于客運動車組運用的研究較多,且它們與網(wǎng)絡(luò)化運營下的城軌列車車底的運用優(yōu)化又有著一定的相通性。因此,本文在借鑒Freling,Bodin,Bertossi,Lue56ebel,Haghani,Su-hl,Oukil,Ribeiro,Ceder,Lamatsch和Hadjar等關(guān)于公交領(lǐng)域車輛調(diào)度問題的研究成果［１－１０］,以及史峰和徐行方等關(guān)于鐵路客運專線動車組列車運用計劃優(yōu)化的研究成果［１１－１２］,就城軌網(wǎng)絡(luò)化運營下城軌列車車底運用計劃的優(yōu)化開展研究。1城軌列車車底運用計劃網(wǎng)絡(luò)化運營下的城軌列車車底運用計劃優(yōu)化包括編制優(yōu)化和調(diào)整優(yōu)化兩部分。前者是指以已知列車時刻表信息和城軌線路或網(wǎng)絡(luò)特征為條件,在一定的時間和空間范圍內(nèi),為城軌線路或者網(wǎng)絡(luò)分配一定數(shù)量的城軌列車車底,并為這些列車車底指定擔(dān)當(dāng)?shù)能嚧?、所出入的車輛段(或停車場,后文將車輛段及停車場統(tǒng)稱為車場)等,以實現(xiàn)整個城軌網(wǎng)絡(luò)內(nèi)列車車底資源的靈活共用,提高運營效益;后者是指由于實際運營中列車車底運用受到較多因素的影響,需要結(jié)合實際運營條件,對列車車底運用計劃的編制優(yōu)化結(jié)果再進行調(diào)整,并根據(jù)一定的評價原則對調(diào)整結(jié)果進行評價,以取得合適的調(diào)整方案。限于篇幅,本文主要針對編制優(yōu)化問題進行研究。單線運營和網(wǎng)絡(luò)化運營下的城軌列車車底運用計劃比較如圖1所示。由圖1(a)可見,按單線獨立運營管理,為完成線路1、線路2和線路3各車次的運輸任務(wù)共需要4列車底。但是實現(xiàn)網(wǎng)絡(luò)化運營后,列車車底的運用計劃針對的是多條線路,甚至是整個網(wǎng)絡(luò)的車次。此時,列車車底不再局限于某一線路使用,而是可以在運營條件允許的不同線路間運行,形成了列車車底可以在區(qū)域內(nèi)多條線路上共用,甚至是全網(wǎng)絡(luò)的綜合運用。如圖1(b)所示,網(wǎng)絡(luò)化運營下完成線路1、線路2和線路3各車次的運輸任務(wù)僅需要2列車底,其中車底1將承擔(dān)線路1和線路2的各車次運輸任務(wù),一般稱其為車底1的跨線運行,這是網(wǎng)絡(luò)化運營后城軌列車車底運用的一個顯著特征。2城軌列車車底及列車底控制模型構(gòu)建網(wǎng)絡(luò)化運營下城軌列車車底運用接續(xù)關(guān)系圖G=(T,E),如圖2所示。其中,T為節(jié)點集合,且T=T１∪T２∪T３,T１為始發(fā)車場節(jié)點集合,T２為城軌列車運行計劃中各車次節(jié)點集合(車次節(jié)點具有始發(fā)時間、終到時間、始發(fā)車站和終到車站等屬性),T３為回送車場節(jié)點集合;E為連接邊集合,在本模型中E由車次節(jié)點與車場節(jié)點,以及車次節(jié)點與車次節(jié)點的連接邊組成,且各邊具有對應(yīng)的費用屬性。圖2中的始發(fā)車場節(jié)點和回送車場節(jié)點是由每個實際車場所具有的車底始發(fā)和車底回送業(yè)務(wù)虛擬出的車場節(jié)點,即每個實際車場(設(shè)實際車場的集合為K={k|k=1,…,n},k為車場編號)分別對應(yīng)1個始發(fā)車場節(jié)點和1個回送車場節(jié)點。按始發(fā)車場節(jié)點、車次節(jié)點(依始發(fā)時間的先后順序)和回送車場節(jié)點的順序?qū)D2中的所有節(jié)點進行連續(xù)編號,得到節(jié)點集合T={i|i=1,2,…,n+N+n};其中,T１={1,2,…,n},T２={n+1,n+2,…,n+N},T３={n+N+1,n+N+2,…,n+N+n};n為車場數(shù)量;N為車次節(jié)點的數(shù)量;且始發(fā)車場節(jié)點和回送車場節(jié)點的對應(yīng)關(guān)系為i=1和i=n+N+1表示同一車場,其他始發(fā)車場節(jié)點與回送車場節(jié)點的關(guān)系同理;設(shè)城軌列車車底集合M={m|m=1,2,…},m為車底編號;取Xｉｊｋｍ為0—1決策變量,當(dāng)?shù)趍列車底從車場k出發(fā)由第i個節(jié)點到第j(j>i且∈T)個節(jié)點時,Xｉｊｋｍ=1,否則為0;當(dāng)i和j均為車次節(jié)點時,它們之間的連接應(yīng)滿足規(guī)定的車站作業(yè)時間以及車站到發(fā)線安排等時空約束;Cｉｊ為第i個節(jié)點連接第j個節(jié)點的接續(xù)費用,元;fｋｍ為辦理列車車底m從車場k始發(fā)所需的運營費用,元;τ為當(dāng)天每列車底從開始運營到結(jié)束運營所需的平均固定運營費用,元·列－１;為計算方便,將城軌運營時刻轉(zhuǎn)換為分鐘制,如0:00記為0min,3:00記為180min。按照某天的部分或全部城軌列車運行計劃,在給定的時刻表信息(車次)固定不變以及列車車底類型均相同的假設(shè)下,建立以運營費用最小為目標(biāo)的網(wǎng)絡(luò)化運營下列車車底運用計劃編制優(yōu)化模型為式(1)為目標(biāo)函數(shù);式(2)為車場能力約束,即每個車場能夠派出的車底數(shù)不能超過其可停放的最大車底數(shù)vｋ;式(3)和式(4)為保證每個車次節(jié)點都與且只與1個前驅(qū)和后繼節(jié)點相連的約束;式(5)為同一車底約束,即保證每個車次節(jié)點的前驅(qū)和后繼節(jié)點都是由同一車場發(fā)出的同一車底連接的:式(6)為車底出發(fā)約束,即每天每列車底至多只能從所屬始發(fā)車場節(jié)點出發(fā)1次;式(7)和式(8)為車底的始發(fā)與回送車場相同的約束,即車底從車場始發(fā)時,其始發(fā)車場節(jié)點的編號i和車場編號k一致,而車底回送到車場時,其回送車場的節(jié)點編號j與車場編號k也一致;式(9)為不允許車底在始發(fā)車場節(jié)點和回送車場節(jié)點間空駛的約束;式(10)為0—1決策變量約束。由式(1)知,城軌交通的運營費用一般包括可變運營費用和固定運營費用兩大類。式(1)中的第1項和第2項為可變運營費用,前者表示由于車底連接的節(jié)點不同而得到的不同接續(xù)費用,簡稱節(jié)點間接續(xù)費用;后者表示因辦理車底從不同車場始發(fā)所需的運營費用,簡稱車底出場費用。式(1)中的第3項為固定運營費用,是所有車底參與運營時需要支付的費用,為單位車底固定運營費用與所需車底總數(shù)的乘積,簡稱車底的總固定費用。目標(biāo)函數(shù)的這3部分費用采用同一量綱,單位可用統(tǒng)一貨幣單位表示。關(guān)于節(jié)點間接續(xù)費用,包括車次節(jié)點與車次節(jié)點的接續(xù)費用和車次節(jié)點與車場(始發(fā)車場和回送車場)節(jié)點的接續(xù)費用。(1)車次節(jié)點i(i∈T２)與車次節(jié)點j(j>i且∈T２)的接續(xù)費用主要是由兩部分組成:1車底從車次節(jié)點i的終到站走行到車次節(jié)點j的始發(fā)站所需的接續(xù)運營費用,記為C１ｉｊ;2車底從車次節(jié)點i的終到站走行到車次節(jié)點j的始發(fā)站后,在該始發(fā)站內(nèi)或站外等待所產(chǎn)生的接續(xù)等待費用,記為C２ｉｊ。車次節(jié)點間的接續(xù)首先必須滿足時間上的約束,即滿足tｉｅ+tｉｊ≤tｊｓ;否則接續(xù)費用→∞,即i與j不可接續(xù)。tｉｅ為車次節(jié)點i在終到站dｉｅ的到達時間,min;tｊｓ為車次節(jié)點j在始發(fā)站dｊｓ的出發(fā)時間,min;tｉｊ為車次節(jié)點j接續(xù)車次節(jié)點i需要的時間(包括清客、折返或跨線等作業(yè)時間),min。另外在空間上,若允許車底在不同車站間空駛,則車底從所擔(dān)當(dāng)車次節(jié)點i的終到站到接續(xù)車次節(jié)點j(j>i且∈T２)的始發(fā)站可能存在2種接續(xù):1車底本線折返接續(xù);2車底跨線接續(xù)。車底跨線接續(xù)只有在城軌網(wǎng)絡(luò)化運營下才可能有,而且相比車底本線折返接續(xù),車底跨線接續(xù)的運營組織更復(fù)雜,單位時間運營費用更高。根據(jù)以上分析,車次節(jié)點接續(xù)運營費用C１ｉｊ可表示為式中:上式表示車次節(jié)點i的終到站dｉｅ與接續(xù)車次節(jié)點j的始發(fā)站dｊｓ為同一車站(車底本線折返接續(xù))時的接續(xù)運營費用,元;下式表示車次節(jié)點i的終到站dｉｅ與接續(xù)車次節(jié)點j的始發(fā)站dｊｓ為不同車站(車底跨線接續(xù))時的接續(xù)運營費用,元;α和β分別為車底本線折返接續(xù)和跨線接續(xù)時的單位時間運營費用,元·min－１;tｚｉｊ為車底本線折返接續(xù)時所需的折返時間,min;tｖｉｊ為車底跨線接續(xù)時車底從所擔(dān)當(dāng)車次節(jié)點i的終到站dｉｅ運行到車次節(jié)點j的始發(fā)站dｊｓ所需的時間,min。式中:上面的等式表示車底本線折返接續(xù)時的等待費用,元;下面的等式表示車底跨線接續(xù)時的等待費用,元;θ為車底在站內(nèi)或站外等待時的單位時間等待費用,元·min－１;tｗｉｊ為車底在站內(nèi)或站外等待接續(xù)的時間,min。(2)車次節(jié)點與車場節(jié)點的接續(xù)費用也分為2種。一種是車底從始發(fā)車場節(jié)點i(i∈T１)運行至所擔(dān)當(dāng)車次節(jié)點j(j∈T２)始發(fā)站所需的費用Cｉｊ;另一種是車底完成車次節(jié)點j(j∈T２)后從其終到站空駛到回送車場節(jié)點i(i∈T３)所需的費用Cｊｉ?？煞謩e表示為式中:tｔｉｊ為車底從始發(fā)車場節(jié)點i到車次節(jié)點j始發(fā)站所需的運行時間,min;tｔｊｉ為車底從車次節(jié)點j的終到站到回送車場節(jié)點i所需的運行時間,min;ue787為車底在車場和車站間非載客運營下的單位時間運營費用,元·min－１。關(guān)于車底出場費用,其所描述的是車底與車場的關(guān)系。一般情況下,車底隸屬于指定的車場,并且原則上都會從所屬車場始發(fā),執(zhí)行運輸任務(wù)。但是,在編制每天的車底運用計劃時,當(dāng)某一車場需要的車底數(shù)大于其存有的車底數(shù)時,允許向其他車場借用車底,這也是網(wǎng)絡(luò)化運營的特點之一。而向哪個車場借用車底,主要取決于車底從所屬車場走行到目的車場的可能性或走行費用。設(shè)車底m從車場k始發(fā)需要支付一定的出場費用,且該費用是關(guān)于車底m從隸屬車場出發(fā)并運行到指定車場k所需時間的函數(shù)fｋｍ,可表示為式中:ue014為車底在車場間非載客情況下單位時間的平均運營費用,元·min－１;為車底m隸屬的車場;為車底m從隸屬車場到車場k所需的走行時間,min。由式(15)可知,當(dāng)車場k為車底m的隸屬車場時,fｋｍ=0。3使用禁忌提取對上述模型可采用ILOGCPLEX數(shù)學(xué)優(yōu)化軟件求解,而且考慮到網(wǎng)絡(luò)化運營下列車車底運用計劃編制優(yōu)化模型的計算復(fù)雜性,設(shè)計了基于任務(wù)協(xié)作類型的并行禁忌搜索算法［１３］進行求解,算法流程如圖3所示。Step0:對車底信息進行編碼設(shè)計。每列車底對應(yīng)1條編碼片段,每條編碼片段包含車底的編號、始發(fā)(回送)車場、被分配車次等信息,如圖4所示。Step1:進行初始化。設(shè)置禁忌表,給定禁忌長度、最大迭代步數(shù)等參數(shù);設(shè)初始全局最優(yōu)解的適應(yīng)度函數(shù)值為極大值。Step2:生成包括P個初始解的初始解集。Step4:對第p個初始解進行鄰域搜索,得到關(guān)于當(dāng)前初始解的鄰居集合,即生成鄰域。Step5:計算鄰域中所有鄰居的適應(yīng)度函數(shù)值,查找其中最小值,將最小值對應(yīng)的鄰居作為候選最優(yōu)解加入到禁忌表中,并替代當(dāng)前初始解。Step6:判斷是否更新全局最優(yōu)解。若該候選最優(yōu)解的適應(yīng)度函數(shù)值較原全局最優(yōu)解的適應(yīng)度函數(shù)值小,則用該候選最優(yōu)解替換原全局最優(yōu)解;否則保持原全局最優(yōu)解不變。Step7:判斷是否滿足迭代終止條件,若是,則進入Step8;否則,若p=P,轉(zhuǎn)Step3,若p<P,則p=p+1,轉(zhuǎn)入Step4。Step8:輸出最優(yōu)解,算法結(jié)束。另外,算法采用明晰記憶方式［１５］對車底運用計劃的結(jié)果進行完整記憶,即將編碼作為禁忌的對象,并以先進先出的方式進行替換。對于不同規(guī)模的車底運用計劃優(yōu)化問題,應(yīng)根據(jù)實際情況進行禁忌表長度的設(shè)定。關(guān)于基于目標(biāo)控制原則的計算終止方式:記憶全局最優(yōu)解,當(dāng)全局最優(yōu)解對應(yīng)的適應(yīng)度函數(shù)值在給定迭代步數(shù)范圍內(nèi)不再改變時,算法停止。對于迭代步數(shù)最大值的選取應(yīng)視車底運用計劃優(yōu)化問題的規(guī)模而定。4線底共享及車底運用以我國地鐵初步成網(wǎng)的某市地鐵系統(tǒng)為例,選取如圖5所示該市地鐵網(wǎng)絡(luò)中的8號線、5號線和YZ線,運用本文方法進行網(wǎng)絡(luò)化運營下城軌列車的車底運用優(yōu)化。之所以選擇8號線、5號線和YZ線這3條地鐵線路,是因為現(xiàn)階段它們雖為獨立運營,但稍加改造就能具備網(wǎng)絡(luò)化運營的條件,具體思路是1現(xiàn)階段服務(wù)于這3條線路的車輛段(場)有TPZ車輛段、PXF車輛段、SJZ停車場和TH車輛段,其中TPZ車輛段和PXF車輛段分別位于5號線和8號線北部盡頭,均在城市邊緣區(qū)而且相互間的直線距離僅為3.5km左右,因此可在這兩車輛段間增設(shè)聯(lián)絡(luò)線(見圖5中虛線所示),由此形成兩車輛段車底及相關(guān)資源的共享;25號線在SJZ站與YZ線匯合,雖然兩線現(xiàn)還沒有跨線運營,但是SJZ停車場現(xiàn)是5號線和YZ線共用的停車場,因此具備兩線車底資源共享的基礎(chǔ)。假設(shè)通過增設(shè)聯(lián)絡(luò)線,TPZ車輛段與PXF車輛段的車底實現(xiàn)共享,且車底在兩車輛段間的走行時間為4.2min;5號線和YZ線也能共用SJZ停車場內(nèi)的車底,且車底經(jīng)該車場跨線共用需要的最小接續(xù)時間為3min。另外,通過對2012年12月某天8號線、5號線和YZ線運營現(xiàn)狀的調(diào)查得知,在這天8號線、5號線和YZ線分別安排了326,490和220個車次(共計1036個車次),各線獨立運行則需要配置64列車底;這3條線涉及的6個始發(fā)與終到站的車底最小在站折返時間和車底由車輛段(車場)往(返)始發(fā)站的走行時間分別見表1和見表2。設(shè)4個車輛段(車場)預(yù)計共有75(任取1個比現(xiàn)實際運用車底數(shù)大的值)列車底可供使用,編號為1~10的車底配屬給TPZ車輛段,編號為11~40的車底配屬給PXF車輛段,編號為41~52的車底配屬給SJZ停車場,編號為53~75的車底配屬給TH車輛段。根據(jù)參考文獻對該市地鐵歷年財務(wù)狀況的統(tǒng)計,設(shè)每列由6節(jié)車廂編組車底在車場間以及車場與車站間的單位運營費用為26元·min－１(即為簡便計算,設(shè)ue787=ue014=26);車底在站等候擔(dān)當(dāng)相應(yīng)車次時,設(shè)該等待時間費用為車底單位運營費用的50%,即θ=13元·min－１。關(guān)于每列車底被使用時的固定運營費用τ,按車公里費用乘以地鐵列車車底日均運營里程計算,得τ=15