葉玉玲，何嘉棋

（1.同濟(jì)大學(xué)交通運(yùn)輸工程學(xué)院，上海 201804; 2.同濟(jì)大學(xué)道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室，上海 201804）

貨運(yùn)機(jī)車乘務(wù)交路是指貨運(yùn)機(jī)車乘務(wù)組（又稱機(jī)班）擔(dān)當(dāng)值乘任務(wù)的周轉(zhuǎn)區(qū)段，可表示為機(jī)車乘務(wù)組從乘務(wù)基地（一般為機(jī)務(wù)段所在站）至乘務(wù)換乘站 （一般為折返段所在站） 之間往返的線路區(qū)段。 貨運(yùn)機(jī)車乘務(wù)交路計(jì)劃的編制不僅影響貨運(yùn)列車能否按計(jì)劃行車， 還關(guān)系到乘務(wù)工作效率和運(yùn)輸經(jīng)濟(jì)效益。 目前我國(guó)貨運(yùn)機(jī)車乘務(wù)交路以機(jī)務(wù)段管理人員憑人工經(jīng)驗(yàn)編制為主， 需要花費(fèi)較長(zhǎng)的時(shí)間，有時(shí)難以得到較優(yōu)方案，甚至產(chǎn)生機(jī)車乘務(wù)超勞、 值乘任務(wù)不均衡、 乘務(wù)資源浪費(fèi)等問題。 而且當(dāng)鐵路運(yùn)輸市場(chǎng)需求或線路條件發(fā)生變化時(shí)，列車運(yùn)行圖需要進(jìn)行不定期調(diào)整，機(jī)車乘務(wù)計(jì)劃也需要同步調(diào)整，人工編制方法難以適應(yīng)。 利用計(jì)算機(jī)技術(shù)輔助編制貨運(yùn)機(jī)車乘務(wù)交路計(jì)劃，對(duì)于提高乘務(wù)工作效率和降低鐵路運(yùn)輸企業(yè)成本具有重要的現(xiàn)實(shí)意義。

國(guó)內(nèi)外學(xué)者在航空運(yùn)輸[1-2]、鐵路運(yùn)輸[3-9]、城市公交[10-11]等領(lǐng)域都開展了有關(guān)乘務(wù)計(jì)劃的研究。 但因各種運(yùn)輸方式特點(diǎn)不同且各國(guó)運(yùn)輸組織制度存在差異， 乘務(wù)交路的編制流程和約束條件也有所不同， 難以直接用來解決我國(guó)鐵路貨運(yùn)機(jī)車乘務(wù)交路問題。 國(guó)內(nèi)有關(guān)鐵路乘務(wù)交路計(jì)劃問題的理論研究主要集中在客運(yùn)專線上，王媛媛等[12]考慮了乘務(wù)繼乘的情況， 將乘務(wù)交路編制問題看作特殊的旅行商問題（traveling salesman problem，TSP）問題，設(shè)計(jì)了改進(jìn)蟻群算法進(jìn)行求解；張哲銘等[13]基于單一循環(huán)乘務(wù)值乘計(jì)劃提出了閉環(huán)排班和非閉環(huán)排班的概念， 研究了結(jié)合乘務(wù)休息規(guī)則的排班方案；符卓等[14]研究了帶立即折返的高速動(dòng)車組乘務(wù)交路優(yōu)化問題。

現(xiàn)有研究在貨運(yùn)機(jī)車乘務(wù)交路方面，主要結(jié)合線路實(shí)際情況或機(jī)車交路對(duì)乘務(wù)機(jī)班存在問題進(jìn)行定性分析[15-16]，缺乏對(duì)貨運(yùn)乘務(wù)交路計(jì)算機(jī)編制方法的量化研究。

因此，在借鑒鐵路客運(yùn)乘務(wù)交路編制方法的基礎(chǔ)上， 考慮貨運(yùn)機(jī)車乘務(wù)的實(shí)際工作要求和特點(diǎn)，研究貨運(yùn)機(jī)車乘務(wù)交路計(jì)劃的編制方法，構(gòu)建貨運(yùn)機(jī)車乘務(wù)交路編制優(yōu)化模型，并設(shè)計(jì)相應(yīng)的求解算法，為鐵路運(yùn)營(yíng)企業(yè)實(shí)現(xiàn)計(jì)算機(jī)輔助編制貨運(yùn)機(jī)車乘務(wù)交路提供理論依據(jù)。

1 乘務(wù)交路計(jì)劃

乘務(wù)交路計(jì)劃編制 （crew scheduling problem，CSP）是鐵路運(yùn)輸組織的一個(gè)重要問題，受到列車運(yùn)行圖、沿線車站性質(zhì)、機(jī)車交路和乘務(wù)規(guī)則等多因素影響[17-18]。目前我國(guó)貨運(yùn)機(jī)車乘務(wù)形式為非立即折返型，即機(jī)班從乘務(wù)基地出勤后，擔(dān)當(dāng)去程乘務(wù)片段的值乘任務(wù)到達(dá)換乘站， 按乘務(wù)作業(yè)時(shí)間標(biāo)準(zhǔn)間休后， 再擔(dān)當(dāng)返程乘務(wù)片段的值乘任務(wù)返回乘務(wù)基地。 具體的貨運(yùn)機(jī)車乘務(wù)交路計(jì)劃編制步驟如下。

1） 數(shù)據(jù)收集。 獲取貨運(yùn)列車運(yùn)行信息、機(jī)車交路圖，確定乘務(wù)基地、折返段及可換乘的車站，明確乘務(wù)基地的任務(wù)范圍，梳理機(jī)車乘務(wù)員的工作時(shí)間和休息時(shí)間要求。

2） 劃分值乘片段。 結(jié)合貨運(yùn)機(jī)車交路信息，選擇合適的乘務(wù)制度和值乘模式，根據(jù)乘務(wù)一次連續(xù)工作時(shí)間標(biāo)準(zhǔn)，以可換乘的車站為分割點(diǎn)，將列車運(yùn)行線劃分為若干個(gè)值乘片段。

3） 組成乘務(wù)交路。根據(jù)乘務(wù)規(guī)則，考慮工作、休息時(shí)間標(biāo)準(zhǔn)約束和機(jī)務(wù)本段、 折返段的空間約束，一般按先到先走的原則，將值乘片段組合成乘務(wù)交路，作為貨運(yùn)機(jī)班一次乘務(wù)工作的內(nèi)容。

4） 組成乘務(wù)交路循環(huán)?？紤]到機(jī)車乘務(wù)員對(duì)所駕駛機(jī)車類型和線路的熟悉程度，原則上一個(gè)機(jī)班通常安排在固定的乘務(wù)交路循環(huán)中值乘；因此需要將區(qū)段內(nèi)的乘務(wù)交路組成若干個(gè)乘務(wù)交路循環(huán)，由若干個(gè)機(jī)班依次循環(huán)執(zhí)行。 貨運(yùn)乘務(wù)交路循環(huán)的接續(xù)主要考慮擔(dān)當(dāng)兩相鄰乘務(wù)交路之間乘務(wù)員在本段的休息時(shí)間標(biāo)準(zhǔn)，優(yōu)化乘務(wù)交路循環(huán)順序能有效縮短乘務(wù)的排班周期。

CSP 問題的最終目標(biāo)是確定乘務(wù)交路循環(huán)，保證乘務(wù)交路集合完全覆蓋全部值乘片段和列車運(yùn)行線[19]。 根據(jù)乘務(wù)交路計(jì)劃的編制步驟，在步驟1）、步驟2）確定的條件下，考慮乘務(wù)交路及其循環(huán)的組合方法，構(gòu)建乘務(wù)交路編制優(yōu)化模型。

2 優(yōu)化模型構(gòu)建

鐵路貨運(yùn)機(jī)車乘務(wù)調(diào)度成本主要受機(jī)班數(shù)量決定，而值乘時(shí)間占總工作時(shí)間的比例是決定機(jī)班數(shù)量的重要因素。 也就是說在符合勞動(dòng)時(shí)間標(biāo)準(zhǔn)的前提下，乘務(wù)值乘時(shí)間比例越高，說明乘務(wù)調(diào)度越充分，所需要的總機(jī)班數(shù)量也就越少。 為了降低乘務(wù)交路編制問題的復(fù)雜性，以乘務(wù)交路非值乘時(shí)間最少， 即值乘片段間的接續(xù)時(shí)間最少為模型目標(biāo)。根據(jù)乘務(wù)交路計(jì)劃的編制步驟，模型分為乘務(wù)交路問題和乘務(wù)交路循環(huán)問題，其中乘務(wù)交路問題的解為乘務(wù)交路循環(huán)問題的輸入條件， 乘務(wù)交路問題主要求解機(jī)班一次乘務(wù)工作的內(nèi)容， 乘務(wù)交路循環(huán)問題是確定機(jī)班執(zhí)行各交路任務(wù)的值乘順序。

2.1 乘務(wù)交路問題

對(duì)于若干個(gè)值乘片段i=1，2，…，n，構(gòu)成乘務(wù)交路需要滿足的條件為[20]

1） 第一個(gè)值乘片段的起始地點(diǎn)與最后一個(gè)值乘片段的結(jié)束地點(diǎn)為同一機(jī)務(wù)本段；

2） 相鄰兩值乘片段i，j， 前一值乘片段的結(jié)束地點(diǎn)sdi與后一值乘片段的起始地點(diǎn)soj相同；

3）相鄰兩值乘片段i，j，前一值乘片段的結(jié)束時(shí)間tdi小于后一值乘片段的起始時(shí)間toj，且接續(xù)時(shí)間滿足乘務(wù)在外段休息時(shí)間標(biāo)準(zhǔn)。

通過構(gòu)造值乘片段之間接續(xù)時(shí)間tij（單位：min）的n 階矩陣來表示各個(gè)值乘片段之間的接續(xù)可能性。

式中：M 為一個(gè)足夠大的正整數(shù)， 表示值乘片段i，j之間由于不滿足地點(diǎn)接續(xù)性而不能組合成乘務(wù)交路。

根據(jù)乘務(wù)休息時(shí)間約束， 機(jī)車乘務(wù)員在本段的休息時(shí)間每次不應(yīng)少于16 h，即960 min；在外段調(diào)休的時(shí)間不得小于5 h，即300 min；在外段駐班休息時(shí)間不得少于10 h，即600 min；輪乘制外段換班繼乘休息時(shí)間不得少于6 h， 即360 min。需要根據(jù)值乘片段i 的結(jié)束地點(diǎn)和換班方式對(duì)tij進(jìn)行調(diào)整。

式中：t′ij+1 440 表示值乘片段j 可與第2 天的值乘片段i 接續(xù)。

因此，tij≠M(fèi) 時(shí)說明值乘片段j 與值乘片段i接續(xù)間有一定的休息時(shí)間， 有可能形成乘務(wù)交路。為了最小化乘務(wù)交路所需要的總機(jī)班數(shù)，保證乘務(wù)在外段停留時(shí)間越少越好， 即去程值乘片段i 與回程值乘片段j 的接續(xù)時(shí)間tij越小越好， 在編制乘務(wù)交路時(shí)遵循乘務(wù)先到先走原則，即先到達(dá)外段的去程值乘片段優(yōu)先接續(xù)最早出發(fā)的回程值乘片段，形成最優(yōu)乘務(wù)交路方案。

2.2 乘務(wù)交路循環(huán)問題

由于單循環(huán)排班方式有利于均衡乘務(wù)員之間的工作量以及提高機(jī)班對(duì)值乘機(jī)車類型和值乘區(qū)段的熟悉程度，在我國(guó)貨運(yùn)機(jī)車乘務(wù)領(lǐng)域可操作性強(qiáng)。 本文采用單循環(huán)的乘務(wù)排班方式，即將某乘務(wù)基地管轄范圍內(nèi)所有的乘務(wù)交路，在符合乘務(wù)規(guī)則的條件下組成一個(gè)有序的循環(huán)，乘務(wù)員按照乘務(wù)交路循環(huán)的順序依次值乘。 對(duì)于同一乘務(wù)基地而言，任意2 個(gè)乘務(wù)交路p，q 的起始和結(jié)束地點(diǎn)相同，滿足空間接續(xù)性。

通過構(gòu)建有向圖以更好地描述乘務(wù)交路循環(huán)問題，如圖1 所示。 設(shè)G=（V，E）為有向圖，V 表示有向圖的頂點(diǎn)集合，E 表示有向圖的弧集合，Vp（p=1，2，…，n）表示第p 條乘務(wù)交路，?。╬，q）∈E 表示乘務(wù)交路p 與乘務(wù)交路q 接續(xù)關(guān)系， 弧上的權(quán)值tpq（單位：min） 表示乘務(wù)交路p 與乘務(wù)交路q 之間的接續(xù)時(shí)間。 可構(gòu)建接續(xù)時(shí)間矩陣Tpq，表示乘務(wù)交路p 與乘務(wù)交路間q 的接續(xù)時(shí)間，為非對(duì)稱矩陣。

圖1 乘務(wù)交路循環(huán)有向圖Fig.1 Directed graph of crew routing cycle

對(duì)于單循環(huán)的乘務(wù)排班方式，尋求乘務(wù)交路循環(huán)最優(yōu)方案的實(shí)質(zhì)，是找到各個(gè)乘務(wù)交路之間的接續(xù)次序，同時(shí)保證總接續(xù)時(shí)間最短，可視為尋找該有向圖內(nèi)經(jīng)過所有頂點(diǎn)的最短路徑。 乘務(wù)交路循環(huán)問題可轉(zhuǎn)化為非對(duì)稱旅行商問題[21]。

對(duì)于若干乘務(wù)交路p=1，2，…，n（p∈V），不同交路之間的接續(xù)時(shí)間為tpq，定義決策變量xpq

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

3.1 基于先到先走的遍歷搜索算法設(shè)計(jì)

當(dāng)一個(gè)乘務(wù)交路去程的值乘片段i 與之可接續(xù)的回程值乘片段不止一個(gè)時(shí)，為了最小化所需要的總機(jī)班數(shù)，需要保證乘務(wù)在外段停留時(shí)間越少越好， 即去程值乘片段i 與回程值乘片段j 的接續(xù)時(shí)間tij越小越好。 在滿足機(jī)車乘務(wù)員外段休息的時(shí)間標(biāo)準(zhǔn)下，基于先到先走原則，即先到達(dá)外段的去程值乘片段優(yōu)先接續(xù)最早出發(fā)的回程值乘片段，設(shè)計(jì)求解乘務(wù)交路問題的遍歷搜索算法，如圖2 所示。

圖2 基于先到先走原則的遍歷搜索算法流程圖Fig.2 Flowchart of the traversal searching algorithm based on “first come first serve” principle

步驟1 輸入值乘片段、接續(xù)時(shí)間矩陣Tij和機(jī)務(wù)段所在站；

步驟2 將出發(fā)地點(diǎn)為本段的值乘片段按退勤時(shí)間由早到晚排序，并組成集合S；

步驟3 取集合S 中的第一個(gè)值乘片段進(jìn)行判斷；

步驟4 若片段x 的接續(xù)時(shí)間全為0，則按順序取下一片段重新判斷；若不是所有接續(xù)時(shí)間為0， 則找出值乘片段x 接續(xù)時(shí)間最小對(duì)應(yīng)的值乘片段j，并將值乘片段x，j 加入待選集合Un中；

步驟5 判斷片段j 的到達(dá)地點(diǎn)是否為本段，若是， 則集合Un中的值乘片段按順序組為一個(gè)乘務(wù)交路；若否，則返回步驟4 繼續(xù)尋找片段j 接續(xù)時(shí)間最小的片段；

步驟6 直至集合S 中所有的片段都被遍歷，則生產(chǎn)乘務(wù)交路集合V。

3.2 遺傳算法設(shè)計(jì)

與旅行商問題相似， 乘務(wù)交路循環(huán)問題是NP難的組合優(yōu)化問題，當(dāng)交路數(shù)目不是很多時(shí)，可采用精確算法求解；對(duì)于乘務(wù)交路數(shù)目較多、問題規(guī)模較大、方案編制較為復(fù)雜的情況，選擇啟發(fā)式算法有利于提高計(jì)算效率、減少計(jì)算時(shí)間，得到較優(yōu)的全局解[22]。 本文設(shè)計(jì)了遺傳算法對(duì)乘務(wù)交路循環(huán)問題進(jìn)行求解，算法流程如下。

1） 編碼個(gè)體。一個(gè)乘務(wù)交路循環(huán)可直接以交路的次序來表示，例如包含6 個(gè)乘務(wù)交路的循環(huán)可表示為[3，4，1，2，5，6]，即循環(huán)從交路3 開始依次經(jīng)歷交路4，1，2，5，6，然后重新值乘交路3，滿足所有交路均遍歷一次且僅一次。

2） 生成初始種群。隨機(jī)產(chǎn)生一組包含n 個(gè)個(gè)體的初始種群，每個(gè)個(gè)體代表一個(gè)可行解。

3） 計(jì)算適應(yīng)度。乘務(wù)交路循環(huán)問題為最小化問題，可以取目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)，符合適應(yīng)度越高、選擇概率越大的要求。 考慮到最優(yōu)解可能有多個(gè)，為了使乘務(wù)交路的接續(xù)時(shí)間分布盡量均衡， 適應(yīng)度函數(shù)同時(shí)考慮了接續(xù)時(shí)間方差的大小，具體如下

式中：F 為適應(yīng)度函數(shù)；Z 為2.2 節(jié)中乘務(wù)交路循環(huán)問題的目標(biāo)函數(shù)；V（tpq）為該乘務(wù)交路循環(huán)的接續(xù)時(shí)間方差；C1，C2為參數(shù)，根據(jù)Z 和V（tpq）的數(shù)量級(jí)來確定。

4） 選擇。 采用輪盤賭選擇法對(duì)種群進(jìn)行選擇。取適應(yīng)度的指數(shù)倍為計(jì)算依據(jù)，以擴(kuò)大個(gè)體間的優(yōu)劣差距。

5） 交叉。 根據(jù)交叉概率Uc對(duì)個(gè)體交叉進(jìn)行部分匹配交叉操作，保證形成的子代基因無沖突。

6） 變異。 根據(jù)變異概率Uv在變異個(gè)體中隨機(jī)產(chǎn)生2 個(gè)變異點(diǎn)，進(jìn)行逆轉(zhuǎn)變異操作。

7） 取代。 經(jīng)過選擇、交叉、變異后，產(chǎn)生的子代種群代替換原有父代種群，利用子代繼續(xù)重復(fù)步驟3）至步驟6），直至迭代次數(shù)N 大于500 或連續(xù)50代的適應(yīng)度未改變，則停止迭代，最終得到的種群中適應(yīng)度最好的個(gè)體為該問題的最優(yōu)解。

4 算例分析

選取某鐵路機(jī)務(wù)段為研究對(duì)象，該機(jī)務(wù)段管轄范圍如圖3 所示，包括6 個(gè)技術(shù)站，其中車站C 為貨運(yùn)車間Ⅰ所在站，E 為貨運(yùn)車間Ⅱ所在站，均為乘務(wù)基地。

圖3 某機(jī)務(wù)段的管轄范圍Fig.3 Jurisdiction of the locomotive depot

貨運(yùn)車間Ⅰ負(fù)責(zé)A～E 的直達(dá)、直通和區(qū)段貨物列車牽引任務(wù)， 以C 站為支點(diǎn)實(shí)行半循環(huán)制式，上行列車機(jī)車乘務(wù)在C 站直通不換班，下行列車乘務(wù)在C 站換班。 貨運(yùn)車間Ⅱ負(fù)責(zé)E～F 的直達(dá)、直通和區(qū)段貨物列車牽引任務(wù)，以E 站為支點(diǎn)，實(shí)行肩回制。 下面以貨運(yùn)車間Ⅱ的乘務(wù)計(jì)劃為例具體說明。

1） 數(shù)據(jù)收集。根據(jù)《鐵路機(jī)車運(yùn)用管理規(guī)則》規(guī)定，貨運(yùn)機(jī)車乘務(wù)每月應(yīng)安排1～2 次不少于48～72 h的大休時(shí)間； 在E 站的換班休息時(shí)間每次不少于16 h，即960 min；在F 站的換班休息時(shí)間每次不少于6 h，即360 min；月度大休時(shí)間最小值為48 h，即2 880 min。

2） 劃分值乘片段。 由于E～F 區(qū)段的最長(zhǎng)運(yùn)行時(shí)間不超過乘務(wù)最長(zhǎng)工作時(shí)間標(biāo)準(zhǔn)， 可將該區(qū)段內(nèi)每列車視為一個(gè)值乘片段。 假定出勤時(shí)間比列車出發(fā)時(shí)間提前70 min， 退勤比列車到達(dá)時(shí)間晚30 min，出退勤時(shí)間主要用于完成乘務(wù)報(bào)到、列車運(yùn)行預(yù)告、接受派班、領(lǐng)取和歸還值乘物件、準(zhǔn)備機(jī)車出庫(kù)、交接班等作業(yè)。 該區(qū)段的貨物列車信息和值乘片段信息見表1。

3） 求解乘務(wù)交路方案。 根據(jù)2.1 節(jié)值乘片段接續(xù)時(shí)間的定義，計(jì)算表1 值乘片段的接續(xù)時(shí)間矩陣Tij，見表2。

表1 貨運(yùn)車間Ⅱ的列車信息和值乘片段信息Tab.1 Trains and crew duties of the railway freight workshop Ⅱ

表2 貨運(yùn)車間Ⅱ的值乘片段間接續(xù)時(shí)間矩陣Tab.2 Connection time matrix of crew duty fragments of the railway freight workshop Ⅱmin

利用3.1 節(jié)基于先到先走的遍歷搜索算法，得到表3 中編號(hào)1～16 的交路方案。 由于貨物列車并非成對(duì)開行， 在求解時(shí)會(huì)存在一些值乘片段沒有回程片段接續(xù)的情況，無法形成完整的乘務(wù)交路。在實(shí)際工作中有兩種處理辦法：一是便乘，即對(duì)乘務(wù)員進(jìn)行異地調(diào)度， 使其在不擔(dān)任值乘任務(wù)的情況下， 從上一結(jié)束車站乘車至下一任務(wù)的起始車站，一般會(huì)產(chǎn)生額外支出；二是調(diào)整值乘范圍，即安排這些乘務(wù)員繼乘其它區(qū)段的貨物列車牽引任務(wù)，但這對(duì)乘務(wù)員的業(yè)務(wù)能力要求較高，他們需要熟悉不同區(qū)段的線路情況甚至需要操縱不同類型的機(jī)車。

貨運(yùn)車間Ⅱ還有4 個(gè)無法成對(duì)的值乘片段，根據(jù)便乘規(guī)則， 按基于先到先走原則的遍歷搜索算法，得到表3 中編號(hào)17～20 的交路方案。

4） 求解乘務(wù)交路循環(huán)方案。 根據(jù)2.2 節(jié)乘務(wù)交路接續(xù)時(shí)間的定義， 計(jì)算表3 中20 個(gè)乘務(wù)交路的接續(xù)時(shí)間矩陣Tpq，見表4。

表3 貨運(yùn)車間Ⅱ的乘務(wù)交路集合Tab.3 Set of crew routing of the railway freight workshop Ⅱ

表4 貨運(yùn)車間Ⅱ的乘務(wù)交路接續(xù)時(shí)間矩陣Tab.4 Connection time matrix of crew routing of the railway freight workshop Ⅱ min

在利用3.2 節(jié)遺傳算法求解乘務(wù)交路循環(huán)方案時(shí)，規(guī)定遺傳種群內(nèi)個(gè)體個(gè)數(shù)n=50，適應(yīng)度函數(shù)參數(shù)C1=106，C2=0.01， 并取適應(yīng)度的10 次冪來計(jì)算累積概率， 以放大不同個(gè)體間的適應(yīng)度值差距。 設(shè)交叉概率Uc=0.7， 變異概率Uv=0.005。遺傳算法適應(yīng)度變化曲線如圖4 所示，當(dāng)?shù)螖?shù)N=364 時(shí)開始收斂。 乘務(wù)交路循環(huán)本段接續(xù)時(shí)間總和變化曲線如圖5 所示， 迭代至42 代開始本段接續(xù)時(shí)間總和TW趨于穩(wěn)定。 得到最 優(yōu) 乘 務(wù) 交 路 循 環(huán) 方 案 為：1 →20 →17 →14 →10→11→13→15→9→6→5→4→18→12→8 →2→16→7→3→19。

圖4 遺傳算法適應(yīng)度變化曲線Fig.4 Fitness variation of genetic algorithm

圖5 乘務(wù)交路循環(huán)本段接續(xù)時(shí)間總和變化曲線Fig.5 Total connecting time variation at locomotive depot of the crew routing cycle

該循環(huán)中， 乘務(wù)值乘時(shí)間TZ為15 065 min，外段休息時(shí)間TB為11 407 min， 本段休息時(shí)間TW為25 213 min，乘務(wù)交路循環(huán)總時(shí)間T 為51 685 min。

根據(jù)勞動(dòng)強(qiáng)度要求和月大休時(shí)間標(biāo)準(zhǔn)，可計(jì)算乘務(wù)交路循環(huán)方案的月循環(huán)次數(shù)和機(jī)班配備數(shù)。

式中：P 為機(jī)班配備數(shù)；β 為乘務(wù)交路循環(huán)每個(gè)月可循環(huán)的次數(shù)；取β1，β2中的較小值；C 為月平均工作時(shí)間最大值，根據(jù)《中華人民共和國(guó)勞動(dòng)法》取176 h，即10 560 min；TM為剔除一次48 h 大休時(shí)間后的月時(shí)間換算值，一個(gè)月按30 d 計(jì)算，取40 320 min。計(jì)算得到，β＝β1＝0.701，完成該乘務(wù)交路循環(huán)所需要配備的機(jī)班43 個(gè)。

同樣的計(jì)算方法可得到貨運(yùn)車間Ⅰ的乘務(wù)編制計(jì)劃，結(jié)果見表5，完成該乘務(wù)交路循環(huán)方案共需要配備124 個(gè)機(jī)班。

表5 貨運(yùn)車間Ⅰ的乘務(wù)交路循環(huán)方案Tab.5 Result of crew routing cycle of the freight workshop Ⅰ

5） 結(jié)果分析。 通過分析上述算例的結(jié)果，得出以下結(jié)論。

①該模型能有效節(jié)省貨運(yùn)機(jī)車乘務(wù)資源。利用優(yōu)化模型所計(jì)算得到的貨運(yùn)機(jī)班數(shù)量相比原有人工經(jīng)驗(yàn)方案的要少，2 個(gè)車間分別有效節(jié)省了22.5%和17.6%的乘務(wù)資源，具體見表6。

表6 乘務(wù)交路編制結(jié)果對(duì)比Tab.6 Results contrast of crew scheduling

②該算法能有效提高乘務(wù)交路編制效率。上述算例利用本文所設(shè)計(jì)的基于先到先走遍歷搜素算法和遺傳算法，平均用時(shí)3.35 s 能求得該優(yōu)化模型的乘務(wù)交路計(jì)劃編制方案，且收斂性較好，相比目前我國(guó)鐵路機(jī)務(wù)段現(xiàn)場(chǎng)工作的人工經(jīng)驗(yàn)編制方法，編制效率和質(zhì)量大大提升。

③單一交路循環(huán)能均衡乘務(wù)工作量并減少機(jī)班配備數(shù)。 本模型所采用的單一乘務(wù)交路循環(huán)方法，相比各乘務(wù)交路獨(dú)立循環(huán)或若干乘務(wù)交路成組循環(huán)的方法，能保證同一貨運(yùn)車間的機(jī)車乘務(wù)員同屬一個(gè)循環(huán)組，組內(nèi)值乘時(shí)長(zhǎng)、休息時(shí)間、月大休時(shí)間相同，對(duì)于均衡各機(jī)車乘務(wù)員的工作量和收入水平具有實(shí)際意義。 同時(shí)，單一乘務(wù)交路循環(huán)方法能盡可能地減少乘務(wù)交路的接續(xù)時(shí)間，整體上減少總循環(huán)時(shí)長(zhǎng)，可相應(yīng)地減少乘務(wù)組的配備數(shù)。

5 結(jié)論

1） 提出了以乘務(wù)員非值乘時(shí)間最少為優(yōu)化目標(biāo)的乘務(wù)交路計(jì)劃編制優(yōu)化模型，符合鐵路貨運(yùn)機(jī)車乘務(wù)交路計(jì)劃編制問題的原理和流程，考慮了機(jī)班工時(shí)符合勞動(dòng)管理規(guī)定、乘務(wù)交路的時(shí)間和空間約束，滿足乘務(wù)交路覆蓋所有車次。

2） 根據(jù)模型特點(diǎn)分別設(shè)計(jì)了基于先到先走原則遍歷搜索算法和遺傳算法，確定求解思路和具體步驟，能有效提高貨運(yùn)部門乘務(wù)交路編制的效率。

3） 以某鐵路貨運(yùn)機(jī)務(wù)段為算例，驗(yàn)證了本文提出的模型和算法可以完整求解鐵路貨運(yùn)乘務(wù)交路計(jì)劃方案，并且與人工經(jīng)驗(yàn)方法相比，有效減少了貨運(yùn)機(jī)班的配備數(shù)，具有一定的實(shí)際意義。