考慮任務數的乘務計劃優化模型及算法研究

張雨瀟，陳霽巖

（上海工程技術大學 城市軌道交通學院，上海 201620）

0 引言

在城市軌道交通運營管理中，乘務計劃是地鐵系統運營計劃的重要組成部分，通過城市軌道交通乘務計劃編制，運營機構能夠確定乘務人力資源的合理化調配，為了保證服務質量、降低乘務成本，需要對乘務計劃的編制優化進行深入的研究。

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

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

1 模型構建

1.1 主規劃

對包含個最小乘務片段和個乘務任務的乘務計劃問題，運用集合分割模型理論建立主規劃模型如下：

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

1.2 迭代過程與成本函數

對主規劃進行線性松弛，得到一個標準線性規劃問題，利用單純性法進行求解。第個乘務任務，即第列的判別數計算公式具體如下：

其中，σ為每一列的判別數，反映非基列入基后對目標函數值的優化程度；表示行向量（，，…，π），這里π表示主規劃中第個約束條件的影子價格；A表示第個乘務任務，是由a組成的第列的列向量。

在子規劃中檢索是否存在乘務任務A使得判別數σ小于0，若存在，則將此任務加入主規劃使得主規劃進一步優化。當迭代至某次子規劃生成的所有乘務任務的檢驗數均大于等于0時，說明此時無法再通過添加列對主規劃進行優化，從而結束迭代。

1.3 子規劃

在子規劃問題中，以生成的新乘務任務的判別數最小為目標構建出子規劃目標函數如下：

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

在子規劃中對運營過程中的特色約束進行如下表示：

（1）單次值乘時間約束，即規定一名乘務員一次連續值乘的時間不能大于規定的最長連續值乘時間，約束條件表達式為：

其中，te表示該乘務任務中第個乘務區段的結束時刻；tb表示該乘務任務中第個乘務區段的開始時刻；，分別表示乘務員單次連續值乘最小、最大時長。

（2）總值乘時間約束，即規定一名乘務員所有值乘時間的時長和不能大于規定的當日最長值乘時間，考慮到工時有效率通常在75%～85%左右，將T設為6 h，T設為2 h，約束條件表達式為：

（3）出、退勤地點約束，為了方便乘務員上下班及交接班，應盡可能使生成的每個乘務任務中第一個乘務片段的發出車站和最后一個乘務片段的到達車站相同，約束表達式如下：

其中，作為0-1懲罰參數，表示乘務任務的出、退勤點相同時為1，不同時為0；Sb，Se分別表示第個乘務片段的發出、到達車站。

（4）就餐約束，即乘務員值乘期間必須在規定時間內就餐。約束表達式為：

其中，Y是0-1參數，當該時間區段處于進餐時間區間內取1，否則取0；為0-1參數，當該乘務工作時間為高峰時段則為1，為平峰時段則為0；表示是否是平峰時段的0-1參數，若為平峰時段則為1，若為高峰時段則為0；T，T分別表示高峰、平峰時段該輪乘站列車運行間隔；t表示乘務員規定用餐時間長度；為輪乘站輪乘間隔數，通常根據線路情況輪乘站有2或3個輪乘間隔。

（5）乘務片段的接續關系，乘務片段序列中2個相鄰的乘務片段必須滿足一定的時間間隔，接續關系表述為：

其中，te表示第1個乘務片段的開始時刻；tb表示第個乘務片段的結束時刻；t表示乘務片段間的最小間隔時間。

2 算法設計

2.1 遺傳算法優化初始解

接著通過適應值函數對編碼后的染色體進行評價，其值可由如下公式計算求出：

此處，γ表示各約束條件所對應懲罰函數的權重系數，通過調整該系數保證各約束條件地位相同。

在對個體進行適應值評價后，進行若干次交叉算子操作繁衍種群。為避免種群在若干次的交叉操作后出現早熟收斂現象，采用黃金分割方法變異算子，計算第代種群中個體的第維個體4個黃金分割點的適應值，選擇值最大的點對應的個體，執行變異算子操作，并推導得到如下的數學公式：

研究中采用了雙重收斂判斷準則，即當出現進化次數達到設定的總迭代次數，或遺傳進行若干次后目標函數值不變的情況，都視為滿足收斂條件結束計算。

2.2 列生成算法求解規劃問題

（1）初始化，求解主規劃，獲得當前主規劃的對偶變量，選取值最大的對偶變量對應的乘務片段，作為本次迭代生成的乘務任務起點，令1，記錄該乘務片段為。

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

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

（4）若的值達到了預設的每個乘務任務能夠包含的乘務片段個數要求，則退出迭代。若還未達到，則返回步驟（3）。

（5）根據目標函數公式（6）選出數條目標函數最小的乘務任務，作為新列添加入主規劃中。

迭代結束將得出的可行乘務任務集合放入主規劃，對優化后的主規劃采用分支定價法進行剪枝，從而得到新的0-1整數解，此時該最優解即為最終結果。整個算法流程如圖1所示。

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

3 實例分析

3.1 結果對比分析

以上海地鐵某條線路的行車數據進行實例分析，根據現場工作實際情況，在不考慮權重系數的賦值對乘務計劃的影響情況下，令02，1，1，取3、4、5、6、7、8，將傳統列生成算法與本文所提出的改進列生成算法求解結果進行對比，見表1。

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

根據表1結果，無論期望工作時長取值如何，提出的改進列生成算法在生成的乘務任務數量上和乘務計劃成本上，均比傳統列生成算法更優。

本次計算結果的迭代次數與乘務排班計劃成本函數值關系，如圖2所示。

圖2 迭代次數與成本函數值關系圖Fig.2 Diagram of relationship between number of iterations and cost function value

觀察圖2發現，構造初始解進行第一次求解主規劃時乘務計劃成本最高，隨著迭代次數的增加與子規劃乘務任務的生成，主規劃的成本函數值迅速下降，在迭代130次左右達到最優的狀態，驗證了本文所設計的求解算法與迭代方式的有效性和高效性。

3.2 不同權重參數對比分析

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

（1）02，1，1時，分析的不同取值對工時有效率及乘務計劃成本的影響，如圖3所示。

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

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

（2）6，1，1時，分析的不同取值對于工時有效率及乘務計劃成本的影響，如圖4所示。

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

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

在實際生產作業中，6，04，1，1可作為乘務工作編制計劃中合適的一組參數。此外，運營單位需要結合實際情況與運營需求，在工時有效率、乘務任務數及乘務計劃成本三者之間進行權衡，以得到滿足實際需求的乘務計劃。

4 結束語

（1）本文提出一種以生成乘務任務數量最小為目標的乘務排班計劃問題編制方法，構造了集合分割主規劃模型和乘務特色約束子規劃模型，并設計了基于影子價格選擇的標號法對子規劃進行求解。

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

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

（4）為了提高該模型和算法與實際生產流程的匹配度，后續研究可在模型中加入更多的現實約束條件，比如將乘務排班計劃與乘務輪班計劃的編制流程結合，進而使模型與算法更高效地解決現場的乘務計劃編制問題。