混合遺傳算法在客運(yùn)專線司機(jī)乘務(wù)排班中的應(yīng)用

黎符忠，王文憲，陳 皓

LI Fu-zhong1, WANG Wen-xian2, CHEN Hao2

（1.重慶市城市建設(shè)研究中心 基礎(chǔ)數(shù)據(jù)所，重慶 400020；2.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031）

(1．Basic Data Institute， Chongqing City Construction Research Center， Chongqing 400020， China； 2．School of Transportation and Logistics， Southwest Jiaotong University， Chengdu 610031， Sichuan， China)

混合遺傳算法在客運(yùn)專線司機(jī)乘務(wù)排班中的應(yīng)用

黎符忠1，王文憲2，陳 皓2

LI Fu-zhong1, WANG Wen-xian2, CHEN Hao2

（1.重慶市城市建設(shè)研究中心 基礎(chǔ)數(shù)據(jù)所，重慶 400020；2.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031）

(1．Basic Data Institute， Chongqing City Construction Research Center， Chongqing 400020， China； 2．School of Transportation and Logistics， Southwest Jiaotong University， Chengdu 610031， Sichuan， China)

為減少客運(yùn)專線司機(jī)乘務(wù)排班計(jì)劃中乘務(wù)組的使用數(shù)量及均衡各個(gè)乘務(wù)組的勞動(dòng)強(qiáng)度，構(gòu)建司機(jī)乘務(wù)排班計(jì)劃的多目標(biāo)規(guī)劃模型，針對(duì)傳統(tǒng)智能算法在求解該問(wèn)題時(shí)收斂性弱、易陷入局部最優(yōu)的缺陷，對(duì)基本遺傳算法進(jìn)行改進(jìn)，即采用特殊的染色體編碼方式縮小存儲(chǔ)空間，將空間劃分的思想對(duì)選擇算子進(jìn)行自適應(yīng)改進(jìn)，并引入模擬退火策略，以提高算法的收斂性及鄰域搜索能力。仿真結(jié)果表明，混合遺傳算法能夠在較短時(shí)間內(nèi)收斂得到優(yōu)化解，可以為客運(yùn)專線司機(jī)乘務(wù)排班問(wèn)題提供有效解決方案。

客運(yùn)專線；排班計(jì)劃；多目標(biāo)規(guī)劃模型；混合遺傳算法；空間劃分

0 引言

作為鐵路運(yùn)輸計(jì)劃中的重要部分，司機(jī)乘務(wù)排班計(jì)劃編制的合理與否，關(guān)系著乘務(wù)組的工作效率及鐵路運(yùn)輸部門(mén)的運(yùn)營(yíng)成本。司機(jī)乘務(wù)排班計(jì)劃的編制由于需要考慮司機(jī)乘務(wù)方式、司機(jī)乘務(wù)交路計(jì)劃及相關(guān)規(guī)程等因素的影響，而傳統(tǒng)人工編制又存在諸如誤差不易控制、人為錯(cuò)誤及效率低等問(wèn)題，難以適應(yīng)客運(yùn)專線高精度、高密度運(yùn)行需要。因此，為了提高乘務(wù)工作效率及保障客運(yùn)專線列車正常運(yùn)行，研究高效、快速的客運(yùn)專線司機(jī)乘務(wù)排班計(jì)劃方法具有重要的現(xiàn)實(shí)意義。

考慮司機(jī)乘務(wù)規(guī)則等多種限制因素，司機(jī)乘務(wù)排班計(jì)劃編制是比較復(fù)雜的組合優(yōu)化問(wèn)題。對(duì)于該問(wèn)題，許多學(xué)者進(jìn)行了深入研究：趙鵬等[1]提出了高速鐵路乘務(wù)計(jì)劃編制的基本過(guò)程，利用模擬進(jìn)化法 ( SE ) 進(jìn)行自動(dòng)編制，并對(duì)乘務(wù)計(jì)劃中非硬性約束進(jìn)行運(yùn)用模糊性描述；李獻(xiàn)忠等[2]引入乘務(wù)廣義費(fèi)用的概念對(duì)城市軌道交通排班問(wèn)題進(jìn)行描述，設(shè)計(jì)了日班和夜班 2 階段解決城市軌道交通乘務(wù)排班計(jì)劃編制的問(wèn)題；李文慧[3]以包乘制為前提，構(gòu)建乘務(wù)組分配模型，并設(shè)計(jì)用以求解的匈牙利算法；王瑩等[4]構(gòu)建基于備選乘務(wù)方案集合的分配模型，并對(duì)列生成算法加以改進(jìn)求解；張?zhí)K波[5]構(gòu)建基于印象因素、業(yè)務(wù)流程及評(píng)價(jià)準(zhǔn)則的乘務(wù)組分配模型，并采用遺傳算法求解。

隨著我國(guó)客運(yùn)專線列車運(yùn)行線數(shù)量規(guī)模的擴(kuò)大，既有算法難以在合理時(shí)間內(nèi)得到最優(yōu)解甚至可行解。而基本遺傳算法或其改進(jìn)算法亦存在運(yùn)算過(guò)程中收斂性弱、搜索空間小及易陷入局部最優(yōu)的缺陷[6]。因此，針對(duì)客運(yùn)專線司機(jī)乘務(wù)排班問(wèn)題的特點(diǎn)，在對(duì)基本遺傳算法選擇算子進(jìn)行自適應(yīng)改進(jìn)的基礎(chǔ)上，通過(guò)引入模擬退火策略擴(kuò)大遺傳算法的鄰域搜索空間，有效解決客運(yùn)專線司機(jī)乘務(wù)排班問(wèn)題。

1 司機(jī)乘務(wù)排班優(yōu)化模型

1.1 問(wèn)題描述

在客運(yùn)專線的實(shí)際運(yùn)營(yíng)中，每一列車運(yùn)行線都安排有司機(jī)乘務(wù)組執(zhí)行司機(jī)乘務(wù)工作，司機(jī)乘務(wù)排班計(jì)劃的實(shí)質(zhì)是給每條列車運(yùn)行線都分配具體的司機(jī)乘務(wù)人員及乘務(wù)組數(shù)量，使其完成運(yùn)行任務(wù)[7]。在編制司機(jī)乘務(wù)排班計(jì)劃時(shí)，應(yīng)達(dá)到以下要求。

（1）每個(gè)司機(jī)乘務(wù)組在同一時(shí)刻只能值乘一個(gè)列車，即完成當(dāng)前值乘的司機(jī)乘務(wù)區(qū)段任務(wù)后，才可以開(kāi)始下次司機(jī)乘務(wù)任務(wù)。

（2）每一條列車運(yùn)行線都必須有司機(jī)乘務(wù)組值乘[8]。

（3）司機(jī)乘務(wù)組的類別必須與所值乘的列車類型相一致。

（4）司機(jī)乘務(wù)組值乘一次連續(xù)值乘時(shí)間應(yīng)不大于 4 h，而且再次值乘間隔時(shí)間應(yīng)滿足一定時(shí)間要求。

（5）為提高乘務(wù)員的勞動(dòng)積極性，從均衡各乘務(wù)組的勞動(dòng)強(qiáng)度考慮，盡可能使各乘務(wù)組間的值班任務(wù)均衡化。

1.2 符號(hào)說(shuō)明

式中：c 為一個(gè)合適的正整數(shù)，可以根據(jù)實(shí)際數(shù)據(jù)調(diào)整。決策變量：為 0-1 變量，表示司機(jī)乘務(wù)組 pi在第 k 天是否值乘交路 qj，取 1 為是，取 0 為否。

1.3 模型建立

以所有司機(jī)乘務(wù)組值乘所有交路的消耗最小及各乘務(wù)組之間的勞動(dòng)強(qiáng)度盡量達(dá)到均衡為目標(biāo)，建立客運(yùn)專線司機(jī)乘務(wù)排班問(wèn)題的優(yōu)化模型 ，即

其中，⑵ 式和 ⑶ 式為目標(biāo)函數(shù)，⑵ 式表示全部司機(jī)乘務(wù)組 pi值與所有交路 qj消耗的乘積；⑶ 式為各司機(jī)乘務(wù)組 pi之間的勞動(dòng)強(qiáng)度方差。⑷ 式— ⑻ 式為約束條件，⑷ 式表示某個(gè)司機(jī)乘務(wù)組在同一時(shí)間內(nèi)只能值乘一個(gè)乘務(wù)交路；⑸ 式表示所有乘務(wù)交路必須都有司機(jī)乘務(wù)組值乘；⑹ 式表示司機(jī)乘務(wù)組連續(xù)值乘不同交路時(shí)的接續(xù)地點(diǎn)約束，即接續(xù)站點(diǎn)相同；⑺ 式表示司機(jī)乘務(wù)組再次值乘的間隔時(shí)間應(yīng)滿足的時(shí)間要求，即不小于最小時(shí)間間隔；⑻ 式表示決策變量的定義域。

2 混合遺傳算法設(shè)計(jì)

現(xiàn)有的大規(guī)模司機(jī)乘務(wù)排班問(wèn)題求解算法多為遺傳算法、禁忌搜索等啟發(fā)式算法，這些算法大多是通過(guò)調(diào)整算法本身的參數(shù)設(shè)置不斷獲得問(wèn)題優(yōu)化解，難以保證求解性能和全局收斂性。引入空間劃分的思想對(duì)多目標(biāo)排班問(wèn)題的解空間進(jìn)行劃分[9]，并引入模擬退火策略加強(qiáng)算法鄰域搜索能力，以解決上述問(wèn)題。

2.1 算法的關(guān)鍵步驟

算法實(shí)現(xiàn)的關(guān)鍵步驟主要包括編碼、選擇、交叉、變異及退火策略 5 個(gè)部分。

（1）編碼。編碼的主要目的是將問(wèn)題的解空間轉(zhuǎn)化為利于遺傳算子操作的虛擬空間結(jié)構(gòu)。司機(jī)乘務(wù)交路數(shù)用傳統(tǒng)的 0-1 編碼時(shí)，會(huì)造成基因編碼維度過(guò)大，導(dǎo)致數(shù)據(jù)的存儲(chǔ)不合理，因而采用整數(shù)編碼。為詳細(xì)說(shuō)明編碼方式和含義，假設(shè) 8 個(gè)司機(jī)乘務(wù)組值乘 6 個(gè)乘務(wù)交路，2 個(gè)不同的染色體為染色體 A ( 12856437 )，染色體 B ( 41782356 )。其中，染色體 A 表示司機(jī)乘務(wù)組 1，2，8，5，6 分別值乘交路 1至交路 5，司機(jī)乘務(wù)組4，3，7休息；染色體 B 表示司機(jī)乘務(wù)組 4，1，7，8，2 分別值乘交路 1 至交路 5，司機(jī)乘務(wù)組 3，5，6 休息。

（2）選擇。為權(quán)衡考慮優(yōu)化模型的 2 個(gè)目標(biāo)，引入空間劃分的思想設(shè)計(jì)選擇策略。建立二維坐標(biāo)空間坐標(biāo)系，該坐標(biāo)系以目標(biāo) Z1的適應(yīng)度函數(shù) f1為橫軸，以目標(biāo) Z2的適應(yīng)度函數(shù) f2為縱軸，種群適應(yīng)度均值為

式中：f1i，f2i分別為染色體 i 的 2 個(gè)適應(yīng)度；n 為種群規(guī)模。

建立包含所有染色體適應(yīng)度及種群適應(yīng)度均值的坐標(biāo)系如圖1 所示，以種群適應(yīng)度均值為中心，將該坐標(biāo)系分成 4 個(gè)象限，即Ⅰ、Ⅱ、Ⅲ、Ⅳ象限。

圖1 解空間分布圖

依次從Ⅰ、Ⅱ、Ⅲ、Ⅳ 4 個(gè)象限選擇優(yōu)秀的染色體組成子代種群，個(gè)體分布于各個(gè)象限中的被選概率分別為

（3）交叉。在 1～6 號(hào)基因位點(diǎn)中隨機(jī)選擇一個(gè)作為交叉位點(diǎn)，按以下方法生成子代染色體：交叉位點(diǎn)之前，兩子代染色體繼承各自父代染色體的基因片段；交叉位點(diǎn)之后，兩子代染色體從對(duì)方父代染色體中按其順序選擇不同的基因。如以上 2 個(gè)染色體在 3 號(hào)位點(diǎn)進(jìn)行交叉，子代 A’ 是從父代 A ( 1246537 ) 的交叉位前取 124，然后以父代 B ( 4372156 ) 依順序選取不與 124 重復(fù)的基因3756，即子代染色體 A’ ( 1243756 )，子代染色體 B’ ( 4371265 )。

（4）變異。在染色體中隨機(jī)挑選 2 個(gè)基因位點(diǎn)，交換這 2 個(gè)位點(diǎn)所對(duì)應(yīng)的基因值，如變異前染色體 A ( 1243756 )，變異后染色體 A ( 1263754 )。

（5）退火策略。在混合遺傳算法中，自適應(yīng)遺傳算法控制全局的尋優(yōu)方向，模擬退火的Metropolics 鄰域搜索策略提高算法的鄰域搜索能力，兩者結(jié)合使算法求解性能得到提高。每次迭代時(shí)，在執(zhí)行完遺傳策略的子代種群中，隨機(jī)選擇一個(gè)當(dāng)前個(gè)體 chrom ( i ) 并按照變異的方式產(chǎn)生其鄰域個(gè)體 chrom ( j )，然后按照 Metropolics 策略對(duì)當(dāng)前個(gè)體進(jìn)行替換，即

2.2 算法的實(shí)現(xiàn)流程

算法實(shí)現(xiàn)的具體步驟如下。

步驟 1：設(shè)定各參數(shù)，種群大小 popsize，算法最大迭代次數(shù) Maxgen，執(zhí)行交叉算子的概率為 pc，執(zhí)行變異算子的概率為 pm，初始溫度 ts，溫度衰減參數(shù) a。

步驟 2：按照前述染色體編碼方式生成初始種群 pop，當(dāng)前代數(shù) n1。

步驟 3：計(jì)算當(dāng)前種群中各染色體適應(yīng)度，選擇最優(yōu)個(gè)體直接進(jìn)入下一代，剩余個(gè)體進(jìn)行輪盤(pán)賭隨機(jī)選擇。

步驟 4：生成 ( 0，1) 間的隨機(jī)數(shù) rand_c，若 rand_c ≤ pc，對(duì)種群進(jìn)行交叉操作。

步驟 5：生成 ( 0，1) 間的隨機(jī)數(shù) rand_m，若 rand_c ≤ pm，對(duì)種群進(jìn)行變異操作。

步驟 6：在子代種群隨機(jī)選擇一個(gè)染色體生成其鄰域解，按 Metropolics 選擇策略即 ⑾ 式對(duì)兩者進(jìn)行選擇，更新當(dāng)前迭代次數(shù) nn + 1 及溫度 tt · a。

步驟 7：算法終止判定，若 n ≤ Maxgen，轉(zhuǎn)步驟 3 循環(huán)計(jì)算，否則輸出當(dāng)前種群中最優(yōu)染色體，并解碼為最優(yōu)司機(jī)乘務(wù)排班計(jì)劃。

3 實(shí)例分析

以某列車運(yùn)行圖為例，選取客運(yùn)專線司機(jī)乘務(wù)交路數(shù)據(jù)[10]，按照《鐵路技術(shù)管理規(guī)程》，休息時(shí)間為 960 min，大休時(shí)間 2 880 min，大休累計(jì)值乘時(shí)間為 2 880 min，間隔時(shí)間為 240 min[11]。其中，司機(jī)乘務(wù)組 1 能夠匹配值乘的交路編號(hào)為 1，3，4，5，8，13，14，15，16；司機(jī)乘務(wù)組 2 能夠匹配值乘的交路編號(hào)為 3，4，5，6，8，9，12，13，14；司機(jī)乘務(wù)組 3 能夠匹配值乘的交路編號(hào)為 1，2，3 ，7 ，8，10，11，12，13。

設(shè)置算法參數(shù)：種群大小 popsize = 25，最大迭代次數(shù) Maxgen = 300，交叉概率 pc= 0.7，變異概率 pm= 0.1，初始溫度 t = 999，溫度衰減參數(shù) a =0.87。運(yùn)用 MATLAB 7.0 編程，運(yùn)行 5 次，選擇最優(yōu)目標(biāo)對(duì)應(yīng)的司機(jī)乘務(wù)排班計(jì)劃編制結(jié)果如表1 所示。

表1 各流向路徑選擇結(jié)果

由表2 可知，經(jīng)過(guò)優(yōu)化后的值乘計(jì)劃為司機(jī)乘務(wù)組 1 值乘交路為 1，15，16，5，8，1；司機(jī)乘務(wù)組 2 值乘交路為 4，14，9，3，6，12，4；司機(jī)乘務(wù)組 3 值乘交路為 10，7，2，13，11，1，10；總接續(xù)時(shí)間為 27 220 min。

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

客運(yùn)專線司機(jī)乘務(wù)排班計(jì)劃優(yōu)化問(wèn)題是一個(gè)大規(guī)模任務(wù)分配問(wèn)題[12]。在遺傳算法的基礎(chǔ)上，根據(jù)研究問(wèn)題的特點(diǎn)對(duì)遺傳策略進(jìn)行自適應(yīng)改進(jìn)并引入模擬退火策略加強(qiáng)鄰域搜索能力，從而避免了遺傳算法求解該問(wèn)題時(shí)不易收斂的弊端。算例仿真表明，針對(duì)客運(yùn)專線司機(jī)乘務(wù)排班計(jì)劃優(yōu)化的自適應(yīng)遺傳退火算法能夠在較短時(shí)間內(nèi)得到的較優(yōu)排班計(jì)劃方案，對(duì)鐵路管理決策人員具有一定指導(dǎo)作用。

[1] 趙 鵬，胡安洲，楊 浩． 機(jī)車乘務(wù)員運(yùn)用計(jì)劃的優(yōu)化編制[J]． 鐵道學(xué)報(bào)，1998，20(4)：8-13．ZHAO Peng，HU An-zhou，YANG Hao． Research on Optimization of Crew Scheduling[J]． Journal of the China Railway Society，1998，20(4)：8-13．

[2] 李獻(xiàn)忠，徐瑞華． 基于時(shí)間耗費(fèi)的城市軌道交通乘務(wù)排班優(yōu)化[J]． 鐵道學(xué)報(bào)，2007，29(1)：21-25．LI Xian-zhong，XU Rui-hua． Optimization of Crew Scheduling for Urban Rail Transportation based on Time Costs[J]． Journal of the China Railway Society，2007，29(1)：21-25．

[3] 李文慧． 匈牙利方法在鐵路列車乘務(wù)組分派問(wèn)題中的應(yīng)用[J]． 蘭州交通大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，26(3)：55-57．LI Wen-hui． Application of Hungary Algorithm in Assignment Problem of Train Crew[J]． Journal of Lanzhou Jiaotong University：Natural Sciences，2007，26(3)：55-57．

[4] 王 瑩，劉 軍，苗建瑞． 客運(yùn)專線乘務(wù)交路計(jì)劃編制的優(yōu)化模型與算法[J]． 鐵道學(xué)報(bào)，2009，31(1)：15-19．WANG Ying，LIU Jun，MIAO Jian-rui． Modeling and Solving the Crew Scheduling Problem of Passenger Dedicated Line[J]． Journal of the China Railway Society，2009，31(1)：15-19．

[5] 張?zhí)K波． 客運(yùn)專線乘務(wù)排班系統(tǒng)相關(guān)問(wèn)題研究[D]． 成都：西南交通大學(xué)，2009．ZHANG Su-bo． Research on the Relative Problems of Crew Scheduling System for Passenger Special Line[D]． Chengdu：Southwest Jiaotong University，2009．

[6] 康立山． 非數(shù)值并行算法—遺傳算法[M]． 北京：科學(xué)出版社，2004．KANG Li-shan． Non-Numerical Parallel Algorithms -Genetic algorithm[M]． Beijing：Science Press，2004．

[7] Kay W A． Seminar on Algorithms and Models for Railway Optimization Crew Scheduling[J]． European Journal of Operational Research，2006，168(2)：403-424．

[8] Jorenz H W． Nonlinear Dynamical Economics and Motion[M]． Berlin：SPringer Publishers，2001．

[9]《運(yùn)籌學(xué)》教材編寫(xiě)組． 運(yùn)籌學(xué)[M]． 北京：清華大學(xué)出版社，2005．Operations Research[M]． Beijing：Tsinghua University Press，2005．

[10] 田志強(qiáng)． 高速鐵路乘務(wù)計(jì)劃編制優(yōu)化理論與方法研究[D]． 成都：西南交通大學(xué)，2011．TIAN Zhi-qiang． Study on Theory and Methods of Crew Planning Problem of High-speed Railway[D]． Chengdu：Southwest Jiaotong University，2011．

[11] 楊文韜，周 強(qiáng)． 客運(yùn)專線動(dòng)車組交路計(jì)劃模型研究[J]． 鐵道運(yùn)輸與經(jīng)濟(jì)，2013，35(12)：30-36．YANG Wen-tao，ZHOU Qiang． Study on DPL EMU Routing Scheme Model[J]． Railway Transport and Economy，2013，35(12)：30-36．

[12] 劉 冰，崔艷萍，劉啟鋼．日本新干線乘務(wù)運(yùn)用與啟示[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2013，35(12)：63-67．LIU Bing，CUI Yan-ping，LIU Qi-gang． Crew Using and Revelation of Japanese Shinkansen[J]． Railway Transport and Economy，2013，35(12)：63-67．

責(zé)任編輯：何 瑩

Application of Hybrid Genetic Algorithm on DPL Driver Crew Scheduling

In order to reduce the quantity of train crew in DPL diver crew scheduling and balancing labor intensity of each crew, the multi-object programming model of driver crew scheduling was established. Targeting with the defects of traditional intelligent algorithm when solving problems, including weak convergence and easily falling into local optimization, the basic genetic algorithm was improved, which means reducing storage space by using special chromosome coding, making adaptive improvement on selection operator based on spatial partitioning idea and introducing simulated annealing strategy, so as to increase the algorithm convergence and neighborhood search capacity. The simulation result shows the hybrid genetic algorithm can reach optimal solutions of convergence in short time and could provide effective solutions for DPL driver crew scheduling.

DPL; Crew Scheduling; Multi-object Programming Model; Hybrid Genetic Algorithm; Spatial Partitioning

1003-1421(2015)08-0088-05

U293.1

A

2015-02-10

2015-05-28

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助(2682015CX043)