基于任務(wù)均衡的乘務(wù)排班計(jì)劃優(yōu)化編制方法研究

陳霽巖，潘寒川，劉志鋼，吳 強(qiáng)，趙 磊

（1.上海工程技術(shù)大學(xué) 城市軌道交通學(xué)院，上海 201600；2.上海地鐵第二運(yùn)營(yíng)有限公司，上海 200063；3.上海地鐵第二運(yùn)營(yíng)有限公司 質(zhì)量安全部，上海 200063）

0 引言

乘務(wù)計(jì)劃是城市軌道交通運(yùn)營(yíng)中的重要環(huán)節(jié)，主要解決軌道交通乘務(wù)員的值乘問(wèn)題。國(guó)內(nèi)多數(shù)城市軌道交通的乘務(wù)計(jì)劃由各線(xiàn)路乘務(wù)部門(mén)編制完成，消耗時(shí)間長(zhǎng)，變更難度大。乘務(wù)計(jì)劃分為乘務(wù)排班計(jì)劃與乘務(wù)輪轉(zhuǎn)計(jì)劃，其中乘務(wù)排班計(jì)劃根據(jù)給定的列車(chē)運(yùn)行圖，將運(yùn)行線(xiàn)根據(jù)線(xiàn)路條件與乘務(wù)制度進(jìn)行分割與重組，從而得到可行的任務(wù)號(hào)集合；乘務(wù)輪轉(zhuǎn)計(jì)劃則是在當(dāng)期各個(gè)運(yùn)行圖的乘務(wù)排班計(jì)劃編制完畢后，根據(jù)列車(chē)運(yùn)行圖屬性(工作日、節(jié)假日、延長(zhǎng)圖等)按照一定的規(guī)則使得乘務(wù)員輪流執(zhí)行任務(wù)。乘務(wù)排班計(jì)劃作為乘務(wù)計(jì)劃的第一步，其編制質(zhì)量對(duì)整個(gè)乘務(wù)計(jì)劃編制結(jié)果有直接的影響。

近年來(lái)，乘務(wù)排班計(jì)劃編制優(yōu)化在國(guó)內(nèi)外引起學(xué)者廣泛的研究，Michael等[1]應(yīng)用圖論解決城市軌道交通車(chē)底運(yùn)用和乘務(wù)計(jì)劃中的每個(gè)子問(wèn)題，不同于以往完成編制運(yùn)行圖后再編制乘務(wù)計(jì)劃，而是同時(shí)進(jìn)行運(yùn)行圖與乘務(wù)計(jì)劃編制，后計(jì)算實(shí)例證明比現(xiàn)實(shí)際使用更低。根據(jù)香港輕軌乘務(wù)排班計(jì)劃的特點(diǎn)，Chu等[2]將乘務(wù)排班計(jì)劃分為2個(gè)階段進(jìn)行研究，依次采用最短路算法、對(duì)稱(chēng)匹配及改進(jìn)的遺傳算法進(jìn)行求解。Elizondo等[3]在對(duì)城市軌道交通乘務(wù)計(jì)劃建模時(shí)，采用人工智能領(lǐng)域的方法來(lái)表示狀態(tài)空間，分別使用基于網(wǎng)絡(luò)圖的貪心搜索和禁忌搜索算法來(lái)解決問(wèn)題，最后通過(guò)數(shù)據(jù)進(jìn)行驗(yàn)證。針對(duì)城市軌道交通的特點(diǎn)，李獻(xiàn)忠等[4-5]提出3種乘務(wù)排班優(yōu)化模型，分別為基于廣義費(fèi)用最小成本、時(shí)間成本最小和總時(shí)間消耗最小，并采用禁忌搜索算法、模擬進(jìn)化算法和最小費(fèi)用最大流算法對(duì)模型進(jìn)行求解。潘寒川等[6]在考慮乘務(wù)員用餐的約束條件下，提出DHM和VGM 2種編制方法，探討 2 種方法在多個(gè)“就餐點(diǎn)”及“網(wǎng)絡(luò)線(xiàn)路乘務(wù)員共享”方法下的適用性和可行性。針對(duì)目前不同地鐵線(xiàn)路具有不同的高峰系數(shù)，潘寒川等[7]提出CRM 和PIM 乘務(wù)計(jì)劃編制方法，可針對(duì)線(xiàn)路情況選擇不同編制方法，提高精細(xì)化管理。

目前針對(duì)乘務(wù)排班計(jì)劃編制問(wèn)題的模型及算法研究較多，但在編制中綜合考慮城市軌道交通乘務(wù)制度的相關(guān)研究較少[8-9]。隨著各個(gè)城市地鐵興建與發(fā)展，乘務(wù)制度與乘務(wù)規(guī)則開(kāi)始出現(xiàn)差異化。目前國(guó)內(nèi)部分線(xiàn)路開(kāi)始采用計(jì)件制薪資方案，即綜合計(jì)算開(kāi)行里程與工時(shí)計(jì)薪。通常乘務(wù)班組中每個(gè)乘務(wù)員的開(kāi)行公里數(shù)與值乘時(shí)長(zhǎng)是不均衡的，除了導(dǎo)致乘務(wù)員收入無(wú)法得到均衡，還會(huì)使得部分乘務(wù)員值乘時(shí)間過(guò)長(zhǎng)從而存在安全隱患。因此，在既有研究基礎(chǔ)上提出以任務(wù)均衡為目標(biāo)的乘務(wù)排班計(jì)劃編制模型，構(gòu)建經(jīng)典集合分割主問(wèn)題模型及基于任務(wù)均衡與乘務(wù)特色約束子問(wèn)題模型。利用計(jì)算機(jī)編程語(yǔ)言實(shí)現(xiàn)主規(guī)劃部分求解，同時(shí)設(shè)計(jì)基于影子價(jià)格選擇的標(biāo)號(hào)法用于求解子規(guī)劃部分，并以上海市軌道交通某條線(xiàn)路為例，驗(yàn)證模型與算法的有效性和效率性。該方法擬尋求在實(shí)際運(yùn)營(yíng)中科學(xué)合理地控制成本，提高運(yùn)輸效率，促進(jìn)企業(yè)長(zhǎng)期可持續(xù)發(fā)展，加強(qiáng)企業(yè)精細(xì)化管理，同時(shí)也為乘務(wù)排班計(jì)劃問(wèn)題的研究提供理論依據(jù)。

1 基于任務(wù)均衡的乘務(wù)排班計(jì)劃優(yōu)化編制方法研究

1.1 乘務(wù)排班計(jì)劃編制影響因素分析

乘務(wù)排班計(jì)劃編制問(wèn)題本質(zhì)上是一個(gè)指派問(wèn)題，是將乘務(wù)員與列車(chē)進(jìn)行綁定的過(guò)程，即在規(guī)定的乘務(wù)員數(shù)量下，指派相應(yīng)的乘務(wù)員執(zhí)行部分列車(chē)開(kāi)行任務(wù)，從而保證每個(gè)運(yùn)營(yíng)時(shí)間段的每列列車(chē)均有乘務(wù)員值乘。城市軌道交通每條線(xiàn)路由停車(chē)場(chǎng)、車(chē)站與軌道組成。停車(chē)場(chǎng)是列車(chē)出庫(kù)、回庫(kù)、維修養(yǎng)護(hù)及乘務(wù)員辦理出勤、退勤的地點(diǎn)；車(chē)站根據(jù)功能可劃分為：輪乘站、交接站、就餐站。

（1）輪乘站設(shè)置對(duì)于乘務(wù)排班計(jì)劃編制影響。根據(jù)《國(guó)務(wù)院關(guān)于職工工作時(shí)間的規(guī)定》：“因工作性質(zhì)或者生產(chǎn)特點(diǎn)的限制，不能實(shí)行每日工作8 h、每周工作40 h標(biāo)準(zhǔn)工時(shí)制度，按照國(guó)家有關(guān)規(guī)定，可以實(shí)行其他工作和休息辦法?！庇捎诔藙?wù)員工作性質(zhì)的特殊性，通常規(guī)定乘務(wù)員在連續(xù)駕駛1 h左右需進(jìn)行休息，從而保證行車(chē)安全，避免疲勞駕駛。各個(gè)線(xiàn)路管理部通常根據(jù)線(xiàn)路長(zhǎng)度、車(chē)站位置及設(shè)施設(shè)備條件設(shè)定數(shù)個(gè)輪乘站，供乘務(wù)員在連續(xù)駕駛一定時(shí)長(zhǎng)后下車(chē)休息。通常以輪乘間隔來(lái)規(guī)定休息時(shí)長(zhǎng)，若乘務(wù)員A需要休息n個(gè)輪乘間隔，則當(dāng)乘務(wù)員A在輪乘站下車(chē)休息后，在駛過(guò)n輛列車(chē)后(包含乘務(wù)員下車(chē)時(shí)所駕駛列車(chē))，當(dāng)?shù)趎+ 1輛列車(chē)進(jìn)站后替換該列車(chē)乘務(wù)員B繼續(xù)駕駛，乘務(wù)員B開(kāi)始輪乘休息。乘務(wù)輪乘過(guò)程如圖1所示(該站輪乘間隔為2)。

（2）交接站設(shè)置對(duì)于乘務(wù)排班計(jì)劃編制影響。由于目前城市軌道交通線(xiàn)路長(zhǎng)度不斷延長(zhǎng)，僅靠停車(chē)場(chǎng)提供出退勤管理已無(wú)法滿(mǎn)足線(xiàn)路乘務(wù)排班計(jì)劃編制需求，通常由線(xiàn)路管理部綜合車(chē)站設(shè)施設(shè)備條件、乘務(wù)員住址等設(shè)立交接站從而滿(mǎn)足乘務(wù)員出退勤需求。交接站設(shè)置個(gè)數(shù)的增加，會(huì)使得乘務(wù)任務(wù)生成更加靈活，但同時(shí)會(huì)導(dǎo)致排列組合的可能性增加，使得求解難度上升。

（3）就餐站設(shè)置對(duì)于乘務(wù)排班計(jì)劃編制影響。乘務(wù)員的工作班制通常為四班三運(yùn)轉(zhuǎn)，即日—夜—早—休，其中日班工作時(shí)長(zhǎng)會(huì)覆蓋午餐時(shí)間，為滿(mǎn)足乘務(wù)員午餐需求，需設(shè)定具備條件站點(diǎn)為就餐站，保證日班每位乘務(wù)員可在11 : 00—13 : 00完成就餐。就餐站的數(shù)量根據(jù)線(xiàn)路長(zhǎng)度決定，每條線(xiàn)路通常設(shè)置1至2個(gè)就餐站于線(xiàn)路中間位置，供乘務(wù)員就餐、休息。

對(duì)于乘務(wù)排班計(jì)劃編制而言，由于在非功能性車(chē)站通常不會(huì)進(jìn)行乘務(wù)員的變換，因而非功能性車(chē)站不會(huì)影響乘務(wù)排班計(jì)劃編制。為此，在后續(xù)模型構(gòu)建及算法設(shè)計(jì)過(guò)程中，將乘務(wù)數(shù)據(jù)進(jìn)行篩選，僅考慮功能站的列車(chē)到發(fā)。

1.2 基于任務(wù)均衡的乘務(wù)計(jì)劃優(yōu)化編制模型構(gòu)建

乘務(wù)排班計(jì)劃編制問(wèn)題，是一個(gè)典型的NPhard問(wèn)題，隨著線(xiàn)路復(fù)雜程度的提升，變量的數(shù)目會(huì)隨之呈爆炸式增長(zhǎng)。在乘務(wù)排班計(jì)劃編制問(wèn)題中，唯一需要分配的資源是乘務(wù)員，編制過(guò)程為將列車(chē)運(yùn)行線(xiàn)按輪乘站、交接站進(jìn)行分割后，按一定的規(guī)則進(jìn)行重組，主要輸入數(shù)據(jù)如下。①一段時(shí)間內(nèi)的列車(chē)運(yùn)行圖數(shù)據(jù)：包括列車(chē)車(chē)底號(hào)、列車(chē)在各個(gè)站點(diǎn)的到發(fā)時(shí)間、交路信息號(hào)；②線(xiàn)路基本條件：包括全線(xiàn)路站點(diǎn)、輪乘站、就餐站及其輪乘間隔、交接站、停車(chē)場(chǎng)位置；③對(duì)生成任務(wù)號(hào)的硬約束：乘務(wù)員值乘區(qū)段全覆蓋、值乘區(qū)段鄰接、乘務(wù)員單次值乘時(shí)間上下限；④對(duì)生成任務(wù)號(hào)的軟約束：時(shí)間均衡度、里程均衡度、乘務(wù)員偏好。輸出數(shù)據(jù)為任務(wù)號(hào)表，包含任務(wù)號(hào)個(gè)數(shù)與各個(gè)任務(wù)號(hào)的開(kāi)行路徑，每個(gè)任務(wù)即對(duì)應(yīng)一個(gè)乘務(wù)員的每日任務(wù)，輸出結(jié)果必須滿(mǎn)足所有硬約束、符合線(xiàn)路條件，同時(shí)盡量將成本降至最低并保證一定的均衡度，直至乘務(wù)排班計(jì)劃編制完畢。

1.2.1 主問(wèn)題模型構(gòu)建

在以往的城軌乘務(wù)排班計(jì)劃編制研究中，通常采用集合覆蓋模型與集合分割模型建立乘務(wù)問(wèn)題模型[10]。集合覆蓋模型允許編制的排班計(jì)劃中存在隨乘情況，即一位乘務(wù)員在A站下車(chē)，但無(wú)法在A站接到后續(xù)規(guī)定時(shí)間內(nèi)的車(chē)次，需搭乘列車(chē)隨乘到B站接車(chē)。隨乘情況的增加降低了乘務(wù)排班計(jì)劃整體的工時(shí)有效率，增加了運(yùn)營(yíng)開(kāi)支，采用集合分割模型建立主問(wèn)題模型，具體如下。

式中：z為總成本，是最后生成并選入乘務(wù)排班計(jì)劃的所有乘務(wù)任務(wù)成本之和；cj為第j個(gè)乘務(wù)任務(wù)的成本；aij表示生成的第j個(gè)乘務(wù)任務(wù)是否包含乘務(wù)片段i，包含則aij= 1，不包含則aij= 0；xj表示第j個(gè)乘務(wù)任務(wù)是否采用，采用則xj= 1，不采則xj= 0；U為乘務(wù)片段集合；R為乘務(wù)任務(wù)集合，每個(gè)乘務(wù)任務(wù)包含1個(gè)或多個(gè)乘務(wù)片段。

為對(duì)此問(wèn)題進(jìn)行求解并獲取其對(duì)偶變量，需先將主問(wèn)題進(jìn)行線(xiàn)性松弛得到一個(gè)線(xiàn)性規(guī)劃問(wèn)題，在迭代完成后，對(duì)主問(wèn)題采用分支定價(jià)法進(jìn)行剪枝從而得到0-1整數(shù)解，線(xiàn)性松弛后的模型如下。

1.2.2 子問(wèn)題模型構(gòu)建

在主問(wèn)題中，僅考慮了乘務(wù)任務(wù)對(duì)于乘務(wù)片段的全覆蓋，對(duì)于輪乘、單次值乘時(shí)間、總值乘時(shí)間等約束則在子規(guī)劃中考慮。子規(guī)劃模型建立如下。

式中：R為所生成的新乘務(wù)任務(wù)的總費(fèi)用；te,i為第i個(gè)乘務(wù)片段的到達(dá)時(shí)間，s；tb,i為第i個(gè)乘務(wù)片段的發(fā)出時(shí)間，s；α為超時(shí)未休懲罰權(quán)重系數(shù)；f為連續(xù)駕駛時(shí)長(zhǎng)超1.2 h未休息次數(shù)；β為工時(shí)有效率權(quán)重系數(shù)；r(p)為所生成乘務(wù)任務(wù)中第p個(gè)乘務(wù)片段車(chē)底號(hào)；te,p,r(p)為所生成乘務(wù)任務(wù)中第p個(gè)乘務(wù)片段的到達(dá)時(shí)間，s；tb,q,r(q)為所生成乘務(wù)任務(wù)中第p個(gè)乘務(wù)片段的發(fā)出時(shí)間，s；Ts為單次連續(xù)值乘最大時(shí)長(zhǎng)，s；Ta,min，Ta,max為當(dāng)日最小、最大值乘時(shí)間，s。

由于所選的上海地鐵線(xiàn)路乘務(wù)數(shù)據(jù)初始數(shù)量為18 000條，在對(duì)數(shù)據(jù)經(jīng)過(guò)清洗和篩選重組后，乘務(wù)數(shù)據(jù)量減少為1 500條。而在以往的研究中，通常數(shù)據(jù)量在500左右，這與上海地鐵的線(xiàn)路長(zhǎng)度、開(kāi)行間隔、客流數(shù)與線(xiàn)路較為復(fù)雜存在一定的關(guān)系。由于主規(guī)劃和子規(guī)劃每迭代一次就需要對(duì)子問(wèn)題進(jìn)行一次求解，若采用以往研究中的方法求解子問(wèn)題可能會(huì)導(dǎo)致求解速度過(guò)慢。以求解主問(wèn)題所得的對(duì)偶變量最大值所對(duì)應(yīng)的節(jié)點(diǎn)為起始點(diǎn)進(jìn)行搜索，并選取生成后數(shù)個(gè)子問(wèn)題目標(biāo)函數(shù)最小的乘務(wù)任務(wù)，添加入主問(wèn)題，從而加速求解并保證解的質(zhì)量。

當(dāng)算法迭代至不存在檢驗(yàn)數(shù)小于0時(shí)，重設(shè)主問(wèn)題目標(biāo)函數(shù)，以求得值乘時(shí)長(zhǎng)與里程均衡。

式中：γ為時(shí)長(zhǎng)均衡權(quán)重系數(shù)；δ為里程均衡權(quán)重系數(shù)；n為迭代完畢后主問(wèn)題中乘務(wù)任務(wù)的總數(shù)量；w為迭代完畢后主問(wèn)題中乘務(wù)任務(wù)集合；cj為第j個(gè)乘務(wù)任務(wù)值乘時(shí)間費(fèi)用；lj為第j個(gè)乘務(wù)任務(wù)值乘里程，km。

1.3 基于任務(wù)均衡的乘務(wù)排班計(jì)劃優(yōu)化編制模型求解

1.3.1 成本函數(shù)

主問(wèn)題在進(jìn)行線(xiàn)性松弛之后，得到的問(wèn)題為一個(gè)線(xiàn)性規(guī)劃問(wèn)題。對(duì)于一個(gè)線(xiàn)性規(guī)劃問(wèn)題，通常的解決辦法是利用單純形法進(jìn)行求解。一個(gè)標(biāo)準(zhǔn)的線(xiàn)性規(guī)劃問(wèn)題如下。

式中：cT為線(xiàn)性規(guī)劃問(wèn)題的成本系數(shù)向量；x為變量向量；A為變量系數(shù)矩陣；b為約束右端常數(shù)項(xiàng)向量。

公式(14)可通過(guò)公式(15)進(jìn)行變換代入得到公式(16)，其中下標(biāo)B表示基變量，下標(biāo)N表示非基變量。

觀察公式(16)右端容易得到，左邊加項(xiàng)對(duì)于一個(gè)既定的問(wèn)題，是一個(gè)常數(shù)。右邊加項(xiàng)若?n∈N使得則可以適當(dāng)增加xN的值，使得目標(biāo)值更優(yōu)；若則此時(shí)令所有非基變量取0，可獲得最優(yōu)解。因此，在單純形法中稱(chēng)為檢驗(yàn)數(shù)。

1.3.2 迭代方法

列生成思想求解過(guò)程則是利用上述推導(dǎo)，首先在主問(wèn)題中構(gòu)造一個(gè)初始可行解，隨后在子問(wèn)題中檢索是否存在乘務(wù)任務(wù)xj使得檢驗(yàn)數(shù)小于0。若存在，則說(shuō)明將此任務(wù)加入到主問(wèn)題可以使得主問(wèn)題進(jìn)一步優(yōu)化。當(dāng)子問(wèn)題中所有乘務(wù)任務(wù)的檢驗(yàn)數(shù)均大于等于0時(shí)結(jié)束迭代，并對(duì)主問(wèn)題進(jìn)行剪枝后求解得出編制結(jié)果。列生成思想求解過(guò)程如圖2所示。

圖2 列生成思想求解過(guò)程Fig.2 Solving process in column generation

2 實(shí)例分析

以上海市某條軌道交通線(xiàn)路為例，對(duì)所建立的模型算法進(jìn)行求解驗(yàn)證。該線(xiàn)由西至東總長(zhǎng)38.83 km，共有31個(gè)車(chē)站、3個(gè)輪乘站與2個(gè)停車(chē)場(chǎng)，現(xiàn)有乘務(wù)排班計(jì)劃主要依靠人工經(jīng)驗(yàn)進(jìn)行編制，模型構(gòu)建及算法設(shè)計(jì)通過(guò)計(jì)算機(jī)編程語(yǔ)言實(shí)現(xiàn)。

2.1 數(shù)據(jù)處理

乘務(wù)排班計(jì)劃編制的數(shù)據(jù)為信號(hào)系統(tǒng)所記錄的數(shù)據(jù)，內(nèi)容為：車(chē)次號(hào)、車(chē)站名、到點(diǎn)、發(fā)點(diǎn)、交路號(hào)等。此時(shí)的數(shù)據(jù)規(guī)模較大，若直接對(duì)此進(jìn)行計(jì)劃編制，會(huì)導(dǎo)致求解速度過(guò)慢或內(nèi)存溢出。而在乘務(wù)排班計(jì)劃編制中，非功能站(輪乘站、交接站、出退勤站)乘務(wù)員通常不會(huì)有更換車(chē)底值乘的動(dòng)作，因而對(duì)數(shù)據(jù)進(jìn)行清洗重組處理。數(shù)據(jù)清洗重組過(guò)程如圖3所示。

圖3 數(shù)據(jù)清洗重組過(guò)程Fig.3 Data cleaning and reorganizing process

乘務(wù)數(shù)據(jù)清洗重組思路基本適用于大部分的地鐵線(xiàn)路乘務(wù)排班計(jì)劃，處理后的結(jié)果可直接由模型算法程序進(jìn)行讀取求解計(jì)算。

2.2 導(dǎo)入求解

所建模型中需輸入?yún)?shù)共有4個(gè)：α為值乘超1.2 h未休息次數(shù)懲罰權(quán)重系數(shù)；β為工時(shí)有效率權(quán)重系數(shù)；γ為值乘時(shí)間費(fèi)用均衡度權(quán)重系數(shù)；δ為值乘里程均衡系數(shù)。在計(jì)算值乘時(shí)間費(fèi)用成本時(shí)，取α= 0.3，β= 1。在求值乘時(shí)間費(fèi)用與值乘里程均衡時(shí)，取γ= 2，δ以數(shù)值間隔為0.1在0.5 ～ 1.5間取值進(jìn)行多次計(jì)算，不同δ權(quán)重系數(shù)下的值乘時(shí)間費(fèi)用均衡度如圖4所示，不同δ權(quán)重系數(shù)下的值乘里程均衡度如圖5所示，不同δ權(quán)重系數(shù)下工時(shí)有效率如圖6所示。

圖5 不同δ權(quán)重系數(shù)下的值乘里程均衡度Fig.5 Rostering mileage balance at different weight coefficients δ

觀察圖4至圖6可知，當(dāng)δ取1.2時(shí)，所輸出的乘務(wù)排班計(jì)劃具有更優(yōu)的任務(wù)均衡度與工時(shí)有效率。乘務(wù)任務(wù)輸出如表1所示，其中以(1301) -(22 911，24 005) - (JYR3，JSJR2)為例進(jìn)行說(shuō)明，1301為車(chē)次號(hào)，為乘務(wù)員登乘重要憑證之一；(22 911，24 005)為該乘務(wù)作業(yè)段的開(kāi)始時(shí)間與結(jié)束時(shí)間，從當(dāng)日0點(diǎn)開(kāi)始以秒計(jì)算，s； (JYR3，JSJR2)為該乘務(wù)作業(yè)段的開(kāi)始地點(diǎn)與結(jié)束地點(diǎn)；“=”符號(hào)連接了相鄰的2個(gè)乘務(wù)片段。

表1 乘務(wù)任務(wù)輸出Tab.1 Crew taskoutput

圖4 不同δ權(quán)重系數(shù)下的值乘時(shí)間均衡度Fig.4 Rostering time balance at different weight coefficients δ

圖6 不同δ權(quán)重系數(shù)下工時(shí)有效率Fig.6 Man-hour efficiency at different weight coefficients δ

δ取1.2時(shí)，乘務(wù)排班計(jì)劃值乘時(shí)長(zhǎng)與上班時(shí)長(zhǎng)如圖7所示，乘務(wù)排班計(jì)劃值乘里程如圖8所示，乘務(wù)排班計(jì)劃工時(shí)有效率如圖9所示。

圖7 乘務(wù)排班計(jì)劃值乘時(shí)長(zhǎng)與上班時(shí)長(zhǎng)Fig.7 Rostering time and work time of crew scheduling

圖8 乘務(wù)排班計(jì)劃值乘里程Fig.8 Rostering mileage of crew scheduling

圖9 乘務(wù)排班計(jì)劃工時(shí)有效率Fig.9 Man-hour efficiency of crew scheduling

可見(jiàn)，基于任務(wù)均衡的乘務(wù)排班計(jì)劃優(yōu)化編制方法所計(jì)算求解的乘務(wù)任務(wù)具有較優(yōu)的任務(wù)均衡和較高的工時(shí)有效率，平均工時(shí)有效率達(dá)到了86.6%。

3 結(jié)束語(yǔ)

基于任務(wù)均衡的乘務(wù)排班計(jì)劃優(yōu)化編制方法充分考慮目前城市軌道交通乘務(wù)員計(jì)件制薪資體系，以所生成的乘務(wù)排班計(jì)劃成本最小為目標(biāo)，構(gòu)建集合分割主規(guī)劃模型與乘務(wù)任務(wù)生成子規(guī)劃模型，并設(shè)計(jì)基于影子價(jià)格選擇的標(biāo)號(hào)法進(jìn)行求解完成迭代。案例分析中的求解結(jié)果驗(yàn)證了模型與算法的有效性和效率性，并且在上海地鐵線(xiàn)路較大規(guī)模的乘務(wù)數(shù)據(jù)下仍有較好的求解速度，可適應(yīng)未來(lái)城市軌道交通路網(wǎng)的進(jìn)一步發(fā)展。方法中初始解所選取的系數(shù)矩陣為一個(gè)單位矩陣，優(yōu)點(diǎn)是生成方法較為簡(jiǎn)便，缺點(diǎn)是一定程度上會(huì)影響求解的速度與結(jié)果，未來(lái)可針對(duì)如何快速構(gòu)造一個(gè)較好的初始解進(jìn)行深入研究。