閆冬

摘 要：高速鐵路乘務(wù)計劃編制的優(yōu)劣直接影響著乘務(wù)工作的效率以及經(jīng)濟效益。該文研究了乘務(wù)交路計劃編制過程中乘務(wù)交路的組成及其費用計算方法，提出了以便乘費用而非值乘費用計算各值乘區(qū)段的相關(guān)費用，設(shè)計了求解值乘區(qū)段集合覆蓋問題的具有雙重信息素和啟發(fā)式信息的蟻群優(yōu)化算法。

關(guān)鍵詞：乘務(wù)交路 值乘區(qū)段 集合覆蓋 最小費用

中途分類號：U292.8 文獻標示碼：A 文章編號：1674-098X（2014）04（a）-0012-02

1 問題的提出

值乘區(qū)段是按照列車運行圖規(guī)定的列車在各站的停車情況和動車組司機換乘站的分布，將列車運行線或動車組交路劃分為動車組司機能夠連續(xù)值乘的最小片段。從運營成本等經(jīng)濟角度，有必要從乘務(wù)計劃角度分析動車組司機的運用費用。

2 運用費用分析

動車組司機完成乘務(wù)交路值乘的過程分為出勤、值乘、換乘、值乘/便乘、退勤等部分，且都存在一定的費用，故將乘務(wù)交路費用分為以下幾部分。

2.1 出、退勤費用

出、退勤費用主要包括動車組司機一次出乘的固定報酬和擔當值乘任務(wù)所需耗材等支出的相關(guān)費用，其取值通常為定值，用常量mb表示。

2.2 值乘費用

對某一乘務(wù)交路而言，動車組司機擔當該交路值乘任務(wù)的費用與值乘時間成正比。若值乘時間為tzc，單位時間值乘費用為mzc，則值乘費用為mzctzc。

2.3 換乘費用

乘務(wù)交路中的換乘涉及換乘次數(shù)與換乘時間兩個問題，本文定義了換乘基本費用和無效換乘費用兩個概念。換乘基本費用是換乘次數(shù)產(chǎn)生的相關(guān)費用。若乘務(wù)交路i中的換乘次數(shù)為ki，一次換乘基本費用為mhc，則乘務(wù)交路i換乘基本費用為kimhc。但在實際換乘中，乘務(wù)員實際換乘時間與換乘時間標準存在差值。若乘務(wù)員某次換乘實際時間為，乘務(wù)員換乘時間標準為thc，單位時間無效換乘費用為，則引起的無效換乘費用為（）mwx。

2.4 便乘費用

便乘費用是在便乘過程中產(chǎn)生的費用。設(shè)便乘時間為tbc，單位時間便乘費用為mbc，則便乘費用為mbctbc。

乘務(wù)交路i的總費用mi=mb+mzctzc+kimhc+

mwx+mbctbc （1）

其中，式中mzc、mwx、mbc均與時間有關(guān)，故可以將mwx、mbc轉(zhuǎn)化為與mzc相關(guān)的函數(shù)。

令α為mwx相對于mzc的系數(shù)，β為mbc相對的mzc系數(shù)。

mi=mb+mzctzc+kimhc+αmzc+

βmzctbc （2）

若將可行乘務(wù)交路i中所有值乘區(qū)段費用均以便乘費用計算，則乘務(wù)交路i的費用可表示為：

=mb+kimhc+αmzc+

βmzcti （3）

則所有乘務(wù)交路的總費用為：

minZ= （4）

式中n—乘務(wù)交路總數(shù)；

xi—0-1決策變量，當乘務(wù)交路i被選入最終解時取1，否則取0。

3 優(yōu)化目標和約束條件

3.1 優(yōu)化目標

動車組司機是完成高速鐵路運輸生產(chǎn)任務(wù)的主體，計劃使用的動車組司機（即覆蓋所有值乘區(qū)段的可行交路數(shù)量）數(shù)量越多，相應(yīng)的費用越高，故選擇以最小化覆蓋所有值乘區(qū)段的乘務(wù)交路的總費用最少作為優(yōu)化目標。

3.2 約束條件

（1）在可行乘務(wù)交路中，接續(xù)的值乘區(qū)段滿足空間約束，即前一值乘區(qū)段的終點和后一值乘區(qū)段的起點為同一車站。

（2）在可行乘務(wù)交路中，當接續(xù)的兩個值乘區(qū)段不屬于同一動車組交路時，應(yīng)滿足時間約束，即前一值乘區(qū)段的到達時間與后一值乘區(qū)段的發(fā)車時間滿足動車組司機換乘時間標準。

（3）動車組司機一次連續(xù)作業(yè)時間滿足機車乘務(wù)員工作和休息時間標準。

4 模型的建立

在上述分析的前提下，建立以乘務(wù)交路總費用為最小為目標的值乘區(qū)段集合覆蓋模型如下：

minZ= （5）

≥1 j=1，2，3…p （6）

式中 n—乘務(wù)交路總數(shù)；

xi—0-1決策變量，當乘務(wù)交路i被選入最終解時取1，否則取0。

P—值乘區(qū)段的數(shù)量

—可行交路i的總費用

aij—0-1變量，當可行乘務(wù)交路i包含值乘區(qū)段j時為1，否則為0。

式（6）表示每一值乘區(qū)段至少屬于一個乘務(wù)交路。

5 算法設(shè)計

該文蟻群算法的關(guān)鍵參數(shù)和主要操作如下。

5.1 解構(gòu)建圖的表示

解的構(gòu)建圖由所有值乘區(qū)段的結(jié)點和若干個原點組成，原點是虛擬的共同點，作為乘務(wù)交路的起點和終點，被復(fù)制為乘務(wù)交路的數(shù)目。

5.2 解的構(gòu)建

所有螞蟻均從某一原點出發(fā)，首先根據(jù)概率選擇乘務(wù)交路的起始結(jié)點，并記錄起始值乘區(qū)段的出發(fā)車站As，若出發(fā)車站為乘務(wù)基地，則令A(yù)s=O，否則令A(yù)s=1。根據(jù)概率選擇下一個值乘區(qū)段結(jié)點，若某名動車組司機累計工作時間未達到相關(guān)時間標準，繼續(xù)選擇下一結(jié)點，直至接續(xù)一系列的值乘區(qū)段后返回該原點，形成一個回路（即乘務(wù)交路），記錄乘務(wù)交路的終止車站Ae。如果若終止車站為乘務(wù)基地，則令A(yù)e=0，否則令A(yù)e=1，若乘務(wù)交路滿足AsAe=O，則表示得到了一個滿足相關(guān)時間和地點約束的乘務(wù)交路，否則采用回溯策略，使乘務(wù)交路滿足AsAe=O。螞蟻重復(fù)該過程進行解的構(gòu)建，當所有的值乘區(qū)都被選擇進入相應(yīng)的乘務(wù)交路時，表示完成解的構(gòu)建過程。

5.3 信息素的表示、初始化及更新

1）信息素的表示

該文同時記錄解構(gòu)建圖中所有路徑的信息素τij和全部結(jié)點的信息素τi。其中，τij是螞蟻處于值乘區(qū)段結(jié)點i時所接續(xù)的是值乘區(qū)段j的期望程度，而τi是指當螞蟻處于原點時，選擇值乘區(qū)段j作為下一個乘務(wù)交路起始結(jié)點的期望程度。endprint

2）信息素的初始化

在蟻群算法迭代前，各路徑及值乘區(qū)段結(jié)點上的信息素初值按照式（7）和（8）確定：

τij（0）= （7）

τi（0）= （8）

3）信息素更新原則

在本蟻群算法中，只有迭代最優(yōu)螞蟻（即構(gòu)造出本次迭代最優(yōu)解的螞蟻）才被允許釋放信息素，在每次迭代后各路徑及結(jié)點上信息素的更新原則表示為：

τij（n+1）=ρτij（n）+△τij （9）

τi（n+1）=ρτi（n）+△τi （10）

式中ρ為信息素的揮發(fā)系數(shù)，0<ρ<1，n為迭代次數(shù)，△τij和△τi為本次迭代的信息素增量。

設(shè)λib為第n次迭代的最優(yōu)解，fib為λib的目標函數(shù)值，則△τij和△τi可由式（11）和（12）確定：

△τij= （11）

△τi= （12）

其中，Starti為0-1變量，當值乘區(qū)段結(jié)點i在最終解中作為某個乘務(wù)交路的起點時取1，否則取0。

5.4 選擇策略

1）當螞蟻r所處結(jié)點i并非原點時，選擇下一個值乘區(qū)段結(jié)點j的概率公式如下：

= （13）

其中，啟發(fā)式信息ηij按式（14）取值：

ηij= （14）

式中Dij為0-1變量，當兩個值乘區(qū)段所屬動車組交路相同且為緊接續(xù)時為1，否則為0。

2）當螞蟻r所處結(jié)點為原點是，選擇值乘區(qū)段i作為下一個乘務(wù)交路起點的概率為

=（15）

其中，selectdi為0-1變量，表示值乘區(qū)段i是否已被選擇。

ηi可按式（16）下式取值：

ηi= （16）

式中為值乘區(qū)段i的結(jié)束時間，△為當前剩余值乘區(qū)段的最早結(jié)束時間；α為控制系數(shù)；Nuf為尚未被選入熱河乘務(wù)交路的值乘區(qū)段的數(shù)量；N為值乘區(qū)段的總數(shù)。

6 算例分析

該文以現(xiàn)行的京滬高鐵部分動車組北京南-濟南西列車運行計劃求解具有最小費用的乘務(wù)交路段集合，其基礎(chǔ)數(shù)據(jù).

在算例中，動車組司機換乘時間標準為15 min，間休時間標準為120 min，連續(xù)工作時間為300 min，一次出乘工作時間標準為480 min。采用C語言編程，在Intel Core5，CPU 2.66 GHz，內(nèi)存2GB的計算機上執(zhí)行20.2712 s后，最終共得到16個乘務(wù)交路，結(jié)果為表2。

7 結(jié)語

該文采用的集合覆蓋模型表示乘務(wù)交路集合覆蓋問題需要對可行乘務(wù)交路的費用進行明確的表示，在計算費用過程中，以便乘費用而非值乘費用計算動車組司機擔當所有值乘區(qū)段的工作費用時，可以建立標準集合覆蓋模型。在求解過程中，將問題轉(zhuǎn)化為在網(wǎng)絡(luò)圖中尋找至少覆蓋所有結(jié)點一次的最小費用鏈問題，經(jīng)驗證取得較好效果。

參考文獻

[1] 趙鵬.高速鐵路動車組和乘務(wù)員運用的研究[D].北京：北方交通大學(xué)，1998：62-67.

[2] 陳華群.動車組運用計劃編制系統(tǒng)相關(guān)問題研究[D].西南交通大學(xué)碩士學(xué)位文，2007.

[3] 王瑩，劉軍，苗建瑞.客運專線乘務(wù)交路計劃編制的優(yōu)化模型與算法[J].鐵道學(xué)報，2009，31（1）：15-19.endprint

2）信息素的初始化

在蟻群算法迭代前，各路徑及值乘區(qū)段結(jié)點上的信息素初值按照式（7）和（8）確定：

τij（0）= （7）

τi（0）= （8）

3）信息素更新原則

在本蟻群算法中，只有迭代最優(yōu)螞蟻（即構(gòu)造出本次迭代最優(yōu)解的螞蟻）才被允許釋放信息素，在每次迭代后各路徑及結(jié)點上信息素的更新原則表示為：

τij（n+1）=ρτij（n）+△τij （9）

τi（n+1）=ρτi（n）+△τi （10）

式中ρ為信息素的揮發(fā)系數(shù)，0<ρ<1，n為迭代次數(shù)，△τij和△τi為本次迭代的信息素增量。

設(shè)λib為第n次迭代的最優(yōu)解，fib為λib的目標函數(shù)值，則△τij和△τi可由式（11）和（12）確定：

△τij= （11）

△τi= （12）

其中，Starti為0-1變量，當值乘區(qū)段結(jié)點i在最終解中作為某個乘務(wù)交路的起點時取1，否則取0。

5.4 選擇策略

1）當螞蟻r所處結(jié)點i并非原點時，選擇下一個值乘區(qū)段結(jié)點j的概率公式如下：

= （13）

其中，啟發(fā)式信息ηij按式（14）取值：

ηij= （14）

式中Dij為0-1變量，當兩個值乘區(qū)段所屬動車組交路相同且為緊接續(xù)時為1，否則為0。

2）當螞蟻r所處結(jié)點為原點是，選擇值乘區(qū)段i作為下一個乘務(wù)交路起點的概率為

=（15）

其中，selectdi為0-1變量，表示值乘區(qū)段i是否已被選擇。

ηi可按式（16）下式取值：

ηi= （16）

式中為值乘區(qū)段i的結(jié)束時間，△為當前剩余值乘區(qū)段的最早結(jié)束時間；α為控制系數(shù)；Nuf為尚未被選入熱河乘務(wù)交路的值乘區(qū)段的數(shù)量；N為值乘區(qū)段的總數(shù)。

6 算例分析

該文以現(xiàn)行的京滬高鐵部分動車組北京南-濟南西列車運行計劃求解具有最小費用的乘務(wù)交路段集合，其基礎(chǔ)數(shù)據(jù).

在算例中，動車組司機換乘時間標準為15 min，間休時間標準為120 min，連續(xù)工作時間為300 min，一次出乘工作時間標準為480 min。采用C語言編程，在Intel Core5，CPU 2.66 GHz，內(nèi)存2GB的計算機上執(zhí)行20.2712 s后，最終共得到16個乘務(wù)交路，結(jié)果為表2。

7 結(jié)語

該文采用的集合覆蓋模型表示乘務(wù)交路集合覆蓋問題需要對可行乘務(wù)交路的費用進行明確的表示，在計算費用過程中，以便乘費用而非值乘費用計算動車組司機擔當所有值乘區(qū)段的工作費用時，可以建立標準集合覆蓋模型。在求解過程中，將問題轉(zhuǎn)化為在網(wǎng)絡(luò)圖中尋找至少覆蓋所有結(jié)點一次的最小費用鏈問題，經(jīng)驗證取得較好效果。

參考文獻

[1] 趙鵬.高速鐵路動車組和乘務(wù)員運用的研究[D].北京：北方交通大學(xué)，1998：62-67.

[2] 陳華群.動車組運用計劃編制系統(tǒng)相關(guān)問題研究[D].西南交通大學(xué)碩士學(xué)位文，2007.

[3] 王瑩，劉軍，苗建瑞.客運專線乘務(wù)交路計劃編制的優(yōu)化模型與算法[J].鐵道學(xué)報，2009，31（1）：15-19.endprint

2）信息素的初始化

在蟻群算法迭代前，各路徑及值乘區(qū)段結(jié)點上的信息素初值按照式（7）和（8）確定：

τij（0）= （7）

τi（0）= （8）

3）信息素更新原則

在本蟻群算法中，只有迭代最優(yōu)螞蟻（即構(gòu)造出本次迭代最優(yōu)解的螞蟻）才被允許釋放信息素，在每次迭代后各路徑及結(jié)點上信息素的更新原則表示為：

τij（n+1）=ρτij（n）+△τij （9）

τi（n+1）=ρτi（n）+△τi （10）

式中ρ為信息素的揮發(fā)系數(shù)，0<ρ<1，n為迭代次數(shù)，△τij和△τi為本次迭代的信息素增量。

設(shè)λib為第n次迭代的最優(yōu)解，fib為λib的目標函數(shù)值，則△τij和△τi可由式（11）和（12）確定：

△τij= （11）

△τi= （12）

其中，Starti為0-1變量，當值乘區(qū)段結(jié)點i在最終解中作為某個乘務(wù)交路的起點時取1，否則取0。

5.4 選擇策略

1）當螞蟻r所處結(jié)點i并非原點時，選擇下一個值乘區(qū)段結(jié)點j的概率公式如下：

= （13）

其中，啟發(fā)式信息ηij按式（14）取值：

ηij= （14）

式中Dij為0-1變量，當兩個值乘區(qū)段所屬動車組交路相同且為緊接續(xù)時為1，否則為0。

2）當螞蟻r所處結(jié)點為原點是，選擇值乘區(qū)段i作為下一個乘務(wù)交路起點的概率為

=（15）

其中，selectdi為0-1變量，表示值乘區(qū)段i是否已被選擇。

ηi可按式（16）下式取值：

ηi= （16）

式中為值乘區(qū)段i的結(jié)束時間，△為當前剩余值乘區(qū)段的最早結(jié)束時間；α為控制系數(shù)；Nuf為尚未被選入熱河乘務(wù)交路的值乘區(qū)段的數(shù)量；N為值乘區(qū)段的總數(shù)。

6 算例分析

該文以現(xiàn)行的京滬高鐵部分動車組北京南-濟南西列車運行計劃求解具有最小費用的乘務(wù)交路段集合，其基礎(chǔ)數(shù)據(jù).

在算例中，動車組司機換乘時間標準為15 min，間休時間標準為120 min，連續(xù)工作時間為300 min，一次出乘工作時間標準為480 min。采用C語言編程，在Intel Core5，CPU 2.66 GHz，內(nèi)存2GB的計算機上執(zhí)行20.2712 s后，最終共得到16個乘務(wù)交路，結(jié)果為表2。

7 結(jié)語

該文采用的集合覆蓋模型表示乘務(wù)交路集合覆蓋問題需要對可行乘務(wù)交路的費用進行明確的表示，在計算費用過程中，以便乘費用而非值乘費用計算動車組司機擔當所有值乘區(qū)段的工作費用時，可以建立標準集合覆蓋模型。在求解過程中，將問題轉(zhuǎn)化為在網(wǎng)絡(luò)圖中尋找至少覆蓋所有結(jié)點一次的最小費用鏈問題，經(jīng)驗證取得較好效果。

參考文獻

[1] 趙鵬.高速鐵路動車組和乘務(wù)員運用的研究[D].北京：北方交通大學(xué)，1998：62-67.

[2] 陳華群.動車組運用計劃編制系統(tǒng)相關(guān)問題研究[D].西南交通大學(xué)碩士學(xué)位文，2007.

[3] 王瑩，劉軍，苗建瑞.客運專線乘務(wù)交路計劃編制的優(yōu)化模型與算法[J].鐵道學(xué)報，2009，31（1）：15-19.endprint