賀 錦，崔文霖

（蘭州交通大學 交通運輸學院，甘肅 蘭州730070）

調(diào)機運用計劃是鐵路客運站作業(yè)計劃的重要組成部分，其核心是確定始發(fā)和終到旅客列車的車底出入庫時間、次序、調(diào)機運用及整備計劃。調(diào)機作業(yè)計劃是協(xié)調(diào)客運站各子系統(tǒng)作業(yè)的重要依據(jù)，具有重要作用。

1 調(diào)機運用優(yōu)化分析

根據(jù)鐵路客運站的列車徑路對調(diào)機的優(yōu)化問題進行分析，現(xiàn)有的鐵路客運站調(diào)機運用安排研究是在調(diào)機數(shù)確定的條件下，從均衡利用調(diào)機的角度出發(fā)，先安排調(diào)機的車底出入庫作業(yè)，并在此基礎上，確定車底出入庫時間。該文獻分析了客運站旅客列車到、發(fā)技術的作業(yè)特點及車底出入庫的時間特點，建立了客運站調(diào)機的運用優(yōu)化模型。

在對調(diào)機作業(yè)進行優(yōu)化的過程中，我們將調(diào)機作業(yè)的最早、最晚開始時間定義為調(diào)機作業(yè)時間窗口，并且調(diào)機所進行的作業(yè)時間窗口必須滿足列車在客運站各項作業(yè)的時間標準，在這樣的條件下，安排調(diào)機在最適當?shù)臅r間下去完成調(diào)機所擔當?shù)娜蝿?，并且使得調(diào)機的運用達到最佳狀態(tài)。根據(jù)對該問題的分析，我們將此問題劃分為三個子問題（成組作業(yè)方案優(yōu)化、調(diào)機作業(yè)順序優(yōu)化、咽喉區(qū)交叉干擾優(yōu)化）進行分析研究:

1）當列車進入車站后，摘取本務機車，由調(diào)機將車底由到發(fā)線牽入至客車整備，進行相應的整備作業(yè)，并在此基礎上為了不讓調(diào)機返回到發(fā)場，使得調(diào)機有一次空程，通常按照車底出入庫時間進行取送車底配對作業(yè)方案，使得調(diào)機的作業(yè)效率達到最佳，減少調(diào)車作業(yè)占用咽喉時間，在條件允許的情況下，應盡可能組織調(diào)機進行該類作業(yè)。

2）通過解決第一個問題可以得到調(diào)機成組的作業(yè)方案，將合并好的取、送車底作業(yè)替換為相應的成組取送作業(yè)后，可以得到一個調(diào)機作業(yè)的任務集合。并且其中有取送車底作業(yè)合并后調(diào)機任務數(shù)，則每個調(diào)機任務都擁有開始服務作業(yè)的時間窗口。調(diào)機作業(yè)順序的優(yōu)化問題，主要是確定每臺調(diào)機的作業(yè)順序，為每一個調(diào)機作業(yè)任務分配一個合適的調(diào)機作業(yè)，并保證調(diào)機的均衡作業(yè)。

3）第三個子問題就是在考慮調(diào)機均衡作業(yè)的同時要考慮到咽喉區(qū)的干擾情況，研究該問題的思路是在上一個問題確定好調(diào)機的作業(yè)任務，既要按照相應的任務安排進路，在安排進路時應盡量使得咽喉區(qū)的平行進路達到最大，減少敵對進路，根據(jù)調(diào)機作業(yè)的時間窗，去安排在該時間窗所要占用咽喉區(qū)的進路，并且計算出在該時間段內(nèi)，咽喉區(qū)的最大平行進路數(shù)，根據(jù)比選找出最優(yōu)進路，安排適合相應調(diào)機作業(yè)的進路。

下面重點分析討論第二個子問題，即調(diào)機順序安排模型。

2 調(diào)機順序安排模型及算法

2.1 符號定義

J＝｛Ji｜i＝1，2，…，n｝:J為調(diào)機的任務集合，n為調(diào)機任務總數(shù)；

D＝｛dj｜j＝1，2，…，m｝:D為調(diào)機集合，m為調(diào)機總數(shù)；

nnew:取送車底作業(yè)合并后調(diào)機任務數(shù)；

Jnew＝｛jnewi｜i＝1，2，…，nnew｝:Jnew為調(diào)機作業(yè)的任務集合；每 個 調(diào) 機 任 務 擁 有 開 始 服 務 時 間窗口；決策變量為第k個調(diào)機承擔作業(yè)后緊接著承擔作業(yè)j，1≤i≤n，1≤j≤n，1≤k≤m，n為作業(yè)項目總數(shù)，m為調(diào)機總數(shù)；

total＿time:所有調(diào)機任務需要的總調(diào)機作業(yè)時間；

work＿timemax:調(diào)機的最大作業(yè)時間；avg＿time:調(diào)機的平均作業(yè)時間。

2.2 問題描述

1）調(diào)機分工明確。對于某些既可用于辦理車底出庫作業(yè)，又能辦理車底入庫作業(yè)的調(diào)機看作“兩臺”調(diào)機，這“兩臺”調(diào)機在同一時刻視為一臺調(diào)機。

2）一個車底在同一時間內(nèi)只能占用一臺調(diào)機，一旦占用則直至完成該次作業(yè)為止，中途不能由其它調(diào)機占用該車底。一臺調(diào)機在同一時間只能被一項作業(yè)占用，直至該項作業(yè)完畢；一個車底同一時間內(nèi)只能占用一條車底停留線，一旦占用某一車底停留線，不允許有其它車底占用該車底停留線，直至該車底離開該停留線時為止。

3）所有調(diào)機的運行速度都相同

2.3 模型建立

Jnew＝｛jnewi｜i＝1，2，…，nnew｝為調(diào)機作業(yè)的任務集合，其中nnew為取送車底作業(yè)合并后調(diào)機任務數(shù)，則每個調(diào)機任務擁有開始服務時間窗口［stei，stli］。

設xki為邏輯變量表示第k個調(diào)機承擔作業(yè)i，車底為加工工件，車底Ji的最早可能入庫時刻TRfirst－i為對應工件的到達時間rj，最晚可能出庫時刻TClast－i為對應工件的完工期限dj，整備作業(yè)時間tj為對應工件的傳遞時間。將負責辦理入庫作業(yè)的調(diào)機集合Z1和出庫作業(yè)的調(diào)機集合Z2作為兩組處理機中心，由于取送車底得到調(diào)機成組作業(yè)方案后，將集合J中合并的取、送車底作業(yè)替換為相應的成組取送作業(yè)后，得到一個調(diào)機作業(yè)的任務集合。則將處理機Z1、Z2合并為一個處理中心，且認為該處理中心所有機器均為同速機。

調(diào)機作業(yè)順序優(yōu)化問題，主要確定每臺調(diào)機的作業(yè)順序，為每一個調(diào)機作業(yè)任務分配一個合適的調(diào)機，并保證調(diào)機均衡作業(yè)，描述為以下數(shù)學模型

由式（2）可以看到Z2為0～1間的正數(shù)，Z2越小表示調(diào)機作業(yè)的均衡性越高。當不需要考慮調(diào)機作業(yè)均衡性時Z2＝0，因此，解S的評價函數(shù)L可以由下式確定

式中:n為沒有安排調(diào)機的任務數(shù)；M為對不可行解的懲罰系數(shù)，可以是一個正整數(shù)（取1 0000）；ω為解不均衡性的目標函數(shù)權重，為正數(shù)，可以取10。

采用M與ω的取值意義是在進行局部搜索時應首先保證解的可行性，并在此基礎上兼顧調(diào)機作業(yè)的均衡性，L（S）的取值越小，解的性能越好

每項作業(yè)必須且只能安排一臺適當?shù)恼{(diào)機承擔

在同一時刻每臺調(diào)機只能承擔一項作業(yè)

滿足車站各項作業(yè)時間的標準，即滿足列車、車底在站各項作業(yè)時間標準的要求，即調(diào)機作業(yè)時間應在其作業(yè)時間窗口內(nèi)

2.4 算法求解

由于調(diào)機運用計劃最終可描述為如下:客運站需要完成m項任務取送車底作業(yè)，現(xiàn)在恰好有n臺機車可承擔這些任務。每項任務只能由一臺機車完成，每臺機車最多只能完成一項任務，由于每臺機車的走行距離以及取送車車底的長度不同，各臺機車完成不同任務的費用（如時間）略有不同。應指派哪臺機車去完成哪項任務，使每一個調(diào)機作業(yè)任務分配一個合適的調(diào)機，并力求調(diào)機均衡作業(yè)，即目標函數(shù)值接近于0。由目標函數(shù)可以看出Z為0～1的正數(shù)，Z越小表示調(diào)機作業(yè)的均衡性越高。該問題也可看成變形后的指派問題。

設計模擬退火算法如下:

Step1:用數(shù)值計算估計法確定模擬退火的初始溫度；

Step2:指定參數(shù)，主要包括:數(shù)據(jù)文件名，人數(shù)n，任務數(shù)m，初始溫度t0，退火速度和實驗次數(shù)Ne；

Step3:從數(shù)據(jù)文件中讀入費用矩陣；

Step4:構造一個初始解S0作為當前解，t?t0，l?1；

Step5:根據(jù)當前解S0構造一個鄰居S′，如果滿足條件S′的目標函數(shù)值f（S′）小于f（S′），則令S0?S′；否則，產(chǎn)生一個［0，1］間的隨機數(shù)x，如果exp（－f（S′）－f（S′）t）＞x，則S0?S′；

Step6:l?l＋1；

Step7:如果l＜n2，轉到Step5繼續(xù)執(zhí)行，否則，轉到Step8；

Step8:t?αt；

Step9:如果t≥1×10－4，轉到Step5繼續(xù)執(zhí)行，否則，結束本次實驗，記錄所得結果；

Step10:如果實驗次數(shù)不足Ne，轉到Step4繼續(xù)執(zhí)行，否則，輸出所有實驗結果，進行統(tǒng)計分析并輸出，結束這組實驗。

模擬退火算法用于求解大規(guī)模不對稱指派問題，不僅收斂速度快，而且找到最滿意解的概率也較高，具有很高的實用價值。該算法是專門針對人數(shù)大于或等于任務數(shù)的指派問題設計的，基本思想是從n個人中選出m個人去完成m個任務，如果任務數(shù)大于人數(shù)（m＞n），而且要求每個人最多只能完成一項任務，可以從m個任務中選出n個任務交給n個人去完成。對上述算法做很少的修改就能實現(xiàn)，因此，上述算法是求解大規(guī)模指派問題的通用算法。

第二階段是對各調(diào)機擔當?shù)娜蝿者M行簡單排序。

Step1:對于新任務入庫車底，計算其最早入庫時刻xj。

Step2:確定調(diào)機集合Z中各調(diào)機所處的狀態(tài)，修正車底的最早入庫時刻xj和最晚出庫時刻yj。

Step3:對于新任務入庫車底按其最早入庫時刻xj由先到后進行排序，即xj＜xj＋1時，xj?xj＋1，否則，xj?xj＋1；若最早入庫時刻相等，則按最晚出庫時刻由先到后排序，即xj＝xj＋1，且yj＜yj＋1時，xj?xj＋1，反之，則xj?xj＋1，由此構成序列I，共n項。

2.5 調(diào)機順序安排流程

調(diào)機順序安排流程如圖1所示。

圖1 調(diào)機順序安排流程

3 實例驗證

某大型客運站一個班白天編制階段計劃，規(guī)定每日18時按0min計算，次日18時按1 440min計算。從中取出一個階段，假設有34項車輛取送、移動任務需要8臺取送調(diào)機完成，始發(fā)、終到列車共34對，取送車底合并后的作業(yè)任務數(shù)為272項，根據(jù)成組配對方案模型，按照建立的模型和算法對調(diào)機進行順序安排、任務分配，在每個調(diào)機都有任務的前提下，對調(diào)機進行均衡性分析，使得每臺調(diào)機都在有任務做的前提下實現(xiàn)調(diào)機均衡。

3.1 調(diào)機任務安排

以某大型客運站為例，將調(diào)機數(shù)量設為8臺，取送車底合并后的作業(yè)任務數(shù)為272項，按照建立的模型和算法對調(diào)機進行順序安排、任務分配，在每個調(diào)機都有任務的前提下，對調(diào)機進行均衡性分析，使得每臺調(diào)機都在有任務做的前提下實現(xiàn)調(diào)機均衡。

3.2 調(diào)機均衡系數(shù)計算

先將各個任務運用快速排序算法按照所用時間長短從小到大進行排序，然后利用給出的模型計算出所有調(diào)機任務需要的總調(diào)機作業(yè)時間total＿time、調(diào)機的平均作業(yè)時間avg＿time、調(diào)機的最大工作時間work＿time，最后，計算出調(diào)機作業(yè)的均衡性系數(shù)h，調(diào)機均衡性系數(shù)越小，表示調(diào)機越均衡。程序中初始溫度t0定為10 000℃，α定為0.98，內(nèi)循環(huán)次數(shù)定為1 000次，算法終止條件為溫度低于1×10－4，將該程序在Visual C＋＋6.0環(huán)境下運行，結果如圖2所示。

圖2 調(diào)機均衡系數(shù)計算

4 結 論

大型客運站的任意一項工作的優(yōu)化都可以提高旅客組織能力?？瓦\站調(diào)機工作組織是保證始發(fā)列車正點的重要環(huán)節(jié)，因此，通過科學的數(shù)學方法進行建模，并輔之以適當?shù)乃惴▉斫鉀Q客運站調(diào)機運用問題具有十分重要的意義。

1）該問題可進一步討論，如綜合考慮旅客列車集中晚點、客流高峰期、客運站設備故障等非正常情況下，通過分析影響調(diào)機運用的因素參數(shù)，得出更加高效、優(yōu)質(zhì)的調(diào)機使用快速調(diào)整方案。

2）在算法上，由于模擬退火算法的復雜性，簡化了問題，不應只考慮算法的收斂性。

3）根據(jù)該問題的研究方向，在此模型基礎上，如何把客技站車底停留線、到發(fā)線、牽出線加以考慮，可對客運站工作組織進行整體優(yōu)化。

［1］宋建業(yè)，謝金寶.鐵路行車組織［M］.北京:中國鐵道出版社，2005.

［2］陳彥.鐵路客運站列車過站徑路與調(diào)機運用優(yōu)化［D］.長沙:中南大學，2006.

［3］刑文訓，謝金星.現(xiàn)代優(yōu)化計算方法［M］.北京:清華大學出版社，2005.

［4］雷定猷，張英貴，劉明翔.鐵路客技站車底作業(yè)排序模型與算法［J］.鐵道學報，2007，29（6）:1－6.

［5］呂紅霞.鐵路大型客運站作業(yè)計劃智能編制的優(yōu)化技術和方法研究［D］.成都:西南交通大學，2008.

［6］龍建成，高自友，馬建軍，等.鐵路車站進路選擇優(yōu)化模型及求解算法的研究［J］.鐵道學報，2007，29（5）:6－13.

［7］陳建鑫，李海鷹，苗建瑞.客運專線客運站到發(fā)線運用優(yōu)化研究［J］.鐵道計算機應用，2008，17（2）:8－11.

［8］劉瀾，王南，杜文.車站咽喉通過能力網(wǎng)絡優(yōu)化模型及算法研究［J］.鐵道學報，2002，24（6）:1－5.