大型客運(yùn)站調(diào)機(jī)運(yùn)用優(yōu)化模型及算法

賀 錦，崔文霖

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州730070）

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

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

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

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

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

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

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

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

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

2.1 符號(hào)定義

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

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

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

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

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

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

2.2 問題描述

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

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

3）所有調(diào)機(jī)的運(yùn)行速度都相同

2.3 模型建立

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

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

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

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

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

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

每項(xiàng)作業(yè)必須且只能安排一臺(tái)適當(dāng)?shù)恼{(diào)機(jī)承擔(dān)

在同一時(shí)刻每臺(tái)調(diào)機(jī)只能承擔(dān)一項(xiàng)作業(yè)

滿足車站各項(xiàng)作業(yè)時(shí)間的標(biāo)準(zhǔn)，即滿足列車、車底在站各項(xiàng)作業(yè)時(shí)間標(biāo)準(zhǔn)的要求，即調(diào)機(jī)作業(yè)時(shí)間應(yīng)在其作業(yè)時(shí)間窗口內(nèi)

2.4 算法求解

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

設(shè)計(jì)模擬退火算法如下:

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

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

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

Step4:構(gòu)造一個(gè)初始解S0作為當(dāng)前解，t?t0，l?1；

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

Step6:l?l＋1；

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

Step8:t?αt；

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

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

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

第二階段是對(duì)各調(diào)機(jī)擔(dān)當(dāng)?shù)娜蝿?wù)進(jìn)行簡(jiǎn)單排序。

Step1:對(duì)于新任務(wù)入庫車底，計(jì)算其最早入庫時(shí)刻xj。

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

Step3:對(duì)于新任務(wù)入庫車底按其最早入庫時(shí)刻xj由先到后進(jìn)行排序，即xj＜xj＋1時(shí)，xj?xj＋1，否則，xj?xj＋1；若最早入庫時(shí)刻相等，則按最晚出庫時(shí)刻由先到后排序，即xj＝xj＋1，且yj＜yj＋1時(shí)，xj?xj＋1，反之，則xj?xj＋1，由此構(gòu)成序列I，共n項(xiàng)。

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

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

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

3 實(shí)例驗(yàn)證

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

3.1 調(diào)機(jī)任務(wù)安排

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

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

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

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

4 結(jié) 論

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

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

2）在算法上，由于模擬退火算法的復(fù)雜性，簡(jiǎn)化了問題，不應(yīng)只考慮算法的收斂性。

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

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

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

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

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

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

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

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

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