符 卓，袁雪瑩，車 瑤

(中南大學 交通運輸工程學院， 湖南 長沙 410075)

機車(含高速動車組)乘務交路是指機車司機(機車乘務員)擔當值乘任務的固定周轉(zhuǎn)區(qū)段，即司機從機務段所在站(乘務基地)到折返站(乘務換乘站)之間往返值乘的線路區(qū)段。高速動車組司機乘務交路是否合理，直接關系到動車組司機的需要數(shù)及其相關作息時間安排。我國高速動車組司機乘務交路的編制由各機務段的技術人員負責。目前仍以“先到先走”的經(jīng)典啟發(fā)式方法為主，靠人工憑經(jīng)驗編制，每次都要花費若干天、甚至半個月的時間才能編制完成，編制質(zhì)量和勞動強度都有待于運用科學的方法并開發(fā)相應的計算機輔助編制系統(tǒng)來改善。

高速動車組司機乘務交路的編制，與普速列車的機車司機乘務交路一樣，是以值乘的高速動車組的運行區(qū)段及其到發(fā)點為依據(jù)，安排司機的值乘車次、出退勤時間和地點等的計劃。其編制步驟為：(1)根據(jù)高速動車組的運行區(qū)段及其到發(fā)點確定乘務片段;(2)根據(jù)乘務片段編制乘務交路;(3)根據(jù)乘務交路構建乘務交路循環(huán)。乘務片段是指司機在退勤休息或間休前連續(xù)值乘的“一個單程或立即折返交路”，且圖定旅行時間一般不超過4 h。根據(jù)乘務片段的時長和是否有可接續(xù)的乘務片段，多數(shù)情況下，乘務交路由1對“往返”的乘務片段組成(有1次間休)，有時由1個或3個乘務片段組成(相應地，無間休或有2次間休)，是司機一天的工作安排(日計劃)。乘務交路循環(huán)是司機一個較長時間段里的工作安排，即乘務排班，由依次值乘的若干乘務交路連接組成。

隨著我國近年來開行高速列車對數(shù)的增多，以及交路區(qū)段劃分、列車運行速度、乘務作息時間等方面的原因，除了由1對往返的乘務片段組成的傳統(tǒng)非立即折返類型乘務交路外，還出現(xiàn)了大量由立即折返(簡稱立折)類型乘務片段組成的乘務交路，若此時仍采用傳統(tǒng)的“先到先走”方法來編制(即先到的“去程”乘務片段優(yōu)先接續(xù)下一個“返程”乘務片段)，則所需要的乘務員數(shù)或乘務片段間總接續(xù)時間往往不是最少的。

鐵路[1-8]、航空[9]及城市公交[10-11]等行業(yè)都開展了對乘務交路編制問題的研究。因運輸方式和各國運輸組織制度的不同，其編制要求也有所差異，難以直接用來解決帶立即折返的高速動車組乘務交路編制問題。近年來，國內(nèi)也有不少學者從事與高速動車組司機乘務交路優(yōu)化編制相關的研究工作，褚飛躍等[12]研究高速鐵路單循環(huán)形式乘務排班計劃編制問題;王瑩等[13]以最小化每天需要的乘務組數(shù)量為優(yōu)化目標，構建了編制客運專線乘務交路的集覆蓋模型，并設計了一個求解的分枝定價法;王媛媛等[14]將乘務交路編制問題轉(zhuǎn)化為一類特殊的旅行商問題，并設計一個蟻群算法來求解。但這些研究工作中均未涉及由立即折返的乘務片段組成乘務交路問題。

在構建帶立折的高速動車組乘務交路時，有以下3種情況：(1)全部乘務片段均兩兩相互配對組成乘務交路；(2)存在某些乘務片段，不能與其他任何乘務片段配對形成乘務交路，稱其為單乘務片段“交路”，且不安排便乘；(3)由3個以上乘務片段組成乘務交路。文獻[15]將帶立折的高速動車組乘務交路構建歸結為一類集合分解問題來求解，但只能處理第1種情形，在應用中有局限性。

本文在文獻[15]的基礎上進行拓展，提出一種能同時處理上述3種情形的帶立即折返的高速動車組司機乘務交路優(yōu)化模型及其求解算法，在滿足相關約束條件下，使需要的司機數(shù)和司機的冗余休息時間為最少。彌補現(xiàn)有方法只考慮非立即折返類型或只能處理上述第1種情形的不足。

1 高速動車組司機乘務交路分析

根據(jù)組成乘務交路形式的不同，可將高速動車組司機乘務交路歸納為以下3種類型：

(1) 非立即折返型(也稱間休折返型)。指司機從機務段所在站(本段站)出勤，擔當去程乘務片段的值乘任務到達司機換乘站(折返站)，按照乘務作業(yè)時間標準間休后，再擔當返程乘務片段的值乘任務返回本段站，見圖1，圖1中的Pi為乘務片段(i為乘務片段編號)。普速機車司機乘務交路基本是由該類型的乘務片段組成，只是乘務片段的時長和間休時長與高速動車組司機的有所不同。目前相關文獻中涉及的基本上是這種類型。

(2) 純立即折返型。指司機從本段站出勤值乘乘務片段，到達折返站作短暫停留后(一般不超過90 min)立即值乘同一動車組返回本段站，組合成一個總值乘時間不超過4 h的立即折返乘務片段，按照規(guī)定間休后繼續(xù)接續(xù)另一立折乘務片段，最終返回本段站退勤，見圖2。與類型(1)不同，在這種情形下，每個立折乘務片段沒有明確的去程或返程，即當P3為去程乘務片段時，可接續(xù)P4；當P3為返程乘務片段時，可被P1接續(xù)。

(3) 混合折返型。指在某些乘務交路中，既有立折乘務片段，又有非立折乘務片段，即司機從本段站(或折返站)出勤，擔當“去程”乘務片段的值乘任務，間休后再擔當“返程”乘務片段的值乘任務到達折返站(或本段站)退勤，見圖3。如立折乘務片段Pi可以接續(xù)從本段站出發(fā)的非立折乘務片段Ri或立折乘務片段Pj(j為乘務片段編號)，也可被從折返站返回的非立折乘務片段Qi接續(xù)。

帶立折的高速動車組司機乘務交路問題，是隨著我國開行高速動車組對數(shù)增多、交路區(qū)段劃分等列車運行組織新要求下出現(xiàn)的新問題。相較非立折乘務交路問題，立折乘務片段的起點站和終點站為同一車站，其乘務交路構建更為復雜，即需考慮其是接續(xù)其他乘務片段，還是被其他乘務片段接續(xù)。目前各機務段的乘務交路編制人員往往先采用非立折型“先到先走”編制方法構建乘務交路初始方案，再憑經(jīng)驗進行局部調(diào)整得出最終方案。編制時間長、難度大，且難以做到整體最優(yōu)。

2 優(yōu)化模型構建

2.1 乘務片段接續(xù)時間矩陣

每一個非立折乘務片段是去程或返程，具有唯一性。與此不同，一個立折乘務片段既可以作為“去程”從而接續(xù)其他乘務片段，也可以作為“返程”而被其他乘務片段接續(xù)，不同的接續(xù)方案，其乘務片段間的接續(xù)時間也不同。

表1 乘務片段接續(xù)時間矩陣

為了讓司機更好地休息，有時會要求所編排的乘務交路不出現(xiàn)司機連續(xù)在折返站過兩夜的情形，即從折返站出勤的必須安排在本段站退勤，此時可將從折返站出勤又在折返站退勤的交路接續(xù)視為無效接續(xù)，也用足夠大的正整數(shù)M表示其接續(xù)時間。

( 1 )

2.2 數(shù)學模型

在與乘務交路編制有關的現(xiàn)有文獻中，常常將該問題歸結為集合覆蓋問題(Set Covering Problem)或集合分解問題(Set Partitioning Problem)模型來求解。但這些方法并不適合于本文所討論的問題類型。于是建立新的雙目標0-1整數(shù)規(guī)劃模型為

設

( 2 )

( 3 )

則

( 4 )

( 5 )

( 6 )

( 7 )

( 8 )

( 9 )

式中：wi為值乘乘務片段i時司機的工作時長；W為日工作時長限制；K為乘務交路數(shù)。

一個乘務交路需由一位司機值乘，乘務交路數(shù)越少，司機需要數(shù)也就越少。設共有n個乘務片段，若所有的乘務交路都是由1個乘務片段單獨組成，即各乘務片段間相互不接續(xù)，式( 4 )的值為0，則乘務交路數(shù)(司機需要數(shù))為n個；若所有的乘務交路都是由1對“往返”的乘務片段組成，即式( 4 )的值為n/2，則乘務交路數(shù)(司機需要數(shù))為n/2個。顯然，式(4)的取值越大，則表示總的乘務交路數(shù)(司機需要數(shù))也就越少。因動車組司機資源緊缺、成本高，鐵路部門明確要求將最小化乘務交路數(shù)(司機需要數(shù))為首要優(yōu)化目標。

式( 5 )為次要優(yōu)化目標，表示乘務片段間的總接續(xù)時間最短，使得乘務片段間的接續(xù)盡量緊湊，有利于司機退勤后能有更多的時間集中休息。式(6)表示乘務片段i和j最多配對接續(xù)一次，求和式為0時表示該乘務片段未能與其他乘務片段配對接續(xù)，成為單乘務片段“乘務交路”。因此，乘務片段都能相互配對接續(xù)構成乘務交路和部分乘務片段相互間不能配對接續(xù)構成乘務交路的兩種情形都已被該模型所涵蓋，更具通用性。式( 7 )表示乘務片段間的接續(xù)必須是可行的，即均為有效接續(xù)。式( 8 )表示每個乘務交路中司機的工作時長不能超過給定的日工作時長限制。

該模型是一個多目標優(yōu)化模型，式( 4 )所表示的優(yōu)化目標具有優(yōu)先權，即先優(yōu)化該目標，再在此基礎上優(yōu)化第二個目標。式( 4 )、式( 5 )也可以轉(zhuǎn)化為如下的單優(yōu)化目標函數(shù)

(10)

式(10)中的第二項表示對乘務片段未配對接續(xù)形成乘務交路的懲罰值。顯然，乘務片段配對接續(xù)形成有效的乘務交路數(shù)越多，該懲罰值就越小；當所有的乘務片段都能配對接續(xù)形成有效的乘務交路時，懲罰值為0，與式( 4 )、式( 5 )的優(yōu)化目標是一致的。

3 求解模型的禁忌搜索算法設計

乘務交路編制問題屬于NP-難問題[16-17]。計算復雜性理論已經(jīng)證明，對于NP-難問題，用精確算法求解時，其計算量會隨問題規(guī)模的增大呈指數(shù)增長。特別是對于較大規(guī)模的NP-難問題，用精確算法在可接受的時間內(nèi)求出這類問題的最優(yōu)解是非常困難的，因此其精確算法在實際應用中具有局限性。從實際應用的角度考慮，一般都是設計啟發(fā)式算法來求出問題的近優(yōu)解或最優(yōu)解。由于乘務交路構建問題的規(guī)模往往較大，因此，根據(jù)本文問題的特點，設計了一個求解上述模型的禁忌搜索(TS)算法，TS屬于亞啟發(fā)式算法(也稱智能優(yōu)化算法)之一。設計的主要內(nèi)容如下:

(1) 解的表示 用0和各乘務片段的序號(1,2,…,n)的一種排列表示問題的一組解，每個乘務片段的序號出現(xiàn)且僅出現(xiàn)一次，相鄰兩個0之間所包含多個非0序號時，表示相應的乘務片段相互接續(xù)構成乘務交路；包含1個乘務片段序號則表示該乘務片段需單獨值乘。例如解(0 1 3 0 4 5 2 0 … 0 6 0)表示乘務片段1、3和4、5、2分別接續(xù)組合為乘務交路，乘務片段6為單乘務片段“乘務交路”，需單獨值乘。

(2) 初始解 一般來說，較好的初始解有助于TS算法在解空間內(nèi)搜尋到的較優(yōu)最終解。因此，本文選擇用傳統(tǒng)的“先到先走”方法生成的方案作為初始解。

(3) 鄰域結構 為避免過早陷入局部最優(yōu)，本算法設置了以下4種基于2-交換產(chǎn)生機制的鄰域操作來增強TS算法的隨機性和多樣性，以便能在減少司機需要數(shù)和司機冗余間休時間兩個方面都能得到更好的改進。每次隨機挑選2個乘務片段(下面示例中有下劃線者)，再隨機挑選其中一種鄰域操作對當前解進行變換。鄰域操作后，若相鄰兩個元素都為0，且該新解又是可行解時，則刪去其中一個，表示由單乘務片段組成的“乘務交路”減少了，而乘務片段配對接續(xù)形成的有效乘務交路增加了，即式( 4 )所示的目標函數(shù)得到了改善。

這4種鄰域變換分別從不同的角度嘗試乘務片段間接續(xù)組成乘務交路的不同方案，以便搜索更優(yōu)的解。其中，鄰域變換①、②和④有助于搜索使乘務片段配對組成的乘務交路數(shù)增加、或乘務片段接續(xù)時間更短的解，優(yōu)化式( 4 )和式( 5 )所表示的目標函數(shù)，鄰域變換④中可隨機選擇是尾部向前或向后插入。鄰域變換③主要搜索使乘務片段接續(xù)時間更短的解，對式( 5 )進行優(yōu)化。

(4) 解的評價 由乘務片段的接續(xù)時間矩陣[Cij]和上述4種鄰域操作中可以看出，當算法搜索進程越接近問題的最優(yōu)解時，從一個可行解經(jīng)一次鄰域變換操作產(chǎn)生另一個新解也為可行解將越難。為解決此問題，本文將算法設計為接受導致不可行解的變換，即當違反了式(7)的限制條件時，通過在目標函數(shù)中增加一個懲罰項而將不可行的程度引入到目標函數(shù)中去進行度量(在式(10)中加入第3項)，即

(11)

式中：R為該解中不可行的乘務交路數(shù)。p∈[2,20 000] 為懲罰系數(shù)， 初始值為100，并進行動態(tài)調(diào)整：每隔10次迭代測試一次，若前面的10個解都是可行的，則將其除于2；若都是不可行的，則將其乘于2。這樣，通過搜索過程中一些不可行解的過渡，有助于找到更好的可行解，降低算法陷入局部最優(yōu)的可能性。

(5) 算法參數(shù)設定 該算法主要有以下參數(shù)：

① 禁忌長度。將上述鄰域結構中的4種鄰域變換作為禁忌對象，禁忌長度在5～10間隨機選取。

② 候選解個數(shù)。設定為150+2n。

③ 終止準則。算法設定2個參數(shù)作為終止準則，即總迭代次數(shù)達到12 000+20n，或在3 500+2n次連續(xù)迭代步數(shù)內(nèi)當前的最好解沒有改變。

(6) 算法框架。本文提出的求解算法可描述如下：

初始化

讀入基礎數(shù)據(jù)和各參數(shù)的設定值。

按照“先到先走”方法生成的方案作為初始解，并置該解為當前解和當前最好解。

While 算法終止準則未滿足 do

While 候選解個數(shù)未滿足 do

隨機挑選2個乘務片段。

隨機挑選4種鄰域操作之一。

將所挑選的鄰域操作對當前解進行變換，并把所產(chǎn)生的新解加入到候選解集中。

End while

從候選解集中按以下順序找出最佳候選解：①若存在一個優(yōu)于當前最好解的禁忌候選解，則將其解禁，并作為最佳候選解；②非禁忌候選解中的最佳者；③若所有候選解都被禁忌，則將最佳者解禁，并將其作為最佳候選解。

置新最佳候選解為當前解。

將禁忌表中各禁忌對象的禁忌長度減1，等于0時解禁。

End while

4 算例分析

式( 1 )中Cij值的計算和所提出的TS算法已用Delphi語言進行編程，并在Intel(R) Core(TM)i7-4790、CPU@3.60 GHz、內(nèi)存8 GB的計算機上實現(xiàn)。本文采用3組實際的高鐵動車組數(shù)據(jù)為例，對模型和算法進行驗證。

4.1 算例1

某機務段值乘的部分乘務片段見表2，共73個，不成對，其中有25個是帶立折的。若按1個乘務交路最多只能由1對“往返”的乘務片段組成(只有1次間休)來構建乘務交路，則乘務交路數(shù)的下限為37。表中的A1、A2為機務段所在站，在該兩站到發(fā)的、由該機務段值乘的列車可聯(lián)合編制乘務交路，B為折返站。根據(jù)列車出發(fā)、到達時刻，間休時間≥90 min，日工作時長≤8 h等規(guī)定，可構造乘務片段接續(xù)時間矩陣見表3。

表2 高速動車組列車時刻表

表3 帶立折的乘務片段接續(xù)時間矩陣 min

分別用鐵路現(xiàn)場目前常用的“先到先走”方法、本文設計的TS算法、以及Cplex對該算例求解，結果見表4。從表4中可見，用本文設計的TS算法所求出的乘務交路數(shù)(任選其中一個見表5)比鐵路現(xiàn)場常用的“先到先走”啟發(fā)式方法編制的要少6個，運算時間基本相等；與Cplex求解結果相同，即求出了問題的最優(yōu)解，但運算時間只有1 s左右，減少約60倍。由此可見，該TS算法能在較短時間內(nèi)求出質(zhì)量較優(yōu)的解。

表4 求解結果對比

表5 某機務段高速動車組司機乘務交路優(yōu)化方案(乘務交路最多由2個乘務片段組成)

表6 高速動車組列車時刻表

續(xù)表6 高速動車組列車時刻表

所提出的TS算法收斂情況見圖4，其中虛線、實線分別表示乘務交路數(shù)(第一優(yōu)化目標)和接續(xù)時間(第二優(yōu)化目標)的變化情況。需說明的是，第一優(yōu)化目標是最大化乘務片段配對數(shù)，即最小化乘務交路數(shù)。開始時乘務交路數(shù)等于乘務片段數(shù)，每配成1對則乘務片段配對數(shù)加1，相應地乘務交路數(shù)減1。因此乘務交路數(shù)變化趨勢是從高到低。單乘務片段“交路”不存在乘務片段之間的接續(xù)，本算法中將其接續(xù)時間取為0，僅計算相互配對的乘務片段間的接續(xù)時間。因此，單乘務片段的“交路”越多，對應的第二個優(yōu)化目標的值越小。隨著第一個目標的優(yōu)化，單乘務片段“交路”會逐步減少，第二個優(yōu)化目標值會相應增加，但也是在保證不影響第一個優(yōu)化目標情況下尋求最小化。

4.2 算例2

某機務段2018年10月30日起值乘的80個乘務片段見表6，其中有26個是立即折返的。由于動車組司機緊缺，且部分乘片段的旅行時較短(約1.5 h)，因此，允許某些乘務交路由3個乘務片段組成(即允許每天有2次間休)，以及個別乘務片段的旅行時間可略超過4 h(最大值是4.8 h)、個別乘務交路的司機日工作時長可超過8 h(最大值是旅行時間10.13 h，加上出退勤輔助時間后是14.6 h)。按照這些要求，現(xiàn)場編制人員人工編制的結果是每天有36個乘務交路，并已按此方案實施；按照同樣的限制條件，用本文的TS算法運行約4 s，輸出的結果是只需33個乘務交路，可節(jié)省3個，其中的一個方案見表7。

表7 高速動車組司機乘務交路優(yōu)化方案(乘務交路最多由3個乘務片段組成)

4.3 算例3

文獻[15]提供了一個有18個乘務片段的算例，并設計了一個蟻群遺傳混合算法求解該算例，得到乘務交路數(shù)為9個，接續(xù)時間為2 658 min，運算時間約40 s。采用本文設計的TS算法對該算例進行求解，得到了同樣的優(yōu)化結果，但運算時間只需約0.1 s。用Cplex例求解也得到了同樣的結果。

5 結論

(1) 本文通過對帶立折的高速動車組司機乘務交路優(yōu)化編制問題的分析和歸納，以所需要的動車組司機數(shù)和司機的冗余休息時間為最少建立了相應的0—1整數(shù)規(guī)劃模型，該模型可以描述每個乘務交路由1個或多個乘務片段組成的類型。

(2) 針對問題模型屬于NP-難問題的特點，設計了一個求解的禁忌搜索算法，并編程在微機上實現(xiàn)。

(3) 以多個機務段值乘的高鐵動車組實際數(shù)據(jù)為例，對模型和算法進行測試，并對求解結果進行對比分析，驗證了本文所提出的方法能快速求出符合實際要求的、較優(yōu)的高速動車組司機乘務交路方案。

以本文所提出的方法為基礎開發(fā)的系統(tǒng)已通過了行業(yè)內(nèi)專家的技術評審，并正在南昌機務段和福州機務段等進行示范性推廣。