城市地鐵作為城市交通的主動脈之一，承載了城市的巨大客流量，運營管理非常復雜。其中，乘務排班是地鐵運營管理的關鍵環(huán)節(jié)之一，也是乘務管理的起點和難點。地鐵交通運載量大，交路復雜多變，運行間隔密，乘務司機面臨著巨大、持續(xù)、高強度的運輸任務，如何合理安排司機的運轉班次和值乘方式、實現(xiàn)人員的最優(yōu)配置，對于保障地鐵高效穩(wěn)定運行非常重要。
由于地鐵運行網日益復雜，傳統(tǒng)的人工排班方式已無法滿足高標準的運營需求，自動化和智能化的乘務排班成為必然趨勢。智能排班作為一個復雜的運籌優(yōu)化問題，對算法、模型和求解器要求較高，目前國內應用并不普遍，以下根據某一線城市地鐵線路的成功實踐，為你解析如何基于國產求解器COPT實現(xiàn)智能乘務排班。
地鐵乘務排班的痛點分析
一般地鐵運營公司進行乘務排班的流程是：根據當前運行圖導出車次運行區(qū)段和時間等信息表，人工根據這些信息表拆分出乘務輪值表，再根據輪值表編制乘務排班母表，最后以排班母表為基礎對乘務組進行輪循分配，形成最終的排班表。整個過程依靠人工編制，主要存在以下三大問題：
排班效率低： 乘務排班業(yè)務規(guī)則復雜，工作量大，人工編制效率很低，至少需要一周時間，人力和時間成本高;
調整難度大： 遇到列車故障、乘務員臨時請假等突發(fā)情況時，很難快速地對排班計劃做出調整，影響運營管理效率;
任務分配不均衡： 人工排班具有主觀局限性，對人的經驗依賴性較強，排班不合理會導致任務分配不均衡，排班有失公平，乘務員滿意度較低。
基于杉數求解器 COPT的智能乘務排班方案
杉數科技為某地鐵線路構建的智能乘務排班方案，利用運籌優(yōu)化技術將乘務排班問題抽象為數學規(guī)劃問題，通過定制化算法和求解器高效求解優(yōu)化，在排班效率和效果上都實現(xiàn)了顯著提升。方案以地鐵運營部門提供的時刻表(即運行圖)為基礎，綜合考慮車次的接車下車時間地點、換乘約束以及班制運營要求，以優(yōu)化正線值乘人數及乘務人員滿意度為目標，編制輪值表。然后基于輪值表，以優(yōu)化乘務人員之間周/月工作內容的整體均衡性為目標，按照特定的班組轉換模式偏好編制排班母表。
排班類問題屬于混合整數規(guī)劃(MILP)問題，決策變量和約束數量大，建模和求解難度大。傳統(tǒng)的時空網絡模型因存在維度爆炸等計算復雜度限制，求解難度較大，而且需要根據業(yè)務邏輯進行算法定制化開發(fā)和模型拆解。在該項目中，杉數科技采用組環(huán)/組鏈模型+時空網絡模型進行建模，并應用求解器COPT求解【1】，一次性考慮所有約束條件進行全局優(yōu)化。
1、技術選型與建模思路
大規(guī)模公共交通系統(tǒng)的人員排班問題(Crew Sche*ng + Crew Rostering)，涉及的決策維度多，約束條件耦合程度高，即使是在最基礎的設定下，學界和業(yè)界目前也都缺乏高效的求解方法。
由于各類約束之間存在復雜的耦合關系，建模求解過程中需要考慮相互之間的影響，求解難度較大。以用餐相關約束為例，用餐約束與班制和工時息息相關，在設計算法和模型時不能只考慮用餐時間和地點，還要考慮白班和夜班的不同用餐時間限制等約束。因此，如何借助算法來處理這種復雜的耦合關系是智能排班方案需要解決的關鍵問題之一。
在最近的相關綜述論文中【2】，長距離軌道交通的人員排班以集合覆蓋問題為原型，并結合列生成的方法為主，城市軌道交通中則更偏向于網絡流模型結合啟發(fā)式算法或拉格朗日松弛等求解技巧。因本項目屬于超大規(guī)模問題，涉及50余項約束條件，項目算法團隊定制化開發(fā)了“先輪值，再排班”的業(yè)務解耦模型。
圖為：輪值表和排班母表模型示意圖
輪值表模型中，核心決策為每日值乘任務的拆分與組合，主要考慮換乘規(guī)則、班制規(guī)則、里程工時上限等業(yè)務規(guī)則，輸出為完成每日值乘任務所需人數及相應工作安排，即輪值任務卡。
排班母表模型中，核心決策為輪值任務的有效均衡分配，主要考慮任務分配的均衡性，輸出為輪值任務卡與值乘人員的對應關系，即每位輪值人員每日的任務。
2、輪值表求解優(yōu)化（Crew Sche*ng）
在輪值表優(yōu)化階段，杉數科技以優(yōu)化正線值乘人數為目標，基于時空網絡模型結合割平面的方法對輪值表場景進行了定制化的精確求解建模，具體來說，就是將時空網絡中一個個離散的任務基于時空連續(xù)性和業(yè)務規(guī)則約束組成一條條任務鏈。
其中，提高求解效率的核心在于將部分約束條件前置到預處理部分，通過排除大量不可行方案縮小模型規(guī)模，并生成割平面使得模型更緊湊。
(1)連接性 - 其中時空連續(xù)性和特殊換乘地點、換乘時間等基礎業(yè)務規(guī)則約束可在預處理模塊的連接性判斷環(huán)節(jié)中得以保證。
(2)非法任務鏈(Illegal Sequence) - 任務數上限、連續(xù)駕駛時長上限等約束可通過在預處理模塊中通過廣度優(yōu)先搜索(BFS)、深度優(yōu)先搜索(DFS)等方式搜索非法任務鏈或最小非法任務子鏈(Minimal Illegal Subsequence)，并以割平面的方式添加到模型中，割平面只由核心決策變量X_ij組成。這種思路與A.E. Roth et al.【3】提出的通過預先搜索最小不可行路徑(Minimal Infeasible Path)，來刻畫多向腎臟交換圖中鏈/環(huán)的長度約束(CCMcP)異曲同工。
(3)非法任務鏈&合法任務子鏈 – 實際業(yè)務場景中，也存在有些不可行任務鏈可以是可行的任務子鏈(如：用餐、出退勤地點相關約束)，故不能完全排除出可行域外。此類場景中，需要在割平面中加入判定頭、尾等的相關輔助變量來刻畫對應的邏輯關系。
上述方法在不犧牲最優(yōu)性的前提下，用更多的約束條件換取了更少的決策變量，且添加的割平面往往會使得系數矩陣更稠密，求解過程中需要對應地調整求解器預求解等參數的強度。
項目團隊在與業(yè)務部門溝通中，也挖掘出一些業(yè)務中通用的“潛規(guī)則”，從模型的角度考慮，可以理解為犧牲一定的最優(yōu)性以縮小問題規(guī)模并顯著提升求解效率。例如，對于出發(fā)或到達站臺為可換乘且不可出退勤站臺的值乘任務，可以通過構建二分圖，以換乘時間為權重進行最小權重最大匹配，基于匹配結果進行任務預連接并生成對應便乘任務。
通過設計一系列定制化算法對各項約束進行預處理，然后基于業(yè)務邏輯進行建模，再結合求解器COPT進行求解，求解速度明顯加快。特別值得一提的是，COPT求解器團隊還針對問題本身的特有結構開發(fā)了定制化加速模塊，打造了更適用于乘務排班的專屬求解方案。
3、排班母表求解優(yōu)化（Crew Rostering）
輪值表優(yōu)化完成后，乘務團隊需要將輪值表中的任務，合理且均衡地分配給每一位司機，即制定排班母表。在制定排班母表時，既要保證輪值表中的每一項任務都有符合駕駛條件的司機執(zhí)行，又要保證每一位司機有充足的休息時間，在鄰近的車站出退勤，按時接受培訓，更要均衡每位司機每周工作時長和駕駛里程，甚至要為司機休假或者個人突發(fā)狀況做好備班準備，問題紛繁復雜。
針對該場景的復雜變量和約束，杉數科技基于業(yè)務規(guī)則構建了混合整數規(guī)劃模型，并開發(fā)了定制化求解器進行求解。整個建模求解思路如下，首先，梳理可執(zhí)行性相關約束，將班制約束、出勤地點約束等業(yè)務約束前置考慮，有效縮小每個司機可執(zhí)行任務集合，通過現(xiàn)實的業(yè)務約束減小問題規(guī)模。隨后，模型執(zhí)行任務初分配(可行性驗證)和任務再分配(均衡性調整)兩個關鍵步驟。在任務初分配中，模型智能決策排班母表司機總人數;在任務再分配中，模型對任務進行重新分配，以實現(xiàn)各個司機里程和工作時長的均衡，并輸出排班母表。
圖為：耦合模型VS分解模型對比
其中模型分解至關重要，以基于班制規(guī)則的日期分解為例，將周度模型分解為七個日度模型，并考慮連續(xù)日期間的耦合約束，通過分解極大提升求解效率。假設乘務團隊采用四班三運轉班制，則每位司機的任務以“白班-夜班-早班-休息”的周期循環(huán)往復，如圖(耦合模型示意圖)所示。直接基于該模型進行可行性驗證或均衡性調整非常困難，所以將其分解為多個日度模型。如圖(分解模型示意圖)所示，只考慮周一的任務，并且考慮周日和周二的"夜班-早班"耦合約束，有效降低了問題規(guī)模。類似的模型分解在實際求解過程中不一而足。
方案價值：乘務排班更加高效和均衡
智能乘務排班方案幫助該地鐵運營公司實現(xiàn)了乘務管理的智能化升級，打破人工排班的局限性，在滿足地鐵穩(wěn)定運行的情況下，考慮各項業(yè)務規(guī)則和人員能力，從全局角度最優(yōu)化排班計劃，合理、均衡分配任務，實現(xiàn)人和車次的最優(yōu)配置，全面提升了乘務排班的效率和彈性。
圖為：任務分配均衡性對比
運營公司在乘務排班時，將更加靈活便捷，遇到高峰期或突發(fā)情況時可以快速調整排班方案，提升乘務管理效率。同時,也提升了人員利用率，為地鐵運營公司節(jié)省了大量人力成本。對于乘務司機而言，方案兼顧運營需求和乘務司機的主觀需求進行綜合優(yōu)化，降低了排班的不合理性，提高了任務分配的均衡性，整體乘務司機滿意度大幅提升。
杉數求解器 COPT的應用價值和優(yōu)勢
國產求解器COPT在本項目中表現(xiàn)出色，給整個優(yōu)化求解方案帶來了多方面助力和提升：
第一，實現(xiàn)快速穩(wěn)健的優(yōu)化。 COPT求解性能領先，在求解速度上處于國際一流水平，本項目中應用混合整數規(guī)劃求解器進行求解，求解過程順暢、穩(wěn)定、高效。
第二，通過定制化模塊提高求解速度和效果。 COPT應用靈活，擴展性好，可以根據不同的業(yè)務場景進行定制化，相對于常規(guī)求解器，針對于乘務排班的定制化求解器在初始解求解速度、分支策略和整體求解效率等方面都更加優(yōu)秀。
第三，可以規(guī)?；瘡椭坪蛻?。 基于一條地鐵線路的定制化求解能力，可以快速推廣到類似場景中去，幫助運營公司快速實現(xiàn)更大范圍的優(yōu)化升級。
第四，國產化技術支撐 ，COPT求解技術自主可控，可以有效保證系統(tǒng)安全運行。
除了乘務排班，基于求解器COPT的智能決策解決方案目前在列車檢修、列車調度、運行圖編制等多個軌交場景中都已經開始應用，其正在為軌交系統(tǒng)的全面智能化升級注入新的動力，未來的應用潛力值得期待。
Reference:
[1] D. Ge, Q. Huangfu, Z. Wang, J. Wu and Y. Ye. Cardinal Optimizer (COPT) user guide. https://guide.coap.online/copt/en-doc, 2022.
[2] J. Zhou, X. Xu, J. Long and J. Ding. Integrated optimization approach to metro crew sche*ng and rostering. Transportation Research Part C. 123 (2021) 102975
[3] A.E. Roth, T. Sonmez and M.U. Unver. Efficient kidney exchange: coincidence of wants in markets with compatibility-based preferences. American Economic Review. (2007) 97:828–851
更多求解器應用案例，可在 CORIDM教學平臺了解
CORIDM(全稱Center for Operations Research and Intelligent Decision Making)是杉數科技推出的運籌與智能決策的案例教學平臺，集成了多個經典運籌學問題以及多個行業(yè)多個領域的真實案例，并且提供一站式的Jupyter Notebook編程環(huán)境，旨在為教授和學生帶來“理論結合實踐”的案例教學/學習體驗。
● 內嵌Python編程/COPT/運籌優(yōu)化等基礎知識介紹。用戶可以在平臺中學習各種基礎知識，為解決工業(yè)界的實際問題做充足的準備;
● 匯聚零售、消費、制造、物流、航空等多個行業(yè)的智能決策案例。對于每個案例，平臺提供了詳細的案例介紹、解決方法和數學模型、實現(xiàn)代碼、總結拓展等，提供了充足的學習資源，能夠讓學習者充分掌握每個案例的內容和思想;
● 提供開箱即用的Jupyter Notebook編程環(huán)境。所需的Python第三方包包括COPT求解器已經部署完成，用戶不需要自行安裝任何軟件即可運行代碼;
申請創(chuàng)業(yè)報道，分享創(chuàng)業(yè)好點子。點擊此處，共同探討創(chuàng)業(yè)新機遇！
