薛 鋒 ，李 海，梁 鵬，陳崇雙，羅 建

（1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 611756；2.西南交通大學(xué) 綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 611756；3.西南交通大學(xué) 綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國(guó)家工程實(shí)驗(yàn)室，四川 成都 611756；4.西南交通大學(xué) 數(shù)學(xué)學(xué)院，四川 成都 611756；5.西華大學(xué) 汽車(chē)與交通學(xué)院，四川 成都 610039)

0 引言

城市軌道交通乘務(wù)計(jì)劃是指導(dǎo)乘務(wù)員日常工作的核心文件，長(zhǎng)期以來(lái)該計(jì)劃都采用人工編制，效率比較低，各項(xiàng)參數(shù)設(shè)置也較為主觀，配置結(jié)果往往出現(xiàn)人員緊張或者人員閑置情況，穩(wěn)定性較差，且隨著城軌線(xiàn)路、客運(yùn)需求的不斷增加，人工編制的方法已難以滿(mǎn)足實(shí)際需求，如何快速編制高效的乘務(wù)計(jì)劃并進(jìn)行優(yōu)化成為亟待解決的問(wèn)題。

目前，我國(guó)城市軌道交通乘務(wù)計(jì)劃普遍分為乘務(wù)任務(wù)配對(duì)和乘務(wù)任務(wù)輪轉(zhuǎn)2 個(gè)子問(wèn)題。乘務(wù)任務(wù)配對(duì)，是根據(jù)相應(yīng)線(xiàn)路條件、運(yùn)營(yíng)約束將列車(chē)運(yùn)行計(jì)劃以輪乘點(diǎn)為分割點(diǎn)進(jìn)行拆分，結(jié)合乘務(wù)員值乘約束，組合配對(duì)形成乘務(wù)任務(wù)。乘務(wù)任務(wù)輪轉(zhuǎn)指將配對(duì)好的早、白、夜3種不同班種的乘務(wù)任務(wù)，按照輪轉(zhuǎn)制度，較為均衡地安排給每個(gè)乘務(wù)員，從而形成乘務(wù)員的階段任務(wù)。這其中乘務(wù)任務(wù)配對(duì)是首要環(huán)節(jié)，更是編制乘務(wù)輪轉(zhuǎn)計(jì)劃的前提。張?jiān)鲇碌萚1]基于懲罰費(fèi)用構(gòu)建了乘務(wù)排班雙層優(yōu)化模型，并設(shè)計(jì)了Dijkstra 算法和離散粒子群算法求解，但模型的目標(biāo)函數(shù)計(jì)算復(fù)雜，得到的乘務(wù)方案間休時(shí)間仍高于標(biāo)準(zhǔn)時(shí)間；豐富等[2]從時(shí)間均衡度角度研究了乘務(wù)排班計(jì)劃優(yōu)化問(wèn)題，但目標(biāo)函數(shù)中的權(quán)重系數(shù)較難確定；Fuentes 等[3]考慮每個(gè)乘務(wù)任務(wù)的總時(shí)間，建立了基于排序的乘務(wù)任務(wù)配對(duì)模型(SEBACS)，并設(shè)計(jì)了拉格朗日松弛算法進(jìn)行求解；胡汪源[4]和袁仁杰[5]將乘務(wù)排班問(wèn)題歸結(jié)為VPR問(wèn)題，并分別從減少乘務(wù)費(fèi)用和等待時(shí)間、減少乘務(wù)任務(wù)數(shù)量和均衡工作量2 個(gè)角度，對(duì)乘務(wù)排班問(wèn)題進(jìn)行優(yōu)化研究；馬卓然[6]和金華等[7]從資源共享角度即不同線(xiàn)路間列車(chē)不跨線(xiàn)情況下的乘務(wù)員可共享角度對(duì)乘務(wù)排班問(wèn)題進(jìn)行優(yōu)化研究；石俊剛等[8]和許仲豪等[9]基于列生成思想，分別結(jié)合跟隨分支策略和貪婪算法對(duì)乘務(wù)排班問(wèn)題進(jìn)行研究；馬亮等[10]考慮實(shí)際便乘情況，以乘務(wù)任務(wù)數(shù)量最少為目標(biāo)，建立了乘務(wù)任務(wù)配對(duì)的約束優(yōu)化模型，并設(shè)計(jì)約束傳播與啟發(fā)式回溯的混合算法，得到在求解質(zhì)量和求解效率方面都比現(xiàn)場(chǎng)和不帶約束傳播的深度優(yōu)先回溯算法高的排班方案。

現(xiàn)有研究主要是基于集合分割與集合覆蓋思想，建立相應(yīng)的乘務(wù)排班優(yōu)化模型，然后采用列生成算法或啟發(fā)式算法進(jìn)行求解，得到滿(mǎn)足約束條件下的乘務(wù)排班方案。但是，既有研究都是在假定各時(shí)間參數(shù)已知情況下進(jìn)行乘務(wù)計(jì)劃編制，而在實(shí)際編制過(guò)程中，這些參數(shù)并非都是已知的，且其中任何一個(gè)參數(shù)的變化都可能影響最終乘務(wù)計(jì)劃編制的效果。為此，研究參數(shù)未知情況下的城市軌道交通乘務(wù)任務(wù)配對(duì)問(wèn)題，以一日內(nèi)所有乘務(wù)員的效率最大化為目標(biāo)，建立混合整數(shù)規(guī)劃模型，并設(shè)計(jì)與之匹配的遺傳禁忌混合搜索算法。

1 問(wèn)題描述

為了方便描述乘務(wù)排班問(wèn)題，有必要對(duì)幾個(gè)概念進(jìn)行說(shuō)明。地鐵運(yùn)營(yíng)部門(mén)固定選擇幾個(gè)車(chē)站作為司機(jī)值乘換班的地點(diǎn)，稱(chēng)之為輪乘站。實(shí)際中，一般將車(chē)輛段、停車(chē)場(chǎng)、某些車(chē)站作為輪乘站。車(chē)輛段和停車(chē)場(chǎng)一般選擇在線(xiàn)路的兩端，處于線(xiàn)路中間的輪乘站一般基于值乘負(fù)荷進(jìn)行設(shè)置。相鄰兩個(gè)輪乘站之間的距離一般不會(huì)太遠(yuǎn)，否則連續(xù)工作時(shí)間太長(zhǎng)，容易致使司機(jī)駕駛疲勞；相鄰兩個(gè)輪乘站之間的距離一般也不會(huì)太近，否則司機(jī)們的工作效率不高。運(yùn)行線(xiàn)上連續(xù)兩個(gè)輪乘站之間的線(xiàn)段，即是乘務(wù)任務(wù)作業(yè)段。每個(gè)司機(jī)一般會(huì)值乘多個(gè)乘務(wù)任務(wù)作業(yè)段。因此，幾個(gè)乘務(wù)任務(wù)作業(yè)段的集合，稱(chēng)之為乘務(wù)任務(wù)，顧名思義，對(duì)應(yīng)了一名司機(jī)的值乘任務(wù)。

在給出上述3 個(gè)概念的基礎(chǔ)上，給出乘務(wù)任務(wù)配對(duì)問(wèn)題描述。所謂乘務(wù)任務(wù)配對(duì)指將給定的列車(chē)運(yùn)行計(jì)劃(即列車(chē)運(yùn)行圖)依據(jù)輪乘站劃分成若干乘務(wù)作業(yè)段，然后再將乘務(wù)作業(yè)段組合成乘務(wù)任務(wù)，每個(gè)乘務(wù)任務(wù)由一個(gè)乘務(wù)員一天內(nèi)完成。此處以一個(gè)簡(jiǎn)單的案例進(jìn)行說(shuō)明，乘務(wù)任務(wù)配對(duì)示意圖如圖1 所示。

圖1 乘務(wù)任務(wù)配對(duì)示意圖Fig.1 Schematic diagram of crew task pairing

假設(shè)該線(xiàn)除起點(diǎn)站、終點(diǎn)站外，只有一個(gè)中間輪乘站，按照地鐵公司要求，當(dāng)列車(chē)經(jīng)過(guò)起點(diǎn)站、終點(diǎn)站、輪乘點(diǎn)時(shí)，乘務(wù)員需要休息，不能跨過(guò)輪乘站進(jìn)行連續(xù)值乘，從而保證每位乘務(wù)員連續(xù)工作時(shí)間不超過(guò)限值。同時(shí)，當(dāng)乘務(wù)員工作時(shí)段處于用餐時(shí)段時(shí)，必須為乘務(wù)員安排時(shí)間用餐，提供就餐的地點(diǎn)只能在起點(diǎn)站、終點(diǎn)站和輪乘站。假設(shè)中午用餐時(shí)間為11 :00—13 :00，則按照乘務(wù)作業(yè)段劃分規(guī)則，乘務(wù)作業(yè)段包括2 種，分別為：起點(diǎn)站輪乘站，終點(diǎn)站輪乘站。結(jié)合休息時(shí)間約束、用餐時(shí)間約束、列車(chē)整備等約束，配對(duì)好的一個(gè)乘務(wù)任務(wù)如圖1 中粗實(shí)線(xiàn)所示，而實(shí)際中的乘務(wù)任務(wù)配對(duì)問(wèn)題便是在案例基礎(chǔ)上，將所有的乘務(wù)作業(yè)段在符合約束的情況下配對(duì)形成特定的乘務(wù)任務(wù)，從而使得整個(gè)列車(chē)運(yùn)行計(jì)劃能夠被完整的執(zhí)行。

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

2.1 目標(biāo)函數(shù)

以一個(gè)工作日內(nèi)全部乘務(wù)員的值乘效率最高為優(yōu)化目標(biāo)。對(duì)于每一位乘務(wù)員，其乘務(wù)任務(wù)的時(shí)間為值乘作業(yè)段的時(shí)間、休息時(shí)間、用餐時(shí)間等多個(gè)環(huán)節(jié)的時(shí)間總和，最大化值乘效率即最大化值乘時(shí)間占整個(gè)乘務(wù)任務(wù)時(shí)間的比重。因此，城市軌道交通乘務(wù)配對(duì)模型的目標(biāo)函數(shù)如下。

式中：N為一日內(nèi)乘務(wù)員總數(shù)，人；M為乘務(wù)任務(wù)總數(shù)，個(gè)；Q為乘務(wù)任務(wù)包含的乘務(wù)作業(yè)段總數(shù)，個(gè)；為第k個(gè)乘務(wù)作業(yè)段的結(jié)束時(shí)間；為第k個(gè)乘務(wù)作業(yè)段的開(kāi)始時(shí)間；為第i個(gè)乘務(wù)員工作結(jié)束時(shí)間為第i個(gè)乘務(wù)員工作開(kāi)始時(shí)間；xij表示第i個(gè)乘務(wù)員是否值乘第j個(gè)乘務(wù)任務(wù)，值乘取1，否則取0；yjk表示第k個(gè)乘務(wù)任務(wù)作業(yè)段是否屬于第j個(gè)乘務(wù)任務(wù)，屬于取1，否則取0。

同時(shí)為方便計(jì)算，以第i個(gè)乘務(wù)員值乘的第一個(gè)乘務(wù)作業(yè)段開(kāi)始時(shí)間為工作開(kāi)始時(shí)間，以第i個(gè)乘務(wù)員值乘的最后一個(gè)乘務(wù)作業(yè)段結(jié)束時(shí)間為工作結(jié)束時(shí)間。

2.2 約束條件

2.2.1 乘務(wù)員與乘務(wù)任務(wù)間的值乘約束

在乘務(wù)任務(wù)配對(duì)過(guò)程中，乘務(wù)員與乘務(wù)任務(wù)之間存在相互唯一的對(duì)應(yīng)關(guān)系，即第j個(gè)乘務(wù)任務(wù)只能由其中一個(gè)乘務(wù)員值乘，第i個(gè)乘務(wù)員也只能值乘一個(gè)乘務(wù)任務(wù)。

2.2.2 乘務(wù)員工作起止時(shí)間約束

對(duì)每個(gè)乘務(wù)員來(lái)說(shuō)，所值乘的任意乘務(wù)作業(yè)段開(kāi)始時(shí)間均不能早于其工作開(kāi)始時(shí)間，同時(shí)，所值乘的任意乘務(wù)任務(wù)段結(jié)束時(shí)間不能晚于其工作結(jié)束時(shí)間。

式中：MS為較大的正常數(shù)。

2.2.3 工作時(shí)間上限約束

根據(jù)勞動(dòng)法規(guī)定，每個(gè)乘務(wù)員一天內(nèi)的工作時(shí)間總長(zhǎng)不能超過(guò)相應(yīng)工作班次的上限。早班、白班、晚班的工作時(shí)間上限約束分別如下。

2.2.4 休息時(shí)間約束

在非用餐時(shí)間段，即當(dāng)前值乘的乘務(wù)任務(wù)作業(yè)段從開(kāi)始到結(jié)束的時(shí)間區(qū)間與用餐時(shí)間區(qū)間無(wú)交叉，那么，乘務(wù)員在完成相鄰兩個(gè)乘務(wù)作業(yè)段的值乘任務(wù)時(shí)，必須安排時(shí)間休息，以避免長(zhǎng)時(shí)間值乘導(dǎo)致乘務(wù)員疲勞駕駛。休息時(shí)間不能過(guò)短，否則乘務(wù)員無(wú)法緩解疲勞、恢復(fù)精力，因而休息時(shí)間有一個(gè)下限，同時(shí)休息時(shí)間也不能過(guò)長(zhǎng)，導(dǎo)致工作效率低下，故休息時(shí)間也必須有一個(gè)上限。該約束條件為當(dāng)

式中：為午餐開(kāi)始時(shí)間；為午餐結(jié)束時(shí)間；為晚餐開(kāi)始時(shí)間；為晚餐結(jié)束時(shí)間；為最短休息時(shí)間，h；為最長(zhǎng)休息時(shí)間，h；tlczb為列車(chē)整備時(shí)間，h時(shí)間為輪乘站k′與k之間的接續(xù)，h。

整備時(shí)間及不同值乘點(diǎn)接續(xù)時(shí)間具體計(jì)算公式如下。

（1）整備時(shí)間的計(jì)算公式為

式中：Tlczb為相應(yīng)地鐵運(yùn)營(yíng)公司整備時(shí)間標(biāo)準(zhǔn)，h；Um為車(chē)輛段地點(diǎn)集合；為第k個(gè)乘務(wù)作業(yè)段結(jié)束地點(diǎn)。

（2）不同值乘點(diǎn)之間所需的接續(xù)時(shí)間。當(dāng)需要值乘點(diǎn)與乘務(wù)員當(dāng)前地點(diǎn)不同時(shí)，必須通過(guò)其他交通工具或便乘到達(dá)指定值乘地點(diǎn)。當(dāng)值乘點(diǎn)不同時(shí)，需要的接續(xù)時(shí)間計(jì)算公式為

式中：為第k個(gè)乘務(wù)作業(yè)段開(kāi)始地點(diǎn)；為第k′個(gè)乘務(wù)作業(yè)段結(jié)束地點(diǎn)；為前后值乘點(diǎn)不同時(shí)，通過(guò)便乘到達(dá)指定值乘地點(diǎn)所需時(shí)間，h。

2.2.5 用餐時(shí)間約束

當(dāng)乘務(wù)任務(wù)的工作時(shí)間段覆蓋用餐時(shí)段時(shí)，即當(dāng)前值乘的乘務(wù)任務(wù)作業(yè)段從開(kāi)始到結(jié)束的時(shí)間區(qū)間包含或部分包含用餐時(shí)間區(qū)間，那么，必須在指定輪乘站預(yù)留充足的時(shí)間為乘務(wù)員安排用餐，通常只考慮午餐和晚餐。該約束具體刻畫(huà)如下，當(dāng)?時(shí)

式中：為最短用餐時(shí)間，h；為最長(zhǎng)用餐時(shí)間，h。

以上約束中用餐時(shí)間與休息時(shí)間不能同時(shí)存在，即若值乘時(shí)間覆蓋用餐時(shí)間段，就必須安排用餐，否則就安排休息。

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

由建立的模型以及相關(guān)約束條件可知，該模型是一個(gè)非線(xiàn)性的混合整數(shù)規(guī)劃模型，涉及參數(shù)較多，如休息時(shí)間上下限、用餐時(shí)間上下限、各班次最長(zhǎng)工作時(shí)間等，且各參數(shù)的選擇具有很大的范圍，為此針對(duì)建立的乘務(wù)任務(wù)配對(duì)模型，設(shè)計(jì)遺傳禁忌混合搜索算法進(jìn)行求解，步驟如下。

步驟1：根據(jù)地鐵運(yùn)營(yíng)公司指定的輪乘站，結(jié)合乘務(wù)員連續(xù)值乘約束，將列車(chē)運(yùn)行任務(wù)劃分為以輪乘站為分割點(diǎn)的乘務(wù)作業(yè)段，同時(shí)依據(jù)乘務(wù)作業(yè)段開(kāi)始時(shí)間，對(duì)乘務(wù)作業(yè)段進(jìn)行排序。

步驟2：給出模型涉及參數(shù)個(gè)數(shù)YCJJNcs，本模型中該值為13，依據(jù)劃分刻度，對(duì)各參數(shù)進(jìn)行劃分，得到其對(duì)應(yīng)節(jié)點(diǎn)數(shù)，依據(jù)解空間規(guī)模給出種群個(gè)體數(shù)YCJJnum，最大迭代次數(shù)YCJJTT，交叉概率YCJJpc，變異概率YCJJby。

步驟3：依據(jù)YCJJNcs，各參數(shù)節(jié)點(diǎn)數(shù)及種群個(gè)體數(shù)，隨機(jī)產(chǎn)生初始種群。每個(gè)種群中個(gè)體的產(chǎn)生方式如下，如模型中有13 個(gè)參數(shù)，那么基因編碼長(zhǎng)度即為13，假設(shè)第一個(gè)基因?qū)?yīng)參數(shù)為休息最少時(shí)間，該參數(shù)可變區(qū)間為8～15 min，依據(jù)該參數(shù)1 min 劃分刻度，得到節(jié)點(diǎn)共有8 個(gè)，那么第一個(gè)基因位的值即為隨機(jī)產(chǎn)生1—8 的隨機(jī)數(shù)，其余基因位同理，據(jù)此，產(chǎn)生該個(gè)體染色體的全部基因，按照此規(guī)則，產(chǎn)生該種群所有個(gè)體的染色體。同時(shí)初始化禁忌表，大小為YCJJTT×YCJJNcs的全0 矩陣，最大效率記錄表，大小為YCJJTT×1的矩陣，最大效率對(duì)應(yīng)參數(shù)記錄表，大小為YCJJTT×YCJJNcs，初始化a=1，b=1。

步驟4：記錄當(dāng)前迭代次數(shù)a，如果a≤YCJJTT，轉(zhuǎn)步驟5，否則，依據(jù)解碼規(guī)則，輸出效率最高的乘務(wù)任務(wù)對(duì)應(yīng)的染色體解碼得到的各個(gè)參數(shù)時(shí)間值及相應(yīng)乘務(wù)任務(wù)效率，繪制最高效率隨迭代次數(shù)a的變化圖。

步驟5：從種群中第b個(gè)體開(kāi)始，b≤YCJJnum，依次代入當(dāng)前種群中該個(gè)體染色體對(duì)應(yīng)的參數(shù)值，代入方式如下：如步驟3 中，第一個(gè)基因位對(duì)應(yīng)休息最少時(shí)間，產(chǎn)生的隨機(jī)數(shù)為5，即對(duì)應(yīng)第5 個(gè)時(shí)間節(jié)點(diǎn)12 min，那么以8 min 減去時(shí)間劃分刻度值，即7 min 對(duì)應(yīng)時(shí)間420 s 為基礎(chǔ)，加上1 min 時(shí)間刻度對(duì)應(yīng)時(shí)間60 s 乘以該隨機(jī)數(shù)5，即得到該基因位對(duì)應(yīng)實(shí)際參數(shù)值12 min。其余各參數(shù)代入方式相同，只是各參數(shù)代入時(shí)的基礎(chǔ)時(shí)間以及跨度時(shí)間依據(jù)各參數(shù)特征而有所不同。代入后基于貪婪算法思想，從第一個(gè)乘務(wù)作業(yè)段開(kāi)始，依據(jù)休息時(shí)間約束、用餐時(shí)間約束，同時(shí)考慮前后值乘點(diǎn)不同時(shí)便乘的情況，在該乘務(wù)作業(yè)段當(dāng)前的所有可接續(xù)作業(yè)段中找出接續(xù)時(shí)間最短且沒(méi)有組合過(guò)的乘務(wù)作業(yè)段，進(jìn)行組合。然后對(duì)被組合乘務(wù)作業(yè)段做同樣的操作，直到乘務(wù)班次時(shí)間達(dá)到工作時(shí)間上限或不存在可接續(xù)乘務(wù)作業(yè)段時(shí)，記錄該班次的乘務(wù)作業(yè)段組合方式。

步驟6：依次從剩余沒(méi)有進(jìn)行組合的乘務(wù)作業(yè)段中，找出開(kāi)始時(shí)間最早的乘務(wù)作業(yè)段，執(zhí)行步驟5 中的組合配對(duì)操作，直到所有乘務(wù)作業(yè)段都被分配到不同的乘務(wù)班次中。

步驟7：令b=b+1，如果b≤YCJJnum，轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟8。

步驟8：計(jì)算當(dāng)前種群所有個(gè)體編制出的乘務(wù)任務(wù)效率，并將效率最高值的個(gè)體參數(shù)記入禁忌表，若a=1，則將該效率值記錄為第a代最高效率，否則將效率最高值與第a-1 代最高效率進(jìn)行比較，若當(dāng)前種群最高效率大于第a-1 代最高效率，則將當(dāng)前種群最高效率值賦值給第a代最高效率，同時(shí)記錄該個(gè)體參數(shù)值；否則，記錄第a代最高效率等于第a-1 代最高效率，第a代最高效率對(duì)應(yīng)參數(shù)表值不變。

步驟9：依據(jù)給定的交叉概率、變異概率，對(duì)種群進(jìn)行選擇、交叉、變異操作，同時(shí)為擴(kuò)大算法搜索范圍，避免算法陷入局部最優(yōu)解，在每一代種群中，隨機(jī)產(chǎn)生1/3 的新種群，加入子代種群中，并將種群個(gè)體與禁忌表進(jìn)行比較，剔除禁忌表中已經(jīng)存在的個(gè)體。

步驟10：令a=a+1，b=1，轉(zhuǎn)步驟4。

4 實(shí)例分析

成都地鐵5 號(hào)線(xiàn)北起新都區(qū)華桂路站，途徑金牛區(qū)、青羊區(qū)、武侯區(qū)，南至雙流區(qū)回龍站，全長(zhǎng)49.02 km，共設(shè)41座車(chē)站。為滿(mǎn)足該線(xiàn)運(yùn)營(yíng)需求，共劃分8 個(gè)輪乘站點(diǎn)，含1 個(gè)車(chē)輛段，2 個(gè)停車(chē)場(chǎng)，成都5 號(hào)線(xiàn)輪乘點(diǎn)設(shè)置如圖2 所示。取其中一日內(nèi)的運(yùn)行圖數(shù)據(jù)進(jìn)行算例分析，該數(shù)據(jù)共包含686 個(gè)乘務(wù)任務(wù)作業(yè)段，乘務(wù)任務(wù)作業(yè)段數(shù)據(jù)如表1 所示，其中8 個(gè)輪乘點(diǎn)分別用X1—X8 來(lái)表示，對(duì)應(yīng)關(guān)系X1 →大豐停車(chē)場(chǎng)，X2 →華桂路，X3 →石犀公園，X4 →福寧路，X5 →元華車(chē)輛段，X6 →二江寺，X7 →回龍站，X8 →回龍停車(chē)場(chǎng)。

圖2 成都5 號(hào)線(xiàn)輪乘點(diǎn)設(shè)置Fig.2 Schematic diagram of rotation points in Chengdu Metro Line 5

表1 乘務(wù)任務(wù)作業(yè)段數(shù)據(jù)Tab.1 Data of crew task operation

根據(jù)參考文獻(xiàn)[1-10]，對(duì)已有文獻(xiàn)乘務(wù)計(jì)劃編制時(shí)涉及的參數(shù)范圍進(jìn)行歸納，同時(shí)，為進(jìn)行參數(shù)設(shè)置分析，需對(duì)各參數(shù)做出相應(yīng)的劃分，但若將所有可變參數(shù)都以1 min 為刻度進(jìn)行劃分，則會(huì)導(dǎo)致整個(gè)解空間巨大，無(wú)法進(jìn)行有效搜索，為此，根據(jù)已有文獻(xiàn)歸納的數(shù)據(jù)并結(jié)合工作實(shí)際，對(duì)各參數(shù)作具體劃分，現(xiàn)有文獻(xiàn)參數(shù)范圍及劃分如表2所示。

表2 現(xiàn)有文獻(xiàn)參數(shù)范圍及劃分Tab.2 Range and division of parameters in existing literature

依據(jù)表2 劃分的時(shí)間跨度，得到各參數(shù)節(jié)點(diǎn)數(shù)，經(jīng)計(jì)算，問(wèn)題的解空間數(shù)量級(jí)已經(jīng)達(dá)到10 億，為此采用軟件編程，計(jì)算環(huán)境是CPU 為Inter (R)Core (TM) i7-10875H 2.30 GHz，內(nèi)存為16 GB 的DDR4 個(gè)人計(jì)算機(jī)。根據(jù)解空間數(shù)量，設(shè)置迭代次數(shù)為100 次，種群數(shù)為50，交叉概率為0.6，變異概率為0.01，遺傳禁忌搜索算法求解過(guò)程如圖3所示。

由圖3 可知，目標(biāo)函數(shù)值是遞增的，求得較優(yōu)解只需要進(jìn)行27 次迭代運(yùn)算，不超過(guò)30 次，整體效率為0.836 1，說(shuō)明設(shè)計(jì)的遺傳禁忌搜索算法在滿(mǎn)足參數(shù)約束的前提下，能夠保證最優(yōu)解的求解效率，與人工編制乘務(wù)排班方案相比，能夠有效減少編制時(shí)間。

圖3 遺傳禁忌搜索算法求解過(guò)程Fig.3 Solving process of genetic tabu search algorithm

此外，將文獻(xiàn)[5]、文獻(xiàn)[10]中的參數(shù)代入模型中，同時(shí)針對(duì)兩文獻(xiàn)中工作時(shí)間都是8 h 的情況，引入第3 組參數(shù)，改變?cè)摻M參數(shù)中各班次工作時(shí)間，求得對(duì)應(yīng)參數(shù)下編制的乘務(wù)任務(wù)效率，不同參數(shù)設(shè)置下求得的乘務(wù)任務(wù)表如表3 所示。代入模型求得的最優(yōu)參數(shù)得到排班方案，乘務(wù)排班結(jié)果如表4 所示。

表3 不同參數(shù)設(shè)置下求得的乘務(wù)任務(wù)表Tab.3 Crew task table under different parameter settings

表4 乘務(wù)排班結(jié)果Tab.4 Crew scheduling results

由表3 可知，所建模型和設(shè)計(jì)的算法求得的結(jié)果明顯優(yōu)于文獻(xiàn)[5]、文獻(xiàn)[10]中參數(shù)所對(duì)應(yīng)的結(jié)果，同時(shí)文獻(xiàn)[5]中各參數(shù)求得的效率是最低的，這是因?yàn)槲墨I(xiàn)[5]中，乘務(wù)作業(yè)段間休息最長(zhǎng)時(shí)間可達(dá)60 min，這使得間隔時(shí)間跨度較大的乘務(wù)作業(yè)段也可以進(jìn)行組合，造成相鄰乘務(wù)作業(yè)段間休息時(shí)間過(guò)長(zhǎng)。

由文獻(xiàn)[10]、各班次時(shí)長(zhǎng)改變組以及本模型求得的最優(yōu)解可知，各班次工作時(shí)長(zhǎng)不同也會(huì)影響整個(gè)乘務(wù)任務(wù)計(jì)劃的值乘效率。當(dāng)各班次最大值乘時(shí)間不同時(shí)，特別是早班工作時(shí)間縮短時(shí)，某些原本時(shí)間跨度較大的早班乘務(wù)任務(wù)被提前停止編制，使得原本后續(xù)銜接的乘務(wù)作業(yè)段可以被其余乘務(wù)作業(yè)段選擇，增加了剩余乘務(wù)作業(yè)段的備選方案，進(jìn)而提升了整個(gè)乘務(wù)計(jì)劃的效率。

由表4 可知，代入最優(yōu)參數(shù)得到的乘務(wù)方案中各班次類(lèi)型工作時(shí)長(zhǎng)都滿(mǎn)足參數(shù)要求，方案是可行的。

5 結(jié)論

以最大化一日內(nèi)所有乘務(wù)員值乘效率為目標(biāo)，建立了乘務(wù)任務(wù)配對(duì)模型，并設(shè)計(jì)啟發(fā)式算法進(jìn)行求解，以成都地鐵5 號(hào)線(xiàn)數(shù)據(jù)進(jìn)行驗(yàn)證分析，得到以下結(jié)論。

（1）在編制乘務(wù)任務(wù)時(shí)，不同的參數(shù)設(shè)置會(huì)不同程度地影響整個(gè)乘務(wù)計(jì)劃的編制，特別是當(dāng)乘務(wù)作業(yè)段間的最長(zhǎng)休息時(shí)間由60 min 變?yōu)?0 min 時(shí)，乘務(wù)任務(wù)效率顯著提升。

（2）與文獻(xiàn)[5]、文獻(xiàn)[10]中既有參數(shù)相比，代入模型求得的最優(yōu)參數(shù)得到的乘務(wù)任務(wù)能夠在滿(mǎn)足既有約束前提下有效提高所有乘務(wù)員的值乘效率，且設(shè)計(jì)的算法求解效率和穩(wěn)定性較高，能夠滿(mǎn)足實(shí)際工作中對(duì)排班計(jì)劃編制的實(shí)時(shí)性要求。

（3）依據(jù)模型設(shè)計(jì)的遺傳禁忌混合搜索算法可以針對(duì)實(shí)際需求對(duì)各時(shí)間參數(shù)作更為具體細(xì)致的劃分，進(jìn)而進(jìn)行求解，具有很好的適用性。