[發明專利]基于SPFA算法的地鐵乘務排班計劃編制優化方法

有效

• 申請號: 202110954688.7
• 申請日: 2021-08-19
• 公開（公告）號: CN113837438B
• 公開（公告）日: 2023-04-07
• 發明（設計）人: 薛鋒;梁鵬;李海;胡萍;陳崇雙;郭東琦;任子蘭;汪雯文
• 申請（專利權）人: 西南交通大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/0631;G06Q50/26
• 代理公司: 成都東恒知盛知識產權代理事務所(特殊普通合伙) 51304
• 代理人: 羅江

本發明涉及軌道交通技術領域，涉及一種基于SPFA算法的地鐵乘務排班計劃編制優化方法，包括：以輪乘站為起止點，將乘務片段集合組合成乘務作業段的集合；構成早班、白班及夜班的三個網絡圖；初始化D數組，把起點加入循環隊列，開始進入循環，直到隊列為空才退出循環；進行松弛操作；對隊列進行更新，得到最短路徑的值；滿足優化模型的路徑作為最終求得的最短路徑；更換起點，重新開始循環，求得更換后起點的最短路徑；求得的各個最短路徑即為早班時間段的乘務任務；將白班時間段與夜班時間段的各個乘務作業段進行求解，求得的所有最短路徑即為一天的乘務排班計劃。本方法簡便、快速，適用于城市軌道交通乘務排班計劃問題的求解。

技術領域

本發明涉及軌道交通技術領域，具體地說，涉及一種基于SPFA算法的地鐵乘務排班計劃編制優化方法。

背景技術

地鐵是城市軌道交通中最重要的一部分，隨著地鐵智能化以及城市發展的迫切需求，地鐵規劃運營的線路不斷增加，行車密度不斷提高，因此地鐵運營管理將變得越來越困難和復雜。乘務計劃是城市軌道交通運營管理中的核心工作之一，是保證城市軌道交通線路安全高效運營的基礎。乘務計劃一般分為乘務排班計劃和乘務輪班計劃，其中乘務排班計劃是尋找列車車次與乘務任務之間的對應關系，是乘務輪班計劃的基礎，也是整個乘務計劃編制過程中最復雜、難度最大的部分。

乘務計劃是交通領域研究的熱點之一，目前研究者們對于乘務計劃的編制問題研究主要集中于鐵路、航空及城市公交等方面，其中，在鐵路方面的研究成果能夠很好地為城市軌道交通乘務計劃的研究提供參考。Hanafi等從多個乘務基地出發，構建了最小化乘務組費用的優化模型，得出了最優乘務交路方案。PantaLucic建立了乘務排班計劃的多目標優化模型，將乘務排班計劃分為兩個階段：第一階段采用“pilot-by-pilot”的啟發式算法生成一個初始可行解，第二階段采用模擬退火技術改進在第一階段生成的可行解。FrelingR等利用價格分支算法對乘務排班計劃問題進行建模和求解，并設計了排班計劃決策支持系統。褚飛躍等研究高速鐵路單循環形式乘務排班計劃編制問題，建立了以乘務交路總接續時間最短和冗余時間分布最均衡的雙目標優化模型，設計基于動態啟發式信息的蟻群優化算法。符卓等以所需要的高速動車組司機數和司機的冗余休息時間最少建立了編制日乘務交路的0-1整數規劃模型，并設計了一個求解的禁忌搜索算法。林楓將乘務交路計劃編制過程分為兩階段，第一階段以總接續時間最小為目標將乘務區段組合為乘務交路段集合，第二階段以過夜次數最小為目標，將過夜交路段組合為閉合乘務交路，并設計了MOMS求解算法。楊嘉寶等通過對帶立即折返的高速動車組乘務交路回路優化構建問題的分析和抽象，建立其優化模型，并設計了一個蟻群-遺傳混合算法求解該模型。

在城市軌道交通方面，Sydney.K.Chu從多個階段對乘務排班計劃進行研究，并分別采用了最短路算法、對稱匹配和改進遺傳算法進行求解；Janacek等將根據時間段分成的多個區間作為列生成算法中的一個子問題進行并行求解，此種方法新列的生成速度較快；石俊剛等建立了基于SPP模型的城軌乘務任務配對模型(R-CP)，并基于列生成思想和跟隨分支策略對乘務任務配對問題進行求解；許仲豪等以列生成算法為框架，采用集合分割模型作為主規劃，將子規劃歸結為以乘務作業段之間的銜接關系為基礎的網絡圖上的最短路問題，對乘務排班計劃進行了研究；豐富等基于時間均衡度構建了乘務排班計劃模型，并通過遺傳算法對模型進行了求解；張增勇等構建了乘務作業段集合生成模型和乘務工作班生成模型，并針對構建的雙層模型，下層模型采用改進的Dijkstra算法，上層模型采用離散粒子群算法進行了求解。

綜上所述，目前國內關于城市軌道交通乘務排班計劃的既有研究較少，且大多都采用列生成算法的思路進行探索。在求解NP-Hard問題的時候，列生成雖具有較好的效果，但其求解復雜、迭代次數較多等問題也不可忽視。

發明內容

本發明的內容是提供一種基于SPFA算法的地鐵乘務排班計劃編制優化方法，其能夠克服現有技術的某種或某些缺陷。

根據本發明的一種基于SPFA算法的地鐵乘務排班計劃編制優化方法，其包括以下步驟：