王東先　孟學(xué)雷　何國(guó)強(qiáng)　孫慧萍　王喜棟

摘 要：為了提升鐵路乘務(wù)排班計(jì)劃編制的質(zhì)量和效率，將乘務(wù)排班計(jì)劃編制問(wèn)題抽象為單基地、考慮中途休息的多旅行商問(wèn)題（MTSP），建立以排班周期最小、乘務(wù)交路間冗余接續(xù)時(shí)間分布最均衡為優(yōu)化目標(biāo)的單一循環(huán)乘務(wù)排班計(jì)劃數(shù)學(xué)模型，并針對(duì)該模型提出了一種啟發(fā)式修正蟻群算法。首先，構(gòu)建滿足時(shí)空約束的解空間，分別對(duì)乘務(wù)交路節(jié)點(diǎn)和接續(xù)路徑設(shè)置信息素濃度;然后，確定基于修正的啟發(fā)式信息，規(guī)定螞蟻按乘務(wù)交路順序依次出發(fā)，使螞蟻遍歷所有乘務(wù)交路;最后，從不同的乘務(wù)排班方案中選擇最優(yōu)的排班計(jì)劃。以廣深城際鐵路為例對(duì)所提模型及算法進(jìn)行驗(yàn)證，并與粒子群算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明：在相同的模型條件下，采用啟發(fā)式修正蟻群算法編制的乘務(wù)排班計(jì)劃平均月工時(shí)降低了8.5%，排班周期降低了9.4%，乘務(wù)人員超勞率為0。所提模型和算法能夠壓縮乘務(wù)排班周期，降低乘務(wù)成本，均衡工作量，避免乘務(wù)人員超勞。

關(guān)鍵詞：鐵路;乘務(wù)排班計(jì)劃;多旅行商問(wèn)題;冗余時(shí)間;啟發(fā)式修正蟻群算法

中圖分類號(hào)： TP301.6（算法理論）;U292.4（列車運(yùn)行組織及調(diào)度工作） 文獻(xiàn)標(biāo)志碼：A

Railway crew rostering plan based on improved ant colony optimization algorithm

WANG Dongxian1， MENG Xuelei1*， HE Guoqiang1， SUN Huiping1， WANG Xidong2

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

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

Abstract： In order to improve the quality and efficiency of railway crew rostering plan arrangement， the problem of crew rostering plan arrangement was abstracted as a Multi-Traveling Salesman Problem （MTSP） with single base and considering mid-way rest， a single-circulation crew rostering plan mathematical model aiming at the smallest rostering period and the most balanced distributed redundant connection time between crew routings was established， and a new amended heuristic ant colony optimization algorithm was proposed aiming at the model. Firstly， a solution space satisfying the spatial-temporal constraints was constructed and the pheromone concentration was set for the crew routing nodes and the continued paths respectively. Then， the amended heuristic information was adopted to make the ants start at the crew routing order and go through all the crew routings. Finally， the optimal crew rostering plan was selected from the different crew rostering schemes. The proposed model and algorithm were tested on the data of the intercity railway from Guangzhou to Shenzhen. The comparison results with the plan arranged by particle swarm optimization show that under the same model conditions， the crew rostering plan arranged by amended heuristic ant colony optimization algorithm has the average monthly man-hour reduced by 8.5%， the rostering period decreased by 9.4%， and the crew overwork rate of 0. The designed model and algorithm can compress the crew rostering cycle， reduce the crew cost， balance the workload， and avoid the overwork of crew.

Key words： railway; crew rostering plan; Multi-Traveling Salesman Problem （MTSP）; redundant time; amended heuristic ant colony optimization algorithm

0 引言

乘務(wù)排班計(jì)劃是乘務(wù)計(jì)劃的一部分，是以列車運(yùn)行圖、乘務(wù)交路、相關(guān)乘務(wù)規(guī)則、車站設(shè)備條件為基本依據(jù)編制的乘務(wù)人員（司乘）工作計(jì)劃。其中，列車運(yùn)行圖包含了待完成的乘務(wù)任務(wù)，乘務(wù)交路規(guī)定了乘務(wù)人員擔(dān)當(dāng)運(yùn)輸任務(wù)的固定周轉(zhuǎn)區(qū)段，乘務(wù)規(guī)則限定了乘務(wù)人員的工作時(shí)間，車站設(shè)備條件限制了車站是否是乘務(wù)基地及具備司乘人員換乘或休息的條件。

為了合理優(yōu)化乘務(wù)計(jì)劃編制，有效提升編制效率，乘務(wù)計(jì)劃的編制分為兩個(gè)階段：乘務(wù)交路計(jì)劃、乘務(wù)排班計(jì)劃。乘務(wù)交路計(jì)劃和乘務(wù)排班計(jì)劃既有聯(lián)系又有區(qū)別，兩者相輔相成，兩者既遵循一定的共性乘務(wù)規(guī)則，同時(shí)又具有自身的獨(dú)特特點(diǎn)。通過(guò)乘務(wù)交路計(jì)劃得到乘務(wù)交路，利用乘務(wù)交路編制乘務(wù)排班計(jì)劃。乘務(wù)排班計(jì)劃編制的優(yōu)劣直接決定了鐵路機(jī)務(wù)部門(mén)的運(yùn)營(yíng)效率及機(jī)務(wù)人員的勞動(dòng)強(qiáng)度。本文針對(duì)乘務(wù)排班計(jì)劃編制問(wèn)題作出進(jìn)一步討論。文獻(xiàn)[1]將乘務(wù)人員排班計(jì)劃和飛機(jī)排班計(jì)劃綜合考慮，建立了動(dòng)態(tài)規(guī)劃模型，具有更好的魯棒性，但是該模型對(duì)于求解“點(diǎn)多線長(zhǎng)”的鐵路乘務(wù)計(jì)劃具有一定局限性。文獻(xiàn)[2]將改進(jìn)的遺傳算法應(yīng)用于乘務(wù)排班計(jì)劃的綜合優(yōu)化問(wèn)題，雖然編制效率顯著提高，但該模型和算法得到的排班計(jì)劃超勞率偏高。文獻(xiàn)[3]將乘務(wù)排班計(jì)劃編制劃分為兩階段問(wèn)題，并用分支定界法進(jìn)行了求解。文獻(xiàn)[4]建立整數(shù)規(guī)劃模型，運(yùn)用拉格朗日松弛和列生成的組合優(yōu)化算法，對(duì)應(yīng)急條件下擾動(dòng)時(shí)間不確定的乘務(wù)排班計(jì)劃問(wèn)題進(jìn)行研究，但該模型沒(méi)有考慮乘務(wù)人員工作量的均衡性。文獻(xiàn)[5]重點(diǎn)研究了工作效率對(duì)于乘務(wù)計(jì)劃編制的影響，采用蟻群算法進(jìn)行求解，但未考慮乘務(wù)交路的均衡性。文獻(xiàn)[6]利用雙重策略蟻群算法編制了乘務(wù)交路計(jì)劃，但是對(duì)乘務(wù)排班計(jì)劃的編制沒(méi)有作進(jìn)一步研究。文獻(xiàn)[7]利用SE（Simulated Evolution）方法編制乘務(wù)排班計(jì)劃，但是對(duì)乘務(wù)交路計(jì)劃的編制沒(méi)有深入研究。文獻(xiàn)[8]首次在國(guó)內(nèi)將列生成技術(shù)應(yīng)用到了乘務(wù)排班計(jì)劃的編制，并把乘務(wù)排班計(jì)劃問(wèn)題抽象成了旅行商問(wèn)題，但是該算法在求解初始可行解時(shí)效率較低。文獻(xiàn)[9]將乘務(wù)排班計(jì)劃問(wèn)題抽象為網(wǎng)絡(luò)流模型，并利用拉格朗日松弛算法進(jìn)行求解，但是該算法的迭代步長(zhǎng)由經(jīng)驗(yàn)公式自行設(shè)定，缺乏論證。文獻(xiàn)[10]將高速鐵路乘務(wù)排班計(jì)劃的編制轉(zhuǎn)化為特殊的旅行商問(wèn)題，并采用改進(jìn)的蟻群算法進(jìn)行求解，該模型雖然能夠有效提高編制效率，但模型中沒(méi)有考慮乘務(wù)排班的月工時(shí)是否超勞。文獻(xiàn)[11]將乘務(wù)計(jì)劃編制問(wèn)題拆分為最優(yōu)回路構(gòu)造、回路循環(huán)優(yōu)化和排班三個(gè)子問(wèn)題，并設(shè)計(jì)了遺傳算法進(jìn)行求解，但是編制步驟繁瑣，不利于鐵路乘務(wù)排班計(jì)劃的快速編制。文獻(xiàn)[12]將乘務(wù)排班計(jì)劃編制問(wèn)題劃分為給定周期、單一循環(huán)乘務(wù)排班計(jì)劃兩類排班形式，并對(duì)非極大排班方案的調(diào)整作了深入研究，設(shè)計(jì)了基于貪婪搜索、集合覆蓋的兩階段求解算法，但是該模型沒(méi)有考慮乘務(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ù)雜交路，沒(méi)有給出具體的評(píng)價(jià)值標(biāo)定方法。文獻(xiàn)[14]以交路單元作為列車乘務(wù)交路編制基本單位的方法，建立了以最小費(fèi)用為目標(biāo)的乘務(wù)交路編制優(yōu)化模型，利用基于貪婪思想的啟發(fā)式算法進(jìn)行求解，但是求解精度仍存在改進(jìn)空間。文獻(xiàn)[15]利用禁忌搜索算法完成系統(tǒng)功能設(shè)計(jì)，能夠快速編制高速動(dòng)車組乘務(wù)交路方案，但是機(jī)車乘務(wù)員容易超勞。文獻(xiàn)[16]在已知乘務(wù)員標(biāo)準(zhǔn)月工時(shí)的前提下，建立了以交路和乘務(wù)工時(shí)為主要約束條件，以乘務(wù)班組最少、乘務(wù)費(fèi)用最低為優(yōu)化目標(biāo)的模型，并利用遺傳算法進(jìn)行求解;該模型和算法可有效降低鐵路部門(mén)乘務(wù)費(fèi)用，但乘務(wù)人員工作量較大，不利于行車安全。對(duì)上述研究成果進(jìn)行分析可以看出，國(guó)內(nèi)大多數(shù)學(xué)者的研究重點(diǎn)主要集中于求得乘務(wù)周期最小的排班方案，而關(guān)于冗余接續(xù)時(shí)間相對(duì)均衡的排班方案的研究較少。冗余接續(xù)時(shí)間的均衡性不僅關(guān)系到乘務(wù)值乘計(jì)劃的穩(wěn)定性，還與乘務(wù)人員作息是否規(guī)律有密切的關(guān)系。

根據(jù)文獻(xiàn)[6]已編制的乘務(wù)交路計(jì)劃，本文在此基礎(chǔ)上利用乘務(wù)交路，繼續(xù)編制乘務(wù)排班計(jì)劃。文獻(xiàn)[6]將乘務(wù)交路計(jì)劃編制問(wèn)題抽象為單基地、均衡行駛路程的多旅行商問(wèn)題（Multi-Traveling Salesman Problem， MTSP），通過(guò)引入均衡因子，建立了以乘務(wù)交路用時(shí)少和子乘務(wù)交路間任務(wù)均衡為目標(biāo)的數(shù)學(xué)模型。針對(duì)該模型文獻(xiàn)[6]提出了一種雙重策略蟻群優(yōu)化算法，該算法設(shè)計(jì)了雙重信息素及雙重策略狀態(tài)的轉(zhuǎn)移概率，結(jié)合乘務(wù)交路時(shí)空約束規(guī)則，設(shè)置了雙重信息素全局更新策略，在每次迭代結(jié)束后，只允許全局最優(yōu)解釋放信息素。在最優(yōu)路徑上，螞蟻才釋放信息素，同時(shí)信息素?fù)]發(fā)，這點(diǎn)非常重要，因?yàn)樵谛畔⑺馗聲r(shí)的時(shí)間復(fù)雜度從O（n2）降到了O（n）。設(shè)置雙重策略狀態(tài)的轉(zhuǎn)移概率，增加了螞蟻搜索路徑的多樣性，又使得更新的路徑具有隨機(jī)性，能夠有效避免算法過(guò)早地陷入局部最優(yōu)。本文在總結(jié)已有研究成果的基礎(chǔ)上，結(jié)合鐵路乘務(wù)規(guī)則及其特點(diǎn)，將乘務(wù)排班計(jì)劃編制問(wèn)題抽象為單基地、考慮中途休息的多旅行商問(wèn)題，建立以排班周期最小、乘務(wù)交路間冗余接續(xù)時(shí)間分布最均衡為優(yōu)化目標(biāo)的單一循環(huán)乘務(wù)排班計(jì)劃數(shù)學(xué)模型，并針對(duì)該模型提出了一種啟發(fā)式修正蟻群算法。該算法對(duì)解空間作了改進(jìn)，構(gòu)建n維向量Crew-scheduling，設(shè)計(jì)了基于啟發(fā)式信息修正的轉(zhuǎn)移概率。通過(guò)啟發(fā)式信息修正的轉(zhuǎn)移概率，使算法在降低問(wèn)題復(fù)雜性的同時(shí)，增加螞蟻搜索路徑的多樣性，減少算法搜索的盲目性，有效引導(dǎo)算法朝全局最優(yōu)方向進(jìn)行搜索。啟發(fā)式信息在算法運(yùn)行時(shí)，能夠指引螞蟻向壓縮乘務(wù)交路總接續(xù)時(shí)長(zhǎng)的相鄰乘務(wù)交路轉(zhuǎn)移。文獻(xiàn)[6]選用遺傳算法作為對(duì)比算法，得出改進(jìn)的雙重策略蟻群優(yōu)化算法較遺傳算法能更快地收斂，解的質(zhì)量也有大幅提升。本文選用粒子群算法作為對(duì)比算法，得出改進(jìn)的啟發(fā)式修正蟻群算法較粒子群算法具有更快的收斂速度。同時(shí)，文獻(xiàn)[6]和本文都運(yùn)用廣深線城際鐵路數(shù)據(jù)作為算例，對(duì)設(shè)計(jì)的模型及算法進(jìn)行檢驗(yàn)。

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

1.1 問(wèn)題描述

螞蟻k從不同的乘務(wù)交路節(jié)點(diǎn)出發(fā)，以概率Pkij向相鄰乘務(wù)交路j轉(zhuǎn)移時(shí)，若轉(zhuǎn)移后的連續(xù)值乘累計(jì)時(shí)長(zhǎng)小于單雙休累計(jì)值乘時(shí)長(zhǎng)標(biāo)準(zhǔn)，則直接轉(zhuǎn)移至乘務(wù)交路j，同時(shí)更新向量Crew-scheduling，并令值乘累計(jì)時(shí)長(zhǎng)為tcj=tci+ttj;若轉(zhuǎn)移后連續(xù)值乘累計(jì)時(shí)長(zhǎng)大于單雙休累計(jì)值乘時(shí)間標(biāo)準(zhǔn)，則按照單雙休累計(jì)值乘時(shí)長(zhǎng)標(biāo)準(zhǔn)轉(zhuǎn)移至乘務(wù)交路j，同時(shí)更新向量Crew-scheduling，令值乘累計(jì)時(shí)長(zhǎng)為tcj=tcj，并將轉(zhuǎn)移后的乘務(wù)交路j定為當(dāng)前節(jié)點(diǎn)，繼續(xù)進(jìn)行解的構(gòu)建，直至向量Crew-scheduling中所有元素都為1時(shí)完成解的構(gòu)建。

3）信息素的表示、初始化及更新。

信息素τij表示螞蟻處在節(jié)點(diǎn)i時(shí)，接續(xù)節(jié)點(diǎn)j的重要程度。其中，路徑上的信息素初始濃度設(shè)定為：

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

0，其他? （15）

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

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

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

Δτij=1/Zibest， eij∈sibest

0，其他 （17）

其中：ρ為信息素?fù)]發(fā)因子，0<ρ<1;n代表迭代次數(shù);Δτij為每次迭代過(guò)程中的信息素增量。

4）基于啟發(fā)式信息修正的轉(zhuǎn)移概率。

當(dāng)?shù)趉只螞蟻在乘務(wù)交路節(jié)點(diǎn)i時(shí)，接續(xù)下一個(gè)乘務(wù)交路j的概率為：

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

0，其他 （18）

式中：ηij為預(yù)見(jiàn)度，表示從乘務(wù)交路節(jié)點(diǎn)i轉(zhuǎn)移到乘務(wù)交路節(jié)點(diǎn)j的預(yù)見(jiàn)程度;Vki表示螞蟻待訪問(wèn)的節(jié)點(diǎn)集合，隨著迭代次數(shù)的增加，Vki中的元素不斷減少，直至為空，即表示所有乘務(wù)交路節(jié)點(diǎn)全部遍歷完畢;α表示殘留信息素的相對(duì)重要程度，其值越大，信息素的濃度在轉(zhuǎn)移中起的作用越大;β為預(yù)見(jiàn)值的相對(duì)重要程度，其值越大，螞蟻以越大的概率轉(zhuǎn)移到接續(xù)時(shí)間較短的下一個(gè)乘務(wù)交路節(jié)點(diǎn)。其中對(duì)啟發(fā)式信息進(jìn)行修正，如式（19）所示：

ηij=

1ttθij-Ts+ω， tci+ttθij≤Tr

1ttθij0+Ts-ttθij01440·1440-Ts+ω，其他 （19）

其中：ttθij為乘務(wù)交路接續(xù)時(shí)間;Tr為單雙休接續(xù)時(shí)長(zhǎng)標(biāo)準(zhǔn);Ts為乘務(wù)交路間實(shí)際接續(xù)時(shí)間對(duì)應(yīng)的接續(xù)時(shí)間標(biāo)準(zhǔn);ttθij0為初始計(jì)算得出的乘務(wù)交路間接續(xù)計(jì)算時(shí)長(zhǎng)，僅滿足乘務(wù)交路的正常接續(xù)時(shí)長(zhǎng)標(biāo)準(zhǔn)，即ttθij0≥Ts，但不一定滿足單雙休接續(xù)時(shí)長(zhǎng)標(biāo)準(zhǔn);ω為常數(shù)，確保當(dāng)實(shí)際接續(xù)時(shí)間與乘務(wù)接續(xù)時(shí)長(zhǎng)標(biāo)準(zhǔn)相同時(shí)，式（19）仍成立。所建模型以排班周期最小為優(yōu)化目標(biāo)，即乘務(wù)交路接續(xù)時(shí)間最小。對(duì)于當(dāng)前乘務(wù)交路，若繼續(xù)接續(xù)后面的乘務(wù)交路，并連續(xù)值乘累計(jì)時(shí)長(zhǎng)不超過(guò)單雙休累計(jì)值乘時(shí)長(zhǎng)標(biāo)準(zhǔn)，則乘務(wù)交路接續(xù)時(shí)長(zhǎng)為通過(guò)初始計(jì)算而得的乘務(wù)交路接續(xù)時(shí)長(zhǎng);若接續(xù)后的連續(xù)值乘累計(jì)時(shí)長(zhǎng)大于單雙休累計(jì)工作時(shí)長(zhǎng)標(biāo)準(zhǔn)，則乘務(wù)交路接續(xù)時(shí)長(zhǎng)需要由初始接續(xù)時(shí)長(zhǎng)作相應(yīng)修改，如式（20）所示。

ttθij=ttθij0，tci+ttθij≤Tr

ttθij0+Ts-ttθij01440·1440，其他 （20）

通過(guò)分析乘務(wù)交路乘務(wù)接續(xù)時(shí)長(zhǎng)特點(diǎn)，設(shè)計(jì)了基于啟發(fā)式信息修正的轉(zhuǎn)移概率，使算法在降低問(wèn)題復(fù)雜性的同時(shí)，減少了算法搜索的盲目性，有效引導(dǎo)算法朝全局最優(yōu)方向進(jìn)行搜索;同時(shí)，增加了螞蟻搜索路徑的多樣性，又使得更新的路徑具有隨機(jī)性，能夠有效避免算法過(guò)早地陷入局部最優(yōu)，而進(jìn)入停滯狀態(tài)。啟發(fā)式信息在算法運(yùn)行時(shí)，能夠指引螞蟻向壓縮乘務(wù)交路總接續(xù)時(shí)長(zhǎng)的相鄰乘務(wù)交路轉(zhuǎn)移。在算法迭代過(guò)程中，啟發(fā)式信息的修正考慮了接續(xù)乘務(wù)交路后乘務(wù)人員休息的類型，即正常休息或單雙休三種情況，并分別進(jìn)行計(jì)算。在算法執(zhí)行過(guò)程中動(dòng)態(tài)地更新，即算法執(zhí)行至某一時(shí)刻時(shí)，并不立即接續(xù)下一個(gè)乘務(wù)交路節(jié)點(diǎn)，而是先判斷既有乘務(wù)交路分別選擇所有可接續(xù)的乘務(wù)交路后對(duì)應(yīng)休息的種類（正常休息或單雙休），并根據(jù)不同乘務(wù)人員休息類型及時(shí)更新啟發(fā)式信息，目的在于使乘務(wù)交路接續(xù)冗余時(shí)間最小，同時(shí)增加算法的全局搜索能力，加快算法的收斂。

5）評(píng)價(jià)函數(shù)。

本文以式（1）作為評(píng)價(jià)函數(shù)，評(píng)價(jià)所有解的質(zhì)量。

6）終止策略。

螞蟻經(jīng)過(guò)若干次搜索后，找到的解不再改變時(shí)，算法終止。

2.2 算法具體實(shí)現(xiàn)流程

本文算法具體實(shí)現(xiàn)流程如下：

步驟1 令nc←0，k←1，初始化α、β、ρ螞蟻數(shù)量、最大迭代次數(shù)等參數(shù)，并令乘務(wù)排班起始乘務(wù)交路節(jié)點(diǎn)e←1。

步驟2 將m只螞蟻放置在乘務(wù)交路節(jié)點(diǎn)e，構(gòu)建一個(gè)n維向量Crew-scheduling，該向量中的元素代表了所有的乘務(wù)交路，所有元素都為0-1變量。當(dāng)某一元素對(duì)應(yīng)的乘務(wù)交路未被選擇時(shí)，該元素為0;否則為1。初始化向量Crew-scheduling，令所有元素初態(tài)為0，并計(jì)算乘務(wù)交路正常接續(xù)時(shí)長(zhǎng)和累計(jì)值乘時(shí)長(zhǎng)。

步驟3 對(duì)于螞蟻k，計(jì)算接續(xù)n維向量Crew-scheduling中乘務(wù)交路i后的累計(jì)值乘時(shí)長(zhǎng)tci，若tci>TCj，則按式（20）將既有乘務(wù)交路與乘務(wù)交路j的接續(xù)時(shí)長(zhǎng)轉(zhuǎn)化為單雙休接續(xù)時(shí)長(zhǎng);否則，保持ttθij不變。

步驟4 針對(duì)螞蟻k，根據(jù)步驟2中更新后的接續(xù)時(shí)長(zhǎng)計(jì)算啟發(fā)式信息，并得到選擇下一個(gè)乘務(wù)交路j的概率，同時(shí)更新n維向量Crew-scheduling，若此時(shí)n維向量Crew-scheduling元素全部為1，則轉(zhuǎn)下一步;否則轉(zhuǎn)步驟3。

步驟5 將得到的乘務(wù)排班方案中末尾乘務(wù)交路節(jié)點(diǎn)與起始乘務(wù)交路e相連接，完成乘務(wù)交路回路的構(gòu)建。并令k←k+1，若k>m，則轉(zhuǎn)下一步;否則轉(zhuǎn)步驟3。

步驟6 所有螞蟻構(gòu)建乘務(wù)交路回路，以式（1）作為評(píng)價(jià)函數(shù)，評(píng)價(jià)所有解的質(zhì)量，并確定最優(yōu)解，根據(jù)迭代最優(yōu)解動(dòng)態(tài)更新啟發(fā)式信息。

步驟7 令nc←nc+1，如果nc小于步驟1中指定的最大迭代次數(shù)，則更新n維向量Crew-scheduling，轉(zhuǎn)至步驟2;否則表示所有螞蟻己完成以乘務(wù)交路節(jié)點(diǎn)e作為起始節(jié)點(diǎn)的乘務(wù)排班計(jì)劃編制。

步驟8 令e←e+1，若e>n，則表示以所有乘務(wù)交路為起始節(jié)點(diǎn)完成乘務(wù)排班計(jì)劃編制，轉(zhuǎn)下一步;否則轉(zhuǎn)步驟2。

步驟9 算法結(jié)束，根據(jù)輸出的不同乘務(wù)排班方案，輸出最優(yōu)解。

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

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

以廣深線城際列車為例對(duì)本文模型和算法的有效性進(jìn)行驗(yàn)證。廣深線正線全長(zhǎng)147km，共設(shè)車站7座，列車最高運(yùn)行速度200km/h，線路起于廣州市越秀區(qū)廣州站，經(jīng)由廣州市廣州東站、東莞市東莞站、常平站、樟木頭站、深圳市平湖站，終于深圳市羅湖區(qū)深圳站。動(dòng)車組檢修基地設(shè)置在廣州東站接軌的石牌動(dòng)車檢修所。乘務(wù)基地設(shè)置在廣州東站，深圳站設(shè)乘務(wù)人員公寓，供在深圳駐班或調(diào)休的乘務(wù)班組休息。

廣深線乘務(wù)運(yùn)用情況說(shuō)明：機(jī)務(wù)乘務(wù)組應(yīng)遵循早出乘早下班，晚出乘晚下班的原則;所有乘務(wù)組在乘務(wù)基地進(jìn)行出退乘作業(yè)，廣州東—廣州乘務(wù)值乘方式為雙班單司機(jī)，廣州東—深圳乘務(wù)值乘方式為單班單司機(jī)。廣深線6：00—24：00的城際列車開(kāi)行方案中，有18對(duì)列車為廣州至深圳直達(dá)列車，57對(duì)列車為廣州東至深圳直達(dá)列車，以廣州東站為乘務(wù)基地，以深圳站為換乘站，根據(jù)文獻(xiàn)[6]編制的乘務(wù)交路計(jì)劃可知廣深線城際列車按照18條乘務(wù)交路運(yùn)行，如表2所示。

3.2 算例結(jié)果

根據(jù)1.2節(jié)所述乘務(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ù)排班計(jì)劃的正常休息時(shí)長(zhǎng)標(biāo)準(zhǔn)為不低于960min，但是也不宜過(guò)長(zhǎng)，否則會(huì)影響乘務(wù)組織效率，因而將最大正常休息時(shí)長(zhǎng)設(shè)定為1110min。雙休最小累計(jì)時(shí)長(zhǎng)標(biāo)準(zhǔn)為2300min，雙休最大累計(jì)時(shí)長(zhǎng)標(biāo)準(zhǔn)為2418min。正整數(shù)M的取值為2880，ε取值為1 （在正常情況下，根據(jù)乘務(wù)基地廣州東的歷史乘務(wù)數(shù)據(jù)，查定得到的數(shù)值）。運(yùn)用本文設(shè)計(jì)的改進(jìn)蟻群算法進(jìn)行求解，其中：信息素重要程度因子α=1，啟發(fā)式信息素重要程度因子為5，信息素?fù)]發(fā)因子取0.2，螞蟻個(gè)數(shù)取20，設(shè)迭代次數(shù)為200，算法重復(fù)執(zhí)行次數(shù)為100。在Intel core i7-8550U CPU 1.8GHz、內(nèi)存8GB的計(jì)算機(jī)上，運(yùn)用Matlab R2015b進(jìn)行求解。

單一循環(huán)乘務(wù)排班計(jì)劃計(jì)算結(jié)果如表3所示。從表3可以看出，以大多數(shù)乘務(wù)交路為起點(diǎn)均能找到總接續(xù)時(shí)間為30431min的乘務(wù)排班計(jì)劃，在以排班周期最小、乘務(wù)交路間冗余接續(xù)時(shí)間分布最均衡為目標(biāo)的情況下，具有最小目標(biāo)函數(shù)值的排班方案是從第1個(gè)乘務(wù)交路出發(fā)，其對(duì)應(yīng)的算法迭代圖如圖1所示，當(dāng)?shù)?5次時(shí)，目標(biāo)函數(shù)值已趨于穩(wěn)定且達(dá)到最小，此時(shí)目標(biāo)函數(shù)值為30438.82min。

各乘務(wù)交路間冗余時(shí)間的均衡性如圖2所示。從圖2可以看出，乘務(wù)交路間冗余接續(xù)時(shí)間的均衡性比較好。根據(jù)計(jì)算結(jié)果，乘務(wù)交路間總接續(xù)時(shí)間為30431min，乘務(wù)人員值乘時(shí)間為14100min，所以乘務(wù)排班計(jì)劃總時(shí)間為44531min。

3.3 結(jié)果評(píng)價(jià)分析

計(jì)算結(jié)果的指標(biāo)如表4所示，分析后可得出如下結(jié)論：

1）本文所求乘務(wù)排班周期為48d，排班周期和乘務(wù)基地所擁有的乘務(wù)組數(shù)相同。根據(jù)計(jì)算結(jié)果，所有乘務(wù)組均連續(xù)作業(yè)6d后，休息2d。乘務(wù)人員在6d值乘時(shí)間里，正常累計(jì)值乘時(shí)間分布在2301～2418min，平均每天值乘6.392～6.717h，符合乘務(wù)人員勞動(dòng)時(shí)間標(biāo)準(zhǔn)。整個(gè)乘務(wù)排班周期內(nèi)，乘務(wù)員的乘務(wù)工作安排如表5所示。

指標(biāo)名稱實(shí)驗(yàn)結(jié)果評(píng)價(jià)原則評(píng)價(jià)結(jié)果平均月工時(shí)178.8h月度最大工時(shí)為180h符合最大連續(xù)值乘

列數(shù)4列連續(xù)值乘不得超過(guò)

4趟列車符合最大值乘列數(shù)5列最大值乘列數(shù)不得

超過(guò)6趟列車符合最大連續(xù)值乘

時(shí)間373.8min最大連續(xù)值乘時(shí)間

不超過(guò)480min符合最大值乘時(shí)間507min最大值乘時(shí)間不超過(guò)

540min符合

2）根據(jù)優(yōu)化結(jié)果，平均月工時(shí)為178.8h，各乘務(wù)組的月度工作時(shí)間接近規(guī)定時(shí)間，有效地避免了乘務(wù)組超勞的情況，使乘務(wù)人員有更充沛的精力值乘后續(xù)列車，有效地保障了列車運(yùn)行安全。調(diào)休乘務(wù)組和值乘乘務(wù)組比例為1/3，比例適中，便于處理臨時(shí)性應(yīng)急乘務(wù)任務(wù)，并保證了乘務(wù)任務(wù)分配的均衡性。

3）乘務(wù)交路間的冗余時(shí)間分布在99～124min，提高了乘務(wù)排班計(jì)劃的魯棒性，使乘務(wù)交路的實(shí)際接續(xù)時(shí)間在列車發(fā)生突發(fā)事件后仍滿足接續(xù)時(shí)間標(biāo)準(zhǔn)。

3.4 算法對(duì)比分析

多數(shù)學(xué)者均采用粒子群算法求解乘務(wù)排班計(jì)劃問(wèn)題，因此本文以粒子群算法作為對(duì)比算法。在同一臺(tái)計(jì)算機(jī)上運(yùn)用Matlab R2015b對(duì)本文模型進(jìn)行求解，均衡因子與上述取值相同，迭代次數(shù)為200，算法重復(fù)執(zhí)行次數(shù)為100。從多次執(zhí)行情況來(lái)看，其平均收斂代數(shù)約在85～95，每次搜索耗時(shí)1.8620s，算法總的執(zhí)行時(shí)間為1023.3240s。起始交路為12號(hào)乘務(wù)交路，較優(yōu)乘務(wù)排班計(jì)劃的運(yùn)行結(jié)果為31439.4117min。兩種算法對(duì)比結(jié)果如表6所示。通過(guò)對(duì)比分析可得，與粒子群算法相比，本文設(shè)計(jì)的改進(jìn)蟻群算法具有更快的收斂速度，能夠使平均月工時(shí)降低8.5%，排班周期降低9.4%，乘務(wù)人員超勞率為0，從而大幅提升了解的質(zhì)量。

4 結(jié)語(yǔ)

本文建立了以排班周期最小、乘務(wù)交路間冗余接續(xù)時(shí)間分布最均衡為目標(biāo)的MTSP模型，通過(guò)引入冗余時(shí)間均衡性，使得模型更具實(shí)際意義;同時(shí)提出了一種啟發(fā)式修正蟻群算法，其特點(diǎn)在于采用運(yùn)行時(shí)信息作為啟發(fā)式信息來(lái)指導(dǎo)蟻群的搜索過(guò)程，在一定程度上既增加了算法的全局搜索能力，又可以加快算法的收斂，同時(shí)避免了傳統(tǒng)蟻群算法易陷入局部最優(yōu)的缺點(diǎn)。

與粒子群算法相比，本文提出的改進(jìn)蟻群算法效率更高、求解質(zhì)量更好，對(duì)本文模型的求解具有很強(qiáng)的適應(yīng)性。

本文模型及算法可為鐵路機(jī)務(wù)部門(mén)編制乘務(wù)排班計(jì)劃提供有價(jià)值的決策支持，對(duì)增強(qiáng)鐵路機(jī)務(wù)系統(tǒng)統(tǒng)籌協(xié)調(diào)能力具有實(shí)際意義和幫助，可作為鐵路系統(tǒng)乘務(wù)管理決策理論的組成部分。本文模型未考慮乘務(wù)排班計(jì)劃與機(jī)車周轉(zhuǎn)圖的一體化協(xié)同編制，對(duì)于這一問(wèn)題的研究將是后續(xù)工作的重點(diǎn)。

參考文獻(xiàn) （References）

[1]MERCIER A， SOUMIS F. An integrated aircraft routing， crew scheduling and flight retiming model [J]. Computers and Operations Research， 2007， 34（8）： 2251-2265.

[2]SOUAI N， TEGHEM J. Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem [J]. European Journal of Operational Research， 2009， 199（3）： 674-683.

[3]NISHI T， SUGIYAMA T， INUIGUCHI M. Two-level decomposition algorithm for crew rostering problems with fair working condition [J]. European Journal of Operational Research， 2014， 237（2）： 465-473.

[4]VEELENTURF L P， POTTHOFF D， HUISMAN D， et al. A quasi-robust optimization approach for resource rescheduling [J]. Transportation Science， 2016， 50（1）： 204-215.

[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]王東先，孟學(xué)雷，喬俊，等.基于改進(jìn)蟻群算法的鐵路乘務(wù)交路計(jì)劃的編制[J].計(jì)算機(jī)應(yīng)用，2019，39（9）：2749-2756.（WANG D X， MENG X L， QIAO J， et al. Research on railway crew routing plan based on improved ant colony algorithm [J]. Journal of Computer Applications， 2019， 39（9）： 2749-2756.）

[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]程巖巖.我國(guó)鐵路乘務(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]張哲銘，王瑩，陳旭，等.高速鐵路單一循環(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.）

[10]褚飛躍，田志強(qiáng)，倪少權(quán).高速鐵路單循環(huán)乘務(wù)排班計(jì)劃編制模型與算法[J].鐵道學(xué)報(bào)，2012，34（7）：1-9.（CHU F Y， TIAN Z Q， NI S Q. Model and algorithm for formulation of the single cycle crew rostering plans of high-speed railways [J]. Journal of the China Railway Society， 2012， 34（7）： 1-9.）

[11]黃珊.機(jī)車乘務(wù)人員運(yùn)用問(wèn)題及其輔助編排系統(tǒng)研究[D].長(zhǎng)沙：中南大學(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）：23-29.（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）： 23-29.）

[14]李雯，賈富強(qiáng)，楊睿.基于交路單元的高速鐵路乘務(wù)交路編制模型與算法[J].交通運(yùn)輸研究，2018，4（4）：48-53.（LI W， JIA F Q， YANG R. A model and algorithm of high-speed railway crew scheduling based on routing unit [J]. Transport Research， 2018， 4（4）： 48-53.）

[15]符卓，袁雪瑩.高速動(dòng)車組乘務(wù)交路輔助編制系統(tǒng)研究[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2019（8）：18-21.（FU Z， YUAN X Y. A research on high-speed EMU crew schedule auxiliary preparation system [J]. Railway Transport and Economy， 2019（8）： 18-21.）

[16]楊國(guó)元，史天運(yùn)，張秋亮.鐵路客運(yùn)乘務(wù)排班計(jì)劃編制模型及算法[J].交通運(yùn)輸系統(tǒng)工程與信息，2016，16（4）：159-164.（YANG G Y， SHI T Y， ZHANG Q L. Model and algorithm for railway passenger crew rostering plan [J]. Journal of Transportation Systems Engineering and Information Technology， 2016，16（4）： 159-164.）

[17]馬良，朱剛，寧愛(ài)兵.蟻群優(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 Program 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 optimization of rail transit.

HE Guoqiang， born in 1990， M. S. candidate. His research interests include intelligent algorithm， management optimization of warehousing logistics.

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

WANG Xidong， born in 1993， assistant engineer. His research interests include optimization of railway traffic organization， cargo transportation organization.

收稿日期：2019-06-27;修回日期：2019-09-05;錄用日期：2019-09-12。

基金項(xiàng)目：國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（2016YFB1200100）;國(guó)家自然科學(xué)基金資助項(xiàng)目（71861022，61563028）。

作者簡(jiǎn)介：王東先（1992—），男，甘肅武威人，碩士研究生，主要研究方向：軌道交通運(yùn)行管理與決策優(yōu)化; 孟學(xué)雷（1979—），男，山東泰安人，教授，博士，主要研究方向：軌道交通運(yùn)行管理與決策優(yōu)化; 何國(guó)強(qiáng)（1990—），男，甘肅白銀人，碩士研究生，主要研究方向∶智能算法、倉(cāng)儲(chǔ)物流管理優(yōu)化; 孫慧萍（1993—），女，甘肅定西人，碩士研究生，主要研究方向：軌道交通運(yùn)行管理與決策優(yōu)化; 王喜棟（1993—），男，甘肅臨洮人，助理工程師，學(xué)士，主要研究方向：鐵路車流組織優(yōu)化、貨物運(yùn)輸組織。

文章編號(hào)：1001-9081（2019）12-3678-07DOI：10.11772/j.issn.1001-9081.2019061118