考慮便乘的地鐵乘務(wù)任務(wù)配對(duì)的約束優(yōu)化模型研究

馬 亮，徐曉英

(1. 西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031；2. 中國(guó)鐵路西安局集團(tuán)有限公司，陜西 西安 710608)

地鐵車(chē)輛基地(包括車(chē)輛段和停車(chē)場(chǎng))主要作業(yè)任務(wù)為檢修、行車(chē)和乘務(wù)，行車(chē)依據(jù)檢修需求和車(chē)輛狀態(tài)為運(yùn)行車(chē)次分配車(chē)輛，乘務(wù)管理為行車(chē)提供司乘保障。乘務(wù)管理的核心是依據(jù)乘務(wù)制度編制乘務(wù)排班計(jì)劃，實(shí)現(xiàn)乘務(wù)任務(wù)、司機(jī)出/退勤、司機(jī)輪休、司機(jī)用餐和司機(jī)工作量的管理，保障正線行車(chē)效率和乘務(wù)人員身心健康，達(dá)到減員增效的目的。

乘務(wù)排班計(jì)劃主要包括：乘務(wù)任務(wù)配對(duì)(Crew Scheduling)和乘務(wù)任務(wù)指派(Crew Rostering)兩個(gè)問(wèn)題。其中，乘務(wù)任務(wù)配對(duì)是指依據(jù)乘務(wù)作業(yè)限制，將給定的列車(chē)運(yùn)行計(jì)劃配對(duì)成若干乘務(wù)任務(wù)；乘務(wù)任務(wù)指派是指依據(jù)乘務(wù)班組和輪班制度將乘務(wù)任務(wù)配對(duì)結(jié)果指派給具體的司乘人員，形成司乘人員一天的值乘計(jì)劃。一般情況下，司乘人員駕駛列車(chē)出勤或者值乘，若司乘人員不在出勤點(diǎn)或者退勤點(diǎn)，就需要像乘客一樣便乘其他列車(chē)至出勤點(diǎn)或者退勤點(diǎn)。因此，乘務(wù)任務(wù)可以分為值乘任務(wù)(Crew Tasks)和便乘任務(wù)(Passenger Tasks)。便乘是指多組司乘人員同時(shí)值乘一個(gè)列車(chē)，其中1組司乘人員擔(dān)任司機(jī)，其他組司乘人員以乘客身份便乘前往目的地出勤或者退勤，即部分司乘人員只能在非出勤點(diǎn)開(kāi)始乘務(wù)任務(wù)或者在非退勤點(diǎn)結(jié)束乘務(wù)任務(wù)。

國(guó)外針對(duì)鐵路司乘任務(wù)優(yōu)化問(wèn)題：文獻(xiàn)[1]考慮了司乘人員可以乘坐其他交通工具便乘出勤和對(duì)原有乘務(wù)任務(wù)修改最少，建立了荷蘭鐵路司乘人員重新調(diào)度的集合覆蓋(Set Covering, SC)模型，但是重新調(diào)度的計(jì)算時(shí)間較長(zhǎng)；文獻(xiàn)[2]研究了鐵路貨物夜間運(yùn)輸?shù)某藙?wù)任務(wù)公平調(diào)度問(wèn)題，以乘務(wù)任務(wù)調(diào)度成本最小、不受歡迎的乘務(wù)任務(wù)最少和不受歡迎乘務(wù)任務(wù)分配均衡為目標(biāo)，建立了歐洲鐵路運(yùn)輸公司乘務(wù)調(diào)度的SC模型，并設(shè)計(jì)了最短路徑和線性規(guī)劃松弛的混合算法；文獻(xiàn)[3]重點(diǎn)考慮了任務(wù)調(diào)度和司乘人員薪酬的均衡性，建立了智利工礦企業(yè)工藝鐵路的乘務(wù)任務(wù)調(diào)度的0-1整數(shù)規(guī)劃模型，但是改進(jìn)的局部啟發(fā)式搜索算法求解耗時(shí)達(dá)幾個(gè)小時(shí)。由于國(guó)外法規(guī)制度和鐵路值乘制度與國(guó)內(nèi)不同，因此需要研究符合我國(guó)國(guó)情的乘務(wù)任務(wù)配對(duì)優(yōu)化問(wèn)題。

針對(duì)我國(guó)鐵路乘務(wù)排班計(jì)劃優(yōu)化問(wèn)題：文獻(xiàn)[4]建立了臺(tái)灣地區(qū)鐵路客運(yùn)乘務(wù)排班計(jì)劃的綜合0-1優(yōu)化模型，并使用深度優(yōu)先回溯搜索算法(DFS)求解，算例表明綜合模型比分解模型的解更優(yōu)；文獻(xiàn)[5]以總交路時(shí)間最小和各乘務(wù)交路間均衡最大為目標(biāo)，建立乘務(wù)交路優(yōu)化的多旅行商模型，算例驗(yàn)證表明改進(jìn)蟻群算法比遺傳算法求解效果好；文獻(xiàn)[6] 建立了客運(yùn)專(zhuān)線乘務(wù)交路計(jì)劃的SC模型，但是分支定價(jià)算法求得初始解的時(shí)間較長(zhǎng)，算法的可信度不高；文獻(xiàn)[7]以乘務(wù)人員效率最高為目標(biāo)，建立了乘務(wù)交路計(jì)劃的SC模型，但是模型中未考慮便乘情況、實(shí)際的乘務(wù)制度、勞動(dòng)規(guī)章等關(guān)鍵因素。

相對(duì)于國(guó)鐵，地鐵具有乘務(wù)任務(wù)段相對(duì)確定、行車(chē)密度大、交路相對(duì)簡(jiǎn)單、有多個(gè)乘務(wù)輪換點(diǎn)等特點(diǎn)。目前，現(xiàn)場(chǎng)絕大多數(shù)司乘派班調(diào)度員借助辦公軟件人工編制司乘排班計(jì)劃，司乘班組的工作效率得不到保證，需要研究地鐵乘務(wù)排班優(yōu)化問(wèn)題。文獻(xiàn)[8-10]以總費(fèi)用最少為目標(biāo)建立雙層整數(shù)規(guī)劃模型，并分別使用最短路、最小費(fèi)用最大流、Hungarian、禁忌搜索、Dijkstra和離散粒子群等算法求解；文獻(xiàn)[11]探討了乘務(wù)排班和值乘方式，比較得出輪乘制比包乘制更節(jié)省費(fèi)用；文獻(xiàn)[12-13]建立乘務(wù)任務(wù)配對(duì)的SC和集合分解(Set Partition, SP)模型，并借鑒列生成思想設(shè)計(jì)混合算法求解；文獻(xiàn)[14]建立乘務(wù)任務(wù)分配的0-1整數(shù)規(guī)劃模型，設(shè)計(jì)了列生成和跟隨分支策略的混合算法，但是應(yīng)該考慮更長(zhǎng)期乘務(wù)任務(wù)的均衡性；文獻(xiàn)[15]針對(duì)啟發(fā)式算法或者列生成算法求解復(fù)雜、難于實(shí)際應(yīng)用等問(wèn)題，以列生成算法為框架，將整個(gè)優(yōu)化問(wèn)題分解為SP主規(guī)劃模型和加權(quán)網(wǎng)絡(luò)最短路徑的子規(guī)劃模型兩部分，但是在實(shí)際應(yīng)用時(shí)成本函數(shù)中的權(quán)值較難確定。

現(xiàn)有研究主要是建立乘務(wù)排班計(jì)劃的0-1規(guī)劃模型，再使用解析算法和啟發(fā)式算法求解，取得了大量的理論成果，但是與投入實(shí)際應(yīng)用之間存有一定的差距。關(guān)鍵問(wèn)題是所建模型是結(jié)構(gòu)化的數(shù)學(xué)表達(dá)式，難于使用程序語(yǔ)言直接表示；而且針對(duì)不同的算例，算法性能的波動(dòng)較大。同時(shí)，部分模型存在不深入和值得商榷的地方，譬如：乘務(wù)任務(wù)與乘務(wù)任務(wù)段之間的關(guān)系定量描述不精確、各約束沒(méi)有分情況討論等。本文使用約束程序(Constraint Programming, CP)[16-17]理論研究便乘情況下的乘務(wù)任務(wù)配對(duì)問(wèn)題，建立約束優(yōu)化(Constraint Optimization, CO)[17]模型，并依據(jù)模型特點(diǎn)使用弧邊界相容的約束傳播(Constraint Propagation, CPr)[17]算法化簡(jiǎn)模型，最后使用CPr和啟發(fā)式回溯的混合算法求解模型。

1 地鐵乘務(wù)任務(wù)配對(duì)問(wèn)題

乘務(wù)任務(wù)配對(duì)指將給定的列車(chē)運(yùn)行計(jì)劃配對(duì)成若干乘務(wù)任務(wù)，每個(gè)乘務(wù)任務(wù)由1個(gè)乘務(wù)班組1天完成，因此，列車(chē)運(yùn)行圖是乘務(wù)任務(wù)配對(duì)的基礎(chǔ)。列車(chē)運(yùn)行圖中縱軸表示所有?？寇?chē)站，這些車(chē)站按照用途可以分為兩類(lèi)：一類(lèi)是普通乘客換乘點(diǎn)；另一類(lèi)是乘務(wù)分割點(diǎn)。其中乘務(wù)分割點(diǎn)是乘務(wù)員進(jìn)行出/退勤、輪換休息和用餐的站點(diǎn)。移除列車(chē)運(yùn)行圖中的乘客換乘點(diǎn)得到只保留乘務(wù)分割點(diǎn)的乘務(wù)運(yùn)行線集合為

G={Gi,1≤i≤NG}

式中：Gi(1≤i≤NG)為第i條乘務(wù)運(yùn)行線集合；NG為總的運(yùn)行線數(shù)量。

將每一條乘務(wù)運(yùn)行線Gi上相鄰乘務(wù)分割點(diǎn)之間的運(yùn)行任務(wù)片段稱(chēng)為乘務(wù)任務(wù)段，則第i條乘務(wù)運(yùn)行線Gi的第l個(gè)乘務(wù)任務(wù)段為

乘務(wù)任務(wù)段劃分示意圖見(jiàn)圖1。

圖1 運(yùn)行線的乘務(wù)任務(wù)段劃分示意圖

為了論述乘務(wù)任務(wù)配對(duì)問(wèn)題，定義變量見(jiàn)表1.

表1 乘務(wù)任務(wù)配對(duì)問(wèn)題變量及說(shuō)明

一個(gè)乘務(wù)任務(wù)是指司乘人員從出勤點(diǎn)開(kāi)始，值乘若干乘務(wù)任務(wù)段并最終從退勤點(diǎn)結(jié)束的全過(guò)程[5]，由若干乘務(wù)任務(wù)段按照一定的乘務(wù)規(guī)則鏈接而成。因此，乘務(wù)任務(wù)段是乘務(wù)任務(wù)配對(duì)的基本單元，其數(shù)量與每日列車(chē)運(yùn)行次數(shù)、乘務(wù)分割點(diǎn)的分布密切相關(guān)，并直接決定了乘務(wù)任務(wù)配對(duì)問(wèn)題的復(fù)雜度。乘務(wù)任務(wù)段之間的樹(shù)形鏈接關(guān)系見(jiàn)圖2。

圖2 乘務(wù)任務(wù)段鏈接關(guān)系的樹(shù)形結(jié)構(gòu)示意圖

2 地鐵乘務(wù)任務(wù)配對(duì)的約束優(yōu)化模型

CO模型記為四元組(X,D,C,F)，其中：X為變量集合；D為變量論域集合；C為約束集合；F為目標(biāo)函數(shù)集合[17]。令某一變量x∈X取值表示為x←v∈D(x)，則CO求得最優(yōu)解S={(x←v)|?x∈X,v∈D(x)}是指對(duì)于任意約束?c∈C滿足相容性檢查c(S)=1，同時(shí)使得任意目標(biāo)函數(shù)?f∈F達(dá)到最優(yōu)。CO的約束是由變量或者變量表達(dá)式之間通過(guò)邏輯謂詞(與“∧”、或“∨”、非“！”、蘊(yùn)含“=>”等)聯(lián)接形成的關(guān)系[17]。乘務(wù)任務(wù)配對(duì)受到地點(diǎn)、時(shí)間、工作強(qiáng)度等限制，而且各約束之間存在較強(qiáng)的邏輯關(guān)系，使用CO直接建立考慮便乘的乘務(wù)任務(wù)配對(duì)優(yōu)化模型(Constrained Optimization Model for Crew Pairing, COCP)。

2.1 常量定義

表2 常量變量及說(shuō)明

2.2 變量定義

每一個(gè)乘務(wù)任務(wù)段可以視為最小的乘務(wù)任務(wù)，理論上最多的乘務(wù)任務(wù)數(shù)量等于NB，令以bm為開(kāi)始任務(wù)區(qū)段的乘務(wù)任務(wù)Bm為變量，則定義變量見(jiàn)表3。

表3 任務(wù)區(qū)段的乘務(wù)任務(wù)Bm為變量及說(shuō)明

依據(jù)上述定義，乘務(wù)任務(wù)的結(jié)構(gòu)見(jiàn)圖3。

圖3 乘務(wù)任務(wù)結(jié)構(gòu)示意圖

2.3 目標(biāo)函數(shù)

為了降低地鐵運(yùn)營(yíng)成本和提高乘務(wù)人員的工作效率，乘務(wù)任務(wù)配對(duì)優(yōu)化的主要目標(biāo)是在允許便乘的情況下乘務(wù)任務(wù)數(shù)量最少，表示為

(1)

2.4 約束條件

乘務(wù)任務(wù)配對(duì)需要滿足乘務(wù)人員總的工作量、乘務(wù)人員連續(xù)工作量、乘務(wù)任務(wù)的班次劃分、出/退勤地點(diǎn)、輪休時(shí)間和地點(diǎn)、用餐時(shí)間和地點(diǎn)、乘務(wù)任務(wù)段完整性等限制。

(2)

(2)1個(gè)乘務(wù)任務(wù)內(nèi)相鄰的乘務(wù)任務(wù)段之間，前1個(gè)乘務(wù)任務(wù)段的到達(dá)地點(diǎn)是后1個(gè)乘務(wù)任務(wù)段的出發(fā)地點(diǎn)，即乘務(wù)任務(wù)內(nèi)的乘務(wù)任務(wù)段之間需要滿足鏈接關(guān)系

(3)

(3)如果某一個(gè)乘務(wù)任務(wù)的開(kāi)始車(chē)站不是出勤點(diǎn)或者結(jié)束車(chē)站不是退勤點(diǎn)，那么此乘務(wù)任務(wù)段為便乘的乘務(wù)任務(wù)段

c3:?m:(om=1∧wm=1)

(4)

(4)在最終形成的乘務(wù)任務(wù)方案應(yīng)該包括所有的乘務(wù)任務(wù)段，而且1個(gè)乘務(wù)任務(wù)段只屬于1個(gè)乘務(wù)任務(wù)。則乘務(wù)任務(wù)段全覆蓋和唯一性約束為

(5)

(5)為了保證乘務(wù)人員之間的工作量均衡，每一個(gè)乘務(wù)任務(wù)需要滿足所屬班次總的工作量約束為

(6)

(6)所形成的乘務(wù)任務(wù)Bm中所有的乘務(wù)任務(wù)段要么沒(méi)有特殊的需求，要么滿足退勤、輪休、用餐中的1個(gè)需求，則乘務(wù)任務(wù)段特殊需求唯一性約束為

c6:?m,?n:(om=1)?(dm,n=rm,n+hm,n+em,n)

(7)

(7)為了保證各司乘人員工作量均衡和避免疲勞駕駛，乘務(wù)任務(wù)內(nèi)總的工作時(shí)間不能超過(guò)上限，否則，需要退勤，則總的工作量約束為

(8)

式(8)表示當(dāng)乘務(wù)任務(wù)Bm滿足其他約束的論域D(Bm)不為空時(shí)，但是其中任意乘務(wù)任務(wù)段加入到Bm中均會(huì)超過(guò)總的工作時(shí)間的上限，則需要退勤。

(8)為了保證司乘人員的身心健康，司乘人員連續(xù)工作時(shí)間不能超過(guò)持續(xù)工作時(shí)間上限，如果超過(guò)，則需要輪換休息，則連續(xù)工作量約束為

(9)一般情況下乘務(wù)任務(wù)分為早、白、夜3班，通過(guò)乘務(wù)任務(wù)的開(kāi)始和結(jié)束時(shí)間來(lái)區(qū)分乘務(wù)任務(wù)所屬班次，則乘務(wù)任務(wù)班次劃分約束為

c9:?m,?u∈ST:(om=1∧um=u)

(11)

(10)早班中的非便乘出勤的乘務(wù)任務(wù)直接從車(chē)輛基地駕駛出勤

(12)

(11)晚班中的不是便乘退勤的乘務(wù)任務(wù)直接駕駛到車(chē)輛基地退勤：

(13)

(12)為了保證司乘人員的身心健康，乘務(wù)人員連續(xù)駕駛一段時(shí)間之后需要在輪換點(diǎn)休息，則乘務(wù)任務(wù)的輪換休息持續(xù)時(shí)間和地點(diǎn)約束為

(14)

(13)乘務(wù)人員連續(xù)駕駛一段時(shí)間之后需要在規(guī)定地點(diǎn)和時(shí)間范圍內(nèi)用餐，而且需要保證用餐時(shí)間，則乘務(wù)任務(wù)的用餐持續(xù)時(shí)間和地點(diǎn)約束包括是否用餐約束和用餐時(shí)間、地點(diǎn)約束為

(15)

COCP模型為單目標(biāo)的約束優(yōu)化模型，每一個(gè)乘務(wù)任務(wù)的確定問(wèn)題為大規(guī)模的NP-Hard問(wèn)題，首先通過(guò)約束傳播算法剔除解空間中不可能成為解的那部分變量取值，縮小解空間，減少無(wú)效搜索。但是約束傳播算法缺乏完備性，同時(shí)基本回溯算法(Backtracking Algorithms, BT)未使用已實(shí)例化變量進(jìn)行相容性檢查避免未來(lái)沖突，求解時(shí)間較長(zhǎng)，因此，設(shè)計(jì)了約束傳播和啟發(fā)式回溯(Heuristic BT, HBT)的混合搜索算法(CPr-HBT)快速求解模型。

3 乘務(wù)任務(wù)配對(duì)的混合搜索算法

(16)

混合搜索算法(CPr-HBT)步驟如下：

Step1如果未達(dá)到總的求解時(shí)間或者迭代次數(shù)，轉(zhuǎn)Step2，否則，返回使得f最小的解B={Bm}。

Step4初始約束傳播約減D(Bm)。在使用啟發(fā)式回溯算法求解乘務(wù)任務(wù)Bm前，使用約束傳播算法對(duì)乘務(wù)任務(wù)Bm的論域D(Bm)進(jìn)行約減，轉(zhuǎn)Step5。

4 算例分析

4.1 算例求解

某地鐵線路的站點(diǎn)設(shè)置見(jiàn)圖4，共有北郊、軍區(qū)和太平3個(gè)乘務(wù)分割點(diǎn)。其中北郊為車(chē)輛段，北郊和軍區(qū)為出/退勤點(diǎn)、軍區(qū)和太平為乘務(wù)輪換休息點(diǎn)、軍區(qū)為用餐點(diǎn)。

某日此地鐵線路有101～120共20個(gè)運(yùn)行車(chē)次，其中101～118車(chē)次之間的間隔為10 min、單向運(yùn)行次數(shù)都為18、在同一單向運(yùn)行中相同乘務(wù)分割點(diǎn)輪換休息時(shí)間相同，119和120車(chē)次之間的間隔為5 min、單向運(yùn)行次數(shù)都為4、在同一單向運(yùn)行中相同乘務(wù)分割點(diǎn)輪換休息時(shí)間相同。不同車(chē)次相同運(yùn)行區(qū)間的運(yùn)行時(shí)間相同，其中北郊和軍區(qū)之間雙向運(yùn)行時(shí)間均為10 min，軍區(qū)和太平之間雙向運(yùn)行時(shí)間均為45 min，則依據(jù)運(yùn)行圖和乘務(wù)分割點(diǎn)劃分得到101和119車(chē)次的乘務(wù)任務(wù)段見(jiàn)表3，表格中b1,l(1≤l≤20)為101車(chē)次的乘務(wù)任務(wù)段，b19,l(1≤l≤6)為119車(chē)次的乘務(wù)任務(wù)段，102～118車(chē)次的乘務(wù)任務(wù)段劃分類(lèi)似于101車(chē)次的乘務(wù)任務(wù)段劃分，120車(chē)次的乘務(wù)任務(wù)段劃分類(lèi)似于119車(chē)次的乘務(wù)任務(wù)段劃分。模型中其他參數(shù)見(jiàn)表4。

圖4 某地鐵線路的站點(diǎn)設(shè)置示意圖

表3 某地鐵線路某日乘務(wù)任務(wù)段

表4 某地鐵線路乘務(wù)計(jì)劃參數(shù)表

本算例的乘務(wù)任務(wù)段總數(shù)為372，變量有1 442個(gè)，約束的數(shù)量級(jí)為百萬(wàn)，在Inter Core i3-2 310 M 2.1 GHz & DRAM 2 G & Windows XP &.NET Framework 4.5環(huán)境下的PC機(jī)上運(yùn)行本模型及算法，根據(jù)現(xiàn)場(chǎng)需求設(shè)置算法總的求解時(shí)間上限為200 s或者總的迭代次數(shù)上限為20 000次。CPr-HBT算法的求解過(guò)程見(jiàn)圖5，乘務(wù)任務(wù)配對(duì)結(jié)果見(jiàn)表5、圖6。從圖5中可知求得較優(yōu)解至少需要迭代5 600次，總的花費(fèi)時(shí)間為56.35 s，產(chǎn)生了56個(gè)乘務(wù)任務(wù)，在這些乘務(wù)任務(wù)中需要進(jìn)行31次便乘，乘務(wù)員之間工作時(shí)間最多相差了310 min。

圖5 CPr-HBT混合算法的求解過(guò)程

圖6中早班、白班和夜班各有兩種情況。早01～早18的乘務(wù)任務(wù)為?i=1…18:{bi,l|l=1…9}，早19～早20的乘務(wù)任務(wù)為?i=19…20:{bi,l|l=1…6}；白01～白09的乘務(wù)任務(wù)為?i=1…9:{bi,l|l=10…16}，白10～白18的乘務(wù)任務(wù)為?i=10…18:{bi,l|l=10…15}；夜01～夜09的乘務(wù)任務(wù)為?i=10…18:{bi,l|l=16…20}，夜10～夜18的乘務(wù)任務(wù)為?i=1…9:{bi,l|l=17…20}。

從圖5中的算法求解過(guò)程可以看出：目標(biāo)函數(shù)值是單調(diào)遞增或者遞減的，較少出現(xiàn)震蕩，說(shuō)明通過(guò)約束傳播技術(shù)保證了最優(yōu)解的求解效率和概率。通過(guò)圖6可得：乘務(wù)任務(wù)覆蓋了表1中所有的乘務(wù)任務(wù)段，所有的乘務(wù)任務(wù)滿足所有約束條件，而且滿足現(xiàn)場(chǎng)的對(duì)計(jì)劃編制的時(shí)效性需求。

表5 乘務(wù)任務(wù)配對(duì)結(jié)果

圖6 乘務(wù)任務(wù)配對(duì)結(jié)果示意圖

4.2 算法比較

為了驗(yàn)證本算法的求解效率，在不改變其他參數(shù)的情況下，使用文獻(xiàn)[4]中不帶約束傳播的深度優(yōu)先回溯算法(DFS)求解本模型，求解過(guò)程見(jiàn)圖7。

圖7 使用DFS算法目標(biāo)函數(shù)的求解過(guò)程

DFS達(dá)到迭代上限20 000次時(shí)，形成的乘務(wù)任務(wù)數(shù)為112個(gè)乘務(wù)任務(wù)，有102次便乘，乘務(wù)員之間總的工作時(shí)間相差了308 min。因此，不帶約束傳播的改進(jìn)回溯算法的求解效率和求解質(zhì)量都比本文算法要低，驗(yàn)證了本混合算法的高效性。

5 結(jié)論

本文綜合考慮了乘務(wù)人員的工作效率、工作量的均衡性和乘務(wù)員便乘等因素，建立了考慮便乘的乘務(wù)任務(wù)配對(duì)的約束優(yōu)化模型。之后設(shè)計(jì)了約束傳播與啟發(fā)式回溯的混合算法求解了模型；最后通過(guò)現(xiàn)場(chǎng)實(shí)際算例驗(yàn)證結(jié)果表明：與現(xiàn)場(chǎng)和其他算法相比，本論文的模型和算法優(yōu)勢(shì)明顯。本論文提出的使用約束程序方法對(duì)于考慮便乘的地鐵乘務(wù)任務(wù)配對(duì)優(yōu)化問(wèn)題是可行的，模型符合現(xiàn)場(chǎng)實(shí)際業(yè)務(wù)需求，保證了排班計(jì)劃的適用性；本混合算法求解效率和穩(wěn)定性較高，滿足現(xiàn)場(chǎng)對(duì)排班計(jì)劃編制的實(shí)時(shí)性要求。本論文提出的模型和算法已經(jīng)成功應(yīng)用于地鐵車(chē)輛基地綜合自動(dòng)化系統(tǒng)中，結(jié)合乘務(wù)任務(wù)指派優(yōu)化方法，共同輔助司乘派班調(diào)度工作，降低了派班調(diào)度員的工作強(qiáng)度，提高了作業(yè)效率。