基于技術(shù)作業(yè)時(shí)間協(xié)調(diào)的鐵路客運(yùn)站技術(shù)作業(yè)計(jì)劃編制算法研究

何 潔，陳 韜，王永成，彭 岳

HE Jie1, CHEN Tao2, WANG Yong-cheng3, PENG Yue4

（1.中鐵集裝箱有限責(zé)任公司國內(nèi)物流部，北京100055；2.西南交通大學(xué)交通運(yùn)輸與物流學(xué)院，四川成都610031；3.北京鐵路局運(yùn)輸處，北京100860；4.西安鐵路局西安站，陜西西安710000）

(1.Domestic Logistic Department, China Railway Container Transport Co., Ltd., Beijing 100055； 2.School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, Sichuan, China； 3.Transport Department, Beijing Railway Administration, Beijing 100860, China； 4.Xi’an Station, Xi’an Railway Administration, Xi’an 710000, Shaanxi, China)

基于技術(shù)作業(yè)時(shí)間協(xié)調(diào)的鐵路客運(yùn)站技術(shù)作業(yè)計(jì)劃編制算法研究

何 潔1，陳 韜2，王永成3，彭 岳4

HE Jie1, CHEN Tao2, WANG Yong-cheng3, PENG Yue4

（1.中鐵集裝箱有限責(zé)任公司國內(nèi)物流部，北京100055；2.西南交通大學(xué)交通運(yùn)輸與物流學(xué)院，四川成都610031；3.北京鐵路局運(yùn)輸處，北京100860；4.西安鐵路局西安站，陜西西安710000）

(1.Domestic Logistic Department, China Railway Container Transport Co., Ltd., Beijing 100055； 2.School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, Sichuan, China； 3.Transport Department, Beijing Railway Administration, Beijing 100860, China； 4.Xi’an Station, Xi’an Railway Administration, Xi’an 710000, Shaanxi, China)

通過分析客運(yùn)站各類技術(shù)作業(yè)的特點(diǎn)，闡述到發(fā)線、調(diào)車機(jī)車、客技線、咽喉進(jìn)路等設(shè)備上技術(shù)作業(yè)的同質(zhì)性與共性，在此基礎(chǔ)上確定技術(shù)作業(yè)富余時(shí)間，以最大限度固定使用和均衡使用設(shè)備為目標(biāo)建立客運(yùn)站技術(shù)作業(yè)計(jì)劃編制模型，并給出模型求解思路及算法，最后通過算例驗(yàn)證模型及算法的有效性。

客運(yùn)站；技術(shù)作業(yè)計(jì)劃；作業(yè)時(shí)間協(xié)調(diào)；算法

1　概述

客運(yùn)站技術(shù)作業(yè)計(jì)劃編制是指在固定的列車運(yùn)行圖和車站設(shè)備資源條件下,在保證安全前提下為列車/車底在站各項(xiàng)技術(shù)作業(yè)安排相應(yīng)設(shè)備和時(shí)間的過程,該問題屬于 NP 難題,一般的方法是將其按作業(yè)流程和設(shè)備種類分解為到發(fā)線運(yùn)用、調(diào)車機(jī)車運(yùn)用、客車整備線運(yùn)用等問題進(jìn)行模型優(yōu)化和求解[1-7]。呂紅霞[4]分別確定到發(fā)線、牽出線、客技線、咽喉進(jìn)路對調(diào)車機(jī)車作業(yè)的約束條件,然后對調(diào)車機(jī)車作業(yè)時(shí)間窗劃分時(shí)間片段來確定作業(yè)起止時(shí)間,從而協(xié)調(diào)各項(xiàng)技術(shù)作業(yè)；陳彥[5]構(gòu)造列車過站徑路與調(diào)車機(jī)車整體優(yōu)化模型,在時(shí)間窗范圍內(nèi)隨機(jī)生成車底出入庫時(shí)間方案,運(yùn)用模擬退火算法進(jìn)行求解；雷定猷等[6-7]利用排序理論建立車底停留線運(yùn)用模型、車底取送模型,并引入滿意度隸屬函數(shù)協(xié)調(diào)車底出入庫時(shí)間,提出基于分派規(guī)則和解改進(jìn)優(yōu)化策略的啟發(fā)式算法進(jìn)行求解。上述方法可以降低求解的規(guī)模和難度。但是,子模型間的協(xié)調(diào)復(fù)雜度較大,特別對一些大型客運(yùn)站,存在復(fù)雜和特殊的作業(yè)流程,如動(dòng)車組與普通列車混合安排、移位式客車準(zhǔn)備作業(yè)等,如果按照作業(yè)環(huán)節(jié)分解成子問題,則子模型的數(shù)量和協(xié)調(diào)難度都會(huì)顯著上升。

雖然客運(yùn)站的股道、調(diào)車機(jī)車等各種設(shè)備特點(diǎn)不同,但就列車/車底在這些設(shè)備上的作業(yè)計(jì)劃安排而言,都需要考慮以下因素：①確定每項(xiàng)技術(shù)作業(yè)占用的設(shè)備；②確定每項(xiàng)技術(shù)作業(yè)的起止時(shí)間；③保證每項(xiàng)技術(shù)作業(yè)滿足相應(yīng)的作業(yè)時(shí)間標(biāo)準(zhǔn)；④保證每項(xiàng)技術(shù)作業(yè)在時(shí)間和空間上的惟一性；⑤保證每項(xiàng)技術(shù)作業(yè)起止時(shí)間的接續(xù)性。因此,無論是到發(fā)線、調(diào)車機(jī)車、客技線、咽喉進(jìn)路還是其他特殊設(shè)備 (如場間聯(lián)絡(luò)線等) 的技術(shù)作業(yè)安排,在優(yōu)化目標(biāo)及約束條件上都具有同質(zhì)化的可能性。為了不依賴設(shè)備種類,提高算法的通用性和適應(yīng)性,將客運(yùn)站各項(xiàng)技術(shù)作業(yè)抽象為基于列車/車底的一組同質(zhì)性的作業(yè)任務(wù)進(jìn)行建模和求解。作業(yè)同質(zhì)化的具體做法為：將每個(gè)列車/車底的每項(xiàng)作業(yè)賦予“作業(yè)起止時(shí)間、作業(yè)靜動(dòng)態(tài)性質(zhì)、作業(yè)可用設(shè)備集合、是否安排進(jìn)路”等屬性,并按時(shí)間進(jìn)行排序。

其中,作業(yè)可用設(shè)備集合、是否安排進(jìn)路根據(jù)車站技術(shù)作業(yè)規(guī)則確定；作業(yè)靜動(dòng)態(tài)性質(zhì)是指列車/車底在作業(yè)時(shí)處于靜止?fàn)顟B(tài)還是運(yùn)動(dòng)狀態(tài),一般情況下,到發(fā)線、客車整備線、檢修庫線等設(shè)備上的作業(yè)稱為靜態(tài)作業(yè),走行線、調(diào)車機(jī)車、牽出線等設(shè)備上的作業(yè)稱為動(dòng)態(tài)作業(yè),靜態(tài)作業(yè)和動(dòng)態(tài)作業(yè)在時(shí)間安排和調(diào)整上有不同的約束規(guī)則,通過這項(xiàng)屬性可以反映不同種類設(shè)備作業(yè)安排上的特點(diǎn)；作業(yè)起止時(shí)間中,只有列車到達(dá)、出發(fā)時(shí)間是確定的,其余各項(xiàng)作業(yè)時(shí)間都存在一個(gè)可調(diào)整的時(shí)間窗,需要算法確定。在上面的幾個(gè)屬性中,技術(shù)作業(yè)起止時(shí)間的確定是進(jìn)行作業(yè)同質(zhì)化的基礎(chǔ)環(huán)節(jié),也是客運(yùn)站各項(xiàng)技術(shù)作業(yè)相互協(xié)調(diào)的關(guān)鍵,車站技術(shù)作業(yè)時(shí)間的協(xié)調(diào)具有多方案性,因而屬于柔性調(diào)整。

2　數(shù)學(xué)模型

2.1 變量定義

根據(jù)客運(yùn)站的技術(shù)作業(yè)要求,為每個(gè)列車/車底Ji確定一個(gè)按時(shí)間順序排列的技術(shù)作業(yè)任務(wù)集合其中 Si表示列車/車底 Ji在車站需要安排的技術(shù)作業(yè)項(xiàng)數(shù),定義每項(xiàng)技術(shù)作業(yè) Rij的七元組變量為分別表示作業(yè)開始時(shí)間、作業(yè)結(jié)束時(shí)間、作業(yè)性質(zhì)、技術(shù)設(shè)備編號(hào)(股道、調(diào)車機(jī)車、走行線等)、是否安排進(jìn)路、進(jìn)路安排開始時(shí)間、進(jìn)路安排結(jié)束時(shí)間。其中：μij為 0-1 變量,如果是靜態(tài)作業(yè)則取值 1,如果是動(dòng)態(tài)作業(yè)則取值 0；θij為 0-1 變量,如果列車/車底 Ji的第 j 項(xiàng)作業(yè)需要安排進(jìn)路則取值 1,否則取值 0。

列車/車底 Ji在每項(xiàng)作業(yè)上的技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)為；進(jìn)路占用時(shí)間標(biāo)準(zhǔn)為。

2.2模型建立

2.2.1技術(shù)作業(yè)富余時(shí)間的確定

大多數(shù)研究者[4-7]是在客運(yùn)站定位式作業(yè)背景下探討車底各項(xiàng)技術(shù)作業(yè)時(shí)間,只要確定了車底入庫、出庫時(shí)間,就可以確定各項(xiàng)技術(shù)作業(yè)起止時(shí)間,時(shí)間的調(diào)整也主要是在入庫、出庫時(shí)間窗內(nèi)進(jìn)行。對于作業(yè)流程復(fù)雜的車站,除了入庫、出庫時(shí)間需要確定,還可能存在多次轉(zhuǎn)場或轉(zhuǎn)線作業(yè),這些轉(zhuǎn)場或轉(zhuǎn)線作業(yè)也存在時(shí)間窗。因此,復(fù)雜作業(yè)流程下的列車/車底技術(shù)作業(yè)時(shí)間的確定和協(xié)調(diào)較為復(fù)雜。

由于每個(gè)列車/車底在車站的到達(dá)時(shí)刻、出發(fā)時(shí)刻、技術(shù)作業(yè)內(nèi)容和技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)是確定的,因而每個(gè)列車/車底在站停留總時(shí)間與在站技術(shù)作業(yè)需要的最少總作業(yè)時(shí)間存在一個(gè)確定的差值這個(gè)時(shí)間差就是列車/車底的技術(shù)作業(yè)富余時(shí)間。列車/車底技術(shù)作業(yè)安排方案示意圖如圖1 所示,作業(yè)占用時(shí)間有實(shí)線和虛線 2 種表示,實(shí)線表示該作業(yè)規(guī)定的時(shí)間標(biāo)準(zhǔn),虛線表示技術(shù)作業(yè)富余時(shí)間。

技術(shù)作業(yè)富余時(shí)間具有以下特點(diǎn)：①技術(shù)作業(yè)富余時(shí)間是常量,而且只能產(chǎn)生在靜態(tài)作業(yè)上；②調(diào)車機(jī)車、走行線等動(dòng)態(tài)作業(yè)的調(diào)整導(dǎo)致技術(shù)作業(yè)富余時(shí)間在各種靜態(tài)作業(yè)上分布的變化。圖1 中的2 個(gè)方案都可行,但 a 方案的技術(shù)作業(yè)富余時(shí)間分布在客車整備線上,客車整備線被占用的時(shí)間長,則后續(xù)車底可利用的客車整備線空閑能力就少；b方案將技術(shù)作業(yè)富余時(shí)間分布在到發(fā)線上,到發(fā)線被占用的時(shí)間長,則后續(xù)車底可利用的到發(fā)線空閑能力就少。因此,根據(jù)設(shè)備資源的緊缺程度,盡量將技術(shù)作業(yè)富余時(shí)間分布在非緊缺設(shè)備上,可以給后續(xù)列車/車底技術(shù)作業(yè)計(jì)劃提供更好的編制條件,有利于更快形成優(yōu)化方案。

2.2.2目標(biāo)函數(shù)

第一優(yōu)化目標(biāo)是使各項(xiàng)技術(shù)作業(yè)最大可能地按照固定使用方案選擇設(shè)備,第二優(yōu)化目標(biāo)是在第一目標(biāo)基礎(chǔ)上最大可能地實(shí)現(xiàn)設(shè)備均衡使用,即

式中：wi表示列車/車底 Ji的權(quán)值,列車等級越高權(quán)值越小,高等級列車應(yīng)盡量優(yōu)先安排；cijk表示列車/車底 i 的第 j 項(xiàng)作業(yè)安排在設(shè)備 k 上的費(fèi)用系數(shù),當(dāng)符合固定設(shè)備使用方案時(shí),cijk取值為 1,當(dāng)該設(shè)備可用時(shí)取值為 10,當(dāng)該設(shè)備不可用時(shí)取值為一個(gè)極大值 F；xijk為 0-1 變量,當(dāng)列車/車底 i 的第 j 項(xiàng)作業(yè)安排在設(shè)備 k 上時(shí) xijk= 1,否則 xijk= 0。

⑴ 式表示盡量按照設(shè)備固定使用方案安排作業(yè)；⑵ 式是列車/車底占用設(shè)備作業(yè)時(shí)間的方差值,該值越小表示設(shè)備使用均衡性越好。

將 2 個(gè)目標(biāo)函數(shù)進(jìn)行歸一化處理,則

式中：α1和 α2是無量綱系數(shù),可以根據(jù)用戶對目標(biāo)函數(shù)的偏好確定取值。

圖1　列車/車底技術(shù)作業(yè)安排方案示意圖

2.2.3約束條件

⑸ 式是設(shè)備占用惟一性約束,保證每個(gè)列車/車底每項(xiàng)技術(shù)作業(yè)只占用 1 個(gè)設(shè)備；⑹ 式表示每個(gè)列車/車底占用每項(xiàng)設(shè)備的作業(yè)時(shí)間要大于作業(yè)時(shí)間標(biāo)準(zhǔn)；⑺ 式表示每個(gè)設(shè)備上的任何 2 個(gè)列車的占用時(shí)間不能相互沖突；⑻ 式表示每個(gè)列車/車底只能占用 1 條接發(fā)車進(jìn)路,其中分別為進(jìn)路開始、結(jié)束占用 0-1 變量,表示列車/車底 i 的第 j 項(xiàng)作業(yè)安排在進(jìn)路 k 上時(shí),則取值為 1,否則取值為 0；⑼ 式表示列車/車底占用進(jìn)路時(shí)間要大于進(jìn)路占用時(shí)間標(biāo)準(zhǔn)；⑽ 式表示每條進(jìn)路上任何 2 個(gè)列車的占用時(shí)間都不能相互沖突；⑾ 式為各項(xiàng)技術(shù)作業(yè) Rij起止時(shí)間的取值,其中第 1 和 4 分項(xiàng)分別是列車占用到發(fā)線的到達(dá)作業(yè)起止時(shí)間和出發(fā)作業(yè)起止時(shí)間,第 2 分項(xiàng)是按順序的其他靜態(tài)作業(yè)起止時(shí)間,第 3 分項(xiàng)是按順序的動(dòng)態(tài)作業(yè)起止時(shí)間。

3　求解思路及算法

作業(yè)時(shí)間調(diào)整策略是指通過調(diào)整和改變技術(shù)作業(yè)當(dāng)前起止時(shí)間的方法,從時(shí)間維度上來化解作業(yè)沖突、優(yōu)化作業(yè)安排。調(diào)整規(guī)則為：①判斷作業(yè)Rij是靜態(tài)還是動(dòng)態(tài)作業(yè),如果是動(dòng)態(tài)作業(yè)則可以直接調(diào)整時(shí)間,如果是靜態(tài)作業(yè)則通過調(diào)整其緊鄰的動(dòng)態(tài)作業(yè)時(shí)間來達(dá)到調(diào)整靜態(tài)作業(yè)時(shí)間的目的；②動(dòng)態(tài)作業(yè)采用起止時(shí)間同時(shí)偏移法進(jìn)行調(diào)整,不能改變動(dòng)態(tài)作業(yè)時(shí)間長度；③每項(xiàng)作業(yè)Rij可調(diào)整的時(shí)間范圍為Δtdik是作業(yè) Rij前每項(xiàng)靜態(tài)作業(yè)的等待時(shí)間；④以需要調(diào)整的動(dòng)態(tài)作業(yè)當(dāng)前時(shí)間為原點(diǎn),以 Δtij為最大限度,向其前后搜尋能夠安排該項(xiàng)動(dòng)態(tài)作業(yè)的合理設(shè)備上的時(shí)間空檔,如果找到合適時(shí)間空檔則判斷其是否滿足化解沖突或優(yōu)化作業(yè)的時(shí)間偏移需求,如果滿足則將動(dòng)態(tài)作業(yè)時(shí)間偏移至該空擋,否則終止調(diào)整算法；⑤時(shí)間調(diào)整后對緊前作業(yè)和緊后作業(yè)時(shí)間進(jìn)行修正(時(shí)間修正的計(jì)算見 ⑾ 式),對修正后的作業(yè)進(jìn)行沖突檢測,如果存在沖突,則運(yùn)用作業(yè)設(shè)備調(diào)整策略對沖突進(jìn)行調(diào)整,如果調(diào)整無效,則終止調(diào)整算法,否則統(tǒng)計(jì)目標(biāo)值,記錄修改后的作業(yè)方案。

4　算例分析

以某站技術(shù)作業(yè)計(jì)劃編制為例進(jìn)行算例分析。該站有 2 條正線,9 條客車到發(fā)線,5 個(gè)站臺(tái),3 條到發(fā)場至客技場的聯(lián)絡(luò)線,17 條客車整備線,2 臺(tái)調(diào)車機(jī)車 (1 臺(tái)負(fù)責(zé)到發(fā)場與聯(lián)絡(luò)線間車底取送,1臺(tái)負(fù)責(zé)客整場與聯(lián)絡(luò)線間車底取送),選取該站某天的列車時(shí)刻表,包含到發(fā)列車 96 對,其中有 22個(gè)車底 (含 2 個(gè)動(dòng)車組)入庫。其車站技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)為：始發(fā)作業(yè) 40 min,到達(dá)作業(yè) 30 min,進(jìn)出站咽喉占用 7 min,調(diào)車機(jī)車取送 10 min,客車整備 360 min,聯(lián)絡(luò)線作業(yè) 10 min。按照上述算法流程并用計(jì)算機(jī)編程開發(fā)的系統(tǒng)計(jì)算[8],得到車站出入庫車底技術(shù)作業(yè)計(jì)劃編制方案如表1 所示。

表1　車站出入庫車底技術(shù)作業(yè)計(jì)劃編制方案

方案給出了 22 個(gè)出入庫車底及動(dòng)車組的計(jì)劃,由于動(dòng)車組無需調(diào)車機(jī)車作業(yè),因而只給出了其在聯(lián)絡(luò)線上的作業(yè)起止時(shí)間。與固定使用方案相比,系統(tǒng)給出的方案中,固定設(shè)備使用兌現(xiàn)率超過 90%,同時(shí)設(shè)備使用過程中的均衡性也較好,達(dá)到了客運(yùn)站技術(shù)作業(yè)計(jì)劃編制要求,證明算法可行、有效,能夠大大減輕人工編制客運(yùn)站技術(shù)作業(yè)計(jì)劃的工作強(qiáng)度。

5　結(jié)束語

客運(yùn)站技術(shù)作業(yè)計(jì)劃的時(shí)間協(xié)調(diào)具有多方案性,屬于柔性調(diào)整,運(yùn)用基于時(shí)間協(xié)調(diào)的技術(shù)作業(yè)任務(wù)同質(zhì)化求解算法尋求有效解,并以某車站為實(shí)例進(jìn)行驗(yàn)證,表明該算法在降低客運(yùn)站技術(shù)作業(yè)編制復(fù)雜度和規(guī)模性上的有效性,為編制復(fù)雜作業(yè)流程客運(yùn)站技術(shù)作業(yè)計(jì)劃提供了解決途徑。為繼續(xù)提升算法效率,還需要對作業(yè)設(shè)備調(diào)整策略和作業(yè)時(shí)間調(diào)整策略算法做進(jìn)一步的研究。

[1] 史 峰,陳 彥,秦 進(jìn),等. 鐵路客運(yùn)站到發(fā)線運(yùn)用和接發(fā)車進(jìn)路排列方案綜合優(yōu)化[J]. 中國鐵道科學(xué),2009, 30(6) ：108-113. SHI Feng,CHEN Yan,QIN Jin,et al. Comprehensive Optimization of Arrival-Departure Track Utilization and Inbound-Outbound Route Assignment in Railway Passenger Station[J]. China Railway Science,2009,30(6)：108-113.

[2] Abbink E,van den Berg B,Kroon L,et al. Allocation of Railway Rolling Stock for Passenger Trains[J]. Transportation Seience,2004,38(1)：33-41.

[3] Billaut J,Moukrim A,Sanlaville E. Flexibility and Robustness in Scheduling[M]. London：John Wiley&Sons,2008.

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

[5] 陳 彥. 鐵路客運(yùn)站列車過站徑路與調(diào)機(jī)運(yùn)用優(yōu)化[D]. 長沙：中南大學(xué),2010.

[6] 雷定猷,張英貴,劉明翔. 鐵路客技站車底作業(yè)排序模型與算法[J]. 鐵道學(xué)報(bào),2007,29(6) ：1-5. LEI Ding-you,ZHANG Ying-gui,LIU Mingxiang. Scheduling Model and Algorithm of Carriage Operations Arrangements in Railway Passenger Technology Stations[J]. Journal of Railway Society,2007,29(6)：1-5.

[7] 雷定猷,張英貴,王新宇,等. 鐵路客技站車底作業(yè)耦合窗時(shí)排序模型與算法[J]. 鐵道學(xué)報(bào),2010,32(4)：1-7. LEI Ding-you,ZHANG Ying-gui,WANG Xin-yu,et al. Coupled Due Windows Scheduling Model and Algorithm of Carriage Operations Arrangements in Railway Technology Stations[J]. Journal of Railway Society,2010,32(4)：1-7.

[8] 陳 韜,呂紅霞,王艷艷. 客運(yùn)專線車站作業(yè)計(jì)劃編制系統(tǒng)的研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì),2009,31(8)：12-15. CHEN Tao,LV Hong-xia,WANG Yan-yan. Study on the System of Railway Station Technical Work Planning for Passenger-dedicated Lines[J]. Railway Transport and Economy,2009,31(8)：12-15.

責(zé)任編輯：劉 新

Study on Drawing Algorithm of Technical Operation Planning of Railway Passenger Station based on Technical Operation Time Coordination

Through analyzing the characteristics of each technical operation in railway passenger station, this paper expounds the homogeneity and common character of the technical operation on equipments of arrival-departure line, shunting locomotive, passenger technical line and throat route. Based on above, the surplus time of technical operation was determined, and the drawing model of technical operation planning of passenger station was established by taking maximized stationary use and balanced use of equipments as the objects, and then, the solution idea and algorithm of the model was provided. In the end, through calculation example, the effectiveness of the model and algorithm were validated.

Passenger Station; Technical Operation Planning; Operation Time Coordination; Algorithm

1003-1421(2015)10-0017-06+7；U292.1

A

U291.6

10.16668/j.cnki.issn.1003-1421.2015.10.04

2015-05-28

國家自然科學(xué)基金項(xiàng)目 (61273242,61403317, 60776826)；四川省科技廳軟科學(xué)計(jì)劃項(xiàng)目 (2015ZR0141)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助 (2682015CX043)；中國鐵路總公司科技研究開發(fā)計(jì)劃項(xiàng)目 (2015X008-B,2014X004-D)