考慮任務(wù)數(shù)的乘務(wù)計(jì)劃優(yōu)化模型及算法研究

張雨瀟，陳霽巖

（上海工程技術(shù)大學(xué) 城市軌道交通學(xué)院，上海 201620）

0 引言

在城市軌道交通運(yùn)營(yíng)管理中，乘務(wù)計(jì)劃是地鐵系統(tǒng)運(yùn)營(yíng)計(jì)劃的重要組成部分，通過城市軌道交通乘務(wù)計(jì)劃編制，運(yùn)營(yíng)機(jī)構(gòu)能夠確定乘務(wù)人力資源的合理化調(diào)配，為了保證服務(wù)質(zhì)量、降低乘務(wù)成本，需要對(duì)乘務(wù)計(jì)劃的編制優(yōu)化進(jìn)行深入的研究。

國(guó)內(nèi)外學(xué)者針對(duì)城市軌道交通乘務(wù)排班問題已有一定的研究，Yunes等人將乘務(wù)排班計(jì)劃問題分為2個(gè)子規(guī)劃問題，結(jié)合數(shù)學(xué)規(guī)劃和約束邏輯規(guī)劃方法開發(fā)了混合列生成算法。Yu等人針對(duì)排班工作約束，建立了以時(shí)間均衡度為目標(biāo)的集合劃分模型并應(yīng)用列生成算法進(jìn)行求解。袁仁杰針對(duì)交通運(yùn)營(yíng)特點(diǎn)，將乘務(wù)任務(wù)配對(duì)和乘務(wù)任務(wù)指派問題分別轉(zhuǎn)化為集合劃分覆蓋和運(yùn)輸指派問題，分別采用列生成結(jié)合遺傳算法和基于規(guī)則啟發(fā)式算法求解。許仲豪等人基于列生成算法思想，以集合分割模型為主規(guī)劃，將子規(guī)劃問題簡(jiǎn)化為網(wǎng)絡(luò)圖上的最短路徑問題，并設(shè)計(jì)了一種基于影子價(jià)格的標(biāo)號(hào)法求解子規(guī)劃問題。

現(xiàn)有研究主要針對(duì)乘務(wù)排班計(jì)劃的均衡度進(jìn)行探討，而未考慮乘務(wù)排班計(jì)劃的乘務(wù)任務(wù)數(shù)量?jī)?yōu)化問題。因此有必要根據(jù)城市軌道交通乘務(wù)計(jì)劃實(shí)際運(yùn)營(yíng)現(xiàn)狀，設(shè)計(jì)針對(duì)大規(guī)模乘務(wù)數(shù)據(jù)的優(yōu)化模型和求解算法。為了在目標(biāo)函數(shù)、約束條件及求解算法的研究上有所突破，本文提出以乘務(wù)任務(wù)數(shù)最小為目標(biāo)函數(shù)建立模型，以此來(lái)衡量所編制的乘務(wù)排班計(jì)劃質(zhì)量；同時(shí)從城市軌道交通運(yùn)營(yíng)管理實(shí)踐和乘務(wù)管理中提取出乘務(wù)特色約束條件作為模型考慮因素；此外針對(duì)本文提出的模型，為了保證解的質(zhì)量的同時(shí)，對(duì)求解速度提出較好的要求，本文基于列生成算法的思想，引入遺傳算法先對(duì)初始解的單位矩陣進(jìn)行迭代優(yōu)化，再使用列生成算法對(duì)優(yōu)化后的解進(jìn)行進(jìn)一步求解，提高算法求解效率。

1 模型構(gòu)建

1.1 主規(guī)劃

對(duì)包含個(gè)最小乘務(wù)片段和個(gè)乘務(wù)任務(wù)的乘務(wù)計(jì)劃問題，運(yùn)用集合分割模型理論建立主規(guī)劃模型如下：

其中，表示最后生成并選入乘務(wù)排班日計(jì)劃的所有乘務(wù)任務(wù)成本之和；c表示第個(gè)乘務(wù)任務(wù)的成本；1，…，，為最小乘務(wù)片段個(gè)數(shù)；1，…，，為可行的乘務(wù)任務(wù)個(gè)數(shù)；x、a是0-1參數(shù)；為乘務(wù)片段集合；為乘務(wù)任務(wù)集合。

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

對(duì)主規(guī)劃進(jìn)行線性松弛，得到一個(gè)標(biāo)準(zhǔn)線性規(guī)劃問題，利用單純性法進(jìn)行求解。第個(gè)乘務(wù)任務(wù)，即第列的判別數(shù)計(jì)算公式具體如下：

其中，σ為每一列的判別數(shù)，反映非基列入基后對(duì)目標(biāo)函數(shù)值的優(yōu)化程度；表示行向量（，，…，π），這里π表示主規(guī)劃中第個(gè)約束條件的影子價(jià)格；A表示第個(gè)乘務(wù)任務(wù)，是由a組成的第列的列向量。

在子規(guī)劃中檢索是否存在乘務(wù)任務(wù)A使得判別數(shù)σ小于0，若存在，則將此任務(wù)加入主規(guī)劃使得主規(guī)劃進(jìn)一步優(yōu)化。當(dāng)?shù)聊炒巫右?guī)劃生成的所有乘務(wù)任務(wù)的檢驗(yàn)數(shù)均大于等于0時(shí)，說明此時(shí)無(wú)法再通過添加列對(duì)主規(guī)劃進(jìn)行優(yōu)化，從而結(jié)束迭代。

1.3 子規(guī)劃

在子規(guī)劃問題中，以生成的新乘務(wù)任務(wù)的判別數(shù)最小為目標(biāo)構(gòu)建出子規(guī)劃目標(biāo)函數(shù)如下：

其中，表示所需生成的新乘務(wù)任務(wù)的判別數(shù)；表示運(yùn)營(yíng)單位期望工作時(shí)長(zhǎng)；表示生成的乘務(wù)任務(wù)中乘務(wù)片段的個(gè)數(shù)；te表示第個(gè)乘務(wù)片段的到達(dá)時(shí)間；tb表示第個(gè)乘務(wù)片段的發(fā)出時(shí)間；表示超時(shí)未休懲罰權(quán)重系數(shù)；表示連續(xù)值乘時(shí)間超1.2 h未休息次數(shù)；表示乘務(wù)任務(wù)的工時(shí)有效率權(quán)重系數(shù)；表示乘務(wù)任務(wù)的出勤點(diǎn)與退勤點(diǎn)不同時(shí)的懲罰權(quán)重系數(shù)；表示0-1懲罰參數(shù)，表示乘務(wù)任務(wù)的出勤點(diǎn)與退勤點(diǎn)是否不同，1為相同，0為不同；表示求解主規(guī)劃所得的對(duì)偶變量，為一個(gè)行向量；A表示主規(guī)劃所生成乘務(wù)任務(wù)的列向量；、、、的參數(shù)的取值具有一定的靈活性，可根據(jù)運(yùn)營(yíng)單位實(shí)際運(yùn)營(yíng)需求賦值，以取得較為理想的乘務(wù)排班方案。

在子規(guī)劃中對(duì)運(yùn)營(yíng)過程中的特色約束進(jìn)行如下表示：

（1）單次值乘時(shí)間約束，即規(guī)定一名乘務(wù)員一次連續(xù)值乘的時(shí)間不能大于規(guī)定的最長(zhǎng)連續(xù)值乘時(shí)間，約束條件表達(dá)式為：

其中，te表示該乘務(wù)任務(wù)中第個(gè)乘務(wù)區(qū)段的結(jié)束時(shí)刻；tb表示該乘務(wù)任務(wù)中第個(gè)乘務(wù)區(qū)段的開始時(shí)刻；，分別表示乘務(wù)員單次連續(xù)值乘最小、最大時(shí)長(zhǎng)。

（2）總值乘時(shí)間約束，即規(guī)定一名乘務(wù)員所有值乘時(shí)間的時(shí)長(zhǎng)和不能大于規(guī)定的當(dāng)日最長(zhǎng)值乘時(shí)間，考慮到工時(shí)有效率通常在75%～85%左右，將T設(shè)為6 h，T設(shè)為2 h，約束條件表達(dá)式為：

（3）出、退勤地點(diǎn)約束，為了方便乘務(wù)員上下班及交接班，應(yīng)盡可能使生成的每個(gè)乘務(wù)任務(wù)中第一個(gè)乘務(wù)片段的發(fā)出車站和最后一個(gè)乘務(wù)片段的到達(dá)車站相同，約束表達(dá)式如下：

其中，作為0-1懲罰參數(shù)，表示乘務(wù)任務(wù)的出、退勤點(diǎn)相同時(shí)為1，不同時(shí)為0；Sb，Se分別表示第個(gè)乘務(wù)片段的發(fā)出、到達(dá)車站。

（4）就餐約束，即乘務(wù)員值乘期間必須在規(guī)定時(shí)間內(nèi)就餐。約束表達(dá)式為：

其中，Y是0-1參數(shù)，當(dāng)該時(shí)間區(qū)段處于進(jìn)餐時(shí)間區(qū)間內(nèi)取1，否則取0；為0-1參數(shù)，當(dāng)該乘務(wù)工作時(shí)間為高峰時(shí)段則為1，為平峰時(shí)段則為0；表示是否是平峰時(shí)段的0-1參數(shù)，若為平峰時(shí)段則為1，若為高峰時(shí)段則為0；T，T分別表示高峰、平峰時(shí)段該輪乘站列車運(yùn)行間隔；t表示乘務(wù)員規(guī)定用餐時(shí)間長(zhǎng)度；為輪乘站輪乘間隔數(shù)，通常根據(jù)線路情況輪乘站有2或3個(gè)輪乘間隔。

（5）乘務(wù)片段的接續(xù)關(guān)系，乘務(wù)片段序列中2個(gè)相鄰的乘務(wù)片段必須滿足一定的時(shí)間間隔，接續(xù)關(guān)系表述為：

其中，te表示第1個(gè)乘務(wù)片段的開始時(shí)刻；tb表示第個(gè)乘務(wù)片段的結(jié)束時(shí)刻；t表示乘務(wù)片段間的最小間隔時(shí)間。

2 算法設(shè)計(jì)

2.1 遺傳算法優(yōu)化初始解

接著通過適應(yīng)值函數(shù)對(duì)編碼后的染色體進(jìn)行評(píng)價(jià)，其值可由如下公式計(jì)算求出：

此處，γ表示各約束條件所對(duì)應(yīng)懲罰函數(shù)的權(quán)重系數(shù)，通過調(diào)整該系數(shù)保證各約束條件地位相同。

在對(duì)個(gè)體進(jìn)行適應(yīng)值評(píng)價(jià)后，進(jìn)行若干次交叉算子操作繁衍種群。為避免種群在若干次的交叉操作后出現(xiàn)早熟收斂現(xiàn)象，采用黃金分割方法變異算子，計(jì)算第代種群中個(gè)體的第維個(gè)體4個(gè)黃金分割點(diǎn)的適應(yīng)值，選擇值最大的點(diǎn)對(duì)應(yīng)的個(gè)體，執(zhí)行變異算子操作，并推導(dǎo)得到如下的數(shù)學(xué)公式：

研究中采用了雙重收斂判斷準(zhǔn)則，即當(dāng)出現(xiàn)進(jìn)化次數(shù)達(dá)到設(shè)定的總迭代次數(shù)，或遺傳進(jìn)行若干次后目標(biāo)函數(shù)值不變的情況，都視為滿足收斂條件結(jié)束計(jì)算。

2.2 列生成算法求解規(guī)劃問題

（1）初始化，求解主規(guī)劃，獲得當(dāng)前主規(guī)劃的對(duì)偶變量，選取值最大的對(duì)偶變量對(duì)應(yīng)的乘務(wù)片段，作為本次迭代生成的乘務(wù)任務(wù)起點(diǎn)，令1，記錄該乘務(wù)片段為。

（2）令2，開始第二次迭代，若存在乘務(wù)片段能夠滿足式（7）～（11）約束與乘務(wù)片段接續(xù)，則將其與點(diǎn)連接，將連接后生成的路徑納入路徑集合P中。

（3）令1，開始第次迭代，對(duì)于路徑集合P中的每一條路徑的終點(diǎn)進(jìn)行步驟（2）的操作，生成路徑集合P。

（4）若的值達(dá)到了預(yù)設(shè)的每個(gè)乘務(wù)任務(wù)能夠包含的乘務(wù)片段個(gè)數(shù)要求，則退出迭代。若還未達(dá)到，則返回步驟（3）。

（5）根據(jù)目標(biāo)函數(shù)公式（6）選出數(shù)條目標(biāo)函數(shù)最小的乘務(wù)任務(wù)，作為新列添加入主規(guī)劃中。

迭代結(jié)束將得出的可行乘務(wù)任務(wù)集合放入主規(guī)劃，對(duì)優(yōu)化后的主規(guī)劃采用分支定價(jià)法進(jìn)行剪枝，從而得到新的0-1整數(shù)解，此時(shí)該最優(yōu)解即為最終結(jié)果。整個(gè)算法流程如圖1所示。

圖1 算法流程圖Fig.1 Flow chart of the algorithm

3 實(shí)例分析

3.1 結(jié)果對(duì)比分析

以上海地鐵某條線路的行車數(shù)據(jù)進(jìn)行實(shí)例分析，根據(jù)現(xiàn)場(chǎng)工作實(shí)際情況，在不考慮權(quán)重系數(shù)的賦值對(duì)乘務(wù)計(jì)劃的影響情況下，令02，1，1，取3、4、5、6、7、8，將傳統(tǒng)列生成算法與本文所提出的改進(jìn)列生成算法求解結(jié)果進(jìn)行對(duì)比，見表1。

表1 EXPT不同取值時(shí)2種算法比較Tab.1 The two algorithms are compared when EXPT values are different

根據(jù)表1結(jié)果，無(wú)論期望工作時(shí)長(zhǎng)取值如何，提出的改進(jìn)列生成算法在生成的乘務(wù)任務(wù)數(shù)量上和乘務(wù)計(jì)劃成本上，均比傳統(tǒng)列生成算法更優(yōu)。

本次計(jì)算結(jié)果的迭代次數(shù)與乘務(wù)排班計(jì)劃成本函數(shù)值關(guān)系，如圖2所示。

圖2 迭代次數(shù)與成本函數(shù)值關(guān)系圖Fig.2 Diagram of relationship between number of iterations and cost function value

觀察圖2發(fā)現(xiàn)，構(gòu)造初始解進(jìn)行第一次求解主規(guī)劃時(shí)乘務(wù)計(jì)劃成本最高，隨著迭代次數(shù)的增加與子規(guī)劃乘務(wù)任務(wù)的生成，主規(guī)劃的成本函數(shù)值迅速下降，在迭代130次左右達(dá)到最優(yōu)的狀態(tài)，驗(yàn)證了本文所設(shè)計(jì)的求解算法與迭代方式的有效性和高效性。

3.2 不同權(quán)重參數(shù)對(duì)比分析

為了深入分析乘務(wù)任務(wù)數(shù)量和工時(shí)有效率之間的影響關(guān)系，研究在工時(shí)有效率權(quán)重參數(shù)不變的情況下，其他參數(shù)變化對(duì)于所生成的乘務(wù)計(jì)劃工時(shí)有效率及乘務(wù)計(jì)劃成本的影響。對(duì)此擬展開研究闡釋如下。

（1）02，1，1時(shí)，分析的不同取值對(duì)工時(shí)有效率及乘務(wù)計(jì)劃成本的影響，如圖3所示。

根據(jù)圖3在保持02，1，1不變的情況下，工時(shí)有效率和乘務(wù)計(jì)劃成本隨取值的增大呈整體下降趨勢(shì)。其原因是當(dāng)其他權(quán)重參數(shù)不變時(shí)，期望工作時(shí)長(zhǎng)越低，所編制出的乘務(wù)計(jì)劃更容易覆蓋所有的乘務(wù)片段，反之當(dāng)期望工作時(shí)長(zhǎng)越高，乘務(wù)計(jì)劃傾向于用更低的成本完成乘務(wù)片段的覆蓋。

圖3 EXPT不同取值時(shí)乘務(wù)計(jì)劃成本與工時(shí)有效率Fig.3 Crew plan cost and man-hour efficiency with different values of EXPT

（2）6，1，1時(shí)，分析的不同取值對(duì)于工時(shí)有效率及乘務(wù)計(jì)劃成本的影響，如圖4所示。

圖4 α不同取值時(shí)乘務(wù)計(jì)劃成本與工時(shí)有效率Fig.4 Crew plan cost and man-hour efficiency with different values of α

根據(jù)圖4在保持6，1，1不變的情況下，當(dāng)取值由0.1至0.4時(shí)，工時(shí)有效率會(huì)隨的增加而增大；當(dāng)04時(shí)，工時(shí)有效率會(huì)隨的增加而減小。究其原因是當(dāng)其他權(quán)重參數(shù)不變時(shí)，對(duì)超時(shí)未休的狀況進(jìn)行一定范圍內(nèi)的懲罰，會(huì)有助于乘務(wù)任務(wù)的生成，但當(dāng)懲罰超過該范圍時(shí)，反而會(huì)限制乘務(wù)片段的組合。

在實(shí)際生產(chǎn)作業(yè)中，6，04，1，1可作為乘務(wù)工作編制計(jì)劃中合適的一組參數(shù)。此外，運(yùn)營(yíng)單位需要結(jié)合實(shí)際情況與運(yùn)營(yíng)需求，在工時(shí)有效率、乘務(wù)任務(wù)數(shù)及乘務(wù)計(jì)劃成本三者之間進(jìn)行權(quán)衡，以得到滿足實(shí)際需求的乘務(wù)計(jì)劃。

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

（1）本文提出一種以生成乘務(wù)任務(wù)數(shù)量最小為目標(biāo)的乘務(wù)排班計(jì)劃問題編制方法，構(gòu)造了集合分割主規(guī)劃模型和乘務(wù)特色約束子規(guī)劃模型，并設(shè)計(jì)了基于影子價(jià)格選擇的標(biāo)號(hào)法對(duì)子規(guī)劃進(jìn)行求解。

（2）為了克服列生成算法中因初始解質(zhì)量太差導(dǎo)致求解速度緩慢且求解質(zhì)量不夠高的問題，本文引入遺傳算法對(duì)列生成算法的初始解進(jìn)行優(yōu)化，使得改進(jìn)后的列生成算法求解速度與求解質(zhì)量有顯著提高。

（3）以上海地鐵某條線路的實(shí)際運(yùn)行圖數(shù)據(jù)為例進(jìn)行分析，結(jié)果顯示本文提出的模型與改進(jìn)后的列生成算法在工時(shí)有效率和乘務(wù)員運(yùn)用數(shù)方面表現(xiàn)良好，驗(yàn)證了模型與算法的適用性和有效性，同時(shí)對(duì)模型中各權(quán)重參數(shù)進(jìn)行不同取值的求解對(duì)比分析，為實(shí)際生產(chǎn)作業(yè)中運(yùn)營(yíng)單位編制乘務(wù)計(jì)劃提供參數(shù)依據(jù)。

（4）為了提高該模型和算法與實(shí)際生產(chǎn)流程的匹配度，后續(xù)研究可在模型中加入更多的現(xiàn)實(shí)約束條件，比如將乘務(wù)排班計(jì)劃與乘務(wù)輪班計(jì)劃的編制流程結(jié)合，進(jìn)而使模型與算法更高效地解決現(xiàn)場(chǎng)的乘務(wù)計(jì)劃編制問題。