基于最小費(fèi)用的高速鐵路值乘區(qū)段集合模型研究

閆冬

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

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

中途分類號(hào)：U292.8 文獻(xiàn)標(biāo)示碼：A 文章編號(hào)：1674-098X（2014）04（a）-0012-02

1 問(wèn)題的提出

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

2 運(yùn)用費(fèi)用分析

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

2.1 出、退勤費(fèi)用

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

2.2 值乘費(fèi)用

對(duì)某一乘務(wù)交路而言，動(dòng)車組司機(jī)擔(dān)當(dāng)該交路值乘任務(wù)的費(fèi)用與值乘時(shí)間成正比。若值乘時(shí)間為tzc，單位時(shí)間值乘費(fèi)用為mzc，則值乘費(fèi)用為mzctzc。

2.3 換乘費(fèi)用

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

2.4 便乘費(fèi)用

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

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

mwx+mbctbc （1）

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

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

mi=mb+mzctzc+kimhc+αmzc+

βmzctbc （2）

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

=mb+kimhc+αmzc+

βmzcti （3）

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

minZ= （4）

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

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

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

3.1 優(yōu)化目標(biāo)

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

3.2 約束條件

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

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

（3）動(dòng)車組司機(jī)一次連續(xù)作業(yè)時(shí)間滿足機(jī)車乘務(wù)員工作和休息時(shí)間標(biāo)準(zhǔn)。

4 模型的建立

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

minZ= （5）

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

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

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

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

—可行交路i的總費(fèi)用

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

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

5 算法設(shè)計(jì)

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

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

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

5.2 解的構(gòu)建

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

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

1）信息素的表示

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

2）信息素的初始化

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

τij（0）= （7）

τi（0）= （8）

3）信息素更新原則

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

τ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的目標(biāo)函數(shù)值，則△τij和△τi可由式（11）和（12）確定：

△τij= （11）

△τi= （12）

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

5.4 選擇策略

1）當(dāng)螞蟻r所處結(jié)點(diǎn)i并非原點(diǎn)時(shí)，選擇下一個(gè)值乘區(qū)段結(jié)點(diǎn)j的概率公式如下：

= （13）

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

ηij= （14）

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

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

=（15）

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

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

ηi= （16）

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

6 算例分析

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

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

7 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

2）信息素的初始化

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

τij（0）= （7）

τi（0）= （8）

3）信息素更新原則

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

τ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的目標(biāo)函數(shù)值，則△τij和△τi可由式（11）和（12）確定：

△τij= （11）

△τi= （12）

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

5.4 選擇策略

1）當(dāng)螞蟻r所處結(jié)點(diǎn)i并非原點(diǎn)時(shí)，選擇下一個(gè)值乘區(qū)段結(jié)點(diǎn)j的概率公式如下：

= （13）

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

ηij= （14）

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

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

=（15）

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

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

ηi= （16）

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

6 算例分析

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

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

7 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

2）信息素的初始化

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

τij（0）= （7）

τi（0）= （8）

3）信息素更新原則

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

τ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的目標(biāo)函數(shù)值，則△τij和△τi可由式（11）和（12）確定：

△τij= （11）

△τi= （12）

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

5.4 選擇策略

1）當(dāng)螞蟻r所處結(jié)點(diǎn)i并非原點(diǎn)時(shí)，選擇下一個(gè)值乘區(qū)段結(jié)點(diǎn)j的概率公式如下：

= （13）

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

ηij= （14）

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

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

=（15）

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

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

ηi= （16）

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

6 算例分析

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

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

7 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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