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