王興慧，頡俊杰

（蘭州交通大學 交通運輸學院，甘肅 蘭州730070）

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

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

1 影響排班計劃的主要因素

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

1.1 乘務交路

乘務交路是排班計劃的基礎，交路主要包括兩個規(guī)則:交路時間規(guī)則和交路空間規(guī)則。

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

表1 乘務時間規(guī)則約束表

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

1.2 乘務制度方式

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

2 基于均衡性的機車乘務排班計劃編制

2.1 排班問題分析

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

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

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

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

2.2.1 排班問題的目標

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

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

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

基于以上問題的考慮，建立模型時應考慮以下兩個方面:

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

2）合理安排乘務員的工作與休息時間，盡量使乘務員每次的休息時間與所值乘交路的勞動量相協(xié)調。

2.2.2 排班問題的約束條件

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

1）乘務排班過程中每個交路僅有一個緊前交路；

2）乘務排班過程中每個交路僅有一個緊后交路；

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

2.2.3 乘務排班模型的建立

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

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

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

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

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

2.3 排班計劃模型求解

2.3.1 算法的選取

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

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

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

2.3.2 算法步驟說明

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

圖1 樹的構建

2.3.2.1 步驟順序

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

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

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

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

2.3.2.2 大休時間添加流程

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

圖2 休息時間添加流程

3 算例分析

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

表3 交路時間表

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

表4 時間接續(xù)表

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

圖3 循環(huán)交路

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

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

表5 排班計劃表

4 結 論

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

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

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

［2］ 李成兵，魯工圓，郭倩倩，等.動車組乘務員運用計劃的均衡性研究［J］.內燃機車，2009（12）:31－33.

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

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

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

［6］ 柴小樹.動車組乘務計劃編制方法研究［D］.長沙:中南大學，2013.

［7］ 李志鵬.鐵路調車機車運用問題探討［J］.交通科技與經(jīng)濟，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.