考慮基地住宿問題的高鐵列車乘務(wù)排班計劃編制

李 雯，代存杰，巨玉祥，成 洋，張芳英

(1. 蘭州交通大學(xué) 交通運輸學(xué)院，蘭州 730070；2. 中國鐵路蘭州局集團有限公司 蘭州車站，蘭州 730000；3. 中國鐵路蘭州局集團有限公司 蘭州客運段，蘭州 730000)

列車乘務(wù)排班計劃，是指對列車乘務(wù)班組的休息、值乘，乘務(wù)車間做出的具體規(guī)劃安排，主要在列車乘務(wù)計劃編制的第二個階段完成.完善的乘務(wù)排班計劃，能夠減少運營成本，并對乘務(wù)員的休息、工作時間進行科學(xué)有效地安排，提升乘務(wù)員對工作的滿意度，具有關(guān)鍵的實踐價值與作用.因乘務(wù)員的組織模式、乘務(wù)車間管轄的值乘區(qū)段存在差別，所以乘務(wù)排班計劃的編制同樣也呈現(xiàn)出不一樣的模式.既有研究表明，乘務(wù)排班通常選取兩類方式，即固定周期和單循環(huán)兩種.目前相關(guān)的研究成果有：

文獻[1]研究上海市軌道交通乘務(wù)排班優(yōu)化問題，將乘務(wù)工作分為日班和夜班兩部分并歸結(jié)為一個二分雙向匹配問題，采用匈牙利算法進行求解.文獻[2]應(yīng)用蟻群算法，針對高速鐵路單循環(huán)模式乘務(wù)排班計劃編制問題，以乘務(wù)交路接續(xù)時間最短和冗余時間分布最均衡為目標進行問題求解.文獻[3]將動車組交路計劃的編制問題轉(zhuǎn)化為多旅行商問題，采用信息素增強的蟻群算法求解，并通過現(xiàn)場采集的數(shù)據(jù)驗證算法的有效性.文獻[4]構(gòu)建了乘務(wù)人員數(shù)量最少與工作時間適應(yīng)的雙目標模型，基于南京—常州區(qū)間的列車運行數(shù)據(jù)，使用改進的蟻群算法進行實例驗證.文獻[5]通過分析車次、交路及乘務(wù)員之間的關(guān)系，以乘務(wù)班組費用最小化為目標，以交路和乘務(wù)工時為約束建立優(yōu)化模型，設(shè)計遺傳算法進行求解.文獻[6]同樣將鐵路乘務(wù)排班問題抽象為多旅行商問題，以排班周期最短、乘務(wù)交路間冗余接續(xù)時間分布最均衡為優(yōu)化目標，構(gòu)建數(shù)學(xué)優(yōu)化模型，使用一種啟發(fā)式修正蟻群算法進行模型求解，并以廣深城際鐵路為案例驗證算法的有效性.文獻[7]設(shè)計了引入文化基因算法的非支配遺傳算法(non dominated sorting genetic algorithm-II，NSGA-II)來解決多目標作業(yè)車間調(diào)度問題，該算法增加了基于模擬退火算法的局部搜索程序.文獻[8]基于時空網(wǎng)絡(luò)模型，對于在某個責(zé)任范圍內(nèi)，針對使用乘務(wù)班組人數(shù)的下限展開求解.文獻[9]設(shè)計自適應(yīng)遺傳算法，初始值為難以獲取的乘務(wù)組數(shù)的最小值，所借助的遺傳算法當(dāng)中的染色體長度，能夠在迭代中進行自適應(yīng)改變.文獻[10]設(shè)計的遺傳算法，含有嵌入式模糊邏輯處理器，用以促使算法交叉、變異機率的增加.文獻[11-12]分別研究手術(shù)調(diào)度和項目調(diào)度的相關(guān)問題，優(yōu)化與完善NSGA-II算法，同時借助運算數(shù)據(jù)，由分布性以及收斂性，驗證優(yōu)化方式的效果.文獻[13]建立了帶時間窗的多車場公交乘務(wù)排班優(yōu)化模型，并使用禁忌搜索算法對該問題進行求解，結(jié)果表明該方法在處理帶有時間窗的多車場公交乘務(wù)組跨線排班問題時具有良好的應(yīng)用效果.文獻[14]研究等待折返的動車乘務(wù)交路改進及優(yōu)化的問題，基于集合分解問題擴展問題模型，同時運用遺傳—蟻群混合算法展開求解.文獻[15]針對公交線路多目標優(yōu)化模型，采用改進的NSGA-II算法，以自然數(shù)進行編碼，采取錦標賽選擇策略進行選擇操作，并采用均勻變異的方式，得到了較好的求解結(jié)果.

在已有文獻中，通常將最小化班組數(shù)量，勞動均衡性做為求解目標，卻沒有對乘務(wù)班組因值乘不同出發(fā)時刻、到達時刻交路而產(chǎn)生的住宿問題進行優(yōu)化.本文針對乘務(wù)基地住宿問題進行了討論，并設(shè)計了相應(yīng)的優(yōu)化求解方法，在客運段車隊(間)實際工作中，有較強現(xiàn)實意義.

1 乘務(wù)排班計劃多目標數(shù)學(xué)模型

1.1 問題描述

本文討論的列車乘務(wù)排班計劃是指，在指定周期排班模式[2]下，對周期內(nèi)乘務(wù)班組與值乘交路的匹配關(guān)系做出具體的安排.客運段通常以運營成本最小作為乘務(wù)計劃編制的總體目標，其中人員成本和住宿成本在運營成本中占比最高.考慮到工作實際中，因值乘早發(fā)交路、晚至交路在乘務(wù)基地的住宿成本取決于在基地住宿的乘務(wù)班組數(shù)量，因此將班組數(shù)量和基地住宿班組數(shù)目作為乘務(wù)排班計劃數(shù)學(xué)模型中的優(yōu)化目標.又因各班組完成的任務(wù)量應(yīng)當(dāng)是均衡的，勞動均衡性也作為求解的目標之一.

基于以上分析，在模型構(gòu)建過程中，在將最小化乘務(wù)班組數(shù)量、勞動均衡性作為目標的基礎(chǔ)上，首次將最小化基地住宿乘務(wù)組數(shù)目作為求解目標，在已有研究基礎(chǔ)上，將乘務(wù)交路與乘務(wù)班組的指派關(guān)系和周期內(nèi)的勞動時長限制作為模型約束，對該問題進行優(yōu)化.

1.2 指定周期乘務(wù)排班計劃指派模型

綜上分析，在原有研究[5]的基礎(chǔ)上將乘務(wù)排班計劃編制問題看作經(jīng)典的指派問題，在此基礎(chǔ)上建立多目標優(yōu)化模型.模型中的符號定義如表1所列.

表1 模型符號定義Tab.1 Definition of model symbols

具體數(shù)學(xué)模型如下:

(1)

minZ2=

(2)

目標函數(shù)(1)為乘務(wù)班組數(shù)量的最小值.目標函數(shù)(2)為各乘務(wù)班組勞動時長差值最小.

(3)

(4)

(5)

式(4)和式(5)為實際工作中乘務(wù)交路和乘務(wù)班組的一一對應(yīng)要求，即每天乘務(wù)班組只能值乘一個乘務(wù)交路，且一個乘務(wù)交路只能由一個乘務(wù)班組值乘.

(6)

式(6)為給定乘務(wù)排班周期范圍內(nèi)的工作時長約束，月度工時限制為166.6 h.

2 改進的NSGA-II算法求解列車乘務(wù)排班計劃

乘務(wù)排班計劃編制問題數(shù)學(xué)模型為多目標優(yōu)化模型，該類問題中的每個子目標間一般是相互矛盾的，求得的解被稱之為非支配解或Pareto最優(yōu)解，主要特征為優(yōu)化任一目標函數(shù)的同時，并不影響至少一個其他目標函數(shù).

結(jié)合該問題特點，設(shè)計基于實數(shù)編碼的NSGA-II算法對模型進行求解，并對算法進行改進，使用基于禁忌思想的變異方式，盡可能的減少非可行解的產(chǎn)生.針對求解時容易出現(xiàn)的收斂速度慢、易陷入局部最優(yōu)的問題，引入基于小生境的精英保留策略及自適應(yīng)交叉變異算子的改進方式.此種改進方式符合問題的特點，可以提高算法的收斂速度，同時提高解的分布.

2.1 算法設(shè)計及改進

2.2.1 算法設(shè)計

1) 初始種群的產(chǎn)生

采用實數(shù)三層編碼模式，第一層設(shè)指定周期內(nèi)的排班計劃為染色體，第二層設(shè)排班計劃內(nèi)每天的值乘計劃為基因，第三層為某天值乘計劃中乘務(wù)班組的排列次序.指定排班周期與乘務(wù)交路個數(shù)之積T×m作為初始種群中個體的乘務(wù)班組數(shù)，以實數(shù)代表一個班組出乘，其排列位置代表乘務(wù)班組值乘的交路和日期.

2) 適應(yīng)度計算

適應(yīng)度為遺傳算法中決定個體優(yōu)劣的指標，本例中，直接利用目標函數(shù)Z1、Z2、Z3數(shù)值作為個體的適應(yīng)度.

3) 非支配排序

非支配排序是本算法篩選后代個體的排序方式，根據(jù)適應(yīng)度函數(shù)對個體進行非劣分層，比較個體函數(shù)值的大小，將當(dāng)前種群中所有非劣解劃分為同一等級，令其為1；在剩余個體中找出新的非劣解，令其等級為2；重復(fù)以上過程，直至種群中所有個體都被設(shè)定相應(yīng)的等級.

4) 錦標賽選擇

隨機選擇兩個個體，首先比較非劣等級，如果非劣等級不同，則取非劣等級較小的個體，若非劣等級相同，則以擁擠度CDl為標準，取擁擠度大的個體，形成新種群.

5) 交叉運算

針對問題編碼特點，采用單點交叉的方法，對排班計劃中某一天的值乘計劃進行交叉，在具體操作中，先對染色體進行隨機配對；其次隨機設(shè)置交叉點位置；最后再相互交換配對排班計劃的某一天的值乘計劃.算法中的交叉運算如圖1所示.

6) 變異運算

針對每天值乘計劃中的值乘班組進行變異，在變異操作中引入禁忌思想，設(shè)置兩種變異方式.首先隨機選擇某天乘務(wù)計劃中乘務(wù)交路的基因變異位置，然后針對每天的值乘交路設(shè)置禁忌表，將當(dāng)天出乘班組編號放入禁忌表中，變異選擇為在當(dāng)天不出乘的乘務(wù)班組.其次對值乘早晚交路做標記，值乘晚至交路的班組，判斷是否在次日的禁忌表中，若不在禁忌表中，則在值乘早發(fā)交路變異為相同班組.

2.2.2 算法改進

根據(jù)已有研究[11]，計算染色體的海明距離即小生境尺寸CDl來實現(xiàn)擁擠密度的排序并減輕計算量，同時改善解的分布多樣性.按海明距離由疏到密的標準，將個體復(fù)制到下一代，直到下一代群體規(guī)模達到進化群體規(guī)模終止復(fù)制.某非支配染色體集上第l個染色體的擁擠度CDl按下式計算:

(7)

為避免NSGA-II算法因選定交叉和變異概率帶來的弊端，引入概率自適應(yīng)策略，動態(tài)控制遺傳操作的頻率.使用自適應(yīng)交叉算子克服不成熟的收斂，使用自適應(yīng)變異算子保持種群內(nèi)個體的多樣化，降低陷入局部解的可能，其中自適應(yīng)交叉算子和變異算子分別為

宋榕華....................................................................................................................................................................科萊恩大中華區(qū)可持續(xù)發(fā)展及管理事務(wù)總監(jiān)

(8)

(9)

算法經(jīng)過多次迭代后，乘務(wù)班組數(shù)值不再有變化，并達到迭代次數(shù)時終止.

2.3 算法具體流程

步驟1設(shè)置進化代數(shù)計數(shù)器t=1,隨機產(chǎn)生滿足不超過周期內(nèi)最大工作時長初始種群P(t)，設(shè)置種群中班組數(shù)量為T×m；

步驟2計算每個個體相應(yīng)的目標函數(shù)值fm；

步驟3快速非支配排序.對種群P進行非劣分層，直至種群中所有個體被設(shè)定相應(yīng)等級；

步驟4錦標賽選擇.隨機選擇兩個個體，若非劣等級不同，首先比較非劣等級，取級數(shù)較小的個體；若個體在同等級中，以擁擠度做進一步比較，取較優(yōu)個體，形成種群P1(t)；

步驟5個體中的某一天的交路進行交叉操作，縮減乘務(wù)班組數(shù)目，并使用禁忌思想對某天內(nèi)交路值乘安排進行變異操作，得到種群Q；

步驟7選擇前N個個體產(chǎn)生新一代種群NPt；

步驟8判斷產(chǎn)生更小乘務(wù)班組數(shù)目則轉(zhuǎn)到步驟2.當(dāng)算法進入停滯狀態(tài)，乘務(wù)班組數(shù)目不再變動時，算法終止.

3 實例驗證及分析

采用北京南站至天津站間的列車運營數(shù)據(jù)對本文設(shè)計的模型算法進行驗算，利用經(jīng)典的NSGA-II算法和改進的NSGA-II算法分別對該問題進行計算.并規(guī)定早于Ts=8:00發(fā)車的乘務(wù)交路為早發(fā)交路，晚于Te=20:30到達的乘務(wù)交路為晚至交路.列車乘務(wù)交路數(shù)據(jù)如表2所列.

表2 列車乘務(wù)交路數(shù)據(jù)Tab.2 Crew scheduling data

對NSGA-II算法參數(shù)進行設(shè)置：T=10 080 min；Maxgen=500次；Popsize=130個；自適應(yīng)概率及變異概率為PC1=0.9；PC2=0.6；PM1=0.1；PM2=0.001.

將經(jīng)典NSGA-II算法和改進后的NSGA-II算法求解速度和求解結(jié)果進行比較，來驗證算法及算法改進的有效性.

算法改進前后的收斂速度如圖2所示.

圖2 算法改進前后收斂曲線對比圖Fig.2 Convergence curve comparison chart before and after the algorithm improvement

通過對比算法改進前后的收斂曲線可得，經(jīng)典的NSGA-II算法在迭代次數(shù)450代附近逐漸呈現(xiàn)出較好的收斂趨勢，而改進后的NSGA-II算法在300代附近收斂穩(wěn)定；改進后的NSGA-II算法收斂效率高、速度快，表現(xiàn)出更好的收斂性能，且求得的目標函數(shù)值更優(yōu).因此針對該問題的算法改進是有效的.

對改進前后所得最后一代Pareto解集的平均值進行對比，并將算法執(zhí)行時間進行對比可知，算法改進后收斂速度提升14%，所得Pareto解集各目標函數(shù)的平均值均優(yōu)于經(jīng)典NSGA-II算法.算法改進前后求得的解的平均值如表3所列.

表3 算法改進前后結(jié)果對比Tab.3 Comparison of results before and after the algorithm improvement

最終求解所得的pareto解如表4所列.

表4 乘務(wù)排班問題非支配解Tab.4 Pareto solution of crew scheduling problem

解碼后得出對應(yīng)乘務(wù)排班計劃表，其中基地住宿班組數(shù)最多和最少所對應(yīng)的乘務(wù)排班計劃表如表5～6所列.

表5 當(dāng)Z1=16，Z2=43 080 408，Z3=42時的乘務(wù)排班計劃表Tab.5 Crew scheduling plan when Z1=16，Z2=43 080 408，Z3=42

表6 當(dāng)Z1=16，Z2=46 159 475，Z3=33時的乘務(wù)排班計劃表Tab.6 Crew scheduling plan when Z1=16，Z2=46 159 475，Z3=33

4 結(jié)論

考慮到乘務(wù)工作中因交路出發(fā)時刻、到達時刻不同而產(chǎn)生的基地住宿實際，討論因該問題產(chǎn)生的乘務(wù)基地住宿班組數(shù)量的優(yōu)化問題，并基于指派模型，建立解決該問題的多目標優(yōu)化模型.針對該模型，設(shè)計NSGA-II算法進行求解，并對算法進行了改進.最后以北京南站至天津站間的列車運行基礎(chǔ)數(shù)據(jù)為算例，對設(shè)計的模型、算法進行驗證，通過求解結(jié)果和算法改進前后計算結(jié)果的對比可得，算法改進后目標函數(shù)的求解結(jié)果及收斂速度均有了提高，從而證明了模型的正確性及算法的有效性.

乘務(wù)班組住宿優(yōu)化問題，在客運段車隊(間)實際工作中，有較強現(xiàn)實應(yīng)用意義.本文未考慮在給定乘務(wù)基地住宿能力情況下列車乘務(wù)排班計劃的編制，對這一問題的研究將是以后研究的重點.