數(shù)學(xué)建模競賽——列車調(diào)度的最大流與分解協(xié)調(diào)模型

1、.列車調(diào)度的最大流與分解協(xié)調(diào)模型胡晶 王鳳娟 廖建華 指導(dǎo)教師：張清華【摘要】本文以濟(jì)南至徐州段作為研究對象，采用規(guī)劃模型確定最大貨車插入量、列車時(shí)刻表及運(yùn)行圖等。在確定貨車插入量時(shí)，建立最小最大值模型，在一定的約束條件下，利用網(wǎng)絡(luò)系統(tǒng)的最大流問題解決兩個(gè)相鄰站點(diǎn)最多可插貨車量，再取各相鄰區(qū)間段可插貨車最小值作為該段的可行插車數(shù)，通過Excel求解，最后得出下行線可插貨車數(shù)為50輛，上行線可插貨車數(shù)為18輛，并通過Matlab編程繪制了列車運(yùn)行圖。在制定臨時(shí)客車時(shí)刻表時(shí)，采用“提高正點(diǎn)率”來刻畫增開臨時(shí)客車對貨車所造成的影響程度，使調(diào)整后的各次列車充分貼近預(yù)定時(shí)刻，盡快恢復(fù)列車的正點(diǎn)運(yùn)行，建立

2、相應(yīng)的線性規(guī)劃模型，并得出了相應(yīng)的列車時(shí)刻表和列車運(yùn)行圖。當(dāng)列車晚點(diǎn)時(shí)需要進(jìn)行列車調(diào)度，提高列車平均運(yùn)行速度和提高列車運(yùn)行正點(diǎn)率是本文使用的兩個(gè)優(yōu)化目標(biāo)。【關(guān)鍵詞】列車調(diào)度 線性規(guī)劃 多目標(biāo)優(yōu)化 Matlab1 問題分析本題以濟(jì)南至徐州區(qū)間段為研究對象，主要研究以下三方面的問題：最大貨車插入量，臨時(shí)列車時(shí)刻表及運(yùn)行圖，因故晚點(diǎn)時(shí)所進(jìn)行的調(diào)度策略。求最大貨車插入量時(shí)，要求相鄰列車必須滿足一定的時(shí)間間隔和空間間隔條件，即兩相鄰列車在區(qū)間運(yùn)行時(shí)的時(shí)刻差與空間距離必須滿足一定的約束條件，這是典型的在約束條件下的規(guī)劃問題；制定臨時(shí)客車時(shí)刻表時(shí)，要求不改變現(xiàn)行列車時(shí)刻表及盡量減少對貨車的影響，此處關(guān)鍵是用

3、一個(gè)指標(biāo)來刻畫臨時(shí)客車對列車的影響，把不影響現(xiàn)行列車和對貨車的影響最小作為目標(biāo)來安排臨時(shí)客車時(shí)刻表；當(dāng)客車因故晚點(diǎn)進(jìn)行調(diào)整時(shí)，要使得造成的影響最小，關(guān)鍵也是用一些指標(biāo)來表示對列車造成的影響。2 基本假設(shè)（1）客車運(yùn)行的讓路原則是慢車讓快車（2）列車在兩個(gè)站點(diǎn)間是勻速運(yùn)行的（3）忽略列車的長度，將其視為一質(zhì)點(diǎn)，不影響運(yùn)行路程（4）各站點(diǎn)可容納停留的列車數(shù)量無限大，即在站點(diǎn)可以超車（5）同相行駛的列車間至少相隔7分鐘才可以正常運(yùn)行3 模型建立與求解1.最大插車量及列車運(yùn)行圖的確定1.1模型建立 列車有序運(yùn)行：列車運(yùn)行必須滿足一定的時(shí)間間隔和空間間隔要求，即兩列列車在區(qū)間運(yùn)行的時(shí)刻差與空間距離必須滿

4、足一定的約束條件。由于不同類型列車具有不同的速度，通過所給數(shù)據(jù)總共有五種類型的列車，分別為直達(dá)（Z）、特快（T）、快速（K）、管道高速（N）、普快（數(shù)字）。根據(jù)所給數(shù)據(jù)，利用不同類型的列車所經(jīng)過的總路程與其所花的總時(shí)間的比值得出不同類型列車的平均速度： （1）各類型列車的平均運(yùn)行速度為： 一般情況下，貨車的運(yùn)行速度小于客車運(yùn)行速度，故設(shè)定貨車的平均運(yùn)行速度為 列車運(yùn)行調(diào)整問題是多目標(biāo)優(yōu)化問題，為研究其數(shù)學(xué)性質(zhì)，下面以復(fù)線調(diào)度區(qū)段為研究對象首先建立最大網(wǎng)絡(luò)流模型。假設(shè)某線路途經(jīng)個(gè)車站，設(shè)為第1個(gè)站點(diǎn)和第個(gè)站點(diǎn)分別為始發(fā)站和終點(diǎn)站，其余各站稱為中轉(zhuǎn)站點(diǎn)。對于任意兩相鄰站點(diǎn)之間均存在最多安排的貨車數(shù)

5、目 （2）則此條鐵路上最多可安排的貨車數(shù)目為 （3）此時(shí)問題轉(zhuǎn)化為求解各區(qū)間段的最大可插貨車數(shù)目的最小值，建立優(yōu)化模型 （4） 即 （5）約束條件：1.相繼兩列列車在兩個(gè)相鄰站點(diǎn)運(yùn)行期間的時(shí)間間隔不得少于7分鐘；2.貨車與客車的運(yùn)行總量比大約為；下面給出約束條件的數(shù)學(xué)表達(dá)式（以濟(jì)南至天津?yàn)榭紤]范圍），考慮沿下行方向的第個(gè)車站的插車情況，一個(gè)運(yùn)行周期內(nèi)共開出輛列車，第個(gè)車站與第個(gè)車站間距離為，設(shè)插車時(shí)間為，從第個(gè)車站開出的時(shí)間按從小到大進(jìn)行排序有，當(dāng)兩個(gè)時(shí)間段可插車時(shí)，首先要滿足 （6）從第個(gè)車站開入的時(shí)間按從小到大進(jìn)行排序有，當(dāng)兩個(gè)時(shí)間段可插車時(shí)，應(yīng)滿足 （7）其中 （8）設(shè)定在兩個(gè)相鄰站點(diǎn)間

6、已經(jīng)運(yùn)行的客車數(shù)量為，則相鄰站點(diǎn)可插入貨車數(shù)量滿足 （9）故整理得出數(shù)學(xué)模型為 (10) (11)1.2 模型求解1.2.1數(shù)據(jù)整理通過下載“列車運(yùn)行時(shí)刻軟件”查找途徑濟(jì)南至徐州線路上站點(diǎn)的列車運(yùn)行時(shí)刻下行方向以濟(jì)南到泰山的列車運(yùn)行情況為例：表1 濟(jì)南到泰山插車情況 濟(jì)南到泰山距離為71公里，若插入貨車，則歷時(shí)71/70約為60分鐘車次 濟(jì)南發(fā)時(shí)插車的最小時(shí)間 泰山發(fā)時(shí)插車到站的最小時(shí)間插車運(yùn)行時(shí)間可插貨車數(shù)（輛）K67/K700:0700:1401:0301:1000:5602042/204301:4301:5002:5202:5901:0942130/213102:0402:1103:04

7、03:1101:009K371/K37403:1603:1304:1204:1901:065K10703:4603:5304:4204:4900:560K10105:0105:0806:1306:2301:1264921/492405:4005:4706:3606:4300:560K5105:5306:0006:5006:5700:5701227/123006:0706:1407:0307:1000:560K187/K19006:1706:2407:1307:2000:5604941/494406:2106:2807:2107:2801:0061345/134806:5607:0307:530

8、8:0000:590K55/K5807:3007:2708:2608:3301:0612 1469/147211:3911:4612:3512:4200:560 N461/N46412:5112:5813:5113:5801:033 108513:1013:1714:0714:1400:570 T159/T16213:2913:3614:1714:2400:480 1033/103613:3813:4514:3314:4000:550 K172/K173A13:5013:5714:5014:5701:003 K172/K173B13:5013:5714:5014:5701:0012 K75/K

9、7814:0914:1615:0515:1200:560 K4515:5716:0416:5216:5900:550 2581/258416:4316:5017:3917:4600:560 1341/134417:2717:3418:2318:3000:560 2555/255819:4419:5120:5020:5701:063 147720:0620:1321:0221:0900:560 K293/K29620:2820:3521:2921:3601:0110 146121:3221:3922:2922:3600:570 2032/203321:4321:5022:5423:0101:11

10、5 142522:1522:2223:1223:1900:570將24小時(shí)可插貨車數(shù)相加，則得濟(jì)南至泰山兩站點(diǎn)之間可插貨車為78輛。上行方向以徐州到棗州列車運(yùn)行情況為例：表2 徐州到棗州插車情況徐州到棗州的距離為67公里，若插入貨車，則歷時(shí)約為57分鐘車次 徐州發(fā)時(shí)插車的最小時(shí)間 棗州發(fā)時(shí)插車到棗州站的最小時(shí)刻插車運(yùn)行時(shí)間可插貨車數(shù)（輛）146201:5001:5703:1103:1801:1818 2129/213202:5303:0003:4003:4700:470 T17803:3603:4304:1804:2500:420 1342/134305:2205:2906:0806:1500

11、:460 2582/258306:5307:0007:3907:4600:460 1470/147109:3009:3710:1710:2300:460 K171/K174A11:2511:3212:1112:1800:460 K171/K174B11:2511:3212:1112:1800:460 1228/122911:3511:4212:2212:2900:470 1034/103512:3312:4013:1913:2600:460 490813:0613:1313:5314:0000:470 K1618:2818:3519:1419:2100:460 4942/494318:3818

12、:4519:2519:3200:470 108619:0119:0819:4819:5500:470 K10819:4219:4920:2820:3500:460 K206/K20720:0120:0820:4720:5400:460 147820:0920:1620:5521:0200:460 K256/K25720:5921:0621:4521:5200:460 2556/255721:3121:3822:1922:2600:480 將24小時(shí)可插貨車數(shù)相加，則得徐州到棗州兩站點(diǎn)之間可插貨車為18輛。1.2.2 求解利用Excel電子表格，解出各個(gè)期間段的可插貨車最大量分別為：表3 下行方

13、向各相鄰站點(diǎn)可插入貨車數(shù)濟(jì)南至泰山泰山至磁窯磁窯至兗州兗州至鄒城鄒城至騰州騰州至棗莊西棗莊西至徐州78輛72輛74輛84輛56輛50輛57輛表4 上行方向各相鄰站點(diǎn)可插入貨車數(shù)徐州至棗莊西棗莊西至騰州騰州至鄒城鄒城至兗州兗州至磁窯磁窯至泰山泰山至濟(jì)南18輛23輛27輛39輛26輛35輛37輛則由最優(yōu)化模型解得：下行線可插貨車最多為50輛，上行線可插貨車最多為18輛，則共可插入68輛貨車。1.3 列車運(yùn)行圖利用Matlab作出列車運(yùn)行圖Step1、將時(shí)間、距離進(jìn)行轉(zhuǎn)換，時(shí)間以分鐘計(jì)算、距離以公里計(jì)算；Step2、作出之間可插貨車運(yùn)行TS圖；Step3、當(dāng)時(shí)，轉(zhuǎn)到第二步；Step4、濟(jì)南至徐州站點(diǎn)

14、遍歷完全后，停止。圖一 濟(jì)南至徐州列車運(yùn)行圖2. 臨時(shí)客車時(shí)刻表及運(yùn)行圖的制定要增開的臨時(shí)客車要滿足以下三個(gè)條件：（1）增開的臨時(shí)客車與原有的客車之間沒有相互追及的問題（2）增開的臨時(shí)客車之間不能有相互追及的問題（3）要盡量使得新增的臨時(shí)客車對已有的貨車影響最小對臨時(shí)客車和貨車而言，我們采用“提高正點(diǎn)率”來刻畫增開臨時(shí)客車所造成的影響程度。提高正點(diǎn)率為目標(biāo)，使調(diào)整后的各次列車充分貼近預(yù)定時(shí)刻，盡快恢復(fù)列車的正點(diǎn)運(yùn)行，這是列車運(yùn)行調(diào)整過程中通常追求的目標(biāo)。由，該函數(shù)可描述為 (12)考慮到列車運(yùn)行晚點(diǎn)才需調(diào)整，即：、比、的值要大，且、對于某一條線路上的調(diào)度來說是常數(shù)，所以上述目標(biāo)可轉(zhuǎn)化為 (13

15、)對一定類別的列車而言，其區(qū)間運(yùn)行時(shí)分是常數(shù)，故可推導(dǎo)出上式的等價(jià)表達(dá)式 (14)為了增開臨時(shí)列車，則必須避免由此產(chǎn)生的區(qū)間、站線以及最小間隔時(shí)間的沖突，但是由題意可知，客車運(yùn)行時(shí)間不能進(jìn)行調(diào)整，因此只能對貨車做出調(diào)整，同時(shí)做出如下的假設(shè)：待調(diào)列車在每一車站都可能停車避免各種沖突。在上述假設(shè)下，各種最小間隔時(shí)間都需要添加一個(gè)起停車附加時(shí)分起停。這樣，一方面保證了列車運(yùn)行絕對滿足間隔時(shí)間要求；另一方面起停車附加時(shí)分起停的數(shù)值較小，對臨時(shí)列車以及貨車的調(diào)整給予了方便。綜上所述，為了得到待調(diào)列車的相互關(guān)系和相互位置，可用如下模型描述 （15） （16）對于客流增加時(shí)要增開的5對臨時(shí)客車：北京上海，北

16、京南京，天津上海，北京合肥（有效區(qū)間為北京蚌埠），北京青島（有效區(qū)間為北京濟(jì)南），進(jìn)行分析。發(fā)現(xiàn)其中有3對臨時(shí)客車經(jīng)過北京天津；5對經(jīng)過天津濟(jì)南；4對經(jīng)過濟(jì)南蚌埠；3對經(jīng)過蚌埠南京；2對經(jīng)過南京上海。根據(jù)上述模型，首先要去掉不能安排臨時(shí)客車的區(qū)間，通過編程計(jì)算，分別求出了各段可以增開的臨時(shí)客車的數(shù)量。表5 北京上海：（下行）北京合肥：（下行）天津上海：（下行）到站時(shí)刻始發(fā)站發(fā)車時(shí)刻0北京20：00到站時(shí)刻始發(fā)站發(fā)車時(shí)刻0北京19：4222：24天津22：280天津22：1022：03天津22：102：10濟(jì)南02：2301：42濟(jì)南02：0001：42濟(jì)南02：0003：34泰山03：4504

17、：16兗州04：3004：16兗州04：3004：43兗州04：5105：50南京06：1205：50南京06：1205：34蚌埠008：42上海008：42上海0北京南京：（下行）北京青島：（下行）到站時(shí)刻始發(fā)站發(fā)車時(shí)刻到站時(shí)刻始發(fā)站發(fā)車時(shí)刻0北京19：500北京20：1222：12天津22：2022：15天津22：2701：52濟(jì)南02：1223：18滄州23：2603：25泰山03：3301：13德州01：2004：25兗州04：4002：25濟(jì)南006：11南京03.列車晚點(diǎn)時(shí)調(diào)度策略的制定當(dāng)某一列客車因故晚點(diǎn)，它必然會影響這一區(qū)間段后面很多列車的正常運(yùn)行，列車調(diào)度員就要調(diào)整后續(xù)列車的

18、運(yùn)行狀態(tài)，制訂出新的列車時(shí)刻表，設(shè)調(diào)整起始時(shí)間為，調(diào)整時(shí)間長度為，在內(nèi)在共有列待調(diào)整列車，記為分別表示在的到達(dá)和出發(fā)時(shí)刻，若在站始發(fā)，則記，若列車在站終到，則記；為在的停車標(biāo)識變量，停車時(shí)值為1，通過時(shí)值為0；表示時(shí)刻占用到發(fā)線的標(biāo)識變量，占用時(shí)為1，否則為0。對于，稱進(jìn)入調(diào)度區(qū)段的車站為其發(fā)站，記為，離開調(diào)度區(qū)段的車站稱為其到站，記為。列車運(yùn)行調(diào)整問題含有很多優(yōu)化目標(biāo)，而提高列車平均旅行速度和提高列車運(yùn)行正點(diǎn)率是實(shí)際指揮中經(jīng)常被使用的兩個(gè)優(yōu)化目標(biāo)。提高列車運(yùn)行平均旅行速度也就是減少列車通過本調(diào)度區(qū)段的時(shí)間，此優(yōu)化目標(biāo)可用在發(fā)站的到達(dá)時(shí)刻與到站的出發(fā)時(shí)刻來計(jì)算，具體為 （17）在上式中，如果為始發(fā)列車，則在發(fā)站取出發(fā)時(shí)刻計(jì)算；如果為終到列車，則在到站取到達(dá)時(shí)刻計(jì)算。列車運(yùn)行正點(diǎn)在運(yùn)輸統(tǒng)計(jì)中有明確規(guī)定，在此定義變量為在到站運(yùn)行正點(diǎn)的標(biāo)識變量，正點(diǎn)時(shí)值為1，否則值為0。是列車種類、發(fā)站與到站的到發(fā)時(shí)刻的函數(shù)。提高列車運(yùn)行正點(diǎn)率也就是減少晚點(diǎn)列車數(shù)，此優(yōu)化目標(biāo)可以表示為 （18）計(jì)算步驟：求解多目標(biāo)優(yōu)化列車運(yùn)行調(diào)整問題的分解協(xié)調(diào)計(jì)算模型的計(jì)算過程如下所示