1. 從“堵車(chē)”到“秒級(jí)調(diào)度”高速列車(chē)調(diào)度為什么是數(shù)學(xué)建模的絕佳戰(zhàn)場(chǎng)如果你在早晚高峰開(kāi)過(guò)車(chē)或者經(jīng)歷過(guò)地鐵站臺(tái)的人潮你大概能理解“調(diào)度”兩個(gè)字背后那種焦灼的無(wú)力感。但和城市交通相比高速鐵路的調(diào)度完全是另一個(gè)維度的挑戰(zhàn)。想象一下在一條雙向、多車(chē)道的軌道上以每小時(shí)300公里以上速度飛馳的列車(chē)它們不是汽車(chē)不能隨意變道、減速或超車(chē)。一趟列車(chē)的晚點(diǎn)就像多米諾骨牌會(huì)引發(fā)一連串的連鎖反應(yīng)導(dǎo)致整個(gè)路網(wǎng)運(yùn)行圖癱瘓。這背后是一個(gè)由時(shí)間、空間、速度和資源交織而成的、極其復(fù)雜的動(dòng)態(tài)系統(tǒng)。這就是高速列車(chē)調(diào)度模型的核心戰(zhàn)場(chǎng)。它遠(yuǎn)不止是“排個(gè)時(shí)刻表”那么簡(jiǎn)單而是一個(gè)典型的、高約束、多目標(biāo)的優(yōu)化問(wèn)題。我們得在確保絕對(duì)安全這是鐵路運(yùn)輸?shù)纳€的前提下去追求最高的運(yùn)行效率比如正點(diǎn)率、通過(guò)能力和最優(yōu)的經(jīng)濟(jì)效益比如能耗、車(chē)底周轉(zhuǎn)。這些目標(biāo)很多時(shí)候是相互矛盾的為了趕點(diǎn)而提速能耗就上去了為了節(jié)能而勻速運(yùn)行可能就擠占了后續(xù)列車(chē)的路徑。數(shù)學(xué)建模就是我們把這片混沌的戰(zhàn)場(chǎng)用清晰的數(shù)學(xué)語(yǔ)言“翻譯”出來(lái)并找到最優(yōu)或近似最優(yōu)作戰(zhàn)方案的過(guò)程。我接觸過(guò)不少相關(guān)項(xiàng)目從學(xué)術(shù)研究到實(shí)際系統(tǒng)的仿真驗(yàn)證發(fā)現(xiàn)很多人一上來(lái)就埋頭寫(xiě)代碼、調(diào)參數(shù)卻忽略了最根本的問(wèn)題定義。這篇內(nèi)容我就以一個(gè)從業(yè)者的視角和你聊聊高速列車(chē)調(diào)度模型到底在解決什么以及如何從零開(kāi)始構(gòu)建一個(gè)能“實(shí)戰(zhàn)”的模型。我們會(huì)避開(kāi)那些空洞的理論直接切入核心的數(shù)學(xué)表達(dá)、關(guān)鍵的算法選擇以及我踩過(guò)的一些坑。無(wú)論你是正在備戰(zhàn)數(shù)學(xué)建模競(jìng)賽的學(xué)生還是對(duì)運(yùn)籌優(yōu)化在實(shí)際工程中應(yīng)用感興趣的工程師相信這些從一線得來(lái)的經(jīng)驗(yàn)?zāi)芙o你帶來(lái)一些不一樣的思路。2. 模型基石如何用數(shù)學(xué)語(yǔ)言描述列車(chē)與軌道構(gòu)建模型的第一步是把物理世界抽象成數(shù)學(xué)對(duì)象和關(guān)系。這一步如果沒(méi)做扎實(shí)后面的所有優(yōu)化都是空中樓閣。我們得先定義清楚在這個(gè)系統(tǒng)里有哪些“演員”以及它們必須遵守哪些“舞臺(tái)規(guī)則”。2.1 核心要素的數(shù)學(xué)定義首先我們把一列列車(chē)看作一個(gè)需要從A點(diǎn)移動(dòng)到B點(diǎn)的“任務(wù)”。這個(gè)任務(wù)不是簡(jiǎn)單的點(diǎn)對(duì)點(diǎn)它由一系列按順序訪問(wèn)的“車(chē)站”或“區(qū)間”組成。我們可以用集合T {1, 2, ..., N}來(lái)表示所有列車(chē)用集合S {1, 2, ..., M}來(lái)表示所有車(chē)站或更細(xì)粒度的“軌道區(qū)段”。對(duì)于每一趟列車(chē)i我們關(guān)心它的路徑和時(shí)間。路徑通常由一個(gè)有序的車(chē)站序列P_i [s_{i1}, s_{i2}, ..., s_{ik}]定義。而時(shí)間則體現(xiàn)在它到達(dá)每個(gè)車(chē)站j的時(shí)間A_{ij}和離開(kāi)時(shí)間D_{ij}上。這里就引出了第一個(gè)關(guān)鍵變量在站停留時(shí)間τ_{ij} D_{ij} - A_{ij}。這個(gè)時(shí)間不是固定的它包含了必要的技術(shù)作業(yè)時(shí)間如上下客、清潔和可能的緩沖時(shí)間。比車(chē)站更精細(xì)的是區(qū)間也就是兩個(gè)車(chē)站之間的軌道。這是沖突最容易發(fā)生的地方。我們需要定義列車(chē)在區(qū)間(s, s)上的運(yùn)行時(shí)間t_{i, s-s}。這個(gè)時(shí)間不是簡(jiǎn)單的距離除以速度它受到列車(chē)性能加速/制動(dòng)曲線、線路坡度、曲率以及臨時(shí)限速的約束。在實(shí)際建模中我們常常會(huì)使用一個(gè)分段函數(shù)或查詢(xún)表來(lái)根據(jù)初始速度、目標(biāo)速度和線路條件計(jì)算運(yùn)行時(shí)間。2.2 安全約束不可逾越的鐵律安全是鐵路運(yùn)輸?shù)牡拙€在模型里體現(xiàn)為一系列硬性約束。最重要的兩個(gè)是最小追蹤間隔和車(chē)站/區(qū)間獨(dú)占性。最小追蹤間隔為了防止后車(chē)追尾前車(chē)在同一區(qū)間內(nèi)前后兩列同向列車(chē)必須保持一個(gè)最小的時(shí)間間隔I_{min}。這意味著如果列車(chē)i進(jìn)入?yún)^(qū)間(s, s)的時(shí)間是t那么下一趟列車(chē)j進(jìn)入同一區(qū)間的時(shí)間必須滿(mǎn)足t_j ≥ t_i I_{min}。這個(gè)間隔的數(shù)值是根據(jù)列車(chē)制動(dòng)性能、信號(hào)系統(tǒng)制式如CTCS-2、CTCS-3精確計(jì)算出來(lái)的在模型中通常作為固定參數(shù)輸入。車(chē)站/區(qū)間獨(dú)占性這是一條更嚴(yán)格的約束。在絕大多數(shù)高速鐵路線上一個(gè)車(chē)站的同一股道或者一個(gè)區(qū)間可以理解為兩個(gè)信號(hào)機(jī)之間的閉塞分區(qū)在同一時(shí)刻只能被一列車(chē)占用。這不像公路可以并行。用數(shù)學(xué)表達(dá)就是對(duì)于任意兩趟列車(chē)i和j以及任意一個(gè)資源r股道或區(qū)間它們的占用時(shí)間區(qū)間[占用開(kāi)始時(shí)間 占用結(jié)束時(shí)間]不能重疊。這是一個(gè)典型的互斥約束是導(dǎo)致調(diào)度問(wèn)題計(jì)算復(fù)雜度的核心根源之一。注意這里有一個(gè)常見(jiàn)的簡(jiǎn)化與現(xiàn)實(shí)的差異。在學(xué)術(shù)模型或競(jìng)賽模型中我們常常把區(qū)間看作一個(gè)“點(diǎn)”資源只要滿(mǎn)足間隔約束即可。但在更精細(xì)的仿真中列車(chē)是有一個(gè)“長(zhǎng)度”的它的頭、尾占用不同資源的時(shí)間點(diǎn)不同這就需要引入更復(fù)雜的“進(jìn)路”概念即列車(chē)從進(jìn)入道岔區(qū)到停穩(wěn)或駛離所經(jīng)過(guò)的一系列連續(xù)的軌道區(qū)段集合。對(duì)于入門(mén)級(jí)模型先從“點(diǎn)”資源假設(shè)開(kāi)始是可行的。2.3 目標(biāo)函數(shù)我們到底要優(yōu)化什么約束定義了可行的解空間而目標(biāo)函數(shù)則指引我們尋找最優(yōu)解。高速列車(chē)調(diào)度通常是一個(gè)多目標(biāo)優(yōu)化問(wèn)題常見(jiàn)的目標(biāo)包括總晚點(diǎn)時(shí)間最小化這是最直觀的運(yùn)營(yíng)指標(biāo)。每趟列車(chē)都有一個(gè)計(jì)劃時(shí)刻表我們定義它的到達(dá)晚點(diǎn)時(shí)間delay_{i} max(0, A_{i,目的地} - 計(jì)劃到達(dá)時(shí)間)。目標(biāo)就是最小化所有列車(chē)晚點(diǎn)時(shí)間的總和或加權(quán)總和。加權(quán)可以體現(xiàn)列車(chē)等級(jí)如G字頭高鐵權(quán)重高于D字頭動(dòng)車(chē)。總旅行時(shí)間最小化這個(gè)目標(biāo)更偏向系統(tǒng)效率即最小化所有列車(chē)從始發(fā)到終點(diǎn)的總耗時(shí)。它和晚點(diǎn)最小化相關(guān)但不完全等同。總能耗最小化在“雙碳”背景下越來(lái)越重要。列車(chē)能耗與運(yùn)行速度曲線工況強(qiáng)相關(guān)。優(yōu)化能耗通常意味著在滿(mǎn)足時(shí)間約束的前提下盡可能讓列車(chē)勻速運(yùn)行減少不必要的加速和制動(dòng)。魯棒性最大化我們希望制定的調(diào)度計(jì)劃不是“繃得太緊”的而是能夠抵御一些小擾動(dòng)如乘客上下車(chē)延誤、輕微的設(shè)備故障。這可以通過(guò)在車(chē)站停留時(shí)間和區(qū)間運(yùn)行時(shí)間中引入緩沖時(shí)間來(lái)實(shí)現(xiàn)優(yōu)化目標(biāo)是最大化緩沖時(shí)間的分布或最小化計(jì)劃對(duì)擾動(dòng)的敏感度。在實(shí)際項(xiàng)目中我們往往需要權(quán)衡這些目標(biāo)。一個(gè)常用的方法是主目標(biāo)法將一個(gè)最重要的目標(biāo)如總晚點(diǎn)時(shí)間作為優(yōu)化目標(biāo)將其他目標(biāo)如總能耗不超過(guò)某個(gè)閾值轉(zhuǎn)化為約束條件。另一種方法是加權(quán)求和法給不同目標(biāo)賦予權(quán)重合并成一個(gè)單一目標(biāo)函數(shù)。但權(quán)重的設(shè)定本身就是一個(gè)需要經(jīng)驗(yàn)和反復(fù)調(diào)試的難題。3. 算法工具箱從精確求解到智能啟發(fā)當(dāng)我們把問(wèn)題用上一章的數(shù)學(xué)公式描述清楚后接下來(lái)就要面對(duì)一個(gè)殘酷的現(xiàn)實(shí)高速列車(chē)調(diào)度問(wèn)題是一個(gè)NP-hard的組合優(yōu)化問(wèn)題。隨著列車(chē)數(shù)量和車(chē)站數(shù)量的增加解空間會(huì)呈指數(shù)級(jí)爆炸想找到全局最優(yōu)解在有限時(shí)間內(nèi)幾乎不可能。因此算法的選擇本質(zhì)上是在求解精度和計(jì)算時(shí)間之間尋找平衡。3.1 精確算法在“小場(chǎng)景”中尋找最優(yōu)基準(zhǔn)對(duì)于規(guī)模非常小的問(wèn)題比如一個(gè)樞紐站附近幾趟列車(chē)的調(diào)度我們可以嘗試使用精確算法來(lái)獲取全局最優(yōu)解這個(gè)解可以作為評(píng)價(jià)其他算法好壞的“黃金標(biāo)準(zhǔn)”。混合整數(shù)線性規(guī)劃M(mǎn)ILP是最常用的精確建模框架。它的強(qiáng)大之處在于能把前面提到的那些復(fù)雜的邏輯約束如互斥約束、順序約束通過(guò)引入0-1決策變量和線性不等式巧妙地表達(dá)出來(lái)。例如為了表達(dá)兩列車(chē)i和j在區(qū)間r上的順序我們可以引入一個(gè)二元變量y_{ijr}如果i在j之前使用資源r則y_{ijr}1否則為0。然后通過(guò)一大組“大M”約束將y_{ijr}與列車(chē)的時(shí)間變量關(guān)聯(lián)起來(lái)。在Matlab中你可以使用優(yōu)化工具箱中的intlinprog函數(shù)來(lái)求解MILP模型。它的優(yōu)勢(shì)是模型清晰一旦建成求解器如Gurobi, CPLEXMatlab也內(nèi)置了相關(guān)接口會(huì)替你處理復(fù)雜的搜索過(guò)程。但劣勢(shì)也極其明顯當(dāng)列車(chē)數(shù)超過(guò)20或者網(wǎng)絡(luò)結(jié)構(gòu)稍復(fù)雜求解時(shí)間可能長(zhǎng)達(dá)數(shù)小時(shí)甚至無(wú)法完成。因此MILP更適合用于理論研究、小規(guī)模案例驗(yàn)證或者作為復(fù)雜算法中的一個(gè)子模塊。3.2 啟發(fā)式與元啟發(fā)式算法應(yīng)對(duì)大規(guī)模問(wèn)題的實(shí)戰(zhàn)主力面對(duì)實(shí)際路網(wǎng)中成百上千的列車(chē)我們必須依賴(lài)啟發(fā)式算法。這類(lèi)算法不保證找到最優(yōu)解但能在可接受的時(shí)間內(nèi)找到一個(gè)高質(zhì)量的可行解。貪婪算法是一種最直觀的啟發(fā)式策略。它的核心思想是“每一步都做出當(dāng)前看起來(lái)最好的選擇”。在列車(chē)調(diào)度中一個(gè)典型的貪婪策略是按照列車(chē)優(yōu)先級(jí)或計(jì)劃出發(fā)時(shí)間的順序一趟一趟地為列車(chē)安排路徑和時(shí)間每次安排時(shí)都將其插入當(dāng)前已安排列車(chē)的時(shí)間隙縫中并盡可能減少對(duì)已有計(jì)劃的干擾。這種方法速度極快但容易陷入局部最優(yōu)因?yàn)橄劝才诺牧熊?chē)“霸占”了好的時(shí)間窗口可能導(dǎo)致后面更高優(yōu)先級(jí)的列車(chē)無(wú)路可走。遺傳算法GA是元啟發(fā)式算法的代表它模擬生物進(jìn)化過(guò)程。在調(diào)度問(wèn)題中一個(gè)“染色體”可以編碼所有列車(chē)的出發(fā)時(shí)間序列或順序。算法從一個(gè)隨機(jī)生成的種群開(kāi)始通過(guò)“選擇”保留適應(yīng)度高的個(gè)體、“交叉”交換兩個(gè)優(yōu)秀個(gè)體的部分基因和“變異”隨機(jī)改變某個(gè)個(gè)體的部分基因來(lái)迭代進(jìn)化。適應(yīng)度函數(shù)就是我們的目標(biāo)函數(shù)如總晚點(diǎn)時(shí)間。GA的優(yōu)點(diǎn)是全局搜索能力強(qiáng)能處理復(fù)雜、非線性的目標(biāo)函數(shù)。但在Matlab中實(shí)現(xiàn)一個(gè)高效的GA需要仔細(xì)設(shè)計(jì)編碼方式、交叉變異算子并調(diào)試種群大小、迭代次數(shù)等參數(shù)否則很容易早熟收斂或計(jì)算緩慢。模擬退火SA是另一種受物理過(guò)程啟發(fā)的算法。它從一個(gè)初始解開(kāi)始通過(guò)隨機(jī)擾動(dòng)產(chǎn)生一個(gè)新解。如果新解更好則接受它如果更差則以一個(gè)隨時(shí)間衰減的概率接受它。這個(gè)“以一定概率接受差解”的機(jī)制使得SA有能力跳出局部最優(yōu)陷阱。在調(diào)度問(wèn)題中擾動(dòng)可以定義為隨機(jī)交換兩趟列車(chē)的發(fā)車(chē)順序或者隨機(jī)延遲某趟列車(chē)的出發(fā)時(shí)間。SA的參數(shù)初始溫度、降溫速率、終止溫度對(duì)結(jié)果影響很大需要反復(fù)試驗(yàn)。3.3 基于規(guī)則的實(shí)時(shí)調(diào)整算法上面討論的多是“離線調(diào)度”即基于計(jì)劃時(shí)刻表提前做出安排。但鐵路運(yùn)營(yíng)中充滿(mǎn)了不確定性真正的挑戰(zhàn)在于“實(shí)時(shí)調(diào)度”或“擾動(dòng)恢復(fù)”。當(dāng)一趟列車(chē)晚點(diǎn)后調(diào)度員需要快速做出調(diào)整決策。這時(shí)復(fù)雜優(yōu)化算法可能來(lái)不及計(jì)算基于規(guī)則的專(zhuān)家系統(tǒng)就顯得非常實(shí)用。這些規(guī)則通常是“if-then”的形式來(lái)源于資深調(diào)度員的經(jīng)驗(yàn)。例如規(guī)則1區(qū)間沖突如果預(yù)測(cè)到兩列車(chē)將在同一區(qū)間發(fā)生沖突且后車(chē)是低等級(jí)列車(chē)則令后車(chē)在前方車(chē)站停車(chē)待避。規(guī)則2到發(fā)線沖突如果一趟列車(chē)晚點(diǎn)導(dǎo)致其計(jì)劃占用的到發(fā)線被另一列車(chē)占用則為其分配另一條空閑的到發(fā)線。規(guī)則3晚點(diǎn)傳播如果一趟始發(fā)列車(chē)晚點(diǎn)超過(guò)X分鐘則考慮調(diào)整其后續(xù)所有車(chē)次的時(shí)刻必要時(shí)取消部分車(chē)次以保證主干線暢通。在Matlab中我們可以用簡(jiǎn)單的狀態(tài)機(jī)和邏輯判斷來(lái)實(shí)現(xiàn)這些規(guī)則。雖然從全局看這些規(guī)則組合起來(lái)不一定是最優(yōu)的但它們決策速度快、可解釋性強(qiáng)在實(shí)際調(diào)度指揮系統(tǒng)中往往是最后落地的方案。將優(yōu)化算法用于生成調(diào)整預(yù)案和規(guī)則引擎用于快速應(yīng)急結(jié)合是一種常見(jiàn)的架構(gòu)。4. 實(shí)戰(zhàn)案例拆解單線區(qū)段列車(chē)晚點(diǎn)恢復(fù)理論說(shuō)了這么多我們來(lái)看一個(gè)簡(jiǎn)化但非常經(jīng)典的實(shí)戰(zhàn)案例單線鐵路區(qū)段列車(chē)晚點(diǎn)后的運(yùn)行調(diào)整。這個(gè)場(chǎng)景在數(shù)學(xué)建模競(jìng)賽和實(shí)際鐵路中都非常常見(jiàn)能很好地體現(xiàn)模型和算法的應(yīng)用。4.1 問(wèn)題場(chǎng)景與模型建立假設(shè)我們有一條單線鐵路有A、B、C、D四個(gè)車(chē)站順序排列。單線意味著上下行列車(chē)共用一條軌道只能在車(chē)站進(jìn)行會(huì)車(chē)一列停靠另一列通過(guò)或越行后車(chē)超越前車(chē)但高速鐵路極少越行通常只能待避。初始計(jì)劃如下T1列車(chē)下行A站發(fā)車(chē)時(shí)間8:00計(jì)劃依次通過(guò)B、C到達(dá)D站。T2列車(chē)上行D站發(fā)車(chē)時(shí)間8:05計(jì)劃依次通過(guò)C、B到達(dá)A站。已知區(qū)間運(yùn)行時(shí)間、車(chē)站最小停站時(shí)間。最小追蹤間隔為5分鐘。車(chē)站只有一條正線可供通過(guò)一條到發(fā)線可供停車(chē)會(huì)車(chē)。現(xiàn)在假設(shè)T1列車(chē)從A站出發(fā)時(shí)晚點(diǎn)了15分鐘8:15才發(fā)車(chē)。如果不做調(diào)整T1和T2將在B-C區(qū)間某個(gè)點(diǎn)發(fā)生正面沖突這是絕對(duì)禁止的。我們的任務(wù)是在滿(mǎn)足所有安全約束的前提下調(diào)整T1和T2的運(yùn)行和停站計(jì)劃使得它們都能安全通過(guò)并且使總晚點(diǎn)時(shí)間T1和T2最終到達(dá)目的地的晚點(diǎn)時(shí)間之和最小。我們首先用MILP來(lái)建模。定義決策變量為兩趟列車(chē)在每個(gè)車(chē)站的到達(dá)和出發(fā)時(shí)間。核心約束包括運(yùn)行時(shí)間約束列車(chē)在區(qū)間的運(yùn)行時(shí)間等于固定值。停站時(shí)間約束在B、C站的停站時(shí)間至少為技術(shù)作業(yè)所需時(shí)間如2分鐘。區(qū)間互斥約束對(duì)于A-B、B-C、C-D這三個(gè)區(qū)間T1和T2的占用時(shí)間不能重疊。這需要引入二元順序變量和“大M”約束來(lái)表達(dá)。車(chē)站到發(fā)線互斥約束在B站和C站兩列車(chē)不能同時(shí)使用到發(fā)線假設(shè)會(huì)車(chē)時(shí)一列停靠到發(fā)線另一列通過(guò)正線。這也需要引入二元變量。目標(biāo)函數(shù)最小化(T1到達(dá)D站時(shí)間 - 原計(jì)劃時(shí)間) (T2到達(dá)A站時(shí)間 - 原計(jì)劃時(shí)間)。4.2 Matlab求解實(shí)現(xiàn)與代碼要點(diǎn)在Matlab中我們可以使用intlinprog來(lái)求解。下面是一些關(guān)鍵的代碼片段和思路% 假設(shè)變量向量 x 的定義如下 % x(1): T1在B站的到達(dá)時(shí)間 % x(2): T1在B站的出發(fā)時(shí)間 % x(3): T1在C站的到達(dá)時(shí)間 % x(4): T1在C站的出發(fā)時(shí)間 % x(5): T1在D站的到達(dá)時(shí)間 % x(6): T2在C站的到達(dá)時(shí)間 % x(7): T2在C站的出發(fā)時(shí)間 % x(8): T2在B站的到達(dá)時(shí)間 % x(9): T2在B站的出發(fā)時(shí)間 % x(10): T2在A站的到達(dá)時(shí)間 % x(11): 二元變量 y1表示在B-C區(qū)間T1是否在T2之前 (1為是) % x(12): 二元變量 y2表示在C站T1是否使用到發(fā)線在T2之前 f [0,0,0,0,1,0,0,0,0,1,0,0]; % 目標(biāo)函數(shù)系數(shù)最小化T1和T2的到達(dá)時(shí)間這里簡(jiǎn)化實(shí)際需減計(jì)劃時(shí)間 intcon [11, 12]; % 指定第11、12個(gè)變量為整數(shù)變量0-1 A []; b []; Aeq []; beq []; % 初始化不等式和等式約束矩陣 lb zeros(12,1); ub inf(12,1); % 下界和上界 % 1. 運(yùn)行時(shí)間與停站時(shí)間約束等式約束 % 例如T1在A-B區(qū)間運(yùn)行時(shí)間為30分鐘且A站出發(fā)晚點(diǎn)至8:15 Aeq(1,1) 1; Aeq(1,5) -1; beq(1) -30; % x(1) - x(5) -30? 需要仔細(xì)定義時(shí)間關(guān)系 % 更準(zhǔn)確的表達(dá)x(1) 8:15 A-B運(yùn)行時(shí)間。這里需要根據(jù)變量定義仔細(xì)構(gòu)建線性等式。 % 停站時(shí)間x(2) - x(1) 2 (B站最少停2分鐘) A(end1, 1) -1; A(end1, 2) 1; b(end1) -2; % 2. 區(qū)間互斥約束使用大M法M為一個(gè)足夠大的數(shù)如1000 % 對(duì)于B-C區(qū)間約束如果 y11 (T1先)則 T2到達(dá)C站時(shí)間 T1離開(kāi)B站時(shí)間 最小間隔 % 這轉(zhuǎn)化為兩組線性不等式 % x(6) x(2) I_min - M*(1-y1) % x(3) x(7) I_min - M*y1 M 1000; I_min 5; A(end1, 2) -1; A(end, 6) 1; A(end, 11) -M; b(end1) I_min - M; A(end1, 7) -1; A(end, 3) 1; A(end, 11) M; b(end1) I_min; % 3. 車(chē)站資源互斥約束類(lèi)似原理 % ... 省略詳細(xì)構(gòu)建過(guò)程 ... % 調(diào)用intlinprog求解 [x, fval, exitflag] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub);注意上面只是一個(gè)極度簡(jiǎn)化的框架示意。真實(shí)建模中變量定義和約束構(gòu)建非常繁瑣且容易出錯(cuò)尤其是“大M”約束如果M值選取不當(dāng)可能導(dǎo)致模型松弛性很差求解困難。建議先用小規(guī)模例子在紙上畫(huà)清楚時(shí)間-空間圖明確所有變量和約束的邏輯關(guān)系再開(kāi)始編碼。對(duì)于這個(gè)簡(jiǎn)單案例MILP可能很快就能求出最優(yōu)解讓晚點(diǎn)的T1在B站停車(chē)等待對(duì)向的T2先通過(guò)B-C區(qū)間然后T1再出發(fā)。這樣T1的晚點(diǎn)會(huì)增加但T2可以正點(diǎn)或輕微晚點(diǎn)總晚點(diǎn)時(shí)間最小。4.3 從精確解到啟發(fā)式拓展如果車(chē)站和列車(chē)數(shù)量增多MILP求解會(huì)變慢。這時(shí)我們可以用啟發(fā)式方法。例如一個(gè)簡(jiǎn)單的沖突消解算法流程可以是按照當(dāng)前時(shí)間預(yù)測(cè)所有列車(chē)的位置。檢測(cè)未來(lái)一段時(shí)間內(nèi)如未來(lái)30分鐘所有潛在的沖突區(qū)間或車(chē)站占用沖突。對(duì)每個(gè)沖突按照預(yù)設(shè)的規(guī)則進(jìn)行消解如讓等級(jí)低的列車(chē)等待讓距離沖突點(diǎn)遠(yuǎn)的列車(chē)提前在站內(nèi)等待。調(diào)整相關(guān)列車(chē)的時(shí)刻重新預(yù)測(cè)回到步驟1直到?jīng)]有沖突。用Matlab實(shí)現(xiàn)這個(gè)循環(huán)其核心是一個(gè)基于事件推進(jìn)的仿真器。代碼結(jié)構(gòu)會(huì)更像是一個(gè)狀態(tài)機(jī)而不是一個(gè)優(yōu)化模型。雖然結(jié)果可能不如MILP最優(yōu)但計(jì)算速度極快適合實(shí)時(shí)性要求高的場(chǎng)景。5. 模型進(jìn)階考慮動(dòng)態(tài)性與不確定性的挑戰(zhàn)前面的模型大多建立在“確定性”假設(shè)上運(yùn)行時(shí)間固定、無(wú)意外事件。但現(xiàn)實(shí)世界充滿(mǎn)不確定性。模型的進(jìn)階就是要擁抱這種不確定性。5.1 隨機(jī)運(yùn)行時(shí)間與魯棒調(diào)度列車(chē)區(qū)間運(yùn)行時(shí)間并非定值它會(huì)受到天氣、乘客載荷、司機(jī)操作、臨時(shí)限速等多種因素影響通常在一個(gè)范圍內(nèi)波動(dòng)。我們可以將其建模為一個(gè)隨機(jī)變量例如服從正態(tài)分布N(μ, σ^2)。這時(shí)我們的調(diào)度目標(biāo)就從“最小化總晚點(diǎn)時(shí)間”轉(zhuǎn)變?yōu)椤白钚』偼睃c(diǎn)時(shí)間的期望值”或者更激進(jìn)一些“在運(yùn)行時(shí)間隨機(jī)波動(dòng)的情況下最大化調(diào)度計(jì)劃按時(shí)完成的概率”。這就引出了隨機(jī)規(guī)劃或魯棒優(yōu)化的框架。隨機(jī)規(guī)劃假設(shè)我們知道運(yùn)行時(shí)間概率分布我們可以通過(guò)生成大量場(chǎng)景Scenarios來(lái)近似。例如用蒙特卡洛方法模擬1000種不同的運(yùn)行時(shí)間組合然后優(yōu)化一個(gè)“平均性能”最好的計(jì)劃。在Matlab中這相當(dāng)于要解一個(gè)大規(guī)模MILP計(jì)算量巨大。魯棒優(yōu)化我們不去假設(shè)具體的分布而是定義一個(gè)“不確定集”例如每個(gè)區(qū)間運(yùn)行時(shí)間在其標(biāo)稱(chēng)值的±5%范圍內(nèi)波動(dòng)。然后我們優(yōu)化的是“在最壞情況下的性能”。也就是說(shuō)尋找一個(gè)調(diào)度計(jì)劃即使所有區(qū)間的運(yùn)行時(shí)間都向不利方向波動(dòng)其造成的總晚點(diǎn)也是可接受的。這種方法得到的計(jì)劃通常更保守會(huì)嵌入更多緩沖時(shí)間。在實(shí)際應(yīng)用中更實(shí)用的是一種兩階段方法第一階段制定一個(gè)基準(zhǔn)計(jì)劃確定性?xún)?yōu)化第二階段設(shè)計(jì)一套實(shí)時(shí)響應(yīng)規(guī)則當(dāng)運(yùn)行時(shí)間與計(jì)劃出現(xiàn)偏差時(shí)觸發(fā)規(guī)則進(jìn)行局部調(diào)整。這比求解一個(gè)完整的隨機(jī)規(guī)劃模型要可行得多。5.2 乘客流銜接與綜合效益優(yōu)化列車(chē)調(diào)度最終是為乘客服務(wù)的。一個(gè)更深層次的模型是車(chē)流-客流協(xié)同優(yōu)化。晚點(diǎn)不僅影響列車(chē)本身還會(huì)導(dǎo)致乘客錯(cuò)過(guò)接續(xù)的列車(chē)。因此高級(jí)的調(diào)度模型會(huì)將乘客的換乘考慮在內(nèi)。我們需要引入乘客OD起訖點(diǎn)矩陣知道在每個(gè)車(chē)站有多少乘客需要從哪趟車(chē)換乘到哪趟車(chē)。然后在目標(biāo)函數(shù)中除了列車(chē)晚點(diǎn)懲罰還要加上乘客總旅行時(shí)間增加的懲罰。這帶來(lái)了巨大的復(fù)雜性決策變量從列車(chē)時(shí)刻擴(kuò)展到了乘客的路徑選擇。一種常見(jiàn)的簡(jiǎn)化方法是假設(shè)乘客總是選擇計(jì)劃時(shí)刻表上最快的換乘方案。當(dāng)調(diào)度調(diào)整導(dǎo)致前一班車(chē)晚點(diǎn)使得部分乘客無(wú)法趕上原定換乘車(chē)次時(shí)系統(tǒng)需要為這些乘客分配新的換乘車(chē)次可能更晚由此產(chǎn)生額外的等待時(shí)間。優(yōu)化算法在調(diào)整列車(chē)時(shí)刻時(shí)需要評(píng)估這種連鎖反應(yīng)對(duì)乘客的影響。這個(gè)層面的模型已經(jīng)非常接近實(shí)際的智能調(diào)度系統(tǒng)核心了。它通常需要分層求解上層優(yōu)化列車(chē)時(shí)刻下層模擬乘客流分配反復(fù)迭代。在Matlab中實(shí)現(xiàn)這樣的仿真-優(yōu)化循環(huán)對(duì)編程和算法設(shè)計(jì)能力是很大的考驗(yàn)。6. 從模型到仿真Matlab實(shí)戰(zhàn)技巧與避坑指南構(gòu)建數(shù)學(xué)模型和算法只是第一步讓它在計(jì)算機(jī)上正確、高效地跑起來(lái)才是真正的挑戰(zhàn)。基于我大量的項(xiàng)目經(jīng)驗(yàn)這里分享一些在Matlab中實(shí)現(xiàn)調(diào)度模型時(shí)的實(shí)戰(zhàn)技巧和常見(jiàn)陷阱。6.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)效率與清晰度的平衡糟糕的數(shù)據(jù)結(jié)構(gòu)會(huì)讓代碼變得難以理解和維護(hù)更會(huì)嚴(yán)重影響運(yùn)行效率。對(duì)于列車(chē)調(diào)度問(wèn)題我推薦使用結(jié)構(gòu)體數(shù)組或表格來(lái)管理實(shí)體數(shù)據(jù)。% 示例使用結(jié)構(gòu)體數(shù)組表示列車(chē) trains(1).ID G101; trains(1).Type HighSpeed; trains(1).Schedule.Arrival [0, 30, 65, 100]; % 在A,B,C,D站的計(jì)劃到達(dá)時(shí)間分鐘 trains(1).Schedule.Departure [0, 32, 67, 100]; % 計(jì)劃出發(fā)時(shí)間 trains(1).Priority 1; % 優(yōu)先級(jí)1為最高 trains(1).Route {A, B, C, D}; % 路徑 % 使用表格表示區(qū)間屬性 sections table(); sections.Name {A-B, B-C, C-D}; sections.Length [50, 60, 55]; % 公里 sections.NominalTime [30, 35, 33]; % 分鐘 sections.MinHeadway [5, 5, 5]; % 最小追蹤間隔這種組織方式非常直觀方便查詢(xún)和更新。當(dāng)進(jìn)行沖突檢測(cè)時(shí)你可以輕松地遍歷trains結(jié)構(gòu)體計(jì)算每列車(chē)在每個(gè)區(qū)間的占用時(shí)間窗口。6.2 時(shí)間推進(jìn)與事件驅(qū)動(dòng)仿真調(diào)度過(guò)程本質(zhì)是隨時(shí)間推進(jìn)的。有兩種主要的仿真推進(jìn)方式固定步長(zhǎng)推進(jìn)仿真的時(shí)鐘以固定的時(shí)間間隔如1秒向前跳動(dòng)。每個(gè)時(shí)間步長(zhǎng)內(nèi)檢查所有列車(chē)的狀態(tài)并更新。這種方法實(shí)現(xiàn)簡(jiǎn)單但效率低下因?yàn)榇蟛糠謺r(shí)間步長(zhǎng)里系統(tǒng)狀態(tài)并未改變。事件驅(qū)動(dòng)推進(jìn)仿真的時(shí)鐘直接跳到下一個(gè)預(yù)定事件發(fā)生的時(shí)間點(diǎn)。事件包括“列車(chē)到達(dá)某站”、“列車(chē)離開(kāi)某站”、“發(fā)生延誤”等。這是離散事件仿真的標(biāo)準(zhǔn)方法效率極高。在Matlab中實(shí)現(xiàn)事件驅(qū)動(dòng)仿真核心是維護(hù)一個(gè)優(yōu)先隊(duì)列事件列表按照事件發(fā)生時(shí)間排序。你可以自己實(shí)現(xiàn)一個(gè)最小堆或者利用第三方工具箱。主循環(huán)就是從隊(duì)列中取出下一個(gè)事件處理它更新列車(chē)狀態(tài)、產(chǎn)生新事件直到事件隊(duì)列為空或達(dá)到仿真結(jié)束時(shí)間。% 偽代碼示例 eventQueue PriorityQueue(); % 初始化事件隊(duì)列 eventQueue.push(Event(Departure, trainID, station, plannedDepartureTime)); % 加入初始事件 while ~eventQueue.isEmpty() currentTime endTime currentEvent eventQueue.pop(); % 取出最早發(fā)生的事件 currentTime currentEvent.time; switch currentEvent.type case Departure % 處理發(fā)車(chē)事件更新列車(chē)位置計(jì)算到達(dá)下一站的時(shí)間生成‘Arrival’事件 estimatedArrival currentTime calculateRunningTime(...); eventQueue.push(Event(Arrival, trainID, nextStation, estimatedArrival)); case Arrival % 處理到達(dá)事件檢查站內(nèi)沖突決定停站時(shí)間生成‘Departure’事件 if checkConflict(...) % 解析沖突可能延遲發(fā)車(chē) newDepartureTime resolveConflict(...); else newDepartureTime currentTime minStopTime; end eventQueue.push(Event(Departure, trainID, station, newDepartureTime)); end end6.3 性能優(yōu)化與調(diào)試心得當(dāng)問(wèn)題規(guī)模變大時(shí)性能會(huì)成為瓶頸。以下是一些優(yōu)化策略向量化操作避免在循環(huán)中對(duì)列車(chē)或區(qū)間進(jìn)行逐一遍歷。盡量將計(jì)算轉(zhuǎn)化為矩陣或向量運(yùn)算。例如計(jì)算所有列車(chē)在下一區(qū)間的預(yù)計(jì)到達(dá)時(shí)間可以一次性完成。預(yù)計(jì)算與緩存區(qū)間運(yùn)行時(shí)間、車(chē)站銜接關(guān)系等靜態(tài)數(shù)據(jù)應(yīng)預(yù)先計(jì)算好并存儲(chǔ)避免在仿真循環(huán)中重復(fù)計(jì)算。優(yōu)化沖突檢測(cè)算法沖突檢測(cè)是計(jì)算最密集的部分。不要用雙重循環(huán)O(N2)去比較每?jī)闪熊?chē)。可以利用時(shí)空?qǐng)D的性質(zhì)對(duì)列車(chē)按時(shí)間和位置排序?qū)?fù)雜度降低到接近O(N log N)。調(diào)試方面最大的坑在于約束遺漏或錯(cuò)誤。一個(gè)微小的約束沒(méi)考慮到就可能導(dǎo)致模型產(chǎn)生完全不可行的“幽靈解”。我的建議是從最小案例開(kāi)始先用只有2趟車(chē)、2個(gè)車(chē)站的極端簡(jiǎn)單案例測(cè)試你的模型和代碼手動(dòng)計(jì)算出所有可能的結(jié)果驗(yàn)證程序輸出是否正確。可視化中間結(jié)果將列車(chē)的時(shí)間-空間軌跡圖畫(huà)出來(lái)。Matlab的plot或stairs函數(shù)非常適合這個(gè)。一張圖能立刻告訴你列車(chē)在哪里發(fā)生了沖突比看一堆數(shù)字直觀得多。檢查邊界條件首班車(chē)、末班車(chē)、列車(chē)在起始站和終點(diǎn)站的行為這些地方最容易出錯(cuò)。壓力測(cè)試用隨機(jī)生成的大量車(chē)次去測(cè)試你的算法觀察其表現(xiàn)是否穩(wěn)定計(jì)算時(shí)間是否可接受。最后記住數(shù)學(xué)模型永遠(yuǎn)是現(xiàn)實(shí)的簡(jiǎn)化。一個(gè)能在仿真中減少10分鐘總晚點(diǎn)的“最優(yōu)”調(diào)度方案如果因?yàn)檫^(guò)于復(fù)雜而無(wú)法被調(diào)度員理解和執(zhí)行那么它的實(shí)際價(jià)值就是零。最好的模型是那些能在理論最優(yōu)和實(shí)際可操作性之間找到最佳平衡點(diǎn)的模型。這需要建模者不僅懂?dāng)?shù)學(xué)和編程更要深入理解鐵路運(yùn)營(yíng)的實(shí)際邏輯和約束。