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

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

（1.中鐵集裝箱有限責任公司國內(nèi)物流部，北京100055；2.西南交通大學(xué)交通運輸與物流學(xué)院，四川成都610031；3.北京鐵路局運輸處，北京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è)時間協(xié)調(diào)的鐵路客運站技術(shù)作業(yè)計劃編制算法研究

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

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

（1.中鐵集裝箱有限責任公司國內(nèi)物流部，北京100055；2.西南交通大學(xué)交通運輸與物流學(xué)院，四川成都610031；3.北京鐵路局運輸處，北京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è)的特點，闡述到發(fā)線、調(diào)車機車、客技線、咽喉進路等設(shè)備上技術(shù)作業(yè)的同質(zhì)性與共性，在此基礎(chǔ)上確定技術(shù)作業(yè)富余時間，以最大限度固定使用和均衡使用設(shè)備為目標建立客運站技術(shù)作業(yè)計劃編制模型，并給出模型求解思路及算法，最后通過算例驗證模型及算法的有效性。

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

1　概述

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

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

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

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

2.1 變量定義

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

列車/車底 Ji在每項作業(yè)上的技術(shù)作業(yè)時間標準為；進路占用時間標準為。

2.2模型建立

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

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

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

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

2.2.2目標函數(shù)

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

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

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

將 2 個目標函數(shù)進行歸一化處理,則

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

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

2.2.3約束條件

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

3　求解思路及算法

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

4　算例分析

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

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

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

5　結(jié)束語

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

[1] 史 峰,陳 彥,秦 進,等. 鐵路客運站到發(fā)線運用和接發(fā)車進路排列方案綜合優(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è)計劃智能編制的優(yōu)化技術(shù)和方法研究[D]. 成都：西南交通大學(xué),2008.

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

[6] 雷定猷,張英貴,劉明翔. 鐵路客技站車底作業(yè)排序模型與算法[J]. 鐵道學(xué)報,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è)耦合窗時排序模型與算法[J]. 鐵道學(xué)報,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è)計劃編制系統(tǒng)的研究[J]. 鐵道運輸與經(jīng)濟,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.

責任編輯：劉 新

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é)基金項目 (61273242,61403317, 60776826)；四川省科技廳軟科學(xué)計劃項目 (2015ZR0141)；中央高?；究蒲袠I(yè)務(wù)費專項資金資助 (2682015CX043)；中國鐵路總公司科技研究開發(fā)計劃項目 (2015X008-B,2014X004-D)