由于地鐵運行網(wǎng)日益復(fù)雜，傳統(tǒng)的人工排班方式已無法滿足高標(biāo)準(zhǔn)的運營需求，自動化和智能化的乘務(wù)排班成為必然趨勢。智能排班作為一個復(fù)雜的運籌優(yōu)化問題，對算法、模型和求解器要求較高，目前國內(nèi)應(yīng)用并不普遍，以下根據(jù)某一線城市地鐵線路的成功實踐，為你解析如何基于國產(chǎn)求解器COPT實現(xiàn)智能乘務(wù)排班。

地鐵乘務(wù)排班的痛點分析

一般地鐵運營公司進行乘務(wù)排班的流程是：根據(jù)當(dāng)前運行圖導(dǎo)出車次運行區(qū)段和時間等信息表，人工根據(jù)這些信息表拆分出乘務(wù)輪值表，再根據(jù)輪值表編制乘務(wù)排班母表，最后以排班母表為基礎(chǔ)對乘務(wù)組進行輪循分配，形成最終的排班表。整個過程依靠人工編制，主要存在以下三大問題：

排班效率低：乘務(wù)排班業(yè)務(wù)規(guī)則復(fù)雜，工作量大，人工編制效率很低，至少需要一周時間，人力和時間成本高;

調(diào)整難度大：遇到列車故障、乘務(wù)員臨時請假等突發(fā)情況時，很難快速地對排班計劃做出調(diào)整，影響運營管理效率;

任務(wù)分配不均衡：人工排班具有主觀局限性，對人的經(jīng)驗依賴性較強，排班不合理會導(dǎo)致任務(wù)分配不均衡，排班有失公平，乘務(wù)員滿意度較低。

基于杉數(shù)求解器COPT的智能乘務(wù)排班方案

杉數(shù)科技為某地鐵線路構(gòu)建的智能乘務(wù)排班方案，利用運籌優(yōu)化技術(shù)將乘務(wù)排班問題抽象為數(shù)學(xué)規(guī)劃問題，通過定制化算法和求解器高效求解優(yōu)化，在排班效率和效果上都實現(xiàn)了顯著提升。方案以地鐵運營部門提供的時刻表(即運行圖)為基礎(chǔ)，綜合考慮車次的接車下車時間地點、換乘約束以及班制運營要求，以優(yōu)化正線值乘人數(shù)及乘務(wù)人員滿意度為目標(biāo)，編制輪值表。然后基于輪值表，以優(yōu)化乘務(wù)人員之間周/月工作內(nèi)容的整體均衡性為目標(biāo)，按照特定的班組轉(zhuǎn)換模式偏好編制排班母表。

排班類問題屬于混合整數(shù)規(guī)劃(MILP)問題，決策變量和約束數(shù)量大，建模和求解難度大。傳統(tǒng)的時空網(wǎng)絡(luò)模型因存在維度爆炸等計算復(fù)雜度限制，求解難度較大，而且需要根據(jù)業(yè)務(wù)邏輯進行算法定制化開發(fā)和模型拆解。在該項目中，杉數(shù)科技采用組環(huán)/組鏈模型+時空網(wǎng)絡(luò)模型進行建模，并應(yīng)用求解器COPT求解【1】，一次性考慮所有約束條件進行全局優(yōu)化。

1、技術(shù)選型與建模思路

大規(guī)模公共交通系統(tǒng)的人員排班問題(Crew Scheduling + Crew Rostering)，涉及的決策維度多，約束條件耦合程度高，即使是在最基礎(chǔ)的設(shè)定下，學(xué)界和業(yè)界目前也都缺乏高效的求解方法。

由于各類約束之間存在復(fù)雜的耦合關(guān)系，建模求解過程中需要考慮相互之間的影響，求解難度較大。以用餐相關(guān)約束為例，用餐約束與班制和工時息息相關(guān)，在設(shè)計算法和模型時不能只考慮用餐時間和地點，還要考慮白班和夜班的不同用餐時間限制等約束。因此，如何借助算法來處理這種復(fù)雜的耦合關(guān)系是智能排班方案需要解決的關(guān)鍵問題之一。

在最近的相關(guān)綜述論文中【2】，長距離軌道交通的人員排班以集合覆蓋問題為原型，并結(jié)合列生成的方法為主，城市軌道交通中則更偏向于網(wǎng)絡(luò)流模型結(jié)合啟發(fā)式算法或拉格朗日松弛等求解技巧。因本項目屬于超大規(guī)模問題，涉及50余項約束條件，項目算法團隊定制化開發(fā)了“先輪值，再排班”的業(yè)務(wù)解耦模型。

圖為：輪值表和排班母表模型示意圖

輪值表模型中，核心決策為每日值乘任務(wù)的拆分與組合，主要考慮換乘規(guī)則、班制規(guī)則、里程工時上限等業(yè)務(wù)規(guī)則，輸出為完成每日值乘任務(wù)所需人數(shù)及相應(yīng)工作安排，即輪值任務(wù)卡。

排班母表模型中，核心決策為輪值任務(wù)的有效均衡分配，主要考慮任務(wù)分配的均衡性，輸出為輪值任務(wù)卡與值乘人員的對應(yīng)關(guān)系，即每位輪值人員每日的任務(wù)。

2、輪值表求解優(yōu)化(Crew Scheduling)

在輪值表優(yōu)化階段，杉數(shù)科技以優(yōu)化正線值乘人數(shù)為目標(biāo)，基于時空網(wǎng)絡(luò)模型結(jié)合割平面的方法對輪值表場景進行了定制化的精確求解建模，具體來說，就是將時空網(wǎng)絡(luò)中一個個離散的任務(wù)基于時空連續(xù)性和業(yè)務(wù)規(guī)則約束組成一條條任務(wù)鏈。

其中，提高求解效率的核心在于將部分約束條件前置到預(yù)處理部分，通過排除大量不可行方案縮小模型規(guī)模，并生成割平面使得模型更緊湊。

(1)連接性 - 其中時空連續(xù)性和特殊換乘地點、換乘時間等基礎(chǔ)業(yè)務(wù)規(guī)則約束可在預(yù)處理模塊的連接性判斷環(huán)節(jié)中得以保證。

(2)非法任務(wù)鏈(Illegal Sequence) - 任務(wù)數(shù)上限、連續(xù)駕駛時長上限等約束可通過在預(yù)處理模塊中通過廣度優(yōu)先搜索(BFS)、深度優(yōu)先搜索(DFS)等方式搜索非法任務(wù)鏈或最小非法任務(wù)子鏈(Minimal Illegal Subsequence)，并以割平面的方式添加到模型中，割平面只由核心決策變量X_ij組成。這種思路與A.E. Roth et al.【3】提出的通過預(yù)先搜索最小不可行路徑(Minimal Infeasible Path)，來刻畫多向腎臟交換圖中鏈/環(huán)的長度約束(CCMcP)異曲同工。

(3)非法任務(wù)鏈&合法任務(wù)子鏈 – 實際業(yè)務(wù)場景中，也存在有些不可行任務(wù)鏈可以是可行的任務(wù)子鏈(如：用餐、出退勤地點相關(guān)約束)，故不能完全排除出可行域外。此類場景中，需要在割平面中加入判定頭、尾等的相關(guān)輔助變量來刻畫對應(yīng)的邏輯關(guān)系。

上述方法在不犧牲最優(yōu)性的前提下，用更多的約束條件換取了更少的決策變量，且添加的割平面往往會使得系數(shù)矩陣更稠密，求解過程中需要對應(yīng)地調(diào)整求解器預(yù)求解等參數(shù)的強度。

項目團隊在與業(yè)務(wù)部門溝通中，也挖掘出一些業(yè)務(wù)中通用的“潛規(guī)則”，從模型的角度考慮，可以理解為犧牲一定的最優(yōu)性以縮小問題規(guī)模并顯著提升求解效率。例如，對于出發(fā)或到達站臺為可換乘且不可出退勤站臺的值乘任務(wù)，可以通過構(gòu)建二分圖，以換乘時間為權(quán)重進行最小權(quán)重最大匹配，基于匹配結(jié)果進行任務(wù)預(yù)連接并生成對應(yīng)便乘任務(wù)。

通過設(shè)計一系列定制化算法對各項約束進行預(yù)處理，然后基于業(yè)務(wù)邏輯進行建模，再結(jié)合求解器COPT進行求解，求解速度明顯加快。特別值得一提的是，COPT求解器團隊還針對問題本身的特有結(jié)構(gòu)開發(fā)了定制化加速模塊，打造了更適用于乘務(wù)排班的專屬求解方案。

3、排班母表求解優(yōu)化(Crew Rostering)

輪值表優(yōu)化完成后，乘務(wù)團隊需要將輪值表中的任務(wù)，合理且均衡地分配給每一位司機，即制定排班母表。在制定排班母表時，既要保證輪值表中的每一項任務(wù)都有符合駕駛條件的司機執(zhí)行，又要保證每一位司機有充足的休息時間，在鄰近的車站出退勤，按時接受培訓(xùn)，更要均衡每位司機每周工作時長和駕駛里程，甚至要為司機休假或者個人突發(fā)狀況做好備班準(zhǔn)備，問題紛繁復(fù)雜。

針對該場景的復(fù)雜變量和約束，杉數(shù)科技基于業(yè)務(wù)規(guī)則構(gòu)建了混合整數(shù)規(guī)劃模型，并開發(fā)了定制化求解器進行求解。整個建模求解思路如下，首先，梳理可執(zhí)行性相關(guān)約束，將班制約束、出勤地點約束等業(yè)務(wù)約束前置考慮，有效縮小每個司機可執(zhí)行任務(wù)集合，通過現(xiàn)實的業(yè)務(wù)約束減小問題規(guī)模。隨后，模型執(zhí)行任務(wù)初分配(可行性驗證)和任務(wù)再分配(均衡性調(diào)整)兩個關(guān)鍵步驟。在任務(wù)初分配中，模型智能決策排班母表司機總?cè)藬?shù);在任務(wù)再分配中，模型對任務(wù)進行重新分配，以實現(xiàn)各個司機里程和工作時長的均衡，并輸出排班母表。

圖為：耦合模型VS分解模型對比

其中模型分解至關(guān)重要，以基于班制規(guī)則的日期分解為例，將周度模型分解為七個日度模型，并考慮連續(xù)日期間的耦合約束，通過分解極大提升求解效率。假設(shè)乘務(wù)團隊采用四班三運轉(zhuǎn)班制，則每位司機的任務(wù)以“白班-夜班-早班-休息”的周期循環(huán)往復(fù)，如圖(耦合模型示意圖)所示。直接基于該模型進行可行性驗證或均衡性調(diào)整非常困難，所以將其分解為多個日度模型。如圖(分解模型示意圖)所示，只考慮周一的任務(wù)，并且考慮周日和周二的"夜班-早班"耦合約束，有效降低了問題規(guī)模。類似的模型分解在實際求解過程中不一而足。

方案價值：乘務(wù)排班更加高效和均衡

智能乘務(wù)排班方案幫助該地鐵運營公司實現(xiàn)了乘務(wù)管理的智能化升級，打破人工排班的局限性，在滿足地鐵穩(wěn)定運行的情況下，考慮各項業(yè)務(wù)規(guī)則和人員能力，從全局角度最優(yōu)化排班計劃，合理、均衡分配任務(wù)，實現(xiàn)人和車次的最優(yōu)配置，全面提升了乘務(wù)排班的效率和彈性。

圖為：任務(wù)分配均衡性對比

運營公司在乘務(wù)排班時，將更加靈活便捷，遇到高峰期或突發(fā)情況時可以快速調(diào)整排班方案，提升乘務(wù)管理效率。同時,也提升了人員利用率，為地鐵運營公司節(jié)省了大量人力成本。對于乘務(wù)司機而言，方案兼顧運營需求和乘務(wù)司機的主觀需求進行綜合優(yōu)化，降低了排班的不合理性，提高了任務(wù)分配的均衡性，整體乘務(wù)司機滿意度大幅提升。

杉數(shù)求解器COPT的應(yīng)用價值和優(yōu)勢

國產(chǎn)求解器COPT在本項目中表現(xiàn)出色，給整個優(yōu)化求解方案帶來了多方面助力和提升：

第一，實現(xiàn)快速穩(wěn)健的優(yōu)化。COPT求解性能領(lǐng)先，在求解速度上處于國際一流水平，本項目中應(yīng)用混合整數(shù)規(guī)劃求解器進行求解，求解過程順暢、穩(wěn)定、高效。

第二，通過定制化模塊提高求解速度和效果。COPT應(yīng)用靈活，擴展性好，可以根據(jù)不同的業(yè)務(wù)場景進行定制化，相對于常規(guī)求解器，針對于乘務(wù)排班的定制化求解器在初始解求解速度、分支策略和整體求解效率等方面都更加優(yōu)秀。

第三，可以規(guī)模化復(fù)制和應(yīng)用。基于一條地鐵線路的定制化求解能力，可以快速推廣到類似場景中去，幫助運營公司快速實現(xiàn)更大范圍的優(yōu)化升級。

第四，國產(chǎn)化技術(shù)支撐，COPT求解技術(shù)自主可控，可以有效保證系統(tǒng)安全運行。

除了乘務(wù)排班，基于求解器COPT的智能決策解決方案目前在列車檢修、列車調(diào)度、運行圖編制等多個軌交場景中都已經(jīng)開始應(yīng)用，其正在為軌交系統(tǒng)的全面智能化升級注入新的動力，未來的應(yī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 scheduling 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

更多求解器應(yīng)用案例，可在CORIDM教學(xué)平臺了解

CORIDM(全稱Center for Operations Research and Intelligent Decision Making)是杉數(shù)科技推出的運籌與智能決策的案例教學(xué)平臺，集成了多個經(jīng)典運籌學(xué)問題以及多個行業(yè)多個領(lǐng)域的真實案例，并且提供一站式的Jupyter Notebook編程環(huán)境，旨在為教授和學(xué)生帶來“理論結(jié)合實踐”的案例教學(xué)/學(xué)習(xí)體驗。

● 內(nèi)嵌Python編程/COPT/運籌優(yōu)化等基礎(chǔ)知識介紹。用戶可以在平臺中學(xué)習(xí)各種基礎(chǔ)知識，為解決工業(yè)界的實際問題做充足的準(zhǔn)備;

● 匯聚零售、消費、制造、物流、航空等多個行業(yè)的智能決策案例。對于每個案例，平臺提供了詳細的案例介紹、解決方法和數(shù)學(xué)模型、實現(xiàn)代碼、總結(jié)拓展等，提供了充足的學(xué)習(xí)資源，能夠讓學(xué)習(xí)者充分掌握每個案例的內(nèi)容和思想;

● 提供開箱即用的Jupyter Notebook編程環(huán)境。所需的Python第三方包包括COPT求解器已經(jīng)部署完成，用戶不需要自行安裝任何軟件即可運行代碼;