基于最小費用的高速鐵路值乘區段集合模型研究

閆冬

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

關鍵詞：乘務交路 值乘區段 集合覆蓋 最小費用

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

1 問題的提出

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

2 運用費用分析

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

2.1 出、退勤費用

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

2.2 值乘費用

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

2.3 換乘費用

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

2.4 便乘費用

便乘費用是在便乘過程中產生的費用。設便乘時間為tbc，單位時間便乘費用為mbc，則便乘費用為mbctbc。

乘務交路i的總費用mi=mb+mzctzc+kimhc+

mwx+mbctbc （1）

其中，式中mzc、mwx、mbc均與時間有關，故可以將mwx、mbc轉化為與mzc相關的函數。

令α為mwx相對于mzc的系數，β為mbc相對的mzc系數。

mi=mb+mzctzc+kimhc+αmzc+

βmzctbc （2）

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

=mb+kimhc+αmzc+

βmzcti （3）

則所有乘務交路的總費用為：

minZ= （4）

式中n—乘務交路總數；

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

3 優化目標和約束條件

3.1 優化目標

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

3.2 約束條件

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

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

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

4 模型的建立

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

minZ= （5）

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

式中 n—乘務交路總數；

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

P—值乘區段的數量

—可行交路i的總費用

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

式（6）表示每一值乘區段至少屬于一個乘務交路。

5 算法設計

該文蟻群算法的關鍵參數和主要操作如下。

5.1 解構建圖的表示

解的構建圖由所有值乘區段的結點和若干個原點組成，原點是虛擬的共同點，作為乘務交路的起點和終點，被復制為乘務交路的數目。

5.2 解的構建

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

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

1）信息素的表示

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

2）信息素的初始化

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

τij（0）= （7）

τi（0）= （8）

3）信息素更新原則

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

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

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

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

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

△τij= （11）

△τi= （12）

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

5.4 選擇策略

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

= （13）

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

ηij= （14）

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

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

=（15）

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

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

ηi= （16）

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

6 算例分析

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

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

7 結語

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

參考文獻

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

[2] 陳華群.動車組運用計劃編制系統相關問題研究[D].西南交通大學碩士學位文，2007.

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

2）信息素的初始化

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

τij（0）= （7）

τi（0）= （8）

3）信息素更新原則

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

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

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

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

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

△τij= （11）

△τi= （12）

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

5.4 選擇策略

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

= （13）

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

ηij= （14）

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

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

=（15）

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

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

ηi= （16）

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

6 算例分析

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

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

7 結語

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

參考文獻

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

[2] 陳華群.動車組運用計劃編制系統相關問題研究[D].西南交通大學碩士學位文，2007.

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

2）信息素的初始化

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

τij（0）= （7）

τi（0）= （8）

3）信息素更新原則

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

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

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

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

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

△τij= （11）

△τi= （12）

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

5.4 選擇策略

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

= （13）

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

ηij= （14）

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

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

=（15）

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

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

ηi= （16）

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

6 算例分析

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

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

7 結語

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

參考文獻

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

[2] 陳華群.動車組運用計劃編制系統相關問題研究[D].西南交通大學碩士學位文，2007.

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