基于改進(jìn)蟻群算法的鐵路乘務(wù)交路計劃的編制

王東先 孟學(xué)雷 喬俊 湯霖 焦志臻

摘 要：針對提高鐵路乘務(wù)交路計劃編制質(zhì)量和效率的問題，將乘務(wù)交路計劃編制問題抽象為單基地、均衡行駛路程的多旅行商問題（MTSP），引入均衡因子，建立了以乘務(wù)交路用時少和子乘務(wù)交路間任務(wù)均衡為目標(biāo)的數(shù)學(xué)模型。針對該模型提出了一種雙重策略蟻群優(yōu)化算法，該算法首先構(gòu)建滿足時空約束的解空間，分別對乘務(wù)區(qū)段節(jié)點(diǎn)和接續(xù)路徑設(shè)置信息素濃度，然后采用雙重策略狀態(tài)的轉(zhuǎn)移概率，使螞蟻遍歷所有乘務(wù)區(qū)段，最終找到符合乘務(wù)約束規(guī)則的子乘務(wù)交路。最后運(yùn)用廣深線城際鐵路數(shù)據(jù)對設(shè)計的模型及算法進(jìn)行檢驗(yàn)，經(jīng)與遺傳算法的實(shí)驗(yàn)結(jié)果對比分析表明：在相同的模型條件下，運(yùn)用雙重策略蟻群優(yōu)化算法編制的乘務(wù)交路計劃乘務(wù)交路個數(shù)減少了約21.74%、乘務(wù)交路總時長降低了約5.76%、交路超勞率為0。運(yùn)用所設(shè)計的模型和算法編制乘務(wù)交路計劃能夠減少乘務(wù)計劃交路時長，均衡工作量，避免產(chǎn)生超勞交路。

關(guān)鍵詞：鐵路;乘務(wù)交路計劃;均衡因子;多旅行商問題;雙重策略蟻群算法

中圖分類號：TP301.6

文獻(xiàn)標(biāo)志碼：A

Railway crew routing plan based on improved ant colony algorithm

WANG Dongxian1， MENG Xuelei1*， QIAO Jun1， TANG Lin1， JIAO Zhizhen2

1.School of Traffic and Transportation， Lanzhou Jiaotong Unirersity， Lanzhou Gansu 730070， China;

2.China Railway Lanzhou Group Company Limited， Wuwei South Station， Wuwei Gansu 733000， China

Abstract：

In order to improve the quality and efficiency of railway crew routing plan， the problem of crew routing plan was abstracted as a Multi-Traveling Salesman Problem （MTSP） with single base and balanced travel distance， and a equilibrium factor was introduced to establish a mathematical model aiming at less crew routing time and balanced tasks between sub-crew routings. A dual-strategy ant colony optimization algorithm was proposed for this model. Firstly， a solution space satisfying the space-time constraints was constructed and pheromone concentration was set for the node of the crew section and the continuation path respectively， then the transitional probability of the dual-strategy state was adopted to make the ant traverse all of the crew segments， and finally the sub-crew routings that meet the crew constraint rules were found. The designed model and algorithm were tested by the data of the intercity railway from Guangzhou to Shenzhen. The comparison with the experimental results of genetic algorithm shows that under the same model conditions， the number of crew routing in the crew routing plan generated by double-strategy ant colony optimization algorithm is reduced by about 21.74%， the total length of crew routing is decreased by about 5.76%， and the routing overload rate is 0. Using the designed model and algorithm to generate the crew routing plan can reduce the crew routing time of crew plan， balance the workload and avoid overload routing.

Key words：

railway; crew routing plan; equilibrium factor; Multi-Traveling Salesman Problem （MTSP）; dual-strategy Ant Colony Algorithm （ACA）

0 引言

鐵路乘務(wù)計劃是依據(jù)列車運(yùn)行圖、機(jī)車交路（動車組交路）、相關(guān)乘務(wù)規(guī)則、車站設(shè)備條件等限制因素編制的，對乘務(wù)人員（司乘）出、退乘時間和地點(diǎn)及擔(dān)當(dāng)車次等做出的詳細(xì)安排，保證了列車運(yùn)行計劃的順利實(shí)施。其中，列車運(yùn)行圖包含了待完成的乘務(wù)任務(wù)，機(jī)車交路（動車組交路）規(guī)定了機(jī)車（動車組）擔(dān)當(dāng)運(yùn)輸任務(wù)的固定周轉(zhuǎn)區(qū)段，乘務(wù)規(guī)則限定了乘務(wù)人員的工作時間，車站設(shè)備條件限制了車站是否是乘務(wù)基地及具備司乘人員換乘或休息的條件。

因?yàn)樵诰幹瞥藙?wù)計劃過程中需要同時考慮到乘務(wù)交路計劃和乘務(wù)排班計劃相關(guān)的大量約束，導(dǎo)致乘務(wù)計劃的編制有難度大、效率低的特點(diǎn)。所以，為了合理優(yōu)化乘務(wù)計劃編制，有效提高編制效率，乘務(wù)計劃往往被分為乘務(wù)交路計劃和乘務(wù)排班計劃。乘務(wù)交路計劃是乘務(wù)排班計劃的基礎(chǔ)，乘務(wù)排班計劃編制的優(yōu)劣取決于乘務(wù)交路計劃。本文針對乘務(wù)交路計劃編制，做出進(jìn)一步的討論。針對乘務(wù)交路計劃編制問題，文獻(xiàn)[1]建立了0-1整數(shù)規(guī)劃和動態(tài)規(guī)劃模型，利用拉格朗日方法求得問題的下界，設(shè)計了樹搜索算法求得最優(yōu)解。文獻(xiàn)[2]利用改進(jìn)的遺傳算法結(jié)合Dijkstra法分階段編制了香港輕軌乘務(wù)計劃，但是該模型對于求解“點(diǎn)多線長”的鐵路乘務(wù)計劃有一定局限性。文獻(xiàn)[3]采用列生成技術(shù)求解了動車組乘務(wù)交路計劃。文獻(xiàn)[4]運(yùn)用了禁忌搜索和圖著色理論編制了乘務(wù)計劃。文獻(xiàn)[5]重點(diǎn)研究了工作效率對于乘務(wù)計劃編制的影響，并用蟻群算法進(jìn)行了求解，但是沒有考慮乘務(wù)交路的均衡性。文獻(xiàn)[6]利用SE（Simulated Evolution）方法編制了京滬高鐵的乘務(wù)計劃。文獻(xiàn)[7]借鑒文獻(xiàn)[6]的SE方法求解了乘務(wù)排班計劃，但是沒有考慮乘務(wù)交路計劃。文獻(xiàn)[8]首次在國內(nèi)將列生成技術(shù)應(yīng)用到了乘務(wù)交路計劃的編制，并把乘務(wù)排班計劃問題抽象成了旅行商問題，但是該算法在求解初始可行解時效率較低。文獻(xiàn)[9]結(jié)合了列生成技術(shù)和分支定界法，進(jìn)而提出了求解乘務(wù)交路計劃的分支定價算法。文獻(xiàn)[10]將客運(yùn)專線的乘務(wù)交路計劃轉(zhuǎn)化為特殊的旅行商問題，并提出了K條徑路的最大最小螞蟻系統(tǒng)（K-Max-Min Ant System， K-MMAS）算法，但是該模型沒有考慮到乘務(wù)人員的任務(wù)均衡性。文獻(xiàn)[11]將乘務(wù)計劃編制問題拆分為最優(yōu)回路構(gòu)造、回路循環(huán)優(yōu)化和排班三個子問題，并設(shè)計了遺傳算法進(jìn)行求解，但是編制步驟過多，不利于鐵路乘務(wù)交路計劃的快速編制。文獻(xiàn)[12]將乘務(wù)交路計劃的編制問題分解為值乘區(qū)段集合的覆蓋和乘務(wù)交路段的匹配兩個子問題，并設(shè)計了改進(jìn)的蟻群算法進(jìn)行求解，但是該模型沒有考慮乘務(wù)計劃與乘務(wù)交路計劃的協(xié)同優(yōu)化。文獻(xiàn)[13]根據(jù)現(xiàn)場調(diào)研統(tǒng)計的結(jié)果，建立了基于乘務(wù)人員偏好性的乘務(wù)交路計劃，但是對于復(fù)雜的交路，沒有給出具體的評價值標(biāo)定方法。文獻(xiàn)[14]通過采用最近鄰域搜索算法和模擬退火算法求解了乘務(wù)交路計劃的數(shù)學(xué)規(guī)劃模型，但是該模型沒有考慮到乘務(wù)交路的均衡性，不適用于城際鐵路乘務(wù)計劃的編制。文獻(xiàn)[15]建立了基于遺傳算法的乘務(wù)計劃編制的求解方法，同時對系統(tǒng)的人機(jī)交互調(diào)整功能進(jìn)行了設(shè)計。文獻(xiàn)[16]提出了基于時空接續(xù)網(wǎng)絡(luò)和網(wǎng)絡(luò)流模型的求解策略來編制高速鐵路乘務(wù)計劃，并利用了拉格朗日松弛算法進(jìn)行求解，但是該算法的迭代步長由經(jīng)驗(yàn)公式自行設(shè)定，缺乏論證。回顧前人研究成果可以看出，國內(nèi)大多數(shù)學(xué)者的研究重點(diǎn)集中于高速鐵路宏觀層面的乘務(wù)計劃，但是，對于乘務(wù)交路計劃研究較少。本文在總結(jié)已有的研究成果基礎(chǔ)上，結(jié)合鐵路乘務(wù)規(guī)則及其特點(diǎn)，將乘務(wù)交路問題抽象為多旅行商問題（Multi-Traveling Salesman Problem， MTSP），最后針對本文研究問題設(shè)計基于雙重策略的蟻群算法求解該模型。

1 乘務(wù)交路計劃數(shù)學(xué)模型的建立

鐵路乘務(wù)交路計劃編制是機(jī)車乘務(wù)計劃的核心問題。乘務(wù)交路計劃編制過程中需綜合考慮鐵路乘務(wù)調(diào)度規(guī)則及資源約束條件，在列車運(yùn)行圖的基礎(chǔ)上，將所有值乘區(qū)段組合成若干個可行乘務(wù)交路，以勞動強(qiáng)度均衡為原則分配乘務(wù)任務(wù)，建立乘務(wù)時長最短，乘務(wù)人員“用戶體驗(yàn)”最佳的乘務(wù)調(diào)度計劃。

1.1 問題描述

最優(yōu)乘務(wù)交路計劃的一項(xiàng)重要指標(biāo)是使用最少的乘務(wù)人員（組）完成上級下達(dá)的運(yùn)行圖任務(wù)。編制鐵路機(jī)車乘務(wù)交路計劃的主要步驟如下。

1）收集列車運(yùn)行信息。根據(jù)列車運(yùn)行圖和機(jī)車交路（動車組交路），獲取列車車次、發(fā)站、到站及動車組在乘務(wù)基地所在站和換乘站的停留作業(yè)時間。

2）選定換乘車站。乘務(wù)人員換乘車站的選取與車站的設(shè)備條件密切相關(guān)，選取的車站必須是具備換乘條件的。根據(jù)運(yùn)行圖數(shù)據(jù)，以單條運(yùn)行線為研究對象，把運(yùn)行線上的所有車站分為3類：具備換乘條件的乘務(wù)基地所在車站、具備換乘條件的非乘務(wù)基地所在車站、不具備換乘條件的非乘務(wù)基地所在車站。

3）劃分乘務(wù)區(qū)段。根據(jù)列車運(yùn)行信息，在輪乘制的值乘模式下，按照乘務(wù)人員一次連續(xù)工作時長標(biāo)準(zhǔn)，以可換乘車站為節(jié)點(diǎn)，把運(yùn)行線逐條劃分為若干滿足乘務(wù)規(guī)則的乘務(wù)區(qū)段。

4）建立可行的乘務(wù)大區(qū)段。一個乘務(wù)大區(qū)段由兩個或兩個以上的乘務(wù)區(qū)段嚴(yán)格按照乘務(wù)規(guī)則（時空接續(xù)規(guī)則）組合而成。乘務(wù)人員（組）完成一個乘務(wù)大區(qū)段值乘任務(wù)的過程是指乘務(wù)人員從乘務(wù)基地開始值乘，到達(dá)換乘公寓所在站，休息一定時間后值乘另一任務(wù)最終返回乘務(wù)基地的過程。

5）把若干可行乘務(wù)大區(qū)段按照乘務(wù)接續(xù)規(guī)則組合成覆蓋整個區(qū)段的乘務(wù)交路。

1.2 乘務(wù)交路計劃時空規(guī)則

1）時間接續(xù)乘務(wù)規(guī)則。相鄰的兩乘務(wù)區(qū)段必須要滿足時間接續(xù)性，即前一個乘務(wù)區(qū)段的到站時刻必須嚴(yán)格早于后一個乘務(wù)區(qū)段的發(fā)車時刻。如果某一個乘務(wù)區(qū)段結(jié)束后乘務(wù)人員正好要換乘（或駐班休息），那么乘務(wù)人員在該站的換乘時間必須嚴(yán)格大于這兩個相鄰乘務(wù)區(qū)段的接續(xù)時間。

2）空間接續(xù)乘務(wù)規(guī)則。相鄰的兩乘務(wù)區(qū)段必須要滿足空間接續(xù)性，即前一個乘務(wù)區(qū)段的到站必須是后一個乘務(wù)區(qū)段的發(fā)站，保證乘務(wù)交路集合必須覆蓋所有的乘務(wù)區(qū)段。因?yàn)殍F路運(yùn)行線相比其他交通運(yùn)行線路較長，經(jīng)常是跨城市甚至是跨省份的，所以乘務(wù)交路必須考慮乘務(wù)人員的歸屬地因素，保證最終生成的乘務(wù)交路的發(fā)站和到站是同一車站。

1.3 乘務(wù)交路數(shù)學(xué)模型

若把乘務(wù)區(qū)段當(dāng)作MTSP中的城市，兩相鄰乘務(wù)區(qū)段之間的接續(xù)就可以看作是城市與城市之間的距離，由于每個子乘務(wù)交路都需一個乘務(wù)組值乘，故子乘務(wù)交路的個數(shù)就是所需乘務(wù)人員（組）的個數(shù)，即旅行商數(shù)目。設(shè)有N個子乘務(wù)交路，則N個子乘務(wù)交路從列車運(yùn)行圖過表時刻（默認(rèn)列車運(yùn)行圖過表時刻為18：00）開始，各子乘務(wù)交路有且僅有一個乘務(wù)組訪問，最后回到過表時刻，形成封閉回路。結(jié)合列車運(yùn)營特點(diǎn)，乘務(wù)交路計劃編制問題可以抽象為單基地、均衡行駛路程的MTSP。

將所有乘務(wù)區(qū)段抽象為點(diǎn)集V，所有的乘務(wù)區(qū)段之間的接續(xù)關(guān)系抽為成邊A，簡化后的乘務(wù)交路區(qū)段可視為有向圖G，即建立具有U個節(jié)點(diǎn)的乘務(wù)交路區(qū)段有向圖G=（V，A）。其中Vi（Vi∈J）是節(jié)點(diǎn)集合V中的節(jié)點(diǎn)，本文將節(jié)點(diǎn)類型分為3類：乘務(wù)區(qū)段點(diǎn)集合、乘務(wù)基地所在站（起點(diǎn)）集合、乘務(wù)基地所在站（終點(diǎn)）集合。其中乘務(wù)區(qū)段點(diǎn)集合含有以下六點(diǎn)屬性：tfi、tdi、sfi、sdi、tti、r 。

弧aij（A={aij/aij=（vi，vj）;vi，vj∈V}）（i、 j=1，2，…，U）表示集合A中的一條連接弧，根據(jù)相關(guān)乘務(wù)規(guī)則，本文將弧集合A分為4種類型：接續(xù)弧集合、外段（折返段）駐班弧集合、出乘弧集合、退乘弧集合。四種不同類型的弧集合都含有以下兩點(diǎn)屬性：ttij、σij。模型中的符號定義如表1所示。

定義1 S={si/si=0，si=1，si=2}（i=1，2，…，U）為列車運(yùn)行圖中的車站集合，令Wsi為第i個車站的屬性，則Wsi=0表示不具備換乘條件的非乘務(wù)基地所在車站，Wsi=1表示具備換乘條件的非乘務(wù)基地所在車站，Wsi=2表示具備換乘條件的乘務(wù)基地所在站。

定義2 H={Hk/k=1，2，…，N}，令Hk為所有子乘務(wù)交路的集合，通常tfi不大于可調(diào)度的乘務(wù)組總數(shù)。

考慮子乘務(wù)交路間工作量均衡的乘務(wù)交路計劃編制問題目標(biāo)函數(shù)包含兩部分：1）乘務(wù)交路總時長最少;2）使子乘務(wù)交路之間的乘務(wù)時間相差最小。通過引入均衡因子將兩部分目標(biāo)統(tǒng)一為：

Z=min{∑Nk=1Zk+δ/ε}; ε∈Z*（1）

Zk=∑Ui=1∑Uj=1[ttij+（tti+ttj）/2]xijk（2）

δ=∑Nk=1∑Ui=1∑Uj=1tdkj-（tdkj-tokj）·xijk+tti+ttjN-12N-1（3）

s.t. Sdi=Sfj; i， j=1，2，…，U（4）

∑h∈Hk ∑i， j∈Aij，φi=φlxijk≥1; l∈L， i，? j=1，2，…，U（5）

∑（i， j）∈Aijxijk=∑（j，i）∈Ajixjik; i∈Vli，i∈Vlj，i， j=1，2，…，U（6）

WSfhk=WSdhk≠0且Sfhk=Sdhk; k=1，2，…，U（7）

∑h∈Hk，（i， j）∈Aoijxijk=1; i∈Vli，j∈Vlj，i， j=1，2，…，U（8）

∑h∈Hk，（i， j）∈Adijxijk=1; i∈Vli，j∈Vlj，i， j=1，2，…，U（9）

tdkj≤tdki+（1-xijk）M+tto+ttj ;

（i， j）∈Aoij， i∈Voi， j∈Vli，l∈L， i， j=1，2，…，U（10）

tdkj≤tdki+（1-xijk）M+ttij+ttj;

（i， j）∈Acij，i， j∈Vli，l∈L，i， j=1，2，…，U（11）

tdkj≤tdki+（1-xijk）M+ttd;

（i， j）∈Adij， i∈Vli， j∈Vdi， l∈L， i， j=1，2，…，U（12）

tdkj≤tdo+（1-xijk）M+ttj;

（i， j）∈Asij， l∈L， i， j=1，2，…，U（13）

tdki≥Tcmin-（1-xijk）M-ttd;

（i， j）∈Asij∪Adij， l∈L， i， j=1，2，…，U（14）

tdki≤Tcmax， i∈Vli， l∈L， i=1，2，…，U（15）

tokj≤toki+（1-xijk）M+ttj（16）

∪Nk=1Hk=H（17）

式（1）中：Zk為乘務(wù)交路時長，具體表達(dá)式為式（2）;δ為子乘務(wù)交路間乘務(wù)任務(wù)分配均衡性，具體表達(dá)式為式（3）。目標(biāo)函數(shù)式（1）旨在尋求可以使得乘務(wù)交路計劃總時長最小的同時盡量達(dá)到每條子乘務(wù)交路任務(wù)均衡的效果。其中ε為均衡因子，ε取較大的值時，表明總目標(biāo)受交路總時長的影響較大，此時每條乘務(wù)交路時長差異較大，均衡交路任務(wù)的效果不理想。在正常情況下，可以根據(jù)乘務(wù)基地在不同情境下的歷史乘務(wù)數(shù)據(jù)，得到相應(yīng)數(shù)值。在應(yīng)急條件下，ε可根據(jù)實(shí)際需求設(shè)定為無窮大值，這種情況下乘務(wù)交路間的均衡性不再成為重要約束因素，以此來保證救援乘務(wù)組能夠快速機(jī)動地到達(dá)事故地點(diǎn)。均衡因子與目標(biāo)函數(shù)的關(guān)系圖如圖4所示。式（4）為互異乘務(wù)區(qū)段接續(xù)空間約束，即為緊前乘務(wù)區(qū)段的到站與緊后乘務(wù)區(qū)段的發(fā)站必須是同一車站;式（5）表示所有劃分的乘務(wù)區(qū)段至少被覆蓋一次，若某些乘務(wù)區(qū)段超過一次，則認(rèn)為該乘務(wù)區(qū)段為乘務(wù)人員“便乘”;式（6）為節(jié)點(diǎn)處流平衡約束：表示對于每個乘務(wù)區(qū)段節(jié)點(diǎn)而言，僅有一條邊進(jìn)，一條邊出;式（7）描述交路閉合性約束，即乘務(wù)大區(qū)段的發(fā)站（到站）與到站（發(fā)站）必須是同一車站，且車站必須是乘務(wù)基地所在站（或乘務(wù)公寓所在站）;式（8）表示所有乘務(wù)大區(qū)段的起始弧必須是出乘弧;式（9）表示所有乘務(wù)大區(qū)段的終止弧必須是退乘弧;式（10）表示乘務(wù)大區(qū)段中的機(jī)車乘務(wù)人員出乘時長需滿足乘務(wù)規(guī)則約束;式（11）表示乘務(wù)大區(qū)段中乘務(wù)區(qū)段之間接續(xù)時長需滿足乘務(wù)規(guī)則約束;式（12）表示乘務(wù)大區(qū)段中的乘務(wù)人員退乘時長參數(shù)需滿足乘務(wù)規(guī)則;式（13）描述了乘務(wù)人員在乘務(wù)公寓駐班或調(diào)休后，乘務(wù)大區(qū)段累計時長需滿足乘務(wù)規(guī)則約束;式（14）、式（15）分別為乘務(wù)人員退乘或在乘務(wù)公寓駐班時，乘務(wù)大區(qū)段累計時長需滿足乘務(wù)規(guī)則;式（16）為乘務(wù)人員連續(xù)值乘累計時長需滿足的乘務(wù)規(guī)則;式（17）表示子乘務(wù)交路的集合需組成一個完整的乘務(wù)交路計劃。

2 雙重策略蟻群算法

顯然MTSP為NP-Hard問題，常用的解決方法包括分支定界法、線性規(guī)劃法、動態(tài)規(guī)劃法等。但是，隨著問題規(guī)模的增大，造成了組合爆炸的情況，精確算法難以求解，啟發(fā)式算法會體現(xiàn)出它特有的優(yōu)勢。對于基本蟻群算法，一次循環(huán)某一路徑走過的螞蟻越多，累積的信息素就越多，而未被走過路徑的信息素將減少，根據(jù)與信息素有關(guān)的轉(zhuǎn)移概率計算出下一步任意可供選擇轉(zhuǎn)移位置的轉(zhuǎn)移概率后，采用比例方式（輪盤賭）方式確定。由于信息素的差別過大，且具有揮發(fā)性，可能導(dǎo)致某些路徑被選擇的比例過大，陷入局部最優(yōu)解。同時初始路徑上信息素的水平一致，算法初期人工螞蟻的運(yùn)動軌跡具有較強(qiáng)的隨機(jī)性，雖然通過啟發(fā)性信息能夠向較優(yōu)路徑進(jìn)化，但當(dāng)求解問題規(guī)模較大時，不容易在短時間內(nèi)從大量路徑中找出較優(yōu)路徑，為了提高搜索效率，增加螞蟻搜索路徑的多樣性，本文提出了雙重信息素、雙重策略的改進(jìn)蟻群算法，對基于MTSP的乘務(wù)交路問題進(jìn)行求解。算法構(gòu)建步驟如下。

1）生成解構(gòu)建圖。

將經(jīng)切割運(yùn)行線后得到的乘務(wù)區(qū)段，按相應(yīng)的乘務(wù)規(guī)則組合成若干乘務(wù)大區(qū)段，令所有乘務(wù)大區(qū)段遍歷所有乘務(wù)區(qū)段。根據(jù)抽象的乘務(wù)交路MTSP，解構(gòu)建圖由所有表示乘務(wù)區(qū)段的節(jié)點(diǎn)和若干虛擬“原點(diǎn)”組成，其中“原點(diǎn)”是乘務(wù)大區(qū)段的起點(diǎn)和終點(diǎn)，若干“原點(diǎn)”實(shí)質(zhì)上是一個點(diǎn)經(jīng)過不斷復(fù)制得到的具有相同特性的離散點(diǎn)。

2）構(gòu)建解空間。

讓所有螞蟻從某“原點(diǎn)”出發(fā)，每個螞蟻按照某一概率選擇乘務(wù)大區(qū)段的初始節(jié)點(diǎn)，設(shè)定初始節(jié)點(diǎn)的始發(fā)車站為φc，φc=0表示始發(fā)車站是乘務(wù)基地所在車站;否則φc=1。螞蟻按照某一概率選擇待接續(xù)的節(jié)點(diǎn)，如果累計時長尚未達(dá)到乘務(wù)大區(qū)段的乘務(wù)時長標(biāo)準(zhǔn)，則繼續(xù)選擇待接續(xù)的節(jié)點(diǎn)，直到接續(xù)一系列的節(jié)點(diǎn)后返回該“原點(diǎn)”形成一個回路，即乘務(wù)大區(qū)段。設(shè)定乘務(wù)大區(qū)段的到站為φd，φd=0表示到站是乘務(wù)基地所在車站，否則φd=1。若乘務(wù)大區(qū)段滿足φc·φd=0 ，則表示得到了一個滿足時空約束的乘務(wù)大區(qū)段，否則螞蟻繼續(xù)搜索，直至使得乘務(wù)大區(qū)段滿足φc·φd=0。螞蟻重復(fù)該過程構(gòu)建解空間，當(dāng)所有節(jié)點(diǎn)都被乘務(wù)大區(qū)段遍歷時，算法完成了解構(gòu)建。

3）初始化及更新雙重信息素。

由于在解構(gòu)建圖中節(jié)點(diǎn)和路徑具有同等的重要性，故本文對節(jié)點(diǎn)和路徑都定義了信息素濃度。設(shè)定全部路徑上的信息素濃度為τij，全部節(jié)點(diǎn)上的信息素濃度為τi。τij表示螞蟻處在節(jié)點(diǎn)i時，接續(xù)節(jié)點(diǎn)j的重要程度。τi表示螞蟻處在“原點(diǎn)”時，選擇節(jié)點(diǎn)i作為下一個乘務(wù)大區(qū)段起始節(jié)點(diǎn)的重要程度。其中，路徑和節(jié)點(diǎn)的信息素初始濃度設(shè)定如下：

τij（0）=1A2-A， i≠j

0，其他（18）

τi（0）=1/A（19）

式（18）、式（19）中A表示互異乘務(wù)區(qū)段節(jié)點(diǎn)之間的接續(xù)頻數(shù)。

信息素濃度與各乘務(wù)節(jié)點(diǎn)和路徑是否參與了最優(yōu)解的構(gòu)建成正相關(guān)。在最優(yōu)螞蟻每次迭代后，各路徑和節(jié)點(diǎn)上信息素的更新取值設(shè)定如下：

τij（n+1）=ρτij（n）+Δτij（20）

τi（n+1）=ρτi（n）+Δτi（21）

Δτij=1/Zibest， eij∈sibest

0，其他 （22）

Δτi=1/Zibest， starti=1

0，其他（23）

式（20）、式（21）中ρ為信息素?fù)]發(fā)因子（0<ρ<1），n代表迭代次數(shù);式（22）、式（23）中Δτij、Δτi 分別為每次迭代過程中的信息素增量。starti為0-1變量，當(dāng)乘務(wù)區(qū)段的節(jié)點(diǎn)i在最優(yōu)解中出現(xiàn)作為某個乘務(wù)大區(qū)段的起點(diǎn)時1，否則取0。

螞蟻從“原點(diǎn)”出發(fā)，以τi的期望搜索到乘務(wù)區(qū)段節(jié)點(diǎn)i （即乘務(wù)大區(qū)段的起始節(jié)點(diǎn)），此時螞蟻以τij的期望繼續(xù)搜索到下一個乘務(wù)區(qū)段節(jié)點(diǎn)j，以此類推，根據(jù)某一概率選擇下一個乘務(wù)區(qū)段的節(jié)點(diǎn)，若其累計時長尚未達(dá)到乘務(wù)大區(qū)段的乘務(wù)時長標(biāo)準(zhǔn)，則繼續(xù)選擇下一個節(jié)點(diǎn)，直到接續(xù)一系列的乘務(wù)區(qū)段后返回該“原點(diǎn)”，形成一個回路，即乘務(wù)大區(qū)段。根據(jù)初始信息素濃度的設(shè)定（式（18）、式（19）），顯然τi（0）>τij（0）。通過設(shè)置雙重信息素全局更新策略，在每次迭代結(jié)束后，只允許全局最優(yōu)解釋放信息素。在最優(yōu)路徑上，螞蟻才釋放信息素，同時信息素才會揮發(fā)，這點(diǎn)非常重要，因?yàn)樵谛畔⑺馗聲r的時間復(fù)雜度從O（n2）降到了O（n），所以螞蟻可以在短時間內(nèi)從大量路徑中找出較優(yōu)路徑，提高螞蟻的搜索效率。

4）基于雙重策略狀態(tài)的轉(zhuǎn)移概率。

①當(dāng)?shù)趉只螞蟻所在的乘務(wù)區(qū)段節(jié)點(diǎn)i不是原點(diǎn)時，由節(jié)點(diǎn)i向下一個乘務(wù)區(qū)段節(jié)點(diǎn)j轉(zhuǎn)移的概率為：

Pkij=[τij]α·[ηij]β∑l∈Vli[τil]α·[ηil]β， j∈Vli

0，其他（24）

其中：ηij為預(yù)見度，表示從乘務(wù)區(qū)段節(jié)點(diǎn)i轉(zhuǎn)移到乘務(wù)區(qū)段節(jié)點(diǎn)j的預(yù)見程度。Vli表示螞蟻待訪問的節(jié)點(diǎn)集合，隨著迭代次數(shù)的增加，Vli中的元素不斷減少，直至為空，即表示所有乘務(wù)區(qū)段節(jié)點(diǎn)全部遍歷完畢。α表示殘留信息素的相對重要程度，其值越大，信息素的濃度在轉(zhuǎn)移中起的作用越大。 β為預(yù)見值的相對重要程度，其值越大，螞蟻以越大的概率轉(zhuǎn)移到接續(xù)時間較短的下一個乘務(wù)區(qū)段節(jié)點(diǎn)。其中預(yù)見度：

ηij=1ttij+（1-Eij）t1-Eijt2（25）

其中：ttij表示兩相鄰乘務(wù)區(qū)段接續(xù)弧的長度。Eij為0-1變量，Eij=1表示相接續(xù)的兩乘務(wù)區(qū)段同屬同一動車組交路，否則為0。t1為乘務(wù)人員換乘時間標(biāo)準(zhǔn)，t2為乘務(wù)人員在同車底上擔(dān)當(dāng)不同乘務(wù)區(qū)段的最小間隔時間。預(yù)見度越大，螞蟻所能搜尋到最鄰近的節(jié)點(diǎn)的概率越大，也就是說，兩相鄰乘務(wù)區(qū)段之間的接續(xù)時長越短，兩乘務(wù)區(qū)段接續(xù)的概率越大。

②當(dāng)?shù)趉只螞蟻位于原點(diǎn)時，選擇節(jié)點(diǎn)i作為下一個乘務(wù)大區(qū)段起點(diǎn)的概率為：

Pki=[τi]α·[ηi]β∑i∈Dl[τl]α·[ηl]β， Dl≠1

0，其他 （26）

其中：Dl為0-1變量，Dl=1時，表示乘務(wù)區(qū)段i被螞蟻選擇;否則，Dl=0。其中ηi為預(yù)見度，可由式（27）計算獲得：

ηi=tsurplus-teitsurplus-tdurationi+ρNnoN+1（27）

其中：tei表示乘務(wù)區(qū)段i的值乘結(jié)束時刻;tsurpius表示除乘務(wù)區(qū)段i外，其余乘務(wù)區(qū)段集合中最早結(jié)束值乘的乘務(wù)區(qū)段的結(jié)束時刻;tdurationi表示乘務(wù)區(qū)段i的值乘時長; ρ為可控參數(shù)，表示螞蟻能夠選擇到最快結(jié)束乘務(wù)區(qū)段的期望值;Nno表示在當(dāng)前階段，尚未被選入任何乘務(wù)大區(qū)段的乘務(wù)區(qū)段的數(shù)量，N表示乘務(wù)區(qū)段的數(shù)量。式（27）表明，隨著迭代次數(shù)的增加，在沒有被選擇的乘務(wù)區(qū)段集合中，能夠較早結(jié)束的乘務(wù)區(qū)段越容易被選為乘務(wù)大區(qū)段的起點(diǎn)。

設(shè)置雙重策略狀態(tài)的轉(zhuǎn)移概率主要目的在于提高算法的全局搜索能力，防止其收斂于局部最優(yōu)解，避免算法停滯或過早收斂。算法針對路徑選擇策略進(jìn)行了改進(jìn)，螞蟻從“原點(diǎn)”或“非原點(diǎn)”出發(fā)，根據(jù)相鄰乘務(wù)區(qū)段節(jié)點(diǎn)間的接續(xù)時間和接續(xù)狀態(tài)動態(tài)地調(diào)整啟發(fā)函數(shù)。當(dāng)螞蟻所在的乘務(wù)區(qū)段節(jié)點(diǎn)i不是原點(diǎn)時，螞蟻以轉(zhuǎn)移概率Pkij（式（24））接續(xù)下一個乘務(wù)區(qū)段節(jié)點(diǎn)j，乘務(wù)區(qū)段節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)越近則接續(xù)預(yù)見度ηij就越大。當(dāng)螞蟻所在的乘務(wù)區(qū)段節(jié)點(diǎn)i不是原點(diǎn)時，螞蟻以轉(zhuǎn)移概率Pki（式（26））接續(xù)下一個乘務(wù)區(qū)段節(jié)點(diǎn)i，能夠較早結(jié)束的乘務(wù)區(qū)段越容易被選為乘務(wù)大區(qū)段的起點(diǎn)，即接續(xù)預(yù)見度ηi越大。這樣， 使算法在降低問題復(fù)雜性的同時，減少了算法搜索的盲目性，有效引導(dǎo)算法朝全局最優(yōu)方向進(jìn)行搜索;同時增加了螞蟻搜索路徑的多樣性，又使得更新的路徑具有隨機(jī)性，能夠有效避免算法過早地陷入局部最優(yōu)，而進(jìn)入停滯狀態(tài)。

5）終止策略。

螞蟻經(jīng)過若干次搜索后，找到的解不再改變，且所有乘務(wù)區(qū)段都已經(jīng)被乘務(wù)交路所遍歷時，算法終止。本文算法具體實(shí)現(xiàn)流程如下所示：

步驟1 令nc ← 0，k ← 1，初始化α、 β、 ρ、螞蟻數(shù)量、最大迭代次數(shù)等參數(shù)。

步驟2 將m只螞蟻隨機(jī)地放置在原點(diǎn)，構(gòu)建一個n維向量Crew-section，n維向量Crew-section中的元素代表了所有的乘務(wù)區(qū)段，所有元素都為0-1變量。當(dāng)某一元素為0時，表示該元素對應(yīng)的乘務(wù)區(qū)段未被乘務(wù)大區(qū)段遍歷，否則為1。初始化向量Crew-section，令所有元素初態(tài)為0。

步驟3 螞蟻k以概率Pkj選擇下一個乘務(wù)大區(qū)段的起點(diǎn)，同時更新向量Crew-section，把被乘務(wù)交路遍歷過的乘務(wù)區(qū)段所對應(yīng)元素取值為1。判斷向量Crew-section中的所有元素是否為1。若是，則令k ← k+1，若k>m則跳轉(zhuǎn)至步驟6;否則重復(fù)步驟3。對于螞蟻k，若Crew-section向量中仍有0元素，則進(jìn)行下步。

步驟4 螞蟻k以概率Pkj為節(jié)點(diǎn)i向下一個乘務(wù)區(qū)段節(jié)點(diǎn)j轉(zhuǎn)移。同時更新向量Crew-section，把被乘務(wù)交路遍歷過的乘務(wù)區(qū)段所對應(yīng)的元素取值為1。判斷Crew-section向量中的所有元素是否為1，若是，則令k ← k+1，若k>m則跳轉(zhuǎn)至步驟6，否則重復(fù)步驟3。對于螞蟻k，若Crew-section向量中仍有0元素，則進(jìn)行下一步。

步驟5 若接續(xù)乘務(wù)區(qū)段的累計工作時長已達(dá)到乘務(wù)大區(qū)段的工作時間標(biāo)準(zhǔn)，則完成一個乘務(wù)大區(qū)段的構(gòu)建，返回原點(diǎn)，跳轉(zhuǎn)至步驟3;若累計工作時間標(biāo)準(zhǔn)還沒有達(dá)到乘務(wù)大區(qū)段的時間標(biāo)準(zhǔn)，而連續(xù)工作時長已達(dá)上限，則調(diào)整乘務(wù)區(qū)段之間的接續(xù)時間標(biāo)準(zhǔn)，給乘務(wù)人員（組）增加調(diào)休時間，并返回步驟4;否則直接返回步驟4。

步驟6 當(dāng)向量Crew-section中的所有元素返回值為1時，m個螞蟻已經(jīng)生成了可行的乘務(wù)大區(qū)段回路。計算生成的乘務(wù)大區(qū)段的數(shù)量，并確定此次迭代產(chǎn)生最優(yōu)解的螞蟻。

步驟7 根據(jù)式（20）和式（21）更新解構(gòu)建圖中所有路徑和乘務(wù)區(qū)段節(jié)點(diǎn)上的信息素濃度。

步驟8 令nc ← nc+1，如果nc小于步驟1中指定的最大迭代次數(shù)，更新向量Crew-section，轉(zhuǎn)至步驟2;否則，終止計算，輸出當(dāng)前最優(yōu)解。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文理論研究和算法的有效性，選取廣深線上城際列車數(shù)據(jù)進(jìn)行驗(yàn)證。廣深線起點(diǎn)廣州站，終點(diǎn)深圳站，全長147km，途經(jīng)廣州、廣州東、東莞、常平、樟木頭、平湖、深圳7個車站，并辦理客運(yùn)營業(yè)業(yè)務(wù)，周內(nèi)每日開行73趟列車，周末每日開行95趟列車。動車組的檢修基地設(shè)置在廣州東站接軌的石牌動車檢修所。乘務(wù)基地設(shè)置在廣州東站，深圳站設(shè)乘務(wù)人員公寓，供在深圳駐班或調(diào)休的乘務(wù)班組休息。線路示意圖如圖1所示。

廣深線乘務(wù)運(yùn)用情況說明：機(jī)務(wù)乘務(wù)組應(yīng)遵循早出乘早下班、晚出乘外下班的出乘原則。所有乘務(wù)組在乘務(wù)基地進(jìn)行出退乘作業(yè)，廣州東廣州乘務(wù)值乘方式為雙班單司機(jī)，廣州東深圳乘務(wù)值乘方式為單班單司機(jī)。廣深線乘務(wù)人員值乘方式如圖2所示。

現(xiàn)以廣深線6：00—24：00的城際列車開行方案數(shù)據(jù)為例。其中，有18對列車為廣州至深圳直達(dá)列車，57對列車為廣州東至深圳直達(dá)列車，以廣州東站為乘務(wù)基地，以深圳為換乘站，將廣深線城際列車開行方案數(shù)據(jù)劃分為150個乘務(wù)區(qū)段，如表2所示。

3.2 算例結(jié)果

根據(jù)上文所述乘務(wù)規(guī)則約束，輸入乘務(wù)交路時間相關(guān)的參數(shù)，實(shí)驗(yàn)參數(shù)可根據(jù)現(xiàn)場具體車站的乘務(wù)規(guī)則作出相應(yīng)調(diào)整。根據(jù)廣深線調(diào)研數(shù)據(jù)可得，乘務(wù)交路相關(guān)時間參數(shù)設(shè)置為：乘務(wù)交路長度不超過2880min，換乘時間不少于12min，間休時間不少于為40min，連續(xù)值乘時間不超過300min，出乘時間60min，退乘時間20min。正整數(shù)M的取值為2880， ε取值為1（在正常情況下，根據(jù)乘務(wù)基地廣州東的歷史乘務(wù)數(shù)據(jù)，查定得到的數(shù)值）。運(yùn)用本文設(shè)計的改進(jìn)蟻群算法進(jìn)行求解，其中：信息素重要程度因子α=2，啟發(fā)式信息素重要程度因子為5，信息素?fù)]發(fā)因子取0.2，螞蟻個數(shù)取40，設(shè)迭代次數(shù)為300次。并運(yùn)用Matlab R2015b進(jìn)行求解，在Intel core i7-8550U CPU 1.8GHz，內(nèi)存8GB的計算機(jī)上迭代到92次時，目標(biāo)函數(shù)值已趨于穩(wěn)定且達(dá)到最小，此時目標(biāo)函數(shù)值為18452.71523min，迭代過程如圖3所示。共得到36條乘務(wù)大區(qū)段，如表3所示。得到18條子乘務(wù)交路，如表4所示。子乘務(wù)交路累計工作時長與平均時長關(guān)系如圖4所示，由圖4可看出子乘務(wù)交路間任務(wù)量較均衡。根據(jù)優(yōu)化結(jié)果，可以看出乘務(wù)大區(qū)段有三種類型：①廣州東（廣州）廣州東，乘務(wù)大區(qū)段個數(shù)為18，占比50%;②廣州東深圳，乘務(wù)大區(qū)段個數(shù)有9，占比25%;③深圳廣州東，乘務(wù)大區(qū)段個數(shù)為9，占比25%。

3.3 實(shí)驗(yàn)結(jié)果評價分析

利用設(shè)計了乘務(wù)交路時間較少、子乘務(wù)交路間乘務(wù)任務(wù)均衡為目標(biāo)的優(yōu)化模型和雙重策略蟻群算法，編制了廣深線

乘務(wù)交路計劃，計算結(jié)果的指標(biāo)分析如表5所示。結(jié)論如下：

1）根據(jù)本文設(shè)計的基于雙重策略的蟻群算法，得到了18條乘務(wù)交路。乘務(wù)人員執(zhí)行完一條乘務(wù)交路需要兩天時間。若乘務(wù)人員第一個工作日內(nèi)早晨6點(diǎn)出乘，那么該乘務(wù)人員值乘當(dāng)日最后一列車不超過14點(diǎn)，即早出乘，早退乘。

比如C7023次列車從廣州6：00始發(fā)，值乘這次列車的乘務(wù)人員就需要5：00從廣州東整備出勤，到中午12：41值乘完當(dāng)天最后一列車退乘休息。充分保證了乘務(wù)人員的休息時間，使乘務(wù)人員有更多的時間學(xué)習(xí)業(yè)務(wù)知識，也利于照顧家人，大大提升了乘務(wù)人員的生活幸福指數(shù)。

2）從編制的18條乘務(wù)交路計劃中可看出，沒有發(fā)生超勞的情況，乘務(wù)人員單日最大值乘5列，并且在連續(xù)值乘4列后，乘務(wù)人員都有不少于40min的間休時間，使乘務(wù)人員有更充沛的精力值乘后續(xù)列車，有效地保障了列車運(yùn)行安全。

3）在本文編制的乘務(wù)交路計劃中，充分考慮到人性化因素。比如每天有9對車底在深圳過夜，即每天必須有9個乘務(wù)組需要在深圳公寓休息。這9個乘務(wù)組都是從15：00以后出乘，即晚出乘，外下班。比如C7129次列車從廣州東18：11始發(fā)，直到乘務(wù)人員值乘完C7121最后一列車，在深圳站23：53退乘，乘務(wù)人員當(dāng)晚在深圳公寓駐班休息。第二個工作日內(nèi)，該乘務(wù)人員經(jīng)過充分休息在12：18值乘C7038次列車從深圳始發(fā)，20：37值乘C7020從廣州東退乘。對于乘務(wù)人員來說，每值乘一條乘務(wù)交路都有充足的休息時間，體現(xiàn)了乘務(wù)交路編制過程中的人性化標(biāo)準(zhǔn)。

4）設(shè)計的目標(biāo)函數(shù)既考慮了乘務(wù)交路總時長，又考慮了各子乘務(wù)交路之間的均衡性。如果某車站發(fā)生突發(fā)事件，比如深圳市某日要舉辦大型國際會展，客流激增的情況下，交路間的均衡性不再成為乘務(wù)交路編制的關(guān)鍵限制因素，此時重點(diǎn)考慮交路時長問題。根據(jù)乘務(wù)基地廣州東的歷史乘務(wù)數(shù)據(jù)，查定得到均衡因子取不同數(shù)值時目標(biāo)函數(shù)值的變化，突發(fā)事件條件下，可根據(jù)乘務(wù)交路時長與均衡因子關(guān)系圖（如圖5）對均衡因子進(jìn)行調(diào)整，Pkijε可根據(jù)實(shí)際需求設(shè)定相應(yīng)較大的數(shù)值（如圖5），這種情況下乘務(wù)交路間的均衡性不再成為重要約束因素，以此來保證救援乘務(wù)組能夠快速機(jī)動地到達(dá)事故地點(diǎn)。

3.4 算法對比分析

多數(shù)學(xué)者在求解乘務(wù)計劃問題時多采用遺傳算法，因此，本文以遺傳算法作為對比算法。在同一臺計算機(jī)上運(yùn)用Matlab R2015b求解，均衡因子取值與上相同，經(jīng)過203次迭代后，結(jié)果趨于穩(wěn)定，運(yùn)行結(jié)果為19580.23793min。通過對比分析得，本文設(shè)計的改進(jìn)蟻群算法與遺傳算法相比，能夠更快地收斂，解的質(zhì)量也有大幅提升。其中，乘務(wù)交路減少了約21.74%、乘務(wù)總時長降低了5.76%、交路超勞率為0。兩種算法對比結(jié)果如表6所示。

4 結(jié)語

1）本文建立了總交路時間最小且各子乘務(wù)交路間任務(wù)均衡的MTSP模型，引入了均衡因子這一概念，使得模型更具備實(shí)際意義，在突發(fā)事件發(fā)生后更容易調(diào)整乘務(wù)交路計劃。同時提出了一種雙重策略狀態(tài)轉(zhuǎn)移的蟻群算法，其特點(diǎn)在于設(shè)計了雙重信息素、雙重策略，提高算法搜索效率的同時避免了傳統(tǒng)蟻群算法易陷入局部最優(yōu)的缺點(diǎn)。

2）通過改進(jìn)后的蟻群算法與遺傳算法相比，得出了本文設(shè)計的改進(jìn)蟻群算法效率更高、解質(zhì)量更好，對該問題求解有很強(qiáng)的適應(yīng)性。

3）該模型及算法可為鐵路機(jī)務(wù)部門編制機(jī)車乘務(wù)人員乘務(wù)交路計劃提供有價值的決策支持，對增強(qiáng)鐵路機(jī)務(wù)系統(tǒng)應(yīng)急處置能力具有實(shí)際意義和幫助，可作為鐵路系統(tǒng)應(yīng)急處置決策理論的組成部分。

參考文獻(xiàn)

[1]BEASLEY J E， CAO B. A tree search algorithm for the crew scheduling problem [J]. European Journal of Operational Research， 1996， 94（3）： 517-526.

[2]CHU S C K. Generating， scheduling and rostering of shift crew-duties， applications at the Hong Kong International Airport [J]. European Journal of Operational Research， 2007， 177（3）： 1764-1778.

[3]DENNIS HUISMAN. A column generation approach for the rail crew re-scheduling problem [J]. European Journal of Operational Research， 2007， 180（1）： 163-173.

[4]GAMACHE M， HERTZ A， OUELLET J O. A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding [J]. Computers and Operations Research， 2007， 34（8）： 2384-2395.

[5]陳海平.高速鐵路乘務(wù)組織理論與優(yōu)化研究[D].北京：北京交通大學(xué)，2013：42-61.（CHEN H P. Research on theory and optimization of crew organization of high-speed railway [D]. Beijing： Beijing Jiaotong University， 2013： 42-61.）

[6]趙鵬，胡安洲，楊浩.機(jī)車乘務(wù)人員運(yùn)用計劃的優(yōu)化編制[J].鐵道學(xué)報，1998，20（4）：8-13.（ZHAO P， HU A Z， YANG H. Research on optimization of crew scheduling [J]. Journal of the China Railway Society， 1998， 20（4）： 8-13.）

[7]閻永光，黃斌.廣深線城際列車乘務(wù)組排班計劃編制方法探討[J].交通運(yùn)輸工程與信息學(xué)報，2010，8（1）：25-29.（YAN Y G， HUANG B. Research on the crew schedule programming method of Guangzhou-Shenzhen intercity trains [J]. Journal of Transportation Engineering and Information， 2010， 8（1）： 25-29.）

[8]程巖巖.我國鐵路乘務(wù)調(diào)度計劃編制方法的研究與設(shè)計[D].北京：北京交通大學(xué)，2007：21-30.（CHENG Y Y. Research and design of domestic railway crew scheduling method [D]. Beijing： Beijing Jiaotong University， 2007： 21-30.）

[9]王瑩，劉軍，苗建瑞.客運(yùn)專線乘務(wù)交路計劃編制的優(yōu)化模型與算法[J].鐵道學(xué)報，2009，31（1）：15-19.（WANG Y， LIU J， MIAO J R. Modeling and solving the crew scheduling problem of passenger dedicated line [J]. Journal of the China Railway Society， 2009， 31（1）： 15-19.）

[10]王媛媛，周成晨，倪少權(quán).基于蟻群算法的客運(yùn)專線乘務(wù)交路計劃編制方法研究[J].鐵路計算機(jī)應(yīng)用，2009，18（7）：11-14.（WANG Y Y， ZHOU C C， NI S Q. Study on algorithm of crew routing scheduling for passenger dedicated line based on ant colony optimization[J]. Railway Computer Application， 2009， 18（7）： 11-14.）

[11]黃珊.機(jī)車乘務(wù)人員運(yùn)用問題及其輔助編排系統(tǒng)研究[D].長沙：中南大學(xué)，2014：30-44.（HUANG S. Locomotive crew scheduling problem and scheduling assistant system [D]. Changsha： Central South University， 2014： 30-44.）

[12]田志強(qiáng).高速鐵路乘務(wù)計劃編制優(yōu)化理論與方法研究[D].成都：西南交通大學(xué)，2011：45-72.（TIAN Z Q. Study on theory and methods of crew planning problem of high-speed railway[D]. Chengdu： Southwest Jiaotong University， 2011： 45-72.）

[13]陳旭，李海鷹，王瑩，等.放射狀路網(wǎng)條件下動車組運(yùn)用優(yōu)化研究[J].鐵道學(xué)報，2017，39（11）：1-7.（CHEN X， LI H Y， WANG Y， et al. Research on optimization of EMU scheduling for radial HSR network [J]. Journal of the China Railway Society， 2017， 39（11）： 1-7.）

[14]郭璞.鐵路客運(yùn)機(jī)車乘務(wù)交路編制問題研究[D].長沙：中南大學(xué)，2013：24-32.（GUO P. Railway passenger train crew scheduling problem [D]. Changsha： Central South University， 2013： 24-32.）

[15]銀大偉.乘務(wù)計劃編制系統(tǒng)的研究與設(shè)計[D].成都：西南交通大學(xué)，2008：30-41.（YIN D W. Research and design of crew scheduling system [D]. Chengdu： Southwest Jiaotong University， 2008： 30-41.）

[16]張哲銘，王瑩，陳旭，等.高速鐵路單一循環(huán)乘務(wù)值乘計劃優(yōu)化研究[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2018，40（1）：21-27.（ZHANG Z M， WANG Y， CHEN X， et al. Research on single-circulation crew rostering plan optimization for high-speed railway [J]. Railway Transport and Economy， 2018， 40（1）： 21-27.）

[17]馬良，朱剛，寧愛兵.蟻群優(yōu)化算法[M].北京：科學(xué)出版社，2008：57-73.（MA L， ZHU G， NING A B. Ant Colony Optimization Algorithm [M]. Beijing： Science Press， 2008： 57-73.）

[18]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，2005：212-232.（DUAN H B. Ant Colony Algorithms： Theory and Applications [M]. Beijing： Science Press， 2005： 212-232.）

This work is partially supported by the National Key Research and Development Project of China （2016YFB1200100）， the National Natural Science Foundation of China （71861022， 61563028）.

WANG Dongxian， born in 1992，M.S. candidate. His research interests include operation management and decision optimization of rail transit.

MENG Xuelei， bon in 1979，Ph.D.，professor.His research interests include operation management and decision ayoptimization of rail transit.

QIAO Jun， born in 1993，M.S. candidate. Her research interests include operation management and decision optimization of rail transit.

TANG Lin， born in 1989，M.S. His research interests include operation management and dcision optimization of rail transit.

JIAO Zhizhen， born in 1992， assistant engineer. His research interests include organization and optimization of railway traffic， organization of cargo transportation.