基于匈牙利算法的新舊交替列車運行方案編制研究

崔元瑞

摘 要：為了使鐵路新舊列車運行圖能夠平穩有序的過渡，以客車車底在配屬站總的停留時間最短為優化目標，建立新舊交替車底周轉優化模型，采用匈牙利算法求解目標函數。依據鐵路總公司的編圖數據，應用上述優化模型對新舊交替期車底周轉問題進行分析計算，得到新舊交替列車運行優化方案。

關鍵詞：運行方案；新舊交替；匈牙利算法；客車車底

中圖分類號：U292 文獻標志碼：A 文章編號：2095-2945（2018）21-0060-03

Abstract： In order to ensure the smooth and orderly transition of the old and the new train operation diagram， the optimization model of the bottom turnover of the new and old trains is established， and the objective function is solved by the Hungarian algorithm， taking the shortest total residence time of the passenger train bottom at the subordinate station as the optimization objective. According to the drawing data of railway corporation， the optimization model is applied to analyze and calculate the bottom turnover problem in the period of alternation between old and new， and the optimal scheme of train operation in the alternation between new and old is obtained.

Keywords： operation scheme； alternation of old and new； Hungarian algorithm； passenger car underside

1 概述

隨著社會經濟與鐵路快速發展，路網趨于完善，人民出行需求的增加，鐵路總公司對列車運行圖調整日益頻繁?，F階段，執行單一運行圖時，各旅客列車車底能夠實現良好的周轉接續，但是在新舊運行圖交替期間，按新圖運行的列車車底與按舊圖運行的車底不能夠完成良好的接續。因此，研究新舊交替期列車車底周轉接續方法，編制新舊交替期列車運行方案，對提高鐵路運輸效率和旅客列車運行圖編制方法的研究有著重要的意義。

列車車底周轉接續分為車底固定和車底不固定模式兩種，車底固定運用模式下，交替過程中不存在不同車次車底之間的相互替換，這樣就導致列車車底在配屬站停留時間過長；車底不固定運用模式下，不同車次的列車車底可以相互替換，即任意兩對滿足車接續要求的列車均可接續，增強了列車車底周轉的靈活性，能有效的減少列車車底在配屬站的停留時間，大大縮短新舊列車運行圖交替周期。因此，本文主要研究列車車底不固定運用時新舊交替列車運行方案圖的編制。

2 新舊交替列車運行方案編制優化模型

2.1 模型條件假設

（1）新舊列車運行圖已知，相應的列車車底周轉關系及車底總數已知。

（2）都是同一種車底，相同數量的編組，不同車次列車之間車底可以相互替換。

（3）在舊列車運行圖和新列車運行圖中，列車車底只在配屬站上下線。

2.2 模型建立

在車底不固定運用方式下，旅客列車新舊交替列車方案編制的主要目標是列車車底在配屬站的停留時間最短。

3 模型求解

上述模型的核心問題是解決在舊列車運行圖中的到達列車車底與新列車運行圖的始發列車車底兩者之間找出最優化的匹配問題。即在列車車底在站停留時間最小的路徑。因此，可采用匈牙利算法求解。求解過程如下：

（2）采用匈牙利算法求解上述各時間矩陣，得到一個使列車車底在站停留時間最小的列車車底接續方案。若最優解不止一組，那么取數據波動最小的一組，即所有列車車底在站時間與車底平均在站停留時間方差最小的一組即可。

4 算例分析

依據鐵路總公司的調圖數據，在執行新列車運行圖之前，車站A始發終到列車時刻表為表1，在執行新列車運行圖之后，車站A始發終到列車時刻表為表2。

（1）按照算法設計，對新舊列車運行圖時刻表進行整理，得到A站在交替日按舊圖運行的列車終到時刻及按新圖運行的列車始發時刻，見表3。

（3）采用匈牙利算法，用MATLAB編程對上面的時間矩陣進行求解，尋找使列車車底在站停留時間最短的接續方案，求解結果如表5。

即該模型求解的新舊交替列車車底最優接續方案為：按舊圖運行的列車T2、T4、T6、T8、T10、T12、T14、T16、T18、T20分別接續按新圖運行的列車T19、T17、T13、T7、T5、T3、T11、T15、T9、T1，總接續時間6331min。

5 結束語

本文主要研究了列車車底不固定運用情況下，新舊列車運行圖交替期列車運行方案的編制，以車底在站停留時間最短為目標建立優化模型，采用匈牙利算法進行求解，并通過實例驗證模型的可行性。但在實際工作中，我國旅客列車車底和動車組車底大多采用固定車底運用模式，因此，對于固定車底運用模式下車底周轉接續問題以及新舊交替期列車運行方案的編制優化方法有待進一步研究。

參考文獻：

[1]倪少權.中國鐵路列車運行圖編制系統研究[D].西南交通大學，2013.

[2]謝金貴，曾亮，徐昕愷.鐵路旅客列車車底套用優化模型的研究[J].鐵道運輸與經濟，2006，28（12）：75-77.

[3]呂苗苗.新舊交替列車運行圖編制優化理論與方法研究[D].西南交通大學，2013.

[4]沈亞威.新舊列車運行圖交替相關問題研究[D].西南交通大學，2012.

[5]史周平，王榮飛，肖小科.基于模擬退火算法的旅客列車車底運用的優化[J].鐵道運營技術，2009，15（01）：37-39.

[6]何曦.城市軌道交通三線交路模式下列車運行線編制的數學模型[J].科技創新與應用，2017（05）：40.