域名預(yù)訂/競(jìng)價(jià)，好“米”不錯(cuò)過(guò)

城市地鐵作為城市交通的主動(dòng)脈之一，承載了城市的巨大客流量，運(yùn)營(yíng)管理非常復(fù)雜。其中，乘務(wù)排班是地鐵運(yùn)營(yíng)管理的關(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)班次和值乘方式、實(shí)現(xiàn)人員的最優(yōu)配置，對(duì)于保障地鐵高效穩(wěn)定運(yùn)行非常重要。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2、輪值表求解優(yōu)化（Crew Sche*ng）

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

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

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

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

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

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

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

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

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

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

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

圖為：耦合模型VS分解模型對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

申請(qǐng)創(chuàng)業(yè)報(bào)道，分享創(chuàng)業(yè)好點(diǎn)子。點(diǎn)擊此處，共同探討創(chuàng)業(yè)新機(jī)遇！