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

崔元瑞

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

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

中圖分類號：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 概述

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

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

2 新舊交替列車運行方案編制優(yōu)化模型

2.1 模型條件假設(shè)

（1）新舊列車運行圖已知，相應(yīng)的列車車底周轉(zhuǎn)關(guān)系及車底總數(shù)已知。

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

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

2.2 模型建立

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

3 模型求解

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

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

4 算例分析

依據(jù)鐵路總公司的調(diào)圖數(shù)據(jù)，在執(zhí)行新列車運行圖之前，車站A始發(fā)終到列車時刻表為表1，在執(zhí)行新列車運行圖之后，車站A始發(fā)終到列車時刻表為表2。

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

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

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

5 結(jié)束語

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

參考文獻：

[1]倪少權(quán).中國鐵路列車運行圖編制系統(tǒng)研究[D].西南交通大學(xué)，2013.

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

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

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

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

[6]何曦.城市軌道交通三線交路模式下列車運行線編制的數(shù)學(xué)模型[J].科技創(chuàng)新與應(yīng)用，2017（05）：40.