基于最大匹配算法的列車調(diào)度模型

孫淑芹,劉家彬,姚 洪

(1.四川民族學(xué)院 數(shù)學(xué)系,四川 康定 626001; 2.四川民族學(xué)院 計算機科學(xué)系,四川 康定 626001;3.四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院,四川 成都 610066)

目前,我國鐵路大都采用客貨混運的機制.在鐵路大提速的背景下,需要對重要的鐵路干線做出更合理的列車調(diào)度方案[1].京滬線是我國最繁忙的鐵路線之一,因此本文就京滬全線某一個區(qū)間段,如濟南至徐州,或南京至上海,在不改變現(xiàn)行列車時刻表的前提下,研究此線最多能安排多少趟次貨車,如何制訂出具體的列車運行圖.列車調(diào)度需要遵循一些基本原則[2-6],如:貨車運行不能影響客車的運行；運行著的列車之間要有足夠的時間間距,等等.京滬鐵路線為雙線鐵路,上行車和下行車之間相互獨立,故在此選擇下行線進行討論即可,上行線可類似討論.為了對行車調(diào)度做出詳細安排及相關(guān)處理,需要了解京滬鐵路全部客車的列車時刻表.經(jīng)過數(shù)據(jù)采集,得到京滬鐵路全部客車的列車時刻表[1].對不再使用的部分列車的數(shù)據(jù)予以剔除,并選定實際中仍在使用的163輛客車建立京滬鐵路客車時刻總表.在實際調(diào)度中,不但需要知道每列客車在任意停車站(客車到達且要停車的站)的入站時間及出站時間,還需要知道每列客車經(jīng)過任意非停車站的路過時間,則在已經(jīng)建立的京滬鐵路客車時刻總表基礎(chǔ)上,對每列客車,都利用其運行時的平均速度求出他們經(jīng)過任意非停車站的路過時間,若有不合理的數(shù)據(jù),則進行適當調(diào)整,得到京滬鐵路客車調(diào)度總表.

1 模型假設(shè)及符號說明

基于以上分析,現(xiàn)對列車調(diào)度做出如下基本假設(shè)以及符號說明.

基本條件假設(shè):不考慮貨車裝卸貨物的時間;每個車站停車容量無限制;所有的客車具有相同的行駛能力,所有的貨車具有相同的行駛能力.

符號說明:

tc(i,j):第i號客車在第j號車站的進站時間;

to(i,j):第i號客車在第j號車站的出站時間;

tc(k,j):第k號貨車在第j號車站的進站時間;

to(k,j):第k號貨車在第j號車站的出站時間;

d(m,n):第m號站與第n站之間的距離.

2 模型的建立

在不影響現(xiàn)有的客車運行狀態(tài)下制定一個合理的貨車調(diào)度表(即貨車時刻表),使得能夠運行的貨車數(shù)量達到最大(即達到最大的運力),并給出相應(yīng)的列車運行圖.

在現(xiàn)實的貨車運行中,影響其調(diào)度的有以下三方面因素:

首先是貨車的空閑時間表,即是在除去現(xiàn)有客車運行時間后的閑置可被利用時間的表格.在現(xiàn)實中,對于貨車的安排是建立在不影響現(xiàn)有客車運行的基礎(chǔ)上的,所以根據(jù)已有的各列客車的列車時刻表統(tǒng)計出可以被利用的空閑時間,所有貨車的安排都應(yīng)該基于此表;其次是當前其他貨車運行狀態(tài).對于貨車的調(diào)度還應(yīng)該遵循不與已安排好的運行貨車相沖突的原則.即除了要考慮當前運行在京滬線上的客車,還要考慮正運行在京滬線上的貨車,這樣才能保證新加入運行的貨車和其他列車不構(gòu)成沖突;最后是貨運申請表.貨車的調(diào)度還取決于當天是否有貨運任務(wù),若沒有貨運任務(wù),則不必安排貨車；若有貨運任務(wù),則再根據(jù)貨車的空閑時間表里的空閑時間來安排貨車車次.

這三方面因素將共同影響貨車的調(diào)度,而“貨車的空閑時間表”對貨車調(diào)度起著決定性作用.為了求得一段鐵路可以同時通行的貨車的理論最大數(shù)目,應(yīng)該先不考慮后兩方面因素的影響,即忽略“當前其他貨車運行狀態(tài)”和“貨運申請表”對“貨車的空閑時間表”的影響.

2.1 基于貨車的空閑時間表及貨車最大通行量的模型

根據(jù)上述分析,取濟南到徐州段鐵路為例,建立模型.

首先討論貨車的空閑時間表的建立方法.對于連續(xù)的兩個車站Sj與Sj+1(Sj先于Sj+1),以及相繼通過這兩個車站的客車ci與ci+1(ci先于ci+1),看是否可以在客車ci與客車ci+1之間插入一列貨車gk(或若干列次貨車)使得這些列車可以在車站Sj與Sj+1之間安全行駛(即相繼兩輛列車之間行車時間間隔不得小于行車的安全時間間隔).則至少有以下條件同時成立才能保證列車在車站Sj與車站Sj+1之間的行駛是安全的.(時間單位:分鐘)

貨車gk從車站Sj出站的時間要至少晚于客車ci一個行車安全時間間隔Ts∶to(k,j)-Ts≥to(i,j);

貨車gk從車站Sj出站的時間要至少早于客車ci+1一個行車安全時間間隔Ts∶to(k,j)+Ts≤to(i+1,j);

貨車gk到達車站Sj+1的進站時間要至少晚于客車ci一個行車安全時間間隔Ts∶tc(k,j+1)≥tc(i,j+1)+Ts;

貨車gk到達車站Sj+1的進站時間要至少早于客車ci+1一個行車安全時間間隔Ts∶tc(k,j+1)≤tc(i+1,j+1)-Ts;

若以上條件不能同時滿足,則客車ci與客車ci+1在車站Sj與Sj+1之間的行駛階段是不能插入貨車運行的；否則,可以對于車站Sj求出一個空閑時間段△tvacancy∶△tvacancy=max(to(k,j))-min(to(k,j)).

顯然,客車ci與ci+1的選取對車站sj的一個“可行的空閑時間段”的計算有決定性作用.由于經(jīng)過每一個車站的客車都有若干輛,那么,對于每一個車站,都將有若干個可行的空閑時間段和到達下站的到達時間范圍,而所有車站的可行的空閑時間段和到達下站的到達時間范圍就構(gòu)成了整張“貨車的空閑時間表”.這就是構(gòu)造貨車的空閑時間表的不等式組模型.從而求得濟南到徐州鐵路段理論上最大的貨車通行量Ngmax.

其中,wj表示第j號車站擁有的可行的空閑時間段的個數(shù)；△tvacancy(j,l)表示第j號車站的第l號可行的空閑時間段.Ngmax表示濟南到徐州貨車數(shù)目的瓶頸量.

2.2 列車時刻表的構(gòu)造算法

根據(jù)已經(jīng)求得的貨車的空閑時間表和貨車的最大通行量,基于原則:對于任意車站,先進站的貨車,先出站,即先進先出.設(shè)計如下算法,構(gòu)造在理論上達到最大貨車行車數(shù)量時,貨車時刻表的一個可行解,進而再制定列車運行圖.

稱貨車的空閑時間表最大匹配算法(VacancyMaximumMatchingAlgorithm)為VMM算法.VMM算法的結(jié)果是以一張時刻表VMMGrid來表現(xiàn),形如表1.

表1 VMMGrid示例表

下面詳細敘述VMM算法:

step1:做一個空表格VMMGrid,其行數(shù)VMMGrid.Lines.Count=濟南與徐州之間的車站數(shù)目=8；其列數(shù)VMMGrid.Columns.Count=濟南到徐州理論上最大的貨車通行量Ngmax×2+1.置單元VMMGrid.Cells[0,0]為空；把首行VMMGrid.Lines[0]除去VMMGrid.Cells[0,0]后的每兩格為一組合并,然后置入站標Sj(j=0,…,6)(S7不置入是因為S6中的“到下站時刻”就確定了S7的數(shù)據(jù))；把首列VMMGrid.Columns[0]除去VMMGrid.Cells[0,0]后的每格依次置入貨車gk(k=1,…,Ngmax).這樣便形成了VMMGrid的框架,如上述VMMGrid示例表.

step4:求Sj0到Sj0之后的所有車站的可行的空閑時刻.

step4.1:求Sj0到Sj0+1可行的空閑時刻.

step4.2:若Sj0的所有可行的空閑時間段已經(jīng)都處理了,則轉(zhuǎn)step4.5,否則取下一個沒有處理的空閑時間段,記此空閑時間段段首時間點為初始時間點,記為t0;

step4.4:若t0+Ts屬于當前可行的空閑時間段,那么令t0∶=t0+Ts,轉(zhuǎn)step4.3,否則轉(zhuǎn)step4.2；

step4.9:從Sj0+1所有可行的空閑時間段的處理成的所有時間點中除去已經(jīng)置入VMMGrid的點后,再作加24小時處理,并重新都視為未處理過,轉(zhuǎn)4.6

step4.10:若S6被處理過了,轉(zhuǎn)step4.11,否則令Sj0∶=Sj0+1、Sj0+1∶=Sj0+2,轉(zhuǎn)step4.1；

step4.11:Sj0到sj0之后的所有車站的可行的列車行車時刻建立完畢,退出step4.

step5:求Sj0之前所有車站的可行的列車行車時刻.(與step4的執(zhí)行流程相類似,逐漸對比Sj0與Sj0-1直到S1被處理完.其中主鍵選為VMMGrid.Columns[2j0+1],初始時間點選取順序變?yōu)橛珊笙蚯?匹配規(guī)則也與step4中相反.)

step6:算法結(jié)束,退出.

VMM算法中的step4和step5為算法的主要執(zhí)行模塊,現(xiàn)以step4為例,建立主算法模塊流程圖,如圖1所示:

圖1 VMM主算法模塊

根據(jù)VMM算法得到的VMMGri即可做出列車運行圖.

3 模型求解及結(jié)果分析

3.1 貨車的空閑時間表和貨車最大通行量的模型結(jié)果

根據(jù)上述貨車的空閑時間表模型和貨車最大通行量的模型,并以貨車運行時的平均速度為60千米/小時,求得貨車的空閑時間表,取其中的一部分作為示例顯示如表2.

表2 貨車的空閑時間表詳表節(jié)選表

可以看出,貨車的空閑時間表清楚地反映了兩個車站之間可以發(fā)出貨車的時間段以及在這個時間段發(fā)車后到達下一站的時間段.

根據(jù)貨車運行速度的不同,得到的貨車最大通行量也不同,其結(jié)果如圖2所示:

圖2 貨車最大通行量與速度關(guān)系圖

此表清楚地反映了隨著運行的貨車速度不同,鐵路段所能允許同時通行的貨車數(shù)量也不同,在一定范圍內(nèi)貨車最大通行量隨著貨車速度的提升而增大.

3.2 列車運行圖的構(gòu)造算法結(jié)果及分析

在此VMM算法中,取貨車運行時的平均速度為60千米/小時,進行計算,得到VMMGrid,再從VMMGrid制定出的列車運行圖總圖.從VMMGrid的內(nèi)容看出,它詳細指明了各個貨車在每個車站的到站時間,是否停車,停車多久以及何時開車這些關(guān)鍵數(shù)據(jù).列車運行圖總圖意義則在于,可以根據(jù)實際需要選取那些合適的貨車車次運行于實際中,而其他的車次可以作為備用；從這張圖表看出所有的線路無交叉,這就直觀的說明了使用VMM算法得到的貨車時刻表是可行的,進一步體現(xiàn)了VMM算法的可行性.

此外,需要注意,在實際的貨車運行當中,還應(yīng)該盡量遵循下列規(guī)則:

1)有直達貨車,也有非直達貨車:直達貨車保證了運送貨物的實時性；非直達貨車則保證了每個車站有貨運請求時都可以得到滿足.

2)各列貨車之間有一定的運行時間間隔:這給以后的列車調(diào)度提供了更加寬松的環(huán)境,尤其是在客運高峰期,為臨時列車的加開提供了基礎(chǔ)；在某列車晚點時提供了可以實時調(diào)整的空間.

3)有限的等待時間:列車到站后不能無限制的等待,等待時間有上限.

4)其他特殊需求:如某城市為貨運大城,則使在此站停車的貨車數(shù)量相對較多,等等.

根據(jù)實際中存在的約束,從列車運行圖總圖中,選擇滿足這些條件的10趟車次,用于實際調(diào)度中,如圖3.

圖3 部分列車運行圖

從此圖中可以看出:有從濟南直達徐州的貨車,也有在各站停靠的貨車；每列貨車之間都有比較合理的運行時間間隔,這是滿足實際需要的.

綜上所述:以貨車的空閑時間表為基礎(chǔ),根據(jù)VMM算法,可以生成可行的詳細貨車時刻表及滿足實際需要列車運行圖.

4 模型評價及改進

(1)數(shù)據(jù)處理中的一些問題.在本模型數(shù)據(jù)處理階段,是采用列車平均速度計算出客車在各非停車站的到站時間,這種處理方式比較簡潔,在一定程度上是可行的,但如果能采集到實際的數(shù)據(jù)將是最準確的處理方式.

這是可以改進的地方,只需采用實際數(shù)據(jù)就可以使基于此數(shù)據(jù)得到的結(jié)果更準確合理.但這并不影響問題的處理方法,本題中的解決方案依然可行.

(2)關(guān)于VMM算法.VMM算法是實現(xiàn)構(gòu)造時刻表的一種有效可行的算法,其主要模塊在step4中完成,其關(guān)鍵可以概述為從到站時刻尋找一個最近的可用空閑時刻作為發(fā)車時間.這樣會產(chǎn)生一個問題:若列車到站時間相對較晚,則在此站的某些可用的空閑時間會被錯過,造成此列車將等待更長時間(直到第二天可用的空閑時刻),而這種處理方法卻能保證絕大多數(shù)貨車找到最近的可用空閑時刻,從而使他們的效率達到最大.可以說這是犧牲了某列或某幾列貨車的效率來保證其他貨車的效率達到最大.

另一種處理方法是,當確定某列貨車會出現(xiàn)長時間等待的情況時,重新對此車站所有貨車的發(fā)車時刻統(tǒng)一做出調(diào)整,使得所有貨車的平均等待時間達到最小.

在實際中,這種長時間等待的情況出現(xiàn)的可能性較小,如本題中的濟南到徐州段就沒有這種長時間等待的情況；又考慮到貨車運輸對實時性的要求并不高,故算法中采用第一種方法來處理長時間等待的情況,即使有對實時性要求高的貨車,也可以保證不犧牲它的效率.

[1]全國大學(xué)生數(shù)學(xué)建模競賽組委會.數(shù)學(xué)建模的實踐[M].北京:高等教育出版社,2007.

[2]聶磊,張星臣,趙鵬,等.高速鐵路列車運行調(diào)整策略的研究[J].鐵道學(xué)報,2001(4):1-6.

[3]蘭淑梅.京滬高速鐵路客車開行方案有關(guān)問題的研究[J].鐵道運輸與經(jīng)濟,2002(5):32-35.

[4]趙麗珍,朱家荷.利用區(qū)間渡線組織列車越行對高速鐵路區(qū)間通過能力的影響[J].中國鐵道科學(xué),2002(5):11-17.

[5]羅晴,金福才,胡思繼.列車運行調(diào)整問題的分解協(xié)調(diào)計算模型[J].北京交通大學(xué)學(xué)報,2004(6):87-89.

[6]趙強.列車運行方案車站到發(fā)線需求可行性模型及其算法[J].西南交通大學(xué)學(xué)報,2000(2):196-200.