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

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

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

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

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

1 問題分析

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

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

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

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

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

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

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

(1)

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

(2)

(3)

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

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

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

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

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

2.2 模型建立

2.2.1 優(yōu)化目標(biāo)

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

(4)

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

2.2.2 約束條件

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

(5)

(6)

(7)

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

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

(8)

(9)

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

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

Ri≠0

(10)

(11)

Ri≠0

(12)

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

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

(13)

(14)

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

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

(15)

(16)

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

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

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

k,k′∈(GZ+GD)

(17)

3 算法設(shè)計(jì)

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

3.1 瓶頸工序的確定[15]

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

(18)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.3 PTS從進(jìn)程TS算法實(shí)現(xiàn)

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

(1)從主進(jìn)程得到一個(gè)初始解Qi。

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

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

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

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

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

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

(3)評價(jià)函數(shù)：以目標(biāo)函數(shù)值進(jìn)行對每個(gè)鄰域解進(jìn)行評價(jià)。

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

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

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

整個(gè)算法流程見圖4。

圖4 算法流程圖

4 算例驗(yàn)證

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

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

圖5 高鐵樞紐站及動(dòng)車所站場圖

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

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

表1 各項(xiàng)作業(yè)時(shí)間標(biāo)準(zhǔn)

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

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

5 結(jié)論

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