楊嘉寶，符卓

?

帶立即折返的高速動(dòng)車組乘務(wù)交路回路優(yōu)化編制方法

楊嘉寶，符卓

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

機(jī)車乘務(wù)交路回路是機(jī)車乘務(wù)交路的組成部分，其合理構(gòu)建對(duì)于乘務(wù)人員(司機(jī))的勞動(dòng)效率和鐵路運(yùn)輸?shù)某杀揪哂兄匾饬x。通過對(duì)帶立即折返的高速動(dòng)車組乘務(wù)交路回路優(yōu)化構(gòu)建問題的分析和抽象，根據(jù)其問題特點(diǎn)在已有的集合分解問題(set partitioning problem)模型基礎(chǔ)上進(jìn)行拓展，建立其優(yōu)化模型，并設(shè)計(jì)一個(gè)蟻群-遺傳混合算法求解該模型。研究結(jié)果表明：用該方法求出的乘務(wù)交路回路方案優(yōu)于鐵路現(xiàn)場(chǎng)現(xiàn)行的“先到先走”的方法。

鐵路運(yùn)輸；機(jī)車乘務(wù)交路；立即折返；集合分解問題；蟻群?遺傳混合算法

鐵路機(jī)車(含動(dòng)車組)運(yùn)用工作主要由3部分組成：機(jī)車交路編制、機(jī)車乘務(wù)交路編制和機(jī)車乘務(wù)排班計(jì)劃編制(把乘務(wù)交路分配給乘務(wù)員(司機(jī)))。機(jī)車交路是機(jī)車乘務(wù)交路編制的基礎(chǔ)，而機(jī)車乘務(wù)交路則是機(jī)車乘務(wù)排班計(jì)劃編制的基礎(chǔ)。機(jī)車乘務(wù)交路合理與否，直接關(guān)系到所需要的乘務(wù)員(司機(jī))數(shù)量及其乘務(wù)員的勞動(dòng)生產(chǎn)率。對(duì)于機(jī)車乘務(wù)交路的編制，我國鐵路部門目前仍然靠人工憑經(jīng)驗(yàn)來進(jìn)行，編制質(zhì)量和效率都有待于借助科學(xué)的方法和手段來提高。鐵路機(jī)車乘務(wù)交路編制可劃分為3個(gè)階段：確定乘務(wù)片段、編制乘務(wù)交路回路、編制乘務(wù)交路循環(huán)。乘務(wù)片段是指在乘務(wù)區(qū)段值乘的“一個(gè)單程或立折交路”(乘務(wù)組在退勤休息或間休前連續(xù)值乘的交路)。乘務(wù)交路回路(簡稱乘務(wù)回路)由固定搭配值乘的1對(duì)乘務(wù)片段組成。乘務(wù)交路循環(huán)(簡稱乘務(wù)循環(huán))則由一個(gè)固定周期內(nèi)輪流值乘的多個(gè)乘務(wù)回路連接組成。目前，我國鐵路機(jī)車和高速動(dòng)車組的運(yùn)用和乘務(wù)工作組織采用的是長交路、輪乘制。普速機(jī)車乘務(wù)回路基本上是由1對(duì)往返的乘務(wù)片段組成。但對(duì)于高速動(dòng)車組乘務(wù)回路的構(gòu)建，由于交路區(qū)段劃分、列車運(yùn)行速度、乘務(wù)作息時(shí)間等方面的不同，其乘務(wù)片段中除了與普速機(jī)車類似的非立即折返類型外，還存在大量的立即折返類型。非立即折返的高速動(dòng)車組乘務(wù)回路編制，與普速機(jī)車乘務(wù)回路的編制基本相同，按鐵路現(xiàn)場(chǎng)現(xiàn)行的“先到先走”原則編制即可。但帶立即折返的高速動(dòng)車組乘務(wù)回路編制卻不同，按“先到先走”的方法編制出來的，往往不是最優(yōu)方案，即構(gòu)成乘務(wù)回路的乘務(wù)片段間總接續(xù)時(shí)間不是最短的，導(dǎo)致所需乘務(wù)員數(shù)不是最少的。乘務(wù)交路計(jì)劃編制問題，廣泛存在于鐵路[1?2]、航空[3?4]及城市公交[5?6]等領(lǐng)域，其中我國鐵路運(yùn)輸中的乘務(wù)交路計(jì)劃研究近年來取得一些成果。在已有文獻(xiàn)中，乘務(wù)交路計(jì)劃編制問題主要?dú)w結(jié)為2種模型[7]：集合覆蓋(set covering)和集合分解(set partitioning，也稱集合劃分)。在鐵路乘務(wù)交路計(jì)劃問題中，2種問題模型的目標(biāo)函數(shù)一致，主要區(qū)別在于是否存在乘務(wù)員便乘這一條件。趙鵬等[8]將機(jī)車乘務(wù)員運(yùn)用計(jì)劃優(yōu)化編制歸結(jié)為集合覆蓋或分解問題。但由于當(dāng)時(shí)我國高鐵處于起步階段，該研究僅模擬了京滬高鐵長距離條件下的乘務(wù)交路計(jì)劃。田志強(qiáng)[9]針對(duì)乘務(wù)員便乘情況，將乘務(wù)員的值乘時(shí)間轉(zhuǎn)化為費(fèi)用，以總費(fèi)用最小為目標(biāo)采用集合覆蓋模型對(duì)可行乘務(wù)交路段費(fèi)用進(jìn)行計(jì)算，其中的時(shí)間成本恰好為集合覆蓋模型中的權(quán)值，構(gòu)建帶權(quán)值的集合覆蓋模型。部分學(xué)者研究了乘務(wù)排班計(jì)劃問題[10?11]，并提出了相應(yīng)的模型和算法。帶立即折返的乘務(wù)交路回路編制問題屬乘務(wù)回路構(gòu)建的一種，隨著我國高鐵的不斷發(fā)展，立即折返乘務(wù)交路也日益增多。本文在已有研究的基礎(chǔ)上主要研究帶立即折返的高速動(dòng)車組乘務(wù)交路回路優(yōu)化編制問題，針對(duì)該問題的特殊性，參考集合分解模型進(jìn)行拓展，并設(shè)計(jì)求解算法，最后通過對(duì)實(shí)例的求解和對(duì)比分析，驗(yàn)證所提出方法的效果。

1 問題描述

高速動(dòng)車組乘務(wù)回路構(gòu)建可分為3種類型：

1) 間休折返型。指乘務(wù)員從機(jī)務(wù)本段站出勤值乘去程乘務(wù)片段，到達(dá)折返站后按規(guī)定間休，再值乘一返程乘務(wù)片段返回機(jī)務(wù)本段站，也稱非立即折返。該類型的乘務(wù)回路構(gòu)建，與普速機(jī)車乘務(wù)回路構(gòu)建本質(zhì)相同，只是乘務(wù)片段和間休的時(shí)間長短略有差異，如圖1所示，圖1中的P表示乘務(wù)片段。

圖1 間休折返

圖2 純立即折返

2) 純立即折返型。指乘務(wù)員從機(jī)務(wù)本段站出勤值乘，到達(dá)折返站后，在停留時(shí)間大于最小立折接續(xù)時(shí)間、小于90 min，且往返總旅行時(shí)間(含立折接續(xù)時(shí)間)不超過4 h的情況下，立即值乘另一車次(一般為同一動(dòng)車組)返回機(jī)務(wù)本段站，形成一個(gè)由乘務(wù)子回路組成的立折乘務(wù)片段，間休后再值乘另一立折乘務(wù)片段，再次返回機(jī)務(wù)本段站，然后退勤，形成帶立折的乘務(wù)回路，如圖2所示。與間休折返型不同，此情形下的乘務(wù)片段不分去、返程，即每個(gè)立折乘務(wù)片段既可被其他立折乘務(wù)片段接續(xù)，也可接續(xù)其他立折乘務(wù)片段。

3) 混合折返型。由立折乘務(wù)片段和非立折乘務(wù)片段混合組成，即從機(jī)務(wù)本段站(或折返站)出發(fā)，值乘“去程”乘務(wù)片段，按規(guī)定間休后，再值乘一“返程”乘務(wù)片段到達(dá)折返站(本段站)終止的“回路”，如圖3所示，其中P表示立折乘務(wù)片段,Q表示從折返站返回的非立折片段，R表示從本段站出發(fā)的非立折片段。

圖3 混合折返

因立折乘務(wù)片段在起點(diǎn)站同時(shí)有起始時(shí)刻和終止時(shí)刻，使得在構(gòu)建帶立折的乘務(wù)回路時(shí)，需對(duì)每個(gè)立折乘務(wù)片段確定其是接續(xù)其他乘務(wù)片段，還是被其他乘務(wù)片段接續(xù)，所以帶立折的高速動(dòng)車組乘務(wù)回路的構(gòu)建比間休折返型要復(fù)雜。該問題是我國開行高速動(dòng)車組后，在機(jī)車乘務(wù)組織方面出現(xiàn)的新問題，但目前文獻(xiàn)中尚未見到解決此問題的相關(guān)報(bào)道。而鐵路現(xiàn)場(chǎng)工作中基本參照間休折返型，先采用“先到先走”的方式構(gòu)建帶立折的乘務(wù)回路，再根據(jù)情況，由人工憑經(jīng)驗(yàn)進(jìn)行局部調(diào)整。

在構(gòu)建帶立折的高速動(dòng)車組乘務(wù)回路時(shí)，由于列車到發(fā)點(diǎn)的原因，會(huì)出現(xiàn)2種情形：其一是所有乘務(wù)片段都能相互配對(duì)構(gòu)成乘務(wù)回路；其二是有部分乘務(wù)片段相互間不能配對(duì)構(gòu)成乘務(wù)回路，而只能單獨(dú)值乘，成為單乘務(wù)片段“回路”。本文將只針對(duì)第一種情形進(jìn)行研究，第二種情形將另文討論。

2 優(yōu)化模型

2.1 構(gòu)建帶立折的乘務(wù)回路接續(xù)時(shí)間矩陣

帶立折的乘務(wù)片段的特殊點(diǎn)在于在本段同時(shí)有起始時(shí)刻與終止時(shí)刻，乘務(wù)組從本段出發(fā)到達(dá)折返段并立即返回本段這一個(gè)過程可視為一個(gè)立折乘務(wù)片段，且這種立折乘務(wù)片段在滿足時(shí)間空間約束條件下，每個(gè)立折片段可以接續(xù)或被接續(xù)另一個(gè)立折或非立折片段，且有多種接續(xù)組合，因此接續(xù)時(shí)間也有所差異。

高速動(dòng)車組的乘務(wù)交路以0點(diǎn)為界劃分每一天，通過給定的0~24點(diǎn)高速動(dòng)車組運(yùn)行時(shí)刻表，可建立乘務(wù)片段接續(xù)時(shí)間表。需注意的是：根據(jù)規(guī)定，高速動(dòng)車組司機(jī)值乘2個(gè)乘務(wù)片段之間的休息時(shí)間(間休時(shí)間)不小于90 min，可將其稱為最短接續(xù)時(shí)間。當(dāng)2個(gè)不同的乘務(wù)片段之間的接續(xù)時(shí)間小于此最短接續(xù)時(shí)間或需跨天配對(duì)時(shí)，則視為無效接續(xù)。純立折乘務(wù)片段的接續(xù)時(shí)間為表1中前行、列所組成的(×)階子矩陣；混合型乘務(wù)片段的接續(xù)時(shí)間矩陣為表1中(+)×(+)階矩陣。

經(jīng)過“ICME-14申辦委員會(huì)”2013年3月—2014年10月緊張的申辦準(zhǔn)備工作，2014年11月30日正式遞交申辦書．

表1 接續(xù)時(shí)間矩陣

表1中，P(=1,…,)表示立折乘務(wù)片段；Q(=+1,…,)表示從折返站返回的非立折乘務(wù)片段；R(=+1,…,)表示從本站出發(fā)的非立折乘務(wù)片段。令=為乘務(wù)片段總數(shù)目，則C(=1,…,)表示值乘乘務(wù)片段P(或Q，R)后接著值乘乘務(wù)片段P(或Q，R)的接續(xù)時(shí)間；無效接續(xù)情況下相應(yīng)的乘務(wù)片段不能接續(xù)，對(duì)應(yīng)的元素用一個(gè)足夠大的正整數(shù)表示。

2.2 帶立折乘務(wù)回路構(gòu)建的轉(zhuǎn)化

通過分析，發(fā)現(xiàn)帶立即折返乘務(wù)片段的乘務(wù)回路優(yōu)化構(gòu)建問題與集合分解問題很強(qiáng)的關(guān)聯(lián)性。主要異同點(diǎn)可歸納如下：

1) 對(duì)于所有乘務(wù)片段，可視為一個(gè)有限集集合，而乘務(wù)片段間組成的可行乘務(wù)回路就可作為這個(gè)有限集的子集族，且這些可行乘務(wù)回路完全覆蓋所有乘務(wù)片段。在所有可行乘務(wù)回路中，都存在一個(gè)接續(xù)時(shí)間，即一般集合分解問題中的權(quán)值，因此問題可表述為：在包含所有可行乘務(wù)回路的集合中尋求一組子回路集，在滿足完全覆蓋所有立折和非立折乘務(wù)片段的情況下，使得回路總接續(xù)時(shí)間最短，即總權(quán)值最小。

2) 一般的集合分解問題中，子集族元素的組合是多樣的，一個(gè)小子集可包含元素?cái)?shù)目也不確定。而帶立即折返乘務(wù)交路回路構(gòu)建問題中，乘務(wù)片段之間要滿足相關(guān)乘務(wù)規(guī)則，因而每個(gè)立折乘務(wù)片段最多上只能與另一立折(或非立折)乘務(wù)片段構(gòu)成一個(gè)回路，即可基本滿足1 d的值乘工作量。

3) 在一般的集合分解問題中，每兩個(gè)元素組合后均有一個(gè)權(quán)值，且不受元素間組合的順序影響，例如：{1,3}與{3,1}2個(gè)集合的權(quán)值是同一個(gè)值。但在帶立即折返的高速動(dòng)車乘務(wù)交路回路構(gòu)建問題中，兩乘務(wù)片段組合的順序不同，接續(xù)時(shí)間也有所不同，即權(quán)值不同。

4) 帶立即折返的乘務(wù)回路構(gòu)建問題中，一旦某立折(非立折)片段被選中與另一個(gè)立折(非立折)片段組成乘務(wù)回路，其他乘務(wù)片段則無法再與之進(jìn)行組合，即集合分解問題中的元素只能無重復(fù)覆蓋一次。

2.3 優(yōu)化目標(biāo)和約束條件

求解帶立即折返的高速動(dòng)車組乘務(wù)交路回路問題的優(yōu)化目標(biāo)：乘務(wù)片段兩兩相互組合形成的乘務(wù)回路總接續(xù)時(shí)間最短，即使乘務(wù)員無效的等待時(shí)間為最少，從而減少乘務(wù)員需要數(shù)。

在乘務(wù)片段相互接續(xù)組合時(shí)，需滿足以下幾個(gè)條件：

1) 每個(gè)乘務(wù)片段都被包含在最終解中，且在解中僅出現(xiàn)一次。

2) 每2個(gè)乘務(wù)片段接續(xù)后，其接續(xù)時(shí)間與接續(xù)順序相關(guān)。

3) 當(dāng)任意一個(gè)乘務(wù)片段與另一乘務(wù)片段認(rèn)定接續(xù)后，其他任何未接續(xù)的乘務(wù)片段均無法再與已認(rèn)定接續(xù)的乘務(wù)片段進(jìn)行接續(xù)。

4) 在帶立即折返乘務(wù)回路構(gòu)建問題中，需滿足相應(yīng)的乘務(wù)休息時(shí)間標(biāo)準(zhǔn)。

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

Gershkoff[12]、田志強(qiáng)[9]和陳海平[7]均曾在論文中提到基于可行乘務(wù)回路建立的集合分解模型 如下：

式中：x為0~1變量，當(dāng)x=1時(shí)表示可行乘務(wù)回路被選入最優(yōu)解，x=0時(shí)表示未入選；c為可行乘務(wù)回路的費(fèi)用；a為0~1變量，a=1時(shí)表示可行乘務(wù)回路覆蓋乘務(wù)區(qū)段，a=0時(shí)表示未覆蓋。

式(1)表示模型目標(biāo)函數(shù)為求解時(shí)間費(fèi)用最小的乘務(wù)回路，式(2)表示每個(gè)乘務(wù)區(qū)段只能被覆蓋一次。

根據(jù)以上模型及本文2.2中求解帶立即折返的高速動(dòng)車組乘務(wù)回路問題的優(yōu)化目標(biāo)和約束條件，可建立其模型如下：

=1,2,…,；1,2,…,(7)

1,2,…,；=1,2,…,(8)

式(3)表示求解接續(xù)時(shí)間最短的乘務(wù)回路；

式(4)表示每個(gè)乘務(wù)片段只能被一個(gè)存在于解集合中的可行回路所覆蓋；

式(5)表示解集合中，組合前后順序不同的2個(gè)立折或非立折乘務(wù)片段只能出現(xiàn)一次，且2個(gè)認(rèn)定接續(xù)的乘務(wù)片段將無法接續(xù)其他乘務(wù)片段；

式(6)表示當(dāng)和2個(gè)乘務(wù)片段進(jìn)行組合時(shí)，若同一天內(nèi)的接續(xù)時(shí)間小于規(guī)定的最短接續(xù)時(shí)間或跨天接續(xù)，則用一個(gè)足夠大的整數(shù)表示，以說明2個(gè)乘務(wù)片段不能接續(xù)。

對(duì)比2個(gè)模型，本文所構(gòu)建的模型中主要增加式(5)和式(6)2個(gè)約束條件，可以看作是原集合分解模型的拓展。該拓展模型中由于立折片段可接續(xù)或被接續(xù)其他乘務(wù)片段，接續(xù)時(shí)需考慮順序問題。針對(duì)立折問題中存在已接續(xù)的2個(gè)乘務(wù)片段都不能接續(xù)其他乘務(wù)片段且不能改變自身的接續(xù)順序這一限制因素，可通過式(5)表示。

3 求解模型的蟻群?遺傳混合算法

集合分解問題已被證明為NP難問題[13]。根據(jù)上述分析，帶立即折返的高速動(dòng)車組乘務(wù)回路優(yōu)化問題中的模型是在已有集合分解模型上進(jìn)行的拓展，顯然，也為NP難問題，且實(shí)際乘務(wù)回路構(gòu)建問題規(guī)模較大，需采用啟發(fā)式算法求解。蟻群算法具有較強(qiáng)的隨機(jī)性和正反饋?zhàn)饔?，常用來解決路徑最優(yōu)問題，但易陷入局部最優(yōu)。遺傳算法實(shí)行并行搜索，交叉、變異操作能保持種群的多樣性，全局搜索能力較強(qiáng)，但收斂速度較慢。所以可利用蟻群算法提供較好的初始解，有利于加快遺傳算法的收斂，再通過交叉、變異操作可有效避免蟻群算法易陷入局部最優(yōu)解的弊端。因此，本文設(shè)計(jì)蟻群-遺傳混合算法對(duì)帶立即折返的高速動(dòng)車組機(jī)車乘務(wù)回路優(yōu)化問題進(jìn)行求解。

3.1 算法描述

根據(jù)蟻群算法和遺傳算法的特點(diǎn)，以及帶立折的乘務(wù)回路構(gòu)建問題的實(shí)際情況，先利用蟻群算法在解空間隨機(jī)安置只螞蟻對(duì)可行解進(jìn)行搜索，完成迭代后，選取部分較優(yōu)解作為遺傳算法的初始種群，進(jìn)行遺傳操作，最終得出近優(yōu)解或最優(yōu)解。

3.2 算法步驟

在算法中規(guī)定有只螞蟻隨機(jī)對(duì)2個(gè)元素進(jìn)行搜索，并將螞蟻?zhàn)哌^的元素及位置存放在周游表()表中，可供選擇的元素及位置存放在()表中(=1,2,…,)，迭代次數(shù)為。

蟻群算法中螞蟻在其行走路徑上的信息素濃度也會(huì)逐漸消失，設(shè)參數(shù)(0＜＜1)表示信息素?fù)]發(fā)程度。因此在所有螞蟻完成一次循環(huán)后，其路徑上的信息素濃度需實(shí)時(shí)更新[14]，即：

算法具體步驟如下：

Step 1：初始化，，和等各項(xiàng)參數(shù)；

Step 2：將只螞蟻隨機(jī)放置在接續(xù)時(shí)間矩陣中的元素上；

Step 3：記錄每只螞蟻的初始位置，即元素在表中的坐標(biāo)，存放在()表中；

Step 4：從第只螞蟻開始，根據(jù)概率的大小，從()表中選擇下一元素，將被選元素記錄在()表中，同時(shí)在()表中刪除將含有被選元素坐標(biāo)的元素；

Step 5：判斷螞蟻是否使()表中元素為空，否,則返回Step 3；

Step 6：對(duì)螞蟻?zhàn)哌^的元素的值進(jìn)行求和，并記錄，更新信息素濃度及路徑信息；

Step 7：判斷迭代次數(shù)是否超過規(guī)定次數(shù)，否，執(zhí)行Step 2至Step 6；

Step 8：當(dāng)=時(shí)，得到每只螞蟻的序列，取前個(gè)較優(yōu)解作為遺傳算法的初始種群；

Step 9：計(jì)算適應(yīng)度；

Step 10：進(jìn)行遺傳操作；

Step 11：輸出最終解。

4 算例分析

本文采用南昌機(jī)務(wù)段值乘的南昌-九江乘務(wù)區(qū)段的相關(guān)數(shù)據(jù)，對(duì)模型和算法進(jìn)行驗(yàn)證?；A(chǔ)數(shù)據(jù)見表2。

表2 帶立即折返的高速動(dòng)車組列車時(shí)刻表

根據(jù)立折返高速動(dòng)車組列車時(shí)刻表數(shù)據(jù)及規(guī)定的最小接續(xù)時(shí)間，構(gòu)造乘務(wù)片段接續(xù)時(shí)間矩陣如表3所示，其中，的值設(shè)置為109。

蟻群算法部分參數(shù)見表4，遺傳算法部分參數(shù)見表5。

該蟻群?遺傳混合算法已用Matlab語言編程實(shí)現(xiàn)，在Intel Core5 CPU2.7GHz、內(nèi)存4GB的計(jì)算機(jī)上運(yùn)行40.140 4 s，得到本算例的乘務(wù)回路數(shù)為9個(gè)，即每天需派出9位乘務(wù)員值乘，總接續(xù)時(shí)間為2 658 min，且具有多種交路回路構(gòu)建方案，任選其中一個(gè)方案為：2-5，3-18，4-11，9-12，10-1，13-7，15-8，16-6和17-14。若采用鐵路現(xiàn)場(chǎng)目前常用的“先到先走”原則構(gòu)建，得到的方案為：16-6，3-17，2-5，13-7，4-8，15-9，10-1，11，12，14和18，即每天需派出11位乘務(wù)員值乘，比用本文提出的優(yōu)化算法求出的方案多2位。原因是按“先到先走”順序排下來，最后剩下的11，12，14和18號(hào)乘務(wù)片段相互間無法配對(duì)構(gòu)成回路，只能分別單獨(dú)構(gòu)成只包含一個(gè)乘務(wù)片段的乘務(wù)“回路”。優(yōu)化后的方案使工作時(shí)間更加緊湊，縮短了乘務(wù)員的工作冗余時(shí)間，從而減少了乘務(wù)員需要數(shù)。

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

表4 蟻群算法參數(shù)

表5 遺傳算法參數(shù)

5 結(jié)論

1) 帶立即折返的高速動(dòng)車組乘務(wù)回路編制問題，是我國開行高速動(dòng)車組后在司機(jī)乘務(wù)組織方面出現(xiàn)的新問題。此時(shí)用現(xiàn)場(chǎng)常用的“先到先走”的傳統(tǒng)方法編制出來的乘務(wù)交路方案，往往不是最優(yōu)方案。

2) 本文根據(jù)帶立即折返的高速動(dòng)車組乘務(wù)回路編制問題的特點(diǎn)，針對(duì)所有乘務(wù)片段都能相互配對(duì)構(gòu)成乘務(wù)回路的情形，在集合分解模型基礎(chǔ)上建立了該問題的數(shù)學(xué)模型，并設(shè)計(jì)了求解的蟻群?遺傳混合算法。經(jīng)實(shí)例求解和對(duì)比分析，優(yōu)化方案相比按“先到先走”編制出來的方案，使乘務(wù)員的工作時(shí)間更加緊湊，節(jié)約了乘務(wù)員的需要數(shù)，驗(yàn)證了該方法的有效性和合理性。

[1] 黃珊. 機(jī)車乘務(wù)員運(yùn)用問題及其輔助編排系統(tǒng)研究[D].長沙: 中南大學(xué), 2014. HUANG Shan. Locomotive crew scheduling problem and scheduling assistant system[D]. Changsha: Central South University, 2014.

[2] 楊國元, 史天運(yùn), 張秋亮. 鐵路客運(yùn)乘務(wù)排班計(jì)劃編制模型及算法[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2016, 16(4): 159?164. YANG Guoyuan, SHI Tianyun, ZHANG Qiuliang. Model and algorithm for railway passenger crew rostering plan[J]. Journal of Transportation System Engineering and Information Technology, 2016, 16(4): 159?164.

[3] Lavoie S, Minoux M, Odier E. A new approach of crew pairing problems by column generation and application to air transport[J]. European Journal of Operational Research, 1988(35): 45?58.

[4] Balaji Gopalakrishnan, Ellis L Johnson. Airline crew scheduling: State-of-the-art[J]. Annals of Operations Research, 2005, 140(1): 305?337.

[5] Desrochers M, Soumis F. A column generation approach to the urban transit crewing scheduling problem[J]. Transportation Science, 1989, 23(1): 1?14.

[6] Chu S C K, Chan E C H. Crew scheduling of light rail transit in Hongkong: from modeling to impelmentation[J]. Computer Ops Res, 1998, 25(11): 887?894.

[7] 陳海平. 高速鐵路乘務(wù)組織理論與優(yōu)化研究[D]. 北京: 北京交通大學(xué), 2013. CHEN Haiping. Research on theory and optimization of crew organization of high-speed railway[D]. Beijing: Beijing Jiaotong University, 2013.

[8] 趙鵬, 胡安洲, 楊浩. 機(jī)車乘務(wù)員運(yùn)用計(jì)劃的優(yōu)化編制[J]. 鐵道學(xué)報(bào), 1998, 20(4): 8?13.ZHAO Peng, HU Anzhou, YANG Hao. Research on optimization of crew scheduling[J]. Journal of the China Railway Society, 1998, 20(4): 8?13.

[9] 田志強(qiáng). 高速鐵路乘務(wù)計(jì)劃編制優(yōu)化理論與方法研究[D]. 成都: 西南交通大學(xué), 2011.TIAN Zhiqiang. Study on theory and methods of crew planning problem of high-speed railway[D]. Chengdu: Southwest Jiaotong University, 2011.

[10] 黎符忠, 王文憲, 陳皓. 混合遺傳算法在客運(yùn)專線司機(jī)乘務(wù)排班中的應(yīng)用[J]. 鐵道運(yùn)輸與經(jīng)濟(jì), 2015, 37(8): 88?92. LI Fuzhong, WANG Wenxian, CHEN Hao. Application of hybrid genetic algorithm on DPL driver crew scheduling[J]. Railway Transport and Economy, 2015, 37(8): 88?92.

[11] 王興慧, 頡俊杰. 基于均衡性的機(jī)車乘務(wù)排班計(jì)劃編制方法研究[J]. 交通科技與經(jīng)濟(jì), 2015, 17(5): 55?59.WANG Xinghui, XIE Junjie. Research on the crew rostering plan of trainset based on equilibrium[J]. Technology & Economy in Areas of Communications, 2015, 17(5): 55?59.

[12] Gershkoff I.Optimizing flight crew schedules[J]. Interfaces, 1989, 19(4): 29?43.

[13] Garey M R, Johnson D S. Computers and intractability: a guide to the theory of NP-completeness[M]. San Francisco: W. H. Freeman, 1979: 23?26.

[14] 史峰, 王輝. Matlab智能算法30個(gè)案例分析[M]. 北京:北京航空航天大學(xué)出版社, 2011.SHI Feng, WANG Hui. Analysis of 30 cases of Matlab algorithm[M]. Beijing: Beihang University Press, 2011.

An optimization method for high-speed motor train unit crew roundtrip routing problem with immediate turn-back

YANG Jiabao, FU Zhuo

(School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

The locomotive crew roundtrip routing is a part of the locomotive crew planning problem, and its reasonable construction is of great significance to the labor capacity of the crew (driver) and the cost of the railway transportation. In this paper, the high-speed motor train unit crew roundtrip routing problem with immediate turn-back is analyzed and abstracted. According to its characteristics，based on the model of set partitioning problem, an optimization model for it is established. A hybrid ant colony genetic algorithm is designed to solve the model. Computational results on real data show that the plan by this method is better than the “first come, first left” scheme.

railway transportation; immediate turn-back; locomotive crew routing; set partitioning problem; hybrid ant colony genetic algorithm

10.19713/j.cnki.43?1423/u.2018.11.003

U292

A

1672 ? 7029(2018)11 ? 2738 ? 08

2017?11?07

國家自然科學(xué)基金資助項(xiàng)目(71271220)；南昌鐵路局科技研究開發(fā)計(jì)劃資助項(xiàng)目(201713)

符卓(1960?)，男，海南文昌人，教授，博士，從事交通運(yùn)輸規(guī)劃與管理研究；E?mail：zhfu@csu.edu.cn

(編輯 蔣學(xué)東)