許仲豪， 杜 鵬，2

(1. 北京交通大學(xué) 交通運輸學(xué)院， 北京 100044； 2. 北京交通大學(xué) 城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點實驗室， 北京 100044)

城市軌道交通乘務(wù)計劃是安排乘務(wù)員值乘的工作計劃，是城市軌道交通運營計劃的重要組成部分。隨著人工成本越來越高，合理、優(yōu)化的乘務(wù)計劃在降低運營成本方面的作用日益受到重視，關(guān)于乘務(wù)計劃優(yōu)化編制方法的研究也成為城市軌道交通運營領(lǐng)域的一個研究熱點。乘務(wù)計劃一般分為乘務(wù)排班計劃和乘務(wù)輪班計劃，其中乘務(wù)排班計劃是尋找列車車次與乘務(wù)任務(wù)之間的對應(yīng)關(guān)系，是乘務(wù)輪班計劃的基礎(chǔ)，也是整個乘務(wù)計劃編制過程中最復(fù)雜、難度最大的部分。

城市軌道交通乘務(wù)排班計劃編制過程中，主要涉及以下幾個概念。車底是列車周轉(zhuǎn)的基本單位，指執(zhí)行一次周轉(zhuǎn)任務(wù)的一列列車。乘務(wù)作業(yè)段是乘務(wù)員值乘的基本單元，代表一列車從一個輪乘站前往下一個輪乘站之間的駕駛?cè)蝿?wù)。乘務(wù)任務(wù)是一日內(nèi)一組滿足實際工作中的約束的可由一名乘務(wù)員值乘的乘務(wù)作業(yè)段的組合，乘務(wù)任務(wù)的工作時長為其第一個乘務(wù)作業(yè)段的開始時間至最后一個乘務(wù)作業(yè)段的結(jié)束時間。乘務(wù)日計劃是所有乘務(wù)員一日的工作計劃，是乘務(wù)任務(wù)的組合，且這一組乘務(wù)任務(wù)中包含了所有乘務(wù)作業(yè)段。乘務(wù)計劃編制是將車底周轉(zhuǎn)圖以輪乘站為邊界分解為乘務(wù)作業(yè)段，再將乘務(wù)作業(yè)段相互組合成為乘務(wù)任務(wù)，最終形成乘務(wù)日計劃的過程。

乘務(wù)計劃編制問題是根據(jù)已有的列車運行計劃編制乘務(wù)日計劃的問題，是交通領(lǐng)域研究的熱點之一。目前研究者們對乘務(wù)計劃編制問題的研究主要集中于鐵路、航空及城市地面公共交通行業(yè)。乘務(wù)計劃編制問題由于實際工作中需求不同，目標函數(shù)多樣、約束條件復(fù)雜、解空間巨大，已經(jīng)被歸為NP-Complete或NP-Hard問題，因此針對該問題的算法也多局限于啟發(fā)式算法：褚飛躍等[1]、楊國元等[2]、夏平等[3]、閆永光等[4]分別將蟻群算法、遺傳算法、啟發(fā)回溯算法、模擬進化算法用于鐵路領(lǐng)域的乘務(wù)計劃編制；李耀華等[5]、吳東華等[6]分別使用遺傳算法與結(jié)合模糊數(shù)學(xué)的啟發(fā)式算法求解航空領(lǐng)域的乘務(wù)計劃編制問題；陳明明等[7-8]則在地面公交領(lǐng)域使用禁忌搜索算法優(yōu)化進行乘務(wù)計劃優(yōu)化編制。

城市軌道的乘務(wù)計劃編制與其他交通方式有所不同，具有乘務(wù)作業(yè)段時間短、乘務(wù)員可在異地交接車的特點，因此不能將適用于其他交通方式的乘務(wù)計劃編制方法生搬硬套進城市軌道交通領(lǐng)域中。在城市軌道領(lǐng)域，研究者們已經(jīng)做出了大量的研究：李獻忠等[9]將乘務(wù)計劃分作劃分乘務(wù)作業(yè)段與編制乘務(wù)日計劃兩步進行，將問題化為最小費用最大流的問題進行求解；張增勇等[10]在描述問題時，將約束條件分為硬約束與軟約束，并對不滿足軟約束的乘務(wù)任務(wù)進行懲罰，在此基礎(chǔ)上利用離散粒子群算法對問題進行求解，能夠有效減少不滿足軟約束的乘務(wù)任務(wù)數(shù)；豐富等[11]參照中國的“兩班倒”工作制度，以乘務(wù)任務(wù)在車時長的方差為目標函數(shù)建立了乘務(wù)計劃編制的數(shù)學(xué)模型，并設(shè)計了一套可行的遺傳算法來求解。

以上研究大多直接使用啟發(fā)式方法求解問題，能在可接受的時間內(nèi)得到可行的解。對于乘務(wù)計劃編制這類擁有大量乘務(wù)作業(yè)段的問題，啟發(fā)式方法有很大的應(yīng)用空間。在規(guī)劃方法求解方面，以列生成為代表的分解算法也是當前的研究熱點之一。Potthoff等[12]使用一種改進的列生成算法，以荷蘭的一段城際軌道網(wǎng)的運營為例，探究了突發(fā)情況下的乘務(wù)調(diào)整計劃編制，并取得了較好的編制結(jié)果；Janacek等[13]提出了一種周期性的乘務(wù)計劃編制方法，根據(jù)時間段將問題分為多個區(qū)間，每個區(qū)間均作為列生成算法中的一個子問題，便于并行求解，加快新列的生成速度；陳仕軍等[14]考慮了中式就餐的特殊約束，以列生成算法為基礎(chǔ)設(shè)計了求解方法；王瑩等[15]針對客運專線的特點，建立了集合覆蓋模型并設(shè)計了基于列生成算法的求解方法。

考慮到乘務(wù)計劃編制問題具有較強的地域性，實際工作中的目標與約束也有較大差異。直接使用啟發(fā)式算法，雖然能夠獲得可行解，但是求解過程比較特殊，且對具體問題的依賴性較強。規(guī)劃方法具有模型嚴謹?shù)膬?yōu)點，但是應(yīng)用在乘務(wù)計劃編制領(lǐng)域，也存在求解方法較為復(fù)雜、繁冗的困難，如何適應(yīng)實際需求值得深入研究。本文沿用前人使用列生成框架求解的思路，提出一種實用的乘務(wù)排班計劃優(yōu)化編制方法。在子規(guī)劃的設(shè)計方面，建立了一種新的能夠快速生成判別數(shù)較小的新列等效網(wǎng)絡(luò)圖模型，該模型利用主規(guī)劃每次迭代過程中所產(chǎn)生的影子價格，以影子價格向量中最大的分量所對應(yīng)的乘務(wù)作業(yè)段為基礎(chǔ)選取最短路，從而快速產(chǎn)生質(zhì)量較優(yōu)的新列。

1 問題描述

以某個乘務(wù)任務(wù)為例簡單說明，見圖1。圖1中有3列車輛的周轉(zhuǎn)任務(wù)，“BT021”等為車底編號。該線路上有一個輪乘站，該輪乘站將每列車輛的運行任務(wù)分割為一系列乘務(wù)作業(yè)段，每個乘務(wù)作業(yè)段有其開始/結(jié)束的時間與地點，在圖中一個完整的矩形代表一個乘務(wù)作業(yè)段。當若干個乘務(wù)作業(yè)段滿足實際工作的需求時可以相互組合。以最小間休時間10 min、一次最長在車時間120 min為例，可將3個深色乘務(wù)作業(yè)段組合為一個乘務(wù)任務(wù)(乘務(wù)任務(wù)1)。該乘務(wù)任務(wù)共有兩段間休時間，分別為15、10 min。最小間休時間在圖中用虛線白色矩形表示。間休時間中超出最小間休時間的部分屬于非必要勞動時間，在圖中以黑色矩形表示。該例子中，第一次間休中有5 min為非必要勞動時間。

一個乘務(wù)任務(wù)中，乘務(wù)員用于駕駛的時間與乘務(wù)任務(wù)的工作時長之比為該乘務(wù)任務(wù)的工作效率，如圖1所示的乘務(wù)任務(wù)1，駕駛時間為135 min，工作時長為160 min，則工作效率為84.38%。非必要勞動時間的存在影響了乘務(wù)日計劃的工作效率，非必要勞動時間越多，日計劃的工作效率越低。除工作效率外，一個乘務(wù)日計劃中乘務(wù)任務(wù)的個數(shù)也是衡量乘務(wù)日計劃質(zhì)量優(yōu)劣的重要標準。乘務(wù)任務(wù)數(shù)代表一個日計劃運用乘務(wù)員的數(shù)量，對運營機構(gòu)的人工成本有直接影響，乘務(wù)任務(wù)數(shù)越多，需要的乘務(wù)員數(shù)量就越多，人工成本越高。乘務(wù)任務(wù)數(shù)與工作效率共同反映了乘務(wù)計劃編制的優(yōu)劣情況，運營機構(gòu)一般傾向于較少的乘務(wù)任務(wù)數(shù)與較高的工作效率。

2 模型構(gòu)建

在列生成算法的框架下，主規(guī)劃是一個線性規(guī)劃，其目標函數(shù)和約束條件描述了解的構(gòu)成，但是每次迭代只在部分列中尋優(yōu)；子規(guī)劃則根據(jù)實際需要構(gòu)建，不斷生成具有較優(yōu)判別數(shù)的可行新列代入主規(guī)劃，使主規(guī)劃的解在下一步獲得更優(yōu)的解。簡而言之，列生成算法是一個通過不斷提高主規(guī)劃中的列的質(zhì)量，從而得到最優(yōu)解的算法。

2.1 主規(guī)劃

集合分割模型[8,10-11,13]與集合覆蓋模型[12,14-15]均可用于描述乘務(wù)計劃編制問題。采用集合覆蓋模型的優(yōu)點在于能夠直觀地將問題描述為允許乘務(wù)員在多個輪乘站之間周轉(zhuǎn)的情況，集合分割模型對問題的描述會更為切合實際，即一個乘務(wù)作業(yè)段能且僅能被一個乘務(wù)任務(wù)執(zhí)行。

本文采用集合分割模型作為主規(guī)劃為

minw=∑cjxj

( 1 )

s.t.

?i∈Ut

( 2 )

xj∈{0,1} ?j∈Us

式中：w為總成本；Us為乘務(wù)任務(wù)的集合，j∈Us，為乘務(wù)日計劃中第j個乘務(wù)任務(wù)；cj為乘務(wù)任務(wù)j的成本，與組成的乘務(wù)作業(yè)段及其銜接關(guān)系相關(guān)，取值詳見2.2節(jié)；xj為0-1變量，表示乘務(wù)任務(wù)j是否入選日計劃，1為入選，0為未入選；Ut為乘務(wù)作業(yè)段的集合，Ut={1，2，…，m}，i∈Ut；aij為0-1參數(shù)，表示乘務(wù)任務(wù)j是否包含乘務(wù)作業(yè)段i，1為包含，0為未包含。

考慮到在列生成框架下，主規(guī)劃每次迭代時可選的列均由子規(guī)劃產(chǎn)生，因此主規(guī)劃僅需對乘務(wù)任務(wù)是否入選進行約束，乘務(wù)任務(wù)的可行性約束可以在子規(guī)劃中討論。

2.2 迭代過程與成本函數(shù)

根據(jù)轉(zhuǎn)軸迭代法，判別數(shù)最小的列入基才能使主規(guī)劃的目標函數(shù)得到最大改善。第j個乘務(wù)任務(wù)的判別數(shù)為

σj=cj-πAj?j∈Us

( 3 )

式中：π為行向量(π1,π2,…，πm)，其中πi是主規(guī)劃中第i個約束條件的單純形乘子，又稱為影子價格，由成本cj與基矩陣B共同求得；Aj為第j列上aij組成的列向量，即第j個乘務(wù)任務(wù)的組成形式。

由于在式( 3 )中除列向量Aj外各參數(shù)皆與cj的取值有關(guān)，因此cj取值的定義將直接影響新生成的列的質(zhì)量。因為運營機構(gòu)更傾向于選擇擁有較少的乘務(wù)任務(wù)數(shù)與較高的工作效率的乘務(wù)日計劃，cj的取值也需要反映這兩項標準。其中，工作效率為乘務(wù)日計劃中值乘時間與工作時間的比，值乘時間與間休時間共同組成了工作時間。在值乘時間不變的情況下，間休時間越長，工作效率越低，該乘務(wù)任務(wù)的成本cj越高，乘務(wù)任務(wù)數(shù)則可在每個乘務(wù)任務(wù)的成本cj中添加作為懲罰值的常數(shù)進行約束。

本文通過為每個目標設(shè)定權(quán)重系數(shù)將多目標化為單一目標，既便于求解，又能直觀反映運營機構(gòu)對各目標的重視程度。成本cj可以為

?p，q∈Ut

( 4 )

式( 4 )中W0、α、β皆根據(jù)運營機構(gòu)的需要與實際情況賦值，將直接影響編制結(jié)果。其中，期望工作時間W0是一個懲罰值，代表每增加一個組成日計劃的乘務(wù)任務(wù)所增加的基礎(chǔ)成本，以此約束乘務(wù)任務(wù)的數(shù)目。非必要勞動時間與值乘時間則是與工作效率直接相關(guān)的量，是成本的重要參數(shù)。

需要注意的是，當β取0時，代表在成本函數(shù)中完全忽略了非必要勞動時間的影響，即不再考慮工作效率的高低，以此得到的乘務(wù)日計劃中乘務(wù)任務(wù)數(shù)最少。另外，因為在車時間的總和為定值，所以α的取值不影響日計劃的統(tǒng)計指標，只影響目標函數(shù)值。

2.3 子規(guī)劃

根據(jù)式( 3 )中經(jīng)典判別數(shù)計算方法，生成的新列需要有最小的判別數(shù)以優(yōu)化主規(guī)劃的目標函數(shù)，可將子規(guī)劃的目標函數(shù)寫為

( 5 )

式中：A=(a1,a2,…,am)，ai為乘務(wù)作業(yè)段i是否被新乘務(wù)任務(wù)執(zhí)行；c(A)即為式( 4 )中的cj，代表cj是A的函數(shù)。在子規(guī)劃中，需要求出可行的A使σj最小。本文用一個等價的最短路問題來描述子規(guī)劃。

建立網(wǎng)絡(luò)圖G(N,E)，集合N為圖中的點的集合，每個點代表一個乘務(wù)作業(yè)段。同時，每個點上都有點的屬性N(tbp,tep,sbp,sep,trp,wp)，tbp、tep代表該乘務(wù)作業(yè)段的開始與結(jié)束時間，sbp、sep代表該乘務(wù)作業(yè)段的開始與結(jié)束地點，trp為執(zhí)行該乘務(wù)作業(yè)段的車底，wp為該點代表的乘務(wù)作業(yè)段的權(quán)值，由該點對應(yīng)的主規(guī)劃的行的單純形乘子決定。集合E為圖中有向弧的集合，每條有向弧代表該弧相連的兩個點在時間與空間上可接續(xù)，并且從時間關(guān)系上來看，弧只可由先進行的乘務(wù)作業(yè)段指向后進行的乘務(wù)作業(yè)段?；∩嫌袡?quán)值dpq，由該弧相連的兩個點代表的乘務(wù)作業(yè)段的時空關(guān)系決定?；〉闹饕s束包括如下兩條

tbq-tep>Trsbq=sep且trq≠trp

( 6 )

tbq-tep>Twsbq≠sep

( 7 )

式( 6 )代表間休時間的約束，即非連續(xù)值乘時，期間的休息時間需大于最短間休時間Tr；式( 7 )代表異地接車時間約束，即在異地接車時需要為乘務(wù)員安排一定的走行或便乘時間Tw。當滿足這兩個條件時，弧epq存在。

綜上，可以用網(wǎng)絡(luò)模型描述子規(guī)劃的解空間。令s為圖上的一條路徑，s(N)為路徑的點集合，s(N(n))代表s上的第n個點，且s總共包含z個點。s(E)為路徑的弧的集合。根據(jù)乘務(wù)計劃編制的要求，建立的作為子規(guī)劃的最短路問題的數(shù)學(xué)模型為

( 8 )

s.t.

?p∈s(N)

( 9 )

tes(N(z))-tbs(N(1))

(10)

tes(N(p))-tbs(N(q))

trs(N(p))=trs(N(p-1))=…=trs(N(q))

(11)

tbs(N(p))-tes(N(p-1))>Td

(ds,de)∩(tes(N(p)),tbs(N(p-1)))≠?

(12)

式( 9 )為s作為路的基本約束；式(10)為工作時長約束，即從出勤時刻到退勤時刻的約束；式(11)為連續(xù)最長在車時間約束，即連續(xù)值乘的時間不能大于規(guī)定的最長連續(xù)在車時間；式(12)為就餐約束，即為乘務(wù)員安排的最短就餐時間。當一名乘務(wù)員的工作時間跨越規(guī)定就餐時間段時，需要為其安排就餐時間，且不得小于最短就餐時間。

為了令網(wǎng)絡(luò)圖的最短路問題與子規(guī)劃問題等價，需要對圖上點與弧的權(quán)重進行定義。根據(jù)一個乘務(wù)任務(wù)的成本函數(shù)式( 4 )與子規(guī)劃目標函數(shù)式( 5 )，可以將子規(guī)劃目標函數(shù)為

(13)

整理后得

(14)

式中:W0為常數(shù)，在求解最優(yōu)解時可忽略。為使子規(guī)劃目標函數(shù)與網(wǎng)絡(luò)圖中最短路的權(quán)值等價，可以將與ap相乘的數(shù)作為點上的權(quán)值，將與bpq相乘的數(shù)作為弧上的權(quán)值

wp=-(αTp+πp)

(15)

dpq=βRpq

(16)

綜上，網(wǎng)絡(luò)圖中的最短路即為子規(guī)劃的最優(yōu)解。

3 求解算法

3.1 構(gòu)建初始解

使用列生成算法求解問題時需要先構(gòu)造一組初始可行解。本文以所有乘務(wù)任務(wù)只包含一個乘務(wù)段的日計劃為初始可行解。這種做法的優(yōu)點一是便捷，無需經(jīng)過繁瑣的步驟即可獲得滿足條件的乘務(wù)任務(wù)，二是該初始可行解易于用矩陣形式表達，初始矩陣即為單位矩陣。

3.2 迭代過程

迭代過程分為主規(guī)劃和子規(guī)劃兩部分。作為主規(guī)劃的整數(shù)規(guī)劃，一般先被松弛為線性規(guī)劃，求出最優(yōu)解后經(jīng)過剪枝得到整數(shù)解。這一部分的求解算法較為成熟，也不乏商業(yè)軟件應(yīng)用。但是子規(guī)劃需要在擁有數(shù)百個節(jié)點、上千萬條弧的網(wǎng)絡(luò)中找出若干條滿足各種約束條件的最短路，經(jīng)典的搜索方法計算量過于龐大，不適用于本問題。除了問題規(guī)模較大以外，在實際工作中還需要考慮到各個乘務(wù)任務(wù)在車時間的均衡性?，F(xiàn)場工作中往往會采用將所有乘務(wù)任務(wù)中乘務(wù)作業(yè)段的數(shù)目限制在一定數(shù)額的做法，如每個乘務(wù)任務(wù)中均包含2～4個乘務(wù)作業(yè)段。這也導(dǎo)致了經(jīng)典的標號法如dijkstra算法并不適用于本問題。對此，本文結(jié)合現(xiàn)場實際情況提出一種基于影子價格選擇的標號法。

基于影子價格選擇的標號法在進入子規(guī)劃的第一步按照一定標準選出一個乘務(wù)作業(yè)段作為起始的乘務(wù)作業(yè)段，同時刪去無法與該乘務(wù)作業(yè)段接續(xù)的無關(guān)乘務(wù)作業(yè)段。在隨后的迭代步驟中，以選擇的起始點為中心，向前后搜尋可以接續(xù)的點并標號。

本方法能夠搜索到擁有固定數(shù)目乘務(wù)作業(yè)段的乘務(wù)任務(wù)中耗費成本較少的乘務(wù)任務(wù)。由于在第一步采用了局部最優(yōu)的選擇方法，大幅度降低了迭代過程中的搜索范圍，加快了算法的速度。

(17)

式中：

wq=-(αTq+πq)

(18)

(19)

Step3對所有可接續(xù)的路進行篩選，若一條路代表的乘務(wù)任務(wù)不滿足約束式(10)～式(12)，則跳過這條路。

Step6若k達到了預(yù)設(shè)的每個乘務(wù)任務(wù)包含乘務(wù)段的個數(shù)限制，則退出迭代。若還未達到，則返回Step2。

本方法一次迭代可以生成若干個包含不同個數(shù)乘務(wù)段的新列，同時代回主規(guī)劃中，既可以加快主規(guī)劃收斂的速度，也增加了乘務(wù)日計劃的靈活性。初始點的選取是該方法中的重要一環(huán)。在每次求解主規(guī)劃后，在網(wǎng)絡(luò)中選擇一個合適的初始點，能夠較快捷地找到讓主規(guī)劃得到更大優(yōu)化的新列。

綜上，本文所使用的乘務(wù)計劃優(yōu)化編制方法的流程見圖2。

4 實例分析

在本文提出的模型和算法基礎(chǔ)上，使用C#語言開發(fā)了城市軌道交通乘務(wù)計劃優(yōu)化編制系統(tǒng)，其中主規(guī)劃求解部分嵌入了ILOG CPLEX調(diào)用。應(yīng)用該系統(tǒng)，對北京地鐵某線路的乘務(wù)計劃編制問題進行了系統(tǒng)研究。

該線路每日運營時間為05:10～23:55，高峰小時最小發(fā)車間隔為4 min，使用車底24組。將列車周轉(zhuǎn)圖按輪乘站和車輛段進行劃分，可分為255個乘務(wù)作業(yè)段。當前的乘務(wù)日計劃為每日76個乘務(wù)任務(wù)，每個乘務(wù)任務(wù)工作時長由3 h到8 h不等，其中包含2至4個乘務(wù)作業(yè)段，工作效率為82.352%。

本次研究根據(jù)現(xiàn)場乘務(wù)日計劃的情況與實際運營中對各項目標的重視程度，為成本函數(shù)中的參數(shù)賦值，設(shè)定每次迭代生成的乘務(wù)任務(wù)中包含2至4個乘務(wù)作業(yè)段，對比數(shù)種狀況下不同日計劃包含的乘務(wù)任務(wù)數(shù)與工作效率的優(yōu)劣性。

為了驗證本文提出的算法的可行性與優(yōu)越性，取α=0,β=1，同時W0的取值為180至480，代表現(xiàn)場所使用的乘務(wù)日計劃中乘務(wù)任務(wù)的持續(xù)時長為3～8 h。將通過算法得到的乘務(wù)日計劃與現(xiàn)場目前使用的乘務(wù)日計劃做對比，比較二者根據(jù)式( 1 )與式( 4 )計算得出的成本，見表1、圖3。

表1α=0,β=1時改變W0原日計劃與算法日計劃成本比較

W0原計劃成本本文算法成本W(wǎng)0原計劃成本本文算法成本18035 02533 59536048 70546 79924039 58537 78942053 26551 73930044 14542 77548057 82555 186

可以看出，不論期望工作時長如何取值，本算法取得的乘務(wù)日計劃的成本都比現(xiàn)場使用乘務(wù)日計劃的成本更少，可見本研究算法不僅可行，編制的乘務(wù)日計劃也優(yōu)于現(xiàn)場使用的日計劃。采用本算法的編制系統(tǒng)運行于普通PC機(1.70 GHz CPU、4.00 GB RAM)，僅需幾分鐘即可自動生成優(yōu)化方案，而現(xiàn)場人工編制出一套方案往往需要若干天。

為進一步分析乘務(wù)任務(wù)數(shù)與工作效率之間的關(guān)系，從而為運營機構(gòu)編制乘務(wù)計劃提供有效的參考，本文采用控制變量法，研究了成本函數(shù)中各參數(shù)的取值變化對編制結(jié)果中乘務(wù)任務(wù)數(shù)與工作效率的影響。

先保持值乘時間與非必要勞動時間的權(quán)重不變，調(diào)節(jié)期望工作時長W0，可得到統(tǒng)計結(jié)果分別見表2、表3，以及展現(xiàn)其變化趨勢的柱狀折線見圖4。

表2 α=1,β=1時改變W0對編制結(jié)果的影響

表3 α=0,β=1時改變W0對編制結(jié)果的影響

不論是否考慮在車時間的影響，可以看出當α、β保持不變時，期望工作時間W0越大，乘務(wù)任務(wù)數(shù)在逐漸減少，但工作效率呈現(xiàn)逐漸降低的趨勢。這是由于當增大每個乘務(wù)任務(wù)的期望值乘時間時，加大了單個乘務(wù)任務(wù)成本中的常數(shù)值，在非必要勞動時間的權(quán)重參數(shù)不變時，對非必要勞動時間長短，即工作效率的考慮會有所下降。因此編制結(jié)果會傾向于選擇用更少的乘務(wù)任務(wù)完成所有乘務(wù)作業(yè)段，而對工作效率的要求便會降低，工作效率會隨著期望工作時長的增加而減少。

若保持期望工作時長W0不變，并且取值乘時間權(quán)重α分別取0或1時，調(diào)節(jié)非必要勞動時間權(quán)重β，可得到如下的編制結(jié)果，分別見表4、表5，及展示趨勢見圖5。

表4 W0=360，α=1時改變β對編制結(jié)果的影響

表5 W0=360，α=0時改變β對編制結(jié)果的影響

可見，若保持期望工作時長不變，隨著非必要勞動時間的權(quán)重β增大，編制結(jié)果中工作效率會逐漸上升，同時乘務(wù)任務(wù)數(shù)也會呈現(xiàn)增多的趨勢。這是由于β的增大表示對非必要勞動時間的重視程度增加，在成本函數(shù)中期望工作時長W0不變的情況下，乘務(wù)任務(wù)數(shù)的權(quán)重相應(yīng)減少，受重視的程度逐漸降低。

較特殊的，當β=0時工作效率與乘務(wù)任務(wù)數(shù)都呈現(xiàn)較明顯的低谷。這是因為當β=0時，編制過程不再考慮非必要勞動時間的多少，而是僅考慮日計劃中乘務(wù)任務(wù)的數(shù)目。因此求解主規(guī)劃的整數(shù)規(guī)劃的過程僅在盡量使組成日計劃的乘務(wù)任務(wù)數(shù)目最少，工作效率的高低對評價結(jié)果沒有影響。

綜合比較以上兩組編制結(jié)果，可以得到關(guān)于α取值的結(jié)論：在上述兩種情況下，α=0時的工作效率都比α=1時的工作效率高，但在大部分情況下會擁有更多乘務(wù)任務(wù)數(shù)。這是由于一份列車運行計劃中的值乘時間總和是固定的，其權(quán)重越大，非必要勞動時間權(quán)重相對減小，對非必要勞動時間的重視程度降低，導(dǎo)致非必要勞動時間因α=1而增多，工作效率降低，同時乘務(wù)任務(wù)數(shù)也因為工作效率降低而增加。

在實際的工作中，運營企業(yè)需要根據(jù)運營需要，合理設(shè)定對工作效率與乘務(wù)任務(wù)數(shù)的權(quán)重，以得到對運營企業(yè)而言較為理想的結(jié)果。本例中，通過第一組編制結(jié)果的對比可以得到令α=0能取得較少的乘務(wù)任務(wù)數(shù)，人工成本在300～420內(nèi)時編制效率較高；另一方面，β值在1～3時乘務(wù)任務(wù)數(shù)增長的趨勢不明顯或在一個數(shù)目周圍不規(guī)則波動，并且隨著β值的增加工作效率有所提高，因此可以選擇α=0、β=3、W0=360為一組合適的參數(shù)。

5 結(jié)論

本文提出了一種基于列生成算法的乘務(wù)計劃優(yōu)化編制方法，將子規(guī)劃構(gòu)造為在以乘務(wù)段為頂點，可行銜接關(guān)系為弧的網(wǎng)絡(luò)圖上的最短路問題；根據(jù)實際運營情況通過引入權(quán)重綜合考慮乘務(wù)任務(wù)數(shù)和工作效率，設(shè)計單目標函數(shù)，并依此設(shè)計了一種基于影子價格選擇的標號法，在保證求解質(zhì)量的同時，能夠以較快的速度求出滿足現(xiàn)場工作需求的乘務(wù)日計劃。

案例分析中，通過設(shè)定不同的權(quán)重系數(shù)并與當前現(xiàn)場所使用的乘務(wù)日計劃的對比，體現(xiàn)了本文提出的乘務(wù)計劃優(yōu)化編制方法的優(yōu)越性。通過調(diào)節(jié)權(quán)重系數(shù)，可以做本文提出的方法的靈敏度分析，并為實際工作中應(yīng)選用何種權(quán)重系數(shù)組合做出合理的判斷。由實例編制結(jié)果可知，在其他參數(shù)不變的情況下，通過增加人工成本W(wǎng)0可令乘務(wù)任務(wù)數(shù)目呈現(xiàn)減少的趨勢，而增加非必要勞動時間權(quán)重β則可有效提高日計劃的工作效率。

此外，通過比較工作效率與乘務(wù)任務(wù)數(shù)目的變化趨勢可以取得較為合理的參數(shù)搭配，使編制的日計劃更符合運營機構(gòu)的要求。并且從實例中可發(fā)現(xiàn)：隨著對使用乘務(wù)員數(shù)目的重視程度增加，乘務(wù)任務(wù)日計劃中乘務(wù)任務(wù)數(shù)呈現(xiàn)下降的趨勢，同時工作效率也在不斷降低。當乘務(wù)任務(wù)數(shù)下降趨勢變緩或不再減少時，即可獲得針對該乘務(wù)編制問題較理想的乘務(wù)日計劃。