陳 韜，王文憲，呂紅霞，呂苗苗，劉曉偉

(1.西南交通大學 交通運輸與物流學院，四川 成都 610031；2.西南交通大學 全國鐵路列車運行圖編制研發(fā)培訓中心，四川 成都 610031；3.綜合交通運輸智能化國家地方聯(lián)合工程實驗室，四川 成都 610031；4.五邑大學 軌道交通學院，廣東 江門 529020)

高速鐵路(以下簡稱高鐵)樞紐站是指位于高鐵的起訖點或銜接兩(多)條高鐵，開行大量始發(fā)、終到高速列車的車站，附近一般設(shè)有動車所(段)，兩者由動車走行線聯(lián)通[1]。為了確保列車運行計劃的可實施性，高鐵樞紐站需要編制技術(shù)作業(yè)計劃，動車所需要編制調(diào)車作業(yè)計劃。由于高鐵樞紐站非立折始發(fā)、終到列車通常都要安排到相鄰動車所進行整備、停留和檢修，因而，高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃具有強耦合性，具體表現(xiàn)為：一方面，高鐵樞紐站非立折始發(fā)、終到列車需及時出入動車所，以減少高鐵樞紐站的到發(fā)線占用，提升車站的通過能力；而另一方面列車密集出入動車所以及動車所作業(yè)安排不當，可能會超過動車所通過能力和作業(yè)能力，造成動車所的擁堵，從而制約列車出入動車所的數(shù)量和時間，引發(fā)高鐵樞紐站技術(shù)作業(yè)計劃的再調(diào)整。因此，高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃在編制過程中需要多次協(xié)調(diào)、共同確定非立折始發(fā)、終到列車的出入動車所時間，并在此基礎(chǔ)上編制可行的高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃。

既有研究大多將高鐵樞紐站技術(shù)作業(yè)計劃[2-5]與動車所調(diào)車作業(yè)計劃[6-8]分開單獨研究，且非立折始發(fā)、終到列車的出入動車所時刻常作為定值[9]處理。朱昌鋒[10]將出入所時刻作為列車占用到發(fā)線的可調(diào)整要素，并假設(shè)動車所能力充分大。郭彬[11]在高鐵大站技術(shù)作業(yè)計劃編制中從減少非立折始發(fā)、終到列車的股道占用時間以及出入所與接發(fā)車進路沖突的角度探討了列車出入所時刻的確定方法，但沒有考慮動車所調(diào)車作業(yè)計劃的可行性。目前，研究高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃相互協(xié)同編制的文獻較少，使得此兩種計劃的編制效率和能力利用優(yōu)化受到限制。

本文在分析高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃的協(xié)同編制過程基礎(chǔ)上，提出了將作業(yè)計劃編制對象由列車映射為車底，并通過優(yōu)化調(diào)整非立折始發(fā)、終到列車出入所時刻，實現(xiàn)兩個計劃一體化編制的思想。研究建立了基于動車組車底的高鐵樞紐站與動車所作業(yè)計劃協(xié)同編制模型，引入瓶頸工序的確定，設(shè)計了啟發(fā)式分配規(guī)則與并行禁忌搜索算法(PTS)相結(jié)合的混合優(yōu)化算法，并通過實例驗證了相關(guān)理論。

1 問題分析

1.1 高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃協(xié)同編制過程分析

高鐵樞紐站技術(shù)作業(yè)計劃、動車所調(diào)車作業(yè)計劃是在列車運行圖、動車組運用計劃等路網(wǎng)層運輸計劃的基礎(chǔ)上編制的微觀節(jié)點層運輸計劃。高鐵樞紐站技術(shù)作業(yè)計劃在保證列車到發(fā)次序、到發(fā)時刻、列車接續(xù)關(guān)系、作業(yè)流程與時間標準的前提下，確定車站內(nèi)各次列車所占用的到發(fā)線、咽喉進路以及這些設(shè)備的占用起止時刻。動車所調(diào)車作業(yè)計劃在保證高鐵樞紐站非立折始發(fā)、終到列車的檢修和整備作業(yè)流程與時間標準前提下，確定動車所內(nèi)各列車車底各項作業(yè)所占用的股道、轉(zhuǎn)線進路以及這些設(shè)備的起止時刻。其中，非立折始發(fā)、終到列車的出入所時刻一般由高鐵樞紐站編圖人員負責確定，但仍需獲得動車所編圖人員的認同，尤其是高峰期能力緊張時，需要共同協(xié)商確定出入所時刻，如果雙方調(diào)整后仍然無法正常安排作業(yè)，需反饋給列車運行圖及動車組運用計劃編圖人員，通過微調(diào)列車到發(fā)時刻或改變動車交路來提升計劃的可行性。高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃協(xié)同編制過程見圖1。研究發(fā)現(xiàn)，若將高鐵樞紐站與動車所看作一個系統(tǒng)，將作業(yè)計劃編制對象由列車映射為車底，通過優(yōu)化調(diào)整非立折始發(fā)、終到列車出入所時刻，就可實現(xiàn)高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃的一體化編制，是高效率實現(xiàn)兩個計劃協(xié)同編制的有效方法。

1.2 協(xié)調(diào)編制中列車與動車組車底作業(yè)計劃的對應(yīng)關(guān)系特點分析

高鐵樞紐站的非立折終到、始發(fā)列車通常以空車底列車的方式出入動車所進行作業(yè)，如圖2所示，非立折終到列車J1的空車底列車是0J1，非立折始發(fā)列車J2的空車底列車是0J2。就高鐵樞紐站而言，列車J1與0J1、J2與0J2分別對應(yīng)兩個獨立的動車組車底，可當高鐵樞紐站與動車所作為一個系統(tǒng)時，列車J1、0J1、0J2、J2兩兩接續(xù)對應(yīng)同一個動車組車底。因此，樞紐站與動車所作業(yè)計劃協(xié)同編制時，將計劃編制對象由所有列車映射為對應(yīng)的動車組車底，可降低計劃編制對象的規(guī)模，能完整的體現(xiàn)樞紐站及動車所作為一個系統(tǒng)的技術(shù)作業(yè)流程，有利于計劃協(xié)同方案的確定。

本文中，將非立折終到、始發(fā)列車對應(yīng)的車底稱為非立折動車組車底，立折終到、始發(fā)列車對應(yīng)的車底稱為立折動車組車底(如圖2中J3 與J4對應(yīng)的動車組車底)，通過列車在樞紐站無接續(xù)列車，自身就對應(yīng)一個動車組車底(如圖2中J5對應(yīng)的動車組車底)，因此，圖2中共有3個動車組車底需要進行作業(yè)安排。由此可見，通過映射關(guān)系，兩個計劃編制對象由7個列車減少為3個動車組車底。

圖2 高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃協(xié)同編制方案圖

1.3 非立折始發(fā)、終到列車出入所時刻確定

(1)

當冗余時間為正值時，非立折動車組車底出入所時刻就分別存在時間窗(如圖2的點畫線所示)為

(2)

(3)

綜上可見，高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃協(xié)同編制思路為：將高鐵樞紐站與銜接的動車所作為一個系統(tǒng)，所有列車映射為對應(yīng)的動車組車底，通過在時間窗內(nèi)合理確定非立折動車組車底出入所時刻，使得所有動車組車底在樞紐站及動車所的技術(shù)作業(yè)(到達、停站、入所、各種檢修整備、出所、發(fā)車等)所需股道設(shè)備能正確安排，同時滿足各種設(shè)備能力、作業(yè)規(guī)則、時間標準的約束。

2 數(shù)學模型

高鐵樞紐站與動車所作業(yè)計劃協(xié)同編制的本質(zhì)是：對高鐵樞紐站與銜接動車所中，一晝夜內(nèi)接發(fā)列車所對應(yīng)的動車組車底所有技術(shù)作業(yè)所需的股道、進路設(shè)備及其占用起止時刻、出入所時刻進行決策。下面基于這些決策變量，給出滿足各種約束的高鐵樞紐站與動車所作業(yè)計劃協(xié)同編制模型。

2.1 條件及變量假設(shè)

對于高鐵樞紐站銜接的動車所：XZD為動車出入段線數(shù)；SD為作業(yè)場庫數(shù)；GD為股道數(shù)；LD為轉(zhuǎn)線調(diào)車進路數(shù)；動車所共有ND種動車組檢修流程(日常存車、一級檢修、二級檢修等)，根據(jù)動車組運用計劃，動車組車底i若是非立折動車組都將對應(yīng)一種檢修流程N(i)，每種檢修流程有RN(i)個需安排股道的檢修作業(yè)任務(wù)，每個作業(yè)任務(wù)都需在特定的場庫完成；F′(i)、F″(i)分別為動車組車底i的接車方向和發(fā)車方向；G(i,j)為動車組車底i的第j個作業(yè)任務(wù)安排的股道，i∈J,j∈Wi。

2.2 模型建立

2.2.1 優(yōu)化目標

列車運行圖及動車運用計劃確定了一晝夜內(nèi)接發(fā)列車對應(yīng)的動車組車底在高鐵樞紐站及動車所的停留總時間及技術(shù)作業(yè)內(nèi)容，但是樞紐站與動車所可能能力不足，不能完全安排技術(shù)作業(yè)。因此，本文提出的優(yōu)化目標為，盡可能多的安排動車組車底在樞紐站及動車所需安排的技術(shù)作業(yè)(到達、停站、入所、各種檢修整備、出所、發(fā)車等)，即所有動車組車底在樞紐站及動車所的技術(shù)作業(yè)安排效益值最大化。模型的優(yōu)化目標為

(4)

式中:Z為效益值；xijk為0-1變量，動車組車底i的第j個作業(yè)任務(wù)安排在股道k上則為1，否則為0；cijk為動車組車底安排在股道上的效益；A為自定義的常數(shù)[2]。

2.2.2 約束條件

(1)動車組車底作業(yè)股道時空占用的唯一性約束，即樞紐站及動車所任何一條股道在任意時間內(nèi)只允許被一個車底占用，而動車組車底作業(yè)只能占用一個股道，可表示為

(5)

(6)

(7)

式(5)表示車底的每個作業(yè)任務(wù)僅能安排一條股道；式(6)表示每個作業(yè)任務(wù)的股道實際停留時間應(yīng)大于占用時間標準；式(7)表示所有車底作業(yè)任務(wù)占用股道的時間不允許重合。

(2)動車組的每項作業(yè)在時間安排上存在嚴格先后次序，不能早于動車組車底到達時刻、不能遲于動車組車底出發(fā)時刻，不能占用天窗時間，且每項作業(yè)的起止時刻必須滿足其前項、后項作業(yè)時間的約束，可表示為

(8)

(9)

式(8)表示立折動車組車底的股道占用起止時刻等于車底到發(fā)時刻；式(9)的分式一表示非立折動車組車底第一項股道占用起止時刻分別等于車底到達時刻和入所時刻，且入所時刻不能占用天窗；式(9)的分式三表示最后一項股道占用起止時刻等于車底出所時刻和出發(fā)時刻，且出所時刻不能占用天窗；式(9)的分式二表示其余的股道占用起止時刻需滿足前后項時刻約束，即是不能早于前一項股道占用終止時刻，不能晚于后一項股道占用始發(fā)時刻。

(3)非立折動車組車底出入所時刻須滿足時間窗約束，即

Ri≠0

(10)

(11)

Ri≠0

(12)

式(10)表示非立折動車組車底的股道冗余時間；式(11)、式(12)分別表示動車組車底出入所時刻應(yīng)在時間窗內(nèi)。具體說明可見1.3節(jié)。

(4)動車組車底須滿足進路時空占用的唯一性約束，即任一動車組車底在任意時間內(nèi)只允許占用一條接發(fā)車進路，且任何一組敵對進路，在任意時間內(nèi)只允許被一個車底占用，可表示為

(13)

(14)

式(13)表示動車組車底i接發(fā)車進路僅能安排在一條接發(fā)車進路上；式(14)表示動車組車底i與動車組車底i′的進路存在沖突時，其接發(fā)間隔應(yīng)不小于間隔時間標準。

(5)動車組車底須滿足轉(zhuǎn)線時調(diào)車進路時空占用的唯一性約束，即任何一個動車組車底在任意時間內(nèi)只允許占用一條調(diào)車進路，且任何一組敵對進路，在任意時間內(nèi)只允許被一個車底占用，可表示為

(15)

(16)

式(15)表示動車組車底i的第j個作業(yè)任務(wù)安排調(diào)車進路時，僅能安排在一條調(diào)車進路上；式(16)的第一分式表示動車組車底的轉(zhuǎn)線進路占用時間等于前后任務(wù)股道占用起止時間之差，第二分式表示動車組車底i與動車組車底i′的調(diào)車進路存在沖突時，其調(diào)車間隔應(yīng)大于等于間隔時間標準，第三、四分式分別表示動車組車底i的調(diào)車進路與動車組車底i′的接、發(fā)車進路存在沖突，其進路安排應(yīng)大于等于間隔時間標準。

此外，如果沒有特別標注，則上述公式中的角標取值范圍為

i,i′∈J,j∈(Wi+RN(i)),j′∈(Wi′+RN(i′)),

k,k′∈(GZ+GD)

(17)

3 算法設(shè)計

把動車組車底看作加工工件，高鐵樞紐站及動車所的股道或進路看作加工設(shè)備，則高鐵樞紐站與動車所作業(yè)計劃協(xié)調(diào)編制是典型的多階段Job-shop車間調(diào)度問題，該問題已經(jīng)被證明是NP問題，其解空間隨著動車組車底數(shù)量的增加、站場規(guī)模的擴大呈現(xiàn)“組合爆炸”[12-13]。本文提出了啟發(fā)式分配規(guī)則與并行禁忌搜索算法(Parallel-TS，PTS)相結(jié)合的混合優(yōu)化算法進行模型求解。其中，啟發(fā)式分配規(guī)則來源于長期實際編圖過程中的人工決策經(jīng)驗，可以快速生成較為可靠的初始解。并行禁忌搜索算法(PTS)在傳統(tǒng)禁忌搜索算法(TS)中引入并行化策略，并運行在計算機分布式并行計算環(huán)境中，實現(xiàn)空間換時間有效提高搜索效率，已被廣泛的運用于解決NP問題[14]。此外，本文在算法中引入瓶頸工序的確定，以進一步加快解的搜索。

3.1 瓶頸工序的確定[15]

瓶頸工序是指制約整個作業(yè)流程加工速度的環(huán)節(jié)，通常表現(xiàn)為設(shè)備能力不足或加工耗時過長造成的工件排序現(xiàn)象。觀察到本問題中非立折動車組需安排的作業(yè)任務(wù)多且往往由于設(shè)備能力不足存在瓶頸制約現(xiàn)象(如動走線、洗車線、檢修庫的能力不足)，此時，動車組車底需要在存車線、臨修線等處進行等待，因此，判斷瓶頸工序并優(yōu)先瓶頸工序的資源分配，可減少無效搜索。瓶頸工序是根據(jù)設(shè)備負荷率來確定的，具體為

(18)

式中：ηSj為場站設(shè)備Sj的負荷率；TSj為第j個作業(yè)任務(wù)所用的Sj類設(shè)備可用的最大時間。

式(18)是一個估算，表示動車組車底在每類設(shè)備上作業(yè)停留占用的時間比率，ηSj越大，則表示被占用時間越大，設(shè)備的負荷越大。

3.2 PTS算法設(shè)計及實現(xiàn)

借鑒賀一[14]的研究成果，本文采用粗粒度主從進程模式的PTS策略。計算機中的主進程負責生成一定規(guī)模的初始解，然后將每個初始解分發(fā)給一個從進程，每個從進程由此獨立的執(zhí)行一個TS算法，迭代足夠的次數(shù)后，每個從進程將搜索當前最優(yōu)解發(fā)給主進程，主進程比較并記錄全局最優(yōu)解，根據(jù)一定的交叉策略，生成新初始解，重新發(fā)送給從進程進行TS搜索，直到終止條件成立。

3.2.1 初始解排序規(guī)則設(shè)計

本文設(shè)計動車組車底在車站及動車所的作業(yè)安排規(guī)則，可快速生成初始解，并在此基礎(chǔ)上構(gòu)造初始解種群，包括：

(1)動車組車底安排次序規(guī)則：優(yōu)先安排擔當高等級列車的動車組車底作業(yè)，當?shù)燃壪嗤瑫r，按照先到先服務(wù)的原則安排，優(yōu)先保證重點列車的安排。

(3)動車組車底到發(fā)線安排規(guī)則：優(yōu)先按照固定使用方案安排到發(fā)線，當固定使用方案無空閑到發(fā)線選擇，按照先到先排、均衡使用原則選擇到發(fā)線安排。

(4)動車組車底調(diào)車股道安排規(guī)則：按照先到先排、均衡使用原則安排動車組每項檢修作業(yè)所在的股道。

(5)動車組車底進路安排規(guī)則：按照出發(fā)進路優(yōu)先到達進路、出場庫調(diào)車進路優(yōu)先入場庫調(diào)車進路、最大平行進路優(yōu)先的規(guī)則安排調(diào)車進路。

(6)動車組車底股道占用起止時刻安排規(guī)則：動車組車底到發(fā)線占用起止時刻由動車組車底擔當列車的到發(fā)時刻以及出入所時刻來確定。動車組車底調(diào)車作業(yè)股道占用的起止時刻以出入所時刻為界，根據(jù)作業(yè)工序需求，遵循最小作業(yè)時間標準，作業(yè)時間連續(xù)規(guī)則來推定。

(7)動車組車底作業(yè)沖突解決規(guī)則：動車組車底每項作業(yè)將通過遍歷股道、進路設(shè)備，尋找空閑的時段按照規(guī)則進行安排，但是如果找不到合適的空閑時段則出現(xiàn)作業(yè)沖突的現(xiàn)象，對作業(yè)沖突進行如下處理：

①到發(fā)線沖突：設(shè)置虛擬到發(fā)線GZ0，當車底的到發(fā)線找不到合適股道時，將直接安排在GZ0上，效益系數(shù)c為0。

②動走線沖突：改變出入所時間，來調(diào)整沖突，這時若引起到發(fā)線沖突，則回到①解決。

③調(diào)車股道沖突：若是在安排非存車工序如洗車、檢修等出現(xiàn)沖突，則增加存車線工序進行等待，調(diào)整非存車工序的起止時間，進行工序安排，如果還是沖突，取消存車線工序直接安排到虛擬股道GD0上，效益系數(shù)c為0，繼續(xù)安排下一工序。

以上步驟中虛擬股道的安排，雖然對實際問題而言不是有效的可行解，但是對于整個模型來說就能快速構(gòu)造每個動車組車底的初始可行解，便于在此基礎(chǔ)上的迭代優(yōu)化，而且由于其效益系數(shù)c為0，所以不會影響模型的目標函數(shù)值。

3.2.2 PTS主進程初始解構(gòu)造

按照3.2.1小節(jié)中的“動車組車底安排次序規(guī)則”對動車組車底J進行排序，隨機調(diào)換同等級的車底順序，得到Q個不同排序組合，依次從中取出排序好的動車組車底集合，按照3.2.1中(2)～(7)的規(guī)則，對每一個動車組車底順序安排車底的各項作業(yè)，形成一個作業(yè)計劃，得到一個初始解，見圖3，將初始解隨機分配給一個從進程。

3.2.3 PTS從進程TS算法實現(xiàn)

PTS從進程執(zhí)行傳統(tǒng)的TS算法，具體操作為：

(1)從主進程得到一個初始解Qi。

(2)基于Qi產(chǎn)生鄰域解。本文提出工序所在的股道2-opt(兩兩交換)和時間調(diào)整兩個操作，然后調(diào)用排序規(guī)則，生成新的作業(yè)安排計劃，構(gòu)成鄰域解，具體操作如下：

圖3 多個初始解構(gòu)造過程

①股道設(shè)備占用調(diào)整：若某個工序存在未被安排的車底作業(yè)，則隨機選擇一個已經(jīng)被安排的車底作業(yè)，選擇一個除虛擬股道GZ0、GD0外的可選的權(quán)值盡可能大的可行股道替換其當前的股道，當有多個可替換股道時，選擇被利用率最高的股道。

②到發(fā)線作業(yè)股道時刻占用調(diào)整：立折動車組車底的到發(fā)線作業(yè)起止時刻不能改變，非立折動車組車底的到發(fā)線起止作業(yè)時刻可以改變，這時隨機選擇一個非立折動車組車底，在時間窗范圍內(nèi)，改變出所或入所時刻，使其不會引起緊前和緊后工序作業(yè)的時間沖突，同時修正緊前和緊后工序的起止時刻。

③動車所內(nèi)作業(yè)股道時間占用調(diào)整：隨機選擇一個非立折動車組車底，若其存在未被安排的車底作業(yè)，且該作業(yè)為非存車作業(yè)，則通過在時間窗范圍內(nèi)，整體前移或后移作業(yè)至時間移動量最小且權(quán)值盡可能大的空閑時間段內(nèi)，同時修正緊前和緊后工序的起止時刻；若該作業(yè)為存車作業(yè)，則改變轉(zhuǎn)線時刻或增加轉(zhuǎn)線作業(yè)來解決時間沖突，同時修正緊前和緊后工序的起止時刻。

然后，遍歷虛擬股道GZ0、GD0上的工序，按照3.2.1小節(jié)的(3)、(4)、(5)、(7)規(guī)則，盡量安排到可用股道上。整個調(diào)整按照到發(fā)線、瓶頸工序、次瓶頸工序的順序進行，如果某個工序上所有動車組車底都安排好了，沒有多余作業(yè)的沖突則無需進行調(diào)整。

(3)評價函數(shù)：以目標函數(shù)值進行對每個鄰域解進行評價。

(4)禁忌表：將鄰域解中生成的作業(yè)方案及其評價值進行禁忌，貯存在禁忌表內(nèi)，本文根據(jù)頻率信息動態(tài)控制禁忌的長度，采用動態(tài)禁忌長度。

(5)特赦條件：找不到領(lǐng)域解及迭代一定次數(shù)后，特赦禁忌表中最優(yōu)值為當前解繼續(xù)進行迭代搜索。

3.2.4 PTS主進程交叉操作及初始解再構(gòu)造

整個算法流程見圖4。

圖4 算法流程圖

4 算例驗證

某高鐵樞紐站及動車所站場設(shè)備布置見圖5，有A、B兩個接發(fā)車方向，各作業(yè)項目的最小時間標準見表1，選取該站某天的列車時刻表，包含到發(fā)列車140列，即有70個動車組車底，其中有 18個非立折動車組車底需進入動車所檢修整備(15個進行一級檢修作業(yè)，3個進行存車作業(yè))，假設(shè)每個股道的效益值都一樣，按照上述算法流程并用計算機編程計算。

根據(jù)動車組車底數(shù)及作業(yè)流程數(shù)，必須安排全部作業(yè)工序為166項：88項樞紐站到發(fā)作業(yè)、36項出入動車所作業(yè)、15項檢修作業(yè)、15項洗車作業(yè)、15項庫前吸污作業(yè)、最少18項的存車作業(yè)(可能由于作業(yè)排隊，需要增加存車線上的等待作業(yè))。按照表1的作業(yè)時間標準、動車所各車場設(shè)備數(shù)、非立折動車組數(shù)，代入式(16)計算非立折動車組主要工序負荷率為：存車線負荷率0.073、洗車線負荷率0.208、庫前吸污線0.091、檢修線0.417。可知瓶頸工序為檢修線。由于到發(fā)線安排更為關(guān)鍵，因此，從進程TS算法優(yōu)化調(diào)整時，將按照“到發(fā)線→動車走行線→檢修線→洗車線→庫前吸污線→存車線”的工序順序進行作業(yè)調(diào)整安排。

圖5 高鐵樞紐站及動車所站場圖

設(shè)計1個主進程和3個從進程運用PTS進行解搜索。為了方便，用未安排作業(yè)錯誤數(shù)進行優(yōu)化目標統(tǒng)計。本文首先主進程生成不同安排次序的3個車底組合，然后根據(jù)排序規(guī)則分別生成3個初始解方案，這時3個方案的在虛擬股道上未安排作業(yè)錯誤數(shù)分別為52項、40項、50項，全局最優(yōu)解是40項的作業(yè)方案。將3個方案分別分給3個從進程，然后按照3.2.3的TS算法不斷調(diào)整優(yōu)化作業(yè)方案，直到最大迭代次數(shù)。這時3個從進程的當前最優(yōu)解分別為未安排作業(yè)錯誤數(shù)分別為17項、11項、13項，將當前全局最優(yōu)解11項的作業(yè)方案傳給主進程，主進程對3個從進程進行交叉操作后，產(chǎn)生新的初始方案，這時未安排作業(yè)錯誤數(shù)分別為19項、11項、12項，在此基礎(chǔ)上3個從進程繼續(xù)尋優(yōu)。如此往復在主進程第4次分配后逐漸收斂，最終得到4項未安排作業(yè)錯誤數(shù)的作業(yè)方案，整個搜索過程見圖6。由于這4項未安排作業(yè)都是存車作業(yè)，最后通過人工調(diào)整，增加轉(zhuǎn)線作業(yè)，完成作業(yè)安排，高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃最終協(xié)調(diào)方案見圖7。

實例證明PTS算法比單純的TS算法節(jié)省2/3以上的時間，且高鐵樞紐站與動車所作業(yè)計劃的一體化編制能生成保證協(xié)調(diào)性和可行性的精確方案，比實際現(xiàn)場中人工分開單獨編制兩個計劃后再協(xié)調(diào)的工作重復性和復雜性顯著降低。

表1 各項作業(yè)時間標準

圖7 高鐵樞紐站技術(shù)作業(yè)與動車所調(diào)車作業(yè)計劃協(xié)同編制方案

圖6 高鐵樞紐站及動車所作業(yè)方案PTS搜索過程

5 結(jié)論

長期以來，高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃編制都被孤立成單獨的兩個問題進行研究，使得兩個計劃在編制協(xié)同效率和能力優(yōu)化利用上存在制約。本文分析了高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃的協(xié)同編制過程，提出了以到發(fā)列車所對應(yīng)的動車組車底為協(xié)同編制對象，動車組車底出入所時間為協(xié)同編制關(guān)鍵的高鐵樞紐站與動車所作業(yè)計劃協(xié)同編制模型，設(shè)計了瓶頸工序、啟發(fā)式分配規(guī)則、并行禁忌搜索算法(PTS)相結(jié)合的混合優(yōu)化算法，最后通過實例驗證了相關(guān)理論的有效性。結(jié)果表明高鐵樞紐站技術(shù)作業(yè)計劃與動車所調(diào)車作業(yè)計劃的一體化編制比分開編制在方案可行性和效率上更具優(yōu)勢。下一步可拓展到多個高鐵樞紐站銜接一個動車所的情形，探求效率更高的計算方法。