王興慧，頡俊杰

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州730070）

隨著鐵路建設(shè)的迅速發(fā)展，鐵路實(shí)現(xiàn)了前所未有的高速度，但鐵路在運(yùn)營過程中安全隱患卻始終存在，影響鐵路安全的因素很多，其中的機(jī)車乘務(wù)員是一個(gè)主要因素，作為機(jī)車的駕馭人，由于機(jī)車乘務(wù)員疲勞而引發(fā)的事故比較常見，機(jī)車乘務(wù)人員的技術(shù)高低以及工作狀態(tài)的好壞直接影響到鐵路行車的安全，因此，為了保證行車安全，調(diào)度人員以及排班人員要高度重視機(jī)車乘務(wù)人員的工作狀態(tài)，深入研究排班計(jì)劃理論與編制方法。一個(gè)好的排班計(jì)劃對于調(diào)動(dòng)工作人員的工作熱情、提高生產(chǎn)效率具有積極作用，能夠給企業(yè)創(chuàng)造巨大的財(cái)富。

在現(xiàn)有的乘務(wù)排班方法中，李成兵利用熵評價(jià)排班計(jì)劃的均衡性，并且給出了均衡度的計(jì)算方法，為月排班計(jì)劃奠定了理論基礎(chǔ)。趙鵬利用SE方法實(shí)現(xiàn)排班的自動(dòng)化，大多數(shù)研究者都將排班問題看作是旅行商（TSP）問題，將乘務(wù)基地作為城市，乘務(wù)基地之間的接續(xù)看作城市之間的銜接，采用了經(jīng)典的遺傳算法或是在遺傳算法基礎(chǔ)上進(jìn)行改進(jìn)的算法求解。

1 影響排班計(jì)劃的主要因素

乘務(wù)排班計(jì)劃是合理安排乘務(wù)員的基礎(chǔ)，在交路確定的條件下，調(diào)度人員根據(jù)相關(guān)規(guī)定對乘務(wù)員在什么時(shí)間和地點(diǎn)值乘哪輛機(jī)車出發(fā)，在某時(shí)某地?fù)Q乘另外一輛機(jī)車或是退乘都做出了詳細(xì)安排，以確保列車準(zhǔn)點(diǎn)、高效地運(yùn)行，排班時(shí)應(yīng)考慮的因素如下:

1.1 乘務(wù)交路

乘務(wù)交路是排班計(jì)劃的基礎(chǔ)，交路主要包括兩個(gè)規(guī)則:交路時(shí)間規(guī)則和交路空間規(guī)則。

1）交路時(shí)間規(guī)則約束:值乘乘務(wù)交路時(shí)，前一個(gè)值乘交路的到達(dá)時(shí)間早于后一個(gè)值乘交路的出發(fā)時(shí)間，使交路的接續(xù)順序合理。此外，還必須滿足規(guī)定的乘務(wù)時(shí)間規(guī)則，這是判斷交路是否可行的必要條件，具體的時(shí)間規(guī)則約束如表1所示。

表1 乘務(wù)時(shí)間規(guī)則約束表

2）交路空間規(guī)則約束:在值乘交路時(shí)，乘務(wù)員值乘交路的到達(dá)地點(diǎn)與下一接續(xù)的交路出發(fā)地點(diǎn)必須是同一地點(diǎn)，這樣保證了空間連續(xù)性，還應(yīng)該考慮乘務(wù)員的休息地點(diǎn)問題，盡量使乘務(wù)員的出發(fā)地點(diǎn)與結(jié)束地點(diǎn)在同一個(gè)乘務(wù)地點(diǎn)。

1.2 乘務(wù)制度方式

現(xiàn)有的機(jī)車乘務(wù)員值乘方式大多采用的是輪乘制，這種方式一方面有利于排班人員合理安排乘務(wù)人員的工作和休息時(shí)間，使得排班靈活；另一方面可以不用考慮機(jī)車因等待乘務(wù)員而浪費(fèi)時(shí)間，提高了機(jī)車效率，同時(shí)也增加了對乘務(wù)員的使用效率。

2 基于均衡性的機(jī)車乘務(wù)排班計(jì)劃編制

2.1 排班問題分析

乘務(wù)排班計(jì)劃是在乘務(wù)交路計(jì)劃制定好的前提下進(jìn)行的，即每天給每條交路安排好乘務(wù)人員，形成乘務(wù)組連續(xù)值乘的排班計(jì)劃。但在排班過程中，交路不同，交路的長度也不相同，若將每條交路固定給特定的一組或幾組乘務(wù)員值乘，那么各個(gè)乘務(wù)組之間的工作時(shí)間也不一樣，必然會(huì)出現(xiàn)乘務(wù)組間的不均衡現(xiàn)象。因此，基于上述原因的考慮，在乘務(wù)交路數(shù)量一定的情況下，將所有交路組合成一個(gè)有序回路，使乘務(wù)員根據(jù)這個(gè)回路循環(huán)進(jìn)行輪換工作，這種排班方式大大消除了乘務(wù)組間由于擔(dān)當(dāng)交路不同而產(chǎn)生的工作量不均衡問題，這種方式被稱為單循環(huán)乘務(wù)排班。

在單循環(huán)乘務(wù)排班方式中，排班人員根據(jù)乘務(wù)員所承擔(dān)的工作量，合理添加乘務(wù)員的休息時(shí)間，表2是一個(gè)短周期的單循環(huán)排班示意表。

表2 單循環(huán)排班示意表

2.2 單循環(huán)乘務(wù)排班計(jì)劃模型的建立

2.2.1 排班問題的目標(biāo)

通過對單循環(huán)乘務(wù)排班計(jì)劃問題的分析，如果將值乘的每條交路看成是旅行商問題中的城市，將交路間的接續(xù)時(shí)間看作城市與城市間的距離，距離的長度就是兩交路的接續(xù)時(shí)間，那么單循環(huán)乘務(wù)排班問題可以認(rèn)為是一個(gè)旅行商問題，目標(biāo)是尋求訪問所有回路僅一次的循環(huán)順序，使得總訪問時(shí)間最短。

其次，乘務(wù)員的使用數(shù)量也是乘務(wù)排班計(jì)劃中考慮的關(guān)鍵因素，一般情況下，乘務(wù)員的使用數(shù)量根據(jù)乘務(wù)交路計(jì)劃來確定，合理的乘務(wù)交路序列是減少乘務(wù)員數(shù)量的關(guān)鍵，但除了考慮乘務(wù)員的正常休息之外，還應(yīng)考慮一些不確定因素導(dǎo)致乘務(wù)員不能按時(shí)出乘，所以在實(shí)際的排班中，所需乘務(wù)員的數(shù)量要比乘務(wù)交路計(jì)劃所需的乘務(wù)員數(shù)量多，因此，在滿足乘務(wù)規(guī)則的基礎(chǔ)上，應(yīng)考慮怎樣縮短排班周期，使得乘務(wù)員運(yùn)用數(shù)量最少。

在單循環(huán)排班方式中，雖然消除了乘務(wù)組間工作量不均衡問題，但由于乘務(wù)交路起止時(shí)間不同，乘務(wù)員擔(dān)當(dāng)不同的乘務(wù)交路后的休息時(shí)間也不完全相同，除了規(guī)定的標(biāo)準(zhǔn)休息時(shí)間外，還會(huì)產(chǎn)生一部分冗余時(shí)間，因此，使得冗余時(shí)間更加均衡也是本文要考慮的一個(gè)關(guān)鍵問題。

基于以上問題的考慮，建立模型時(shí)應(yīng)考慮以下兩個(gè)方面:

1）尋找最優(yōu)的乘務(wù)交路順序，使得所有交路的接續(xù)時(shí)間最短，盡可能縮短乘務(wù)排班周期，減少乘務(wù)員的使用數(shù)量。

2）合理安排乘務(wù)員的工作與休息時(shí)間，盡量使乘務(wù)員每次的休息時(shí)間與所值乘交路的勞動(dòng)量相協(xié)調(diào)。

2.2.2 排班問題的約束條件

單循環(huán)乘務(wù)排班計(jì)劃的編制結(jié)果是所有乘務(wù)交路以最優(yōu)順序接續(xù)構(gòu)成的回路，在找尋最優(yōu)接續(xù)順序時(shí)，需滿足以下幾個(gè)條件:

1）乘務(wù)排班過程中每個(gè)交路僅有一個(gè)緊前交路；

2）乘務(wù)排班過程中每個(gè)交路僅有一個(gè)緊后交路；

3）乘務(wù)交路間的接續(xù)應(yīng)滿足相應(yīng)的乘務(wù)時(shí)間規(guī)則，根據(jù)交路的值乘時(shí)間長短，合理的安排正常休息和大休時(shí)間。

2.2.3 乘務(wù)排班模型的建立

根據(jù)以上問題的描述與分析，單循環(huán)機(jī)車乘務(wù)員排班計(jì)劃的約束條件主要考慮相鄰交路間的接續(xù)關(guān)系，用n表示交路數(shù)量，tij表示值乘交路i和值乘交路j間的接續(xù)時(shí)間，xij表示0～1變量，當(dāng)交路i的后面交路為j時(shí)，xij值為1，否則為0。

首先在乘務(wù)排班過程中要找出最優(yōu)的交路順序，使得所有交路的總接續(xù)時(shí)間最小，也就是說使整個(gè)排班計(jì)劃的周期最短。需要建立目標(biāo)函數(shù)，可用下列公式求得

在求解交路接續(xù)順序的過程中，每個(gè)不是起點(diǎn)的交路在排班過程中只有一個(gè)緊前交路，并且每個(gè)不是末尾的交路在排班過程中只有一個(gè)后續(xù)交路，需要滿足的條件為

在所有交路遍歷完之前，根節(jié)點(diǎn)與葉節(jié)點(diǎn)的數(shù)量必須小于交路的總個(gè)數(shù)，保證每條交路都被遍歷，且只遍歷一次，需滿足的條件為

其中還需要考慮不會(huì)出現(xiàn)交路與交路本身相接續(xù)的情況，當(dāng)i＝j(luò)時(shí)，tij＝∞，并且交路的起點(diǎn)到終點(diǎn)與交路的終點(diǎn)到起點(diǎn)不具有對稱性，因此有tij≠tji。

2.3 排班計(jì)劃模型求解

2.3.1 算法的選取

由上述模型可以看出，乘務(wù)排班問題可以看成是單目標(biāo)整數(shù)規(guī)劃問題，由于整數(shù)變量取離散的整數(shù)值，其可行解的數(shù)量是有限的，即把問題的解全部列出來，將其比較得出最優(yōu)解，但可行解的數(shù)量會(huì)隨著問題的規(guī)模增大成指數(shù)倍的增長，枚舉是不可能完成的，分枝定界法是一種求解整數(shù)規(guī)劃問題比較有效的方法。因此，文章采用分枝定界法求解單循環(huán)乘務(wù)排班計(jì)劃模型。這里將排班問題的求解分為兩部分:

1）利用分枝定界法找出總接續(xù)時(shí)間和最小的乘務(wù)交路順序；

2）根據(jù)乘務(wù)時(shí)間規(guī)則，在最優(yōu)循序的回路中添加雙休日。

2.3.2 算法步驟說明

在文章中只研究相同乘務(wù)區(qū)段的乘務(wù)交路，這樣前一個(gè)乘務(wù)交路到達(dá)地點(diǎn)與后一個(gè)乘務(wù)交路的出發(fā)地點(diǎn)始終是同一個(gè)地方，任意兩條交路之間都可以接續(xù)。以圖1為例說明算法步驟。

圖1 樹的構(gòu)建

2.3.2.1 步驟順序

Step1:先將所有交路按照出發(fā)時(shí)間從早到晚進(jìn)行順序排序，以A，B，C，D 4個(gè)點(diǎn)代表4條交路為例說明，將出發(fā)時(shí)間最早的交路A作為樹的根節(jié)點(diǎn)；

Step2:從根節(jié)點(diǎn)的交路A開始，依次從左向右深度遍歷剩下的所有交路B，C，D，每個(gè)節(jié)點(diǎn)僅加入一次，并最終回到A；

Step3:先計(jì)算出A→B→C→D→A總接續(xù)時(shí)間，并記住這個(gè)接續(xù)時(shí)間，記為tmin，每次從A遍歷，每加入一個(gè)節(jié)點(diǎn)將接續(xù)時(shí)間累加記為t，并與tmin比較，若t＞tmin，則停止遍歷，舍棄這一分支；若直至遍歷到A，依然有t＜tmin，則令tmin＝t；

Step4:依次將所有節(jié)點(diǎn)遍歷完，使tmin值最小的序列就是所要找的總接續(xù)時(shí)間最短交路序列。

2.3.2.2 大休時(shí)間添加流程

利用分枝定界法獲得一條接續(xù)時(shí)間最短的乘務(wù)交路回路，根據(jù)乘務(wù)時(shí)間規(guī)則在這條回路中添加休息時(shí)間。將乘務(wù)員從執(zhí)行第一條交路開始將工作時(shí)間進(jìn)行累加，記為tsum，將工作時(shí)間達(dá)到雙休時(shí)間上限記為T休，其中的大修累計(jì)時(shí)間參照文獻(xiàn)［6］，使T休＝1 969min，交路的總個(gè)數(shù)為n個(gè)，ji記為第i條交路，第i條交路與第j條交路的接續(xù)時(shí)間記為tij，則添加休息時(shí)間的流程如圖2所示。

圖2 休息時(shí)間添加流程

3 算例分析

以京津線的部分交路數(shù)據(jù)為例驗(yàn)證算法的有效性，表3選取了9條交路，分別給出了每條交路的出發(fā)時(shí)間和到達(dá)時(shí)間，根據(jù)出發(fā)時(shí)間和到達(dá)時(shí)間計(jì)算出每條交路的值乘總時(shí)間，具體的交路數(shù)據(jù)如表3所示。

表3 交路時(shí)間表

由上面的步驟分析可知，先將所有的交路按照順序接續(xù)，例如交路1和交路6的接續(xù)時(shí)間為19min，交路2和交路8的接續(xù)時(shí)間為1 419min，統(tǒng)計(jì)接續(xù)時(shí)間如表4所示。

表4 時(shí)間接續(xù)表

根據(jù)上述算法步驟，利用C＋＋語言編寫了程序，并在VC6.0環(huán)境下實(shí)現(xiàn)算法，得到的總接續(xù)時(shí)間最短、最優(yōu)，交路回路順序?yàn)?1→6→8→2→9→3→7→4→5→1，最短的總接續(xù)時(shí)間為5 226min。最優(yōu)交路循環(huán)如圖3所示。

圖3 循環(huán)交路

按照添加大休時(shí)間流程，給得到的循環(huán)交路圖添加休息時(shí)間，結(jié)果如表5所示。

根據(jù)單循環(huán)乘務(wù)排班思想，由表5的乘務(wù)排班計(jì)劃結(jié)果可看出，這9條乘務(wù)交路需要8組乘務(wù)員擔(dān)任。

表5 排班計(jì)劃表

4 結(jié) 論

由上述算法以及實(shí)現(xiàn)的結(jié)果可以看出，分枝定界法可以有效解決單循環(huán)乘務(wù)排班問題，合理有效地安排機(jī)車乘務(wù)員的工作休息時(shí)間，使各個(gè)乘務(wù)組的工作量達(dá)到均衡，從而保證了公平公正的原則，這對提高機(jī)車乘務(wù)員的工作效率、激發(fā)機(jī)車乘務(wù)員的工作積極性具有重要意義。

但利用分支定界法求解單循環(huán)乘務(wù)排班問題也存在一些不足，此種方法適合乘務(wù)交路規(guī)模較小的排班，當(dāng)乘務(wù)交路的數(shù)量較大時(shí)，算法的復(fù)雜度比較高，這時(shí)就要將乘務(wù)交路劃分成較小的塊來求解或者是尋找更優(yōu)的方法求解，總之，求解乘務(wù)排班問題，還有待于更深入的研究。

［1］ 田志強(qiáng).高速鐵路乘務(wù)計(jì)劃編制優(yōu)化理論與方法研究［D］.成都:西南交通大學(xué)，2011.

［2］ 李成兵，魯工圓，郭倩倩，等.動(dòng)車組乘務(wù)員運(yùn)用計(jì)劃的均衡性研究［J］.內(nèi)燃機(jī)車，2009（12）:31－33.

［3］ 王媛媛，周成晨，倪少權(quán).基于蟻群算法的客運(yùn)專線乘務(wù)交路計(jì)劃編制方法研究［J］.鐵路計(jì)算機(jī)應(yīng)用，2009（7）:11－14.

［4］ 鄭金子，苗建瑞，張君平.蟻群算法在鐵路乘務(wù)運(yùn)用計(jì)劃編制中的應(yīng)用研究［J］.鐵路計(jì)算機(jī)應(yīng)用，2010（10）:36－40.

［5］ 趙鵬，姚鳳金，張洪亮.綜合調(diào)度仿真系統(tǒng)中的機(jī)車乘務(wù)計(jì)劃的編制［J］.鐵道運(yùn)輸與經(jīng)濟(jì)，2005（3）:74－76.

［6］ 柴小樹.動(dòng)車組乘務(wù)計(jì)劃編制方法研究［D］.長沙:中南大學(xué)，2013.

［7］ 李志鵬.鐵路調(diào)車機(jī)車運(yùn)用問題探討［J］.交通科技與經(jīng)濟(jì)，2014，16（6）:47－48，52.

［8］ Shangyao Yan，Yu－Ping Tu.A network model for airline cabin crew scheduling［J］.European Journal of Operational Research，2002（140）:531－540.

［9］ Sydney C.K.Chu.Generating，scheduling and rostering of shift crew－duties，Applications at the Hong Kong International Airport［J］.European Journal of Operational Research，2007（177）:1764－1778.