基于任務均衡的乘務排班計劃優化編制方法研究

陳霽巖，潘寒川，劉志鋼，吳 強，趙 磊

（1.上海工程技術大學 城市軌道交通學院，上海 201600；2.上海地鐵第二運營有限公司，上海 200063；3.上海地鐵第二運營有限公司 質量安全部，上海 200063）

0 引言

乘務計劃是城市軌道交通運營中的重要環節，主要解決軌道交通乘務員的值乘問題。國內多數城市軌道交通的乘務計劃由各線路乘務部門編制完成，消耗時間長，變更難度大。乘務計劃分為乘務排班計劃與乘務輪轉計劃，其中乘務排班計劃根據給定的列車運行圖，將運行線根據線路條件與乘務制度進行分割與重組，從而得到可行的任務號集合；乘務輪轉計劃則是在當期各個運行圖的乘務排班計劃編制完畢后，根據列車運行圖屬性(工作日、節假日、延長圖等)按照一定的規則使得乘務員輪流執行任務。乘務排班計劃作為乘務計劃的第一步，其編制質量對整個乘務計劃編制結果有直接的影響。

近年來，乘務排班計劃編制優化在國內外引起學者廣泛的研究，Michael等[1]應用圖論解決城市軌道交通車底運用和乘務計劃中的每個子問題，不同于以往完成編制運行圖后再編制乘務計劃，而是同時進行運行圖與乘務計劃編制，后計算實例證明比現實際使用更低。根據香港輕軌乘務排班計劃的特點，Chu等[2]將乘務排班計劃分為2個階段進行研究，依次采用最短路算法、對稱匹配及改進的遺傳算法進行求解。Elizondo等[3]在對城市軌道交通乘務計劃建模時，采用人工智能領域的方法來表示狀態空間，分別使用基于網絡圖的貪心搜索和禁忌搜索算法來解決問題，最后通過數據進行驗證。針對城市軌道交通的特點，李獻忠等[4-5]提出3種乘務排班優化模型，分別為基于廣義費用最小成本、時間成本最小和總時間消耗最小，并采用禁忌搜索算法、模擬進化算法和最小費用最大流算法對模型進行求解。潘寒川等[6]在考慮乘務員用餐的約束條件下，提出DHM和VGM 2種編制方法，探討 2 種方法在多個“就餐點”及“網絡線路乘務員共享”方法下的適用性和可行性。針對目前不同地鐵線路具有不同的高峰系數，潘寒川等[7]提出CRM 和PIM 乘務計劃編制方法，可針對線路情況選擇不同編制方法，提高精細化管理。

目前針對乘務排班計劃編制問題的模型及算法研究較多，但在編制中綜合考慮城市軌道交通乘務制度的相關研究較少[8-9]。隨著各個城市地鐵興建與發展，乘務制度與乘務規則開始出現差異化。目前國內部分線路開始采用計件制薪資方案，即綜合計算開行里程與工時計薪。通常乘務班組中每個乘務員的開行公里數與值乘時長是不均衡的，除了導致乘務員收入無法得到均衡，還會使得部分乘務員值乘時間過長從而存在安全隱患。因此，在既有研究基礎上提出以任務均衡為目標的乘務排班計劃編制模型，構建經典集合分割主問題模型及基于任務均衡與乘務特色約束子問題模型。利用計算機編程語言實現主規劃部分求解，同時設計基于影子價格選擇的標號法用于求解子規劃部分，并以上海市軌道交通某條線路為例，驗證模型與算法的有效性和效率性。該方法擬尋求在實際運營中科學合理地控制成本，提高運輸效率，促進企業長期可持續發展，加強企業精細化管理，同時也為乘務排班計劃問題的研究提供理論依據。

1 基于任務均衡的乘務排班計劃優化編制方法研究

1.1 乘務排班計劃編制影響因素分析

乘務排班計劃編制問題本質上是一個指派問題，是將乘務員與列車進行綁定的過程，即在規定的乘務員數量下，指派相應的乘務員執行部分列車開行任務，從而保證每個運營時間段的每列列車均有乘務員值乘。城市軌道交通每條線路由停車場、車站與軌道組成。停車場是列車出庫、回庫、維修養護及乘務員辦理出勤、退勤的地點；車站根據功能可劃分為：輪乘站、交接站、就餐站。

（1）輪乘站設置對于乘務排班計劃編制影響。根據《國務院關于職工工作時間的規定》：“因工作性質或者生產特點的限制，不能實行每日工作8 h、每周工作40 h標準工時制度，按照國家有關規定，可以實行其他工作和休息辦法。”由于乘務員工作性質的特殊性，通常規定乘務員在連續駕駛1 h左右需進行休息，從而保證行車安全，避免疲勞駕駛。各個線路管理部通常根據線路長度、車站位置及設施設備條件設定數個輪乘站，供乘務員在連續駕駛一定時長后下車休息。通常以輪乘間隔來規定休息時長，若乘務員A需要休息n個輪乘間隔，則當乘務員A在輪乘站下車休息后，在駛過n輛列車后(包含乘務員下車時所駕駛列車)，當第n+ 1輛列車進站后替換該列車乘務員B繼續駕駛，乘務員B開始輪乘休息。乘務輪乘過程如圖1所示(該站輪乘間隔為2)。

（2）交接站設置對于乘務排班計劃編制影響。由于目前城市軌道交通線路長度不斷延長，僅靠停車場提供出退勤管理已無法滿足線路乘務排班計劃編制需求，通常由線路管理部綜合車站設施設備條件、乘務員住址等設立交接站從而滿足乘務員出退勤需求。交接站設置個數的增加，會使得乘務任務生成更加靈活，但同時會導致排列組合的可能性增加，使得求解難度上升。

（3）就餐站設置對于乘務排班計劃編制影響。乘務員的工作班制通常為四班三運轉，即日—夜—早—休，其中日班工作時長會覆蓋午餐時間，為滿足乘務員午餐需求，需設定具備條件站點為就餐站，保證日班每位乘務員可在11 : 00—13 : 00完成就餐。就餐站的數量根據線路長度決定，每條線路通常設置1至2個就餐站于線路中間位置，供乘務員就餐、休息。

對于乘務排班計劃編制而言，由于在非功能性車站通常不會進行乘務員的變換，因而非功能性車站不會影響乘務排班計劃編制。為此，在后續模型構建及算法設計過程中，將乘務數據進行篩選，僅考慮功能站的列車到發。

1.2 基于任務均衡的乘務計劃優化編制模型構建

乘務排班計劃編制問題，是一個典型的NPhard問題，隨著線路復雜程度的提升，變量的數目會隨之呈爆炸式增長。在乘務排班計劃編制問題中，唯一需要分配的資源是乘務員，編制過程為將列車運行線按輪乘站、交接站進行分割后，按一定的規則進行重組，主要輸入數據如下。①一段時間內的列車運行圖數據：包括列車車底號、列車在各個站點的到發時間、交路信息號；②線路基本條件：包括全線路站點、輪乘站、就餐站及其輪乘間隔、交接站、停車場位置；③對生成任務號的硬約束：乘務員值乘區段全覆蓋、值乘區段鄰接、乘務員單次值乘時間上下限；④對生成任務號的軟約束：時間均衡度、里程均衡度、乘務員偏好。輸出數據為任務號表，包含任務號個數與各個任務號的開行路徑，每個任務即對應一個乘務員的每日任務，輸出結果必須滿足所有硬約束、符合線路條件，同時盡量將成本降至最低并保證一定的均衡度，直至乘務排班計劃編制完畢。

1.2.1 主問題模型構建

在以往的城軌乘務排班計劃編制研究中，通常采用集合覆蓋模型與集合分割模型建立乘務問題模型[10]。集合覆蓋模型允許編制的排班計劃中存在隨乘情況，即一位乘務員在A站下車，但無法在A站接到后續規定時間內的車次，需搭乘列車隨乘到B站接車。隨乘情況的增加降低了乘務排班計劃整體的工時有效率，增加了運營開支，采用集合分割模型建立主問題模型，具體如下。

式中：z為總成本，是最后生成并選入乘務排班計劃的所有乘務任務成本之和；cj為第j個乘務任務的成本；aij表示生成的第j個乘務任務是否包含乘務片段i，包含則aij= 1，不包含則aij= 0；xj表示第j個乘務任務是否采用，采用則xj= 1，不采則xj= 0；U為乘務片段集合；R為乘務任務集合，每個乘務任務包含1個或多個乘務片段。

為對此問題進行求解并獲取其對偶變量，需先將主問題進行線性松弛得到一個線性規劃問題，在迭代完成后，對主問題采用分支定價法進行剪枝從而得到0-1整數解，線性松弛后的模型如下。

1.2.2 子問題模型構建

在主問題中，僅考慮了乘務任務對于乘務片段的全覆蓋，對于輪乘、單次值乘時間、總值乘時間等約束則在子規劃中考慮。子規劃模型建立如下。

式中：R為所生成的新乘務任務的總費用；te,i為第i個乘務片段的到達時間，s；tb,i為第i個乘務片段的發出時間，s；α為超時未休懲罰權重系數；f為連續駕駛時長超1.2 h未休息次數；β為工時有效率權重系數；r(p)為所生成乘務任務中第p個乘務片段車底號；te,p,r(p)為所生成乘務任務中第p個乘務片段的到達時間，s；tb,q,r(q)為所生成乘務任務中第p個乘務片段的發出時間，s；Ts為單次連續值乘最大時長，s；Ta,min，Ta,max為當日最小、最大值乘時間，s。

由于所選的上海地鐵線路乘務數據初始數量為18 000條，在對數據經過清洗和篩選重組后，乘務數據量減少為1 500條。而在以往的研究中，通常數據量在500左右，這與上海地鐵的線路長度、開行間隔、客流數與線路較為復雜存在一定的關系。由于主規劃和子規劃每迭代一次就需要對子問題進行一次求解，若采用以往研究中的方法求解子問題可能會導致求解速度過慢。以求解主問題所得的對偶變量最大值所對應的節點為起始點進行搜索，并選取生成后數個子問題目標函數最小的乘務任務，添加入主問題，從而加速求解并保證解的質量。

當算法迭代至不存在檢驗數小于0時，重設主問題目標函數，以求得值乘時長與里程均衡。

式中：γ為時長均衡權重系數；δ為里程均衡權重系數；n為迭代完畢后主問題中乘務任務的總數量；w為迭代完畢后主問題中乘務任務集合；cj為第j個乘務任務值乘時間費用；lj為第j個乘務任務值乘里程，km。

1.3 基于任務均衡的乘務排班計劃優化編制模型求解

1.3.1 成本函數

主問題在進行線性松弛之后，得到的問題為一個線性規劃問題。對于一個線性規劃問題，通常的解決辦法是利用單純形法進行求解。一個標準的線性規劃問題如下。

式中：cT為線性規劃問題的成本系數向量；x為變量向量；A為變量系數矩陣；b為約束右端常數項向量。

公式(14)可通過公式(15)進行變換代入得到公式(16)，其中下標B表示基變量，下標N表示非基變量。

觀察公式(16)右端容易得到，左邊加項對于一個既定的問題，是一個常數。右邊加項若?n∈N使得則可以適當增加xN的值，使得目標值更優；若則此時令所有非基變量取0，可獲得最優解。因此，在單純形法中稱為檢驗數。

1.3.2 迭代方法

列生成思想求解過程則是利用上述推導，首先在主問題中構造一個初始可行解，隨后在子問題中檢索是否存在乘務任務xj使得檢驗數小于0。若存在，則說明將此任務加入到主問題可以使得主問題進一步優化。當子問題中所有乘務任務的檢驗數均大于等于0時結束迭代，并對主問題進行剪枝后求解得出編制結果。列生成思想求解過程如圖2所示。

圖2 列生成思想求解過程Fig.2 Solving process in column generation

2 實例分析

以上海市某條軌道交通線路為例，對所建立的模型算法進行求解驗證。該線由西至東總長38.83 km，共有31個車站、3個輪乘站與2個停車場，現有乘務排班計劃主要依靠人工經驗進行編制，模型構建及算法設計通過計算機編程語言實現。

2.1 數據處理

乘務排班計劃編制的數據為信號系統所記錄的數據，內容為：車次號、車站名、到點、發點、交路號等。此時的數據規模較大，若直接對此進行計劃編制，會導致求解速度過慢或內存溢出。而在乘務排班計劃編制中，非功能站(輪乘站、交接站、出退勤站)乘務員通常不會有更換車底值乘的動作，因而對數據進行清洗重組處理。數據清洗重組過程如圖3所示。

圖3 數據清洗重組過程Fig.3 Data cleaning and reorganizing process

乘務數據清洗重組思路基本適用于大部分的地鐵線路乘務排班計劃，處理后的結果可直接由模型算法程序進行讀取求解計算。

2.2 導入求解

所建模型中需輸入參數共有4個：α為值乘超1.2 h未休息次數懲罰權重系數；β為工時有效率權重系數；γ為值乘時間費用均衡度權重系數；δ為值乘里程均衡系數。在計算值乘時間費用成本時，取α= 0.3，β= 1。在求值乘時間費用與值乘里程均衡時，取γ= 2，δ以數值間隔為0.1在0.5 ～ 1.5間取值進行多次計算，不同δ權重系數下的值乘時間費用均衡度如圖4所示，不同δ權重系數下的值乘里程均衡度如圖5所示，不同δ權重系數下工時有效率如圖6所示。

圖5 不同δ權重系數下的值乘里程均衡度Fig.5 Rostering mileage balance at different weight coefficients δ

觀察圖4至圖6可知，當δ取1.2時，所輸出的乘務排班計劃具有更優的任務均衡度與工時有效率。乘務任務輸出如表1所示，其中以(1301) -(22 911，24 005) - (JYR3，JSJR2)為例進行說明，1301為車次號，為乘務員登乘重要憑證之一；(22 911，24 005)為該乘務作業段的開始時間與結束時間，從當日0點開始以秒計算，s； (JYR3，JSJR2)為該乘務作業段的開始地點與結束地點；“=”符號連接了相鄰的2個乘務片段。

表1 乘務任務輸出Tab.1 Crew taskoutput

圖4 不同δ權重系數下的值乘時間均衡度Fig.4 Rostering time balance at different weight coefficients δ

圖6 不同δ權重系數下工時有效率Fig.6 Man-hour efficiency at different weight coefficients δ

δ取1.2時，乘務排班計劃值乘時長與上班時長如圖7所示，乘務排班計劃值乘里程如圖8所示，乘務排班計劃工時有效率如圖9所示。

圖7 乘務排班計劃值乘時長與上班時長Fig.7 Rostering time and work time of crew scheduling

圖8 乘務排班計劃值乘里程Fig.8 Rostering mileage of crew scheduling

圖9 乘務排班計劃工時有效率Fig.9 Man-hour efficiency of crew scheduling

可見，基于任務均衡的乘務排班計劃優化編制方法所計算求解的乘務任務具有較優的任務均衡和較高的工時有效率，平均工時有效率達到了86.6%。

3 結束語

基于任務均衡的乘務排班計劃優化編制方法充分考慮目前城市軌道交通乘務員計件制薪資體系，以所生成的乘務排班計劃成本最小為目標，構建集合分割主規劃模型與乘務任務生成子規劃模型，并設計基于影子價格選擇的標號法進行求解完成迭代。案例分析中的求解結果驗證了模型與算法的有效性和效率性，并且在上海地鐵線路較大規模的乘務數據下仍有較好的求解速度，可適應未來城市軌道交通路網的進一步發展。方法中初始解所選取的系數矩陣為一個單位矩陣，優點是生成方法較為簡便，缺點是一定程度上會影響求解的速度與結果，未來可針對如何快速構造一個較好的初始解進行深入研究。