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

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

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

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

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

2）空間接續(xù)乘務(wù)規(guī)則。相鄰的兩乘務(wù)區(qū)段必須要滿足空間接續(xù)性，即前一個(gè)乘務(wù)區(qū)段的到站必須是后一個(gè)乘務(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ù)就可以看作是城市與城市之間的距離，由于每個(gè)子乘務(wù)交路都需一個(gè)乘務(wù)組值乘，故子乘務(wù)交路的個(gè)數(shù)就是所需乘務(wù)人員（組）的個(gè)數(shù)，即旅行商數(shù)目。設(shè)有N個(gè)子乘務(wù)交路，則N個(gè)子乘務(wù)交路從列車運(yùn)行圖過表時(shí)刻（默認(rèn)列車運(yùn)行圖過表時(shí)刻為18：00）開始，各子乘務(wù)交路有且僅有一個(gè)乘務(wù)組訪問，最后回到過表時(shí)刻，形成封閉回路。結(jié)合列車運(yùn)營特點(diǎn)，乘務(wù)交路計(jì)劃編制問題可以抽象為單基地、均衡行駛路程的MTSP。

將所有乘務(wù)區(qū)段抽象為點(diǎn)集V，所有的乘務(wù)區(qū)段之間的接續(xù)關(guān)系抽為成邊A，簡化后的乘務(wù)交路區(qū)段可視為有向圖G，即建立具有U個(gè)節(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。模型中的符號(hào)定義如表1所示。

定義1 S={si/si=0，si=1，si=2}（i=1，2，…，U）為列車運(yùn)行圖中的車站集合，令Wsi為第i個(gè)車站的屬性，則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ù)交路計(jì)劃編制問題目標(biāo)函數(shù)包含兩部分：1）乘務(wù)交路總時(shí)長最少;2）使子乘務(wù)交路之間的乘務(wù)時(shí)間相差最小。通過引入均衡因子將兩部分目標(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ù)交路時(shí)長，具體表達(dá)式為式（2）;δ為子乘務(wù)交路間乘務(wù)任務(wù)分配均衡性，具體表達(dá)式為式（3）。目標(biāo)函數(shù)式（1）旨在尋求可以使得乘務(wù)交路計(jì)劃總時(shí)長最小的同時(shí)盡量達(dá)到每條子乘務(wù)交路任務(wù)均衡的效果。其中ε為均衡因子，ε取較大的值時(shí)，表明總目標(biāo)受交路總時(shí)長的影響較大，此時(shí)每條乘務(wù)交路時(shí)長差異較大，均衡交路任務(wù)的效果不理想。在正常情況下，可以根據(jù)乘務(wù)基地在不同情境下的歷史乘務(wù)數(shù)據(jù)，得到相應(yīng)數(shù)值。在應(yīng)急條件下，ε可根據(jù)實(shí)際需求設(shè)定為無窮大值，這種情況下乘務(wù)交路間的均衡性不再成為重要約束因素，以此來保證救援乘務(wù)組能夠快速機(jī)動(dòng)地到達(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)處流平衡約束：表示對(duì)于每個(gè)乘務(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ù)人員出乘時(shí)長需滿足乘務(wù)規(guī)則約束;式（11）表示乘務(wù)大區(qū)段中乘務(wù)區(qū)段之間接續(xù)時(shí)長需滿足乘務(wù)規(guī)則約束;式（12）表示乘務(wù)大區(qū)段中的乘務(wù)人員退乘時(shí)長參數(shù)需滿足乘務(wù)規(guī)則;式（13）描述了乘務(wù)人員在乘務(wù)公寓駐班或調(diào)休后，乘務(wù)大區(qū)段累計(jì)時(shí)長需滿足乘務(wù)規(guī)則約束;式（14）、式（15）分別為乘務(wù)人員退乘或在乘務(wù)公寓駐班時(shí)，乘務(wù)大區(qū)段累計(jì)時(shí)長需滿足乘務(wù)規(guī)則;式（16）為乘務(wù)人員連續(xù)值乘累計(jì)時(shí)長需滿足的乘務(wù)規(guī)則;式（17）表示子乘務(wù)交路的集合需組成一個(gè)完整的乘務(wù)交路計(jì)劃。

2 雙重策略蟻群算法

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

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

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

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

由于在解構(gòu)建圖中節(jié)點(diǎn)和路徑具有同等的重要性，故本文對(duì)節(jié)點(diǎn)和路徑都定義了信息素濃度。設(shè)定全部路徑上的信息素濃度為τij，全部節(jié)點(diǎn)上的信息素濃度為τi。τij表示螞蟻處在節(jié)點(diǎn)i時(shí)，接續(xù)節(jié)點(diǎn)j的重要程度。τi表示螞蟻處在“原點(diǎn)”時(shí)，選擇節(jié)點(diǎn)i作為下一個(gè)乘務(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)作為某個(gè)乘務(wù)大區(qū)段的起點(diǎn)時(shí)1，否則取0。

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

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

①當(dāng)?shù)趉只螞蟻所在的乘務(wù)區(qū)段節(jié)點(diǎn)i不是原點(diǎn)時(shí)，由節(jié)點(diǎn)i向下一個(gè)乘務(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)全部遍歷完畢。α表示殘留信息素的相對(duì)重要程度，其值越大，信息素的濃度在轉(zhuǎn)移中起的作用越大。 β為預(yù)見值的相對(duì)重要程度，其值越大，螞蟻以越大的概率轉(zhuǎn)移到接續(xù)時(shí)間較短的下一個(gè)乘務(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ū)段同屬同一動(dòng)車組交路，否則為0。t1為乘務(wù)人員換乘時(shí)間標(biāo)準(zhǔn)，t2為乘務(wù)人員在同車底上擔(dān)當(dāng)不同乘務(wù)區(qū)段的最小間隔時(shí)間。預(yù)見度越大，螞蟻所能搜尋到最鄰近的節(jié)點(diǎn)的概率越大，也就是說，兩相鄰乘務(wù)區(qū)段之間的接續(xù)時(shí)長越短，兩乘務(wù)區(qū)段接續(xù)的概率越大。

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

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

0，其他 （26）

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

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

其中：tei表示乘務(wù)區(qū)段i的值乘結(jié)束時(shí)刻;tsurpius表示除乘務(wù)區(qū)段i外，其余乘務(wù)區(qū)段集合中最早結(jié)束值乘的乘務(wù)區(qū)段的結(jié)束時(shí)刻;tdurationi表示乘務(wù)區(qū)段i的值乘時(shí)長; ρ為可控參數(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)解，避免算法停滯或過早收斂。算法針對(duì)路徑選擇策略進(jìn)行了改進(jìn)，螞蟻從“原點(diǎn)”或“非原點(diǎn)”出發(fā)，根據(jù)相鄰乘務(wù)區(qū)段節(jié)點(diǎn)間的接續(xù)時(shí)間和接續(xù)狀態(tài)動(dòng)態(tài)地調(diào)整啟發(fā)函數(shù)。當(dāng)螞蟻所在的乘務(wù)區(qū)段節(jié)點(diǎn)i不是原點(diǎn)時(shí)，螞蟻以轉(zhuǎn)移概率Pkij（式（24））接續(xù)下一個(gè)乘務(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)時(shí)，螞蟻以轉(zhuǎn)移概率Pki（式（26））接續(xù)下一個(gè)乘務(wù)區(qū)段節(jié)點(diǎn)i，能夠較早結(jié)束的乘務(wù)區(qū)段越容易被選為乘務(wù)大區(qū)段的起點(diǎn)，即接續(xù)預(yù)見度ηi越大。這樣， 使算法在降低問題復(fù)雜性的同時(shí)，減少了算法搜索的盲目性，有效引導(dǎo)算法朝全局最優(yōu)方向進(jìn)行搜索;同時(shí)增加了螞蟻搜索路徑的多樣性，又使得更新的路徑具有隨機(jī)性，能夠有效避免算法過早地陷入局部最優(yōu)，而進(jìn)入停滯狀態(tài)。

5）終止策略。

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

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

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

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

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

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

步驟6 當(dāng)向量Crew-section中的所有元素返回值為1時(shí)，m個(gè)螞蟻已經(jīng)生成了可行的乘務(wù)大區(qū)段回路。計(jì)算生成的乘務(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;否則，終止計(jì)算，輸出當(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個(gè)車站，并辦理客運(yùn)營業(yè)業(yè)務(wù)，周內(nèi)每日開行73趟列車，周末每日開行95趟列車。動(dòng)車組的檢修基地設(shè)置在廣州東站接軌的石牌動(dòng)車檢修所。乘務(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對(duì)列車為廣州至深圳直達(dá)列車，57對(duì)列車為廣州東至深圳直達(dá)列車，以廣州東站為乘務(wù)基地，以深圳為換乘站，將廣深線城際列車開行方案數(shù)據(jù)劃分為150個(gè)乘務(wù)區(qū)段，如表2所示。

3.2 算例結(jié)果

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

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

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

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

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

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

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

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

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

3.4 算法對(duì)比分析

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

4 結(jié)語

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

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

3）該模型及算法可為鐵路機(jī)務(wù)部門編制機(jī)車乘務(wù)人員乘務(wù)交路計(jì)劃提供有價(jià)值的決策支持，對(duì)增強(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)用計(jì)劃的優(yōu)化編制[J].鐵道學(xué)報(bào)，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ì)劃編制方法探討[J].交通運(yùn)輸工程與信息學(xué)報(bào)，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)度計(jì)劃編制方法的研究與設(shè)計(jì)[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ù)交路計(jì)劃編制的優(yōu)化模型與算法[J].鐵道學(xué)報(bào)，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].鐵路計(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ù)計(jì)劃編制優(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)條件下動(dòng)車組運(yùn)用優(yōu)化研究[J].鐵道學(xué)報(bào)，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ù)計(jì)劃編制系統(tǒng)的研究與設(shè)計(jì)[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ù)值乘計(jì)劃優(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.