符 卓，袁雪瑩，車(chē) 瑤

(中南大學(xué) 交通運(yùn)輸工程學(xué)院， 湖南 長(zhǎng)沙 410075)

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

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

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

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

在構(gòu)建帶立折的高速動(dòng)車(chē)組乘務(wù)交路時(shí)，有以下3種情況：(1)全部乘務(wù)片段均兩兩相互配對(duì)組成乘務(wù)交路；(2)存在某些乘務(wù)片段，不能與其他任何乘務(wù)片段配對(duì)形成乘務(wù)交路，稱(chēng)其為單乘務(wù)片段“交路”，且不安排便乘；(3)由3個(gè)以上乘務(wù)片段組成乘務(wù)交路。文獻(xiàn)[15]將帶立折的高速動(dòng)車(chē)組乘務(wù)交路構(gòu)建歸結(jié)為一類(lèi)集合分解問(wèn)題來(lái)求解，但只能處理第1種情形，在應(yīng)用中有局限性。

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

1 高速動(dòng)車(chē)組司機(jī)乘務(wù)交路分析

根據(jù)組成乘務(wù)交路形式的不同，可將高速動(dòng)車(chē)組司機(jī)乘務(wù)交路歸納為以下3種類(lèi)型：

(1) 非立即折返型(也稱(chēng)間休折返型)。指司機(jī)從機(jī)務(wù)段所在站(本段站)出勤，擔(dān)當(dāng)去程乘務(wù)片段的值乘任務(wù)到達(dá)司機(jī)換乘站(折返站)，按照乘務(wù)作業(yè)時(shí)間標(biāo)準(zhǔn)間休后，再擔(dān)當(dāng)返程乘務(wù)片段的值乘任務(wù)返回本段站，見(jiàn)圖1，圖1中的Pi為乘務(wù)片段(i為乘務(wù)片段編號(hào))。普速機(jī)車(chē)司機(jī)乘務(wù)交路基本是由該類(lèi)型的乘務(wù)片段組成，只是乘務(wù)片段的時(shí)長(zhǎng)和間休時(shí)長(zhǎng)與高速動(dòng)車(chē)組司機(jī)的有所不同。目前相關(guān)文獻(xiàn)中涉及的基本上是這種類(lèi)型。

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

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

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

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

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

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

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

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

( 1 )

2.2 數(shù)學(xué)模型

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

設(shè)

( 2 )

( 3 )

則

( 4 )

( 5 )

( 6 )

( 7 )

( 8 )

( 9 )

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

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

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

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

(10)

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

3 求解模型的禁忌搜索算法設(shè)計(jì)

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

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

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

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

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

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

(11)

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

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

① 禁忌長(zhǎng)度。將上述鄰域結(jié)構(gòu)中的4種鄰域變換作為禁忌對(duì)象，禁忌長(zhǎng)度在5～10間隨機(jī)選取。

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

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

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

初始化

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

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

While 算法終止準(zhǔn)則未滿足 do

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

隨機(jī)挑選2個(gè)乘務(wù)片段。

隨機(jī)挑選4種鄰域操作之一。

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

End while

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

置新最佳候選解為當(dāng)前解。

將禁忌表中各禁忌對(duì)象的禁忌長(zhǎng)度減1，等于0時(shí)解禁。

End while

4 算例分析

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

4.1 算例1

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

表2 高速動(dòng)車(chē)組列車(chē)時(shí)刻表

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

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

表4 求解結(jié)果對(duì)比

表5 某機(jī)務(wù)段高速動(dòng)車(chē)組司機(jī)乘務(wù)交路優(yōu)化方案(乘務(wù)交路最多由2個(gè)乘務(wù)片段組成)

表6 高速動(dòng)車(chē)組列車(chē)時(shí)刻表

續(xù)表6 高速動(dòng)車(chē)組列車(chē)時(shí)刻表

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

4.2 算例2

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

表7 高速動(dòng)車(chē)組司機(jī)乘務(wù)交路優(yōu)化方案(乘務(wù)交路最多由3個(gè)乘務(wù)片段組成)

4.3 算例3

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

5 結(jié)論

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

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

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

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