城際鐵路列車停站方案的遺傳算法求解

高明瑤，石紅國

（西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 611756)

0 引言

城際鐵路是服務(wù)于相鄰城市間旅客的鐵路。近年來，我國城市群快速發(fā)展，相鄰城市間的人員交流增多，城際鐵路成為相鄰城市間旅客出行的重要交通方式。相比普速鐵路，我國的城際鐵路在服務(wù)質(zhì)量與服務(wù)水平方面提升較大，但仍然面臨城際高速公路客運(yùn)的強(qiáng)有力競爭。優(yōu)化城際鐵路列車停站方案可以提升城際鐵路列車的競爭力，提升城際鐵路在相鄰城市間客運(yùn)市場的客流分擔(dān)率。

國內(nèi)外學(xué)者對列車開行方案問題進(jìn)行了大量研究。史峰等[1]從鐵路運(yùn)輸企業(yè)和旅客利益出發(fā)，研究客運(yùn)專線旅客列車開行方案的多目標(biāo)優(yōu)化模型及求解方法。張旭等[2]以丹大城際鐵路為背景，以運(yùn)營收益最大、旅客候車時間最小和列車空費(fèi)能力最小為目標(biāo)函數(shù)，采用遺傳算法求解。牛豐等[3]分析長途客流輸送的直達(dá)模式和中轉(zhuǎn)換乘模式，綜合分析不同列車種類的直達(dá)模式，提出中轉(zhuǎn)換乘模式客流輸送方案的優(yōu)化方法。曹志超等[4]基于越行站滯留旅客數(shù)量，提出列車停站方案的雙目標(biāo)非線性混合整數(shù)規(guī)劃模型，采用禁忌搜索算法求解。牛豐等[5]構(gòu)建不確定客流條件下高速鐵路列車停站方案設(shè)計(jì)的機(jī)會約束規(guī)劃模型，采用Gurobi 求得最優(yōu)列車停站方案。劉璐等[6]針對高速鐵路旅客出行時空敏感性較高的特點(diǎn)，構(gòu)建三維時空狀態(tài)網(wǎng)絡(luò)，建立基于旅客出行需求的停站方案與列車運(yùn)行圖綜合優(yōu)化0-1 整數(shù)規(guī)劃模型，并設(shè)計(jì)拉格朗日松弛算法求解。閆海峰等[7]考慮高速鐵路列車客流需求與技術(shù)條件，以列車運(yùn)行線占用時間最少為目標(biāo)，建立非線性0-1 規(guī)劃模型，采用Lingo 求解。唐祿林等[8]針對快慢車的越行特點(diǎn)，分析城市軌道交通乘客出行時間和企業(yè)運(yùn)營成本，構(gòu)建城市軌道交通快慢車模式下的停站優(yōu)化模型，采用遺傳算法求解。

針對城際鐵路列車停站方案問題，以鐵路企業(yè)運(yùn)營收益最大和旅客出行成本最小為目標(biāo)函數(shù)，以車站服務(wù)頻率、設(shè)備能力、列車停站次數(shù)等作為約束條件，建立城際鐵路列車停站方案的多目標(biāo)混合整數(shù)規(guī)劃模型，設(shè)計(jì)基于理想點(diǎn)法的城際鐵路列車停站方案遺傳算法，求解鐵路企業(yè)收益與旅客出行成本相對符合預(yù)期的城際鐵路列車停站方案。

1 城際鐵路列車停站方案優(yōu)化模型

1.1 模型假設(shè)

常見的城際鐵路列車停站模式有“大站?！薄皳裾就！薄罢菊就！? 種。在設(shè)計(jì)停站方案時，應(yīng)實(shí)現(xiàn)多種停站方式相互配合與協(xié)調(diào)，形成最優(yōu)的停站方案。借鑒史峰等[1]的思路，對城際鐵路列車停站方案問題作出以下基本假設(shè)。

（1）列車運(yùn)行方向假設(shè)。城際鐵路列車的停站方案對應(yīng)某一特定的列車運(yùn)行方向。為方便闡述，選擇下行方向?yàn)檠芯糠较?，假設(shè)不考慮運(yùn)行方向?qū)Σ煌Ｕ绢愋土熊嚨挠绊憽?/p>

（2）封閉性假設(shè)。在制訂停站方案時，只考慮本線客流，不考慮跨線和換乘客流。

（3）確定性假設(shè)。在編制停站方案時，假設(shè)列車的起訖點(diǎn)、運(yùn)行徑路、編組等已經(jīng)確定。

1.2 符號說明

設(shè)Q= {B，Z，A}表示3種列車停站模式的集合，其中B為“大站停”模式，Z為“擇站?！蹦Ｊ?，A為“站站?！蹦Ｊ健ＴO(shè)W為上述3 中停站模式中的1 種，有W∈Ω，該種模式的城際鐵路列車1 次停站成本為SW，單位距離運(yùn)行成本為RW，單位運(yùn)價率為pW，按該模式停站的列車數(shù)量為N W。M為車站集，i，j為車站，i，j∈M。dij為車站i到車站j的距離，D為城際鐵路線路起訖車站之間的距離。為在車站i與車站j之間，選擇停站模式W列車的客流量。為乘坐W模式的列車k，在車站i上車，去往車站j的旅客數(shù)量。表示停站模式為W的列車在車站h的停留時間。決策變量= 1表示停站模式為W的列車k在車站h停站，= 0表示停站模式為W的列車k在車站h不停站。

1.3 目標(biāo)函數(shù)

停站方案優(yōu)化目標(biāo)為最大化城際鐵路總運(yùn)營收益和旅客總出行時間最小。

（1）最大化城際鐵路總運(yùn)營收益為

式中：f1為城際鐵路總運(yùn)營收益；IW為停站模式W的列車總客票收入；C1W為總停站成本；C2W為總運(yùn)行成本。

綜上，最大化城際鐵路總運(yùn)營收益為

（2）最小化旅客總出行時間。對于城際鐵路列車，起訖點(diǎn)固定后，同一OD 間旅客的出行時間只與列車的總停站時間有關(guān)，因而將旅客總出行時間最少的目標(biāo)轉(zhuǎn)化為總停站時間最少的目標(biāo)，即

式中：f2為總停站時間。

1.4 約束條件

（1）車站的服務(wù)頻率約束。車站有一定的服務(wù)頻率要求，在某車站停站的列車數(shù)不能低于給定的下限，即

式中：nh為車站h停站的最少列車數(shù)。

（2）車站設(shè)備能力的約束為

式中：eh為在車站h停站的最大列車數(shù)。

（3）列車停站次數(shù)的約束為

式中：l W為W模式列車的最少停站次數(shù)；gW為W模式列車的最大停站次數(shù)。

（4）客流條件約束。從車站i出發(fā)的W模式所有列車能夠運(yùn)輸?shù)目偮每蛿?shù)不小于車站i到車站j的W模式列車的客流量，即

（5）變量取值范圍的約束?？紤]到所有列車在起訖點(diǎn)車站必須停車，因而的取值為

2 城際鐵路列車停站方案的遺傳算法

2.1 多目標(biāo)轉(zhuǎn)化為單目標(biāo)的理想點(diǎn)法

采用理想點(diǎn)法將上述多目標(biāo)混合整數(shù)規(guī)劃模型轉(zhuǎn)化為單目標(biāo)模型。以多目標(biāo)fi在上述模型中輸出的最優(yōu)值為分量，生成向量= (f1*，…，fn*)，由于所研究問題是一個多目標(biāo)問題，考慮采用歐幾里得距離評價法將多目標(biāo)轉(zhuǎn)換為單目標(biāo)問題。構(gòu)建以下評價函數(shù)

公式 ⒀ 表示各個可行方案到最優(yōu)方案的歐幾里得距離，該距離直觀上表現(xiàn)為任一方案較最優(yōu)方案更劣的程度，方案的該距離越小，則表示該方案更優(yōu)。原模型轉(zhuǎn)化后的單目標(biāo)優(yōu)化模型為

2.2 城際鐵路列車停站方案遺傳算法

城際鐵路列車停站方案優(yōu)化問題是大規(guī)模組合優(yōu)化問題，鑒于上述混合整數(shù)規(guī)劃模型的計(jì)算復(fù)雜度，采用遺傳算法求解轉(zhuǎn)化后的單目標(biāo)模型。遺傳算法流程如圖1 所示。

遺傳算法的具體求解步驟如下。

步驟1：編碼及初始種群生成。城際鐵路列車線路上的每1 列車都用1 個染色體表示，染色體的數(shù)量即為城際鐵路列車的數(shù)量，每個基因位都與線路上每1 車站相對應(yīng)，染色體長度即為車站數(shù)量，基因位i取值為0 表示列車在第i站不停站，取值為1 表示列車在第i站停站。隨機(jī)生成初始種群。設(shè)置迭代次數(shù)t= 0。

步驟2：解碼及染色體有效性檢驗(yàn)與修正。在生成初始種群和遺傳進(jìn)化過程中，可能產(chǎn)生不滿足上述約束條件的無效染色體，此時，該無效染色體由步驟1 中生成的染色體種群中1 個新的染色體替換，按初始種群的形成機(jī)制重新隨機(jī)生成。

步驟3：計(jì)算適應(yīng)度函數(shù)。選取公式⒁中的單目標(biāo)函數(shù)為適應(yīng)度函數(shù)，適應(yīng)度函數(shù)取值越小，表示方案越好，即個體適應(yīng)度越好，則該個體被選擇復(fù)制進(jìn)下一代的概率越大。

圖1 遺傳算法流程Fig.1 Process of the genetic algorithm

步驟4：新種群生成。①遺傳算子。選擇算子采用排序選擇策略，將群體中的個體按照個體適應(yīng)度值升序排列并均分成10 組，最后1 組的個體用第1 組的個體替代，保證每代進(jìn)化過程中適應(yīng)度好的個體被復(fù)制到新的種群中去，且種群規(guī)模不變。②交叉算子。采用兩點(diǎn)交叉的方法，將種群中的個體隨機(jī)兩兩匹配，再按照均勻分布隨機(jī)參數(shù)交叉位置，以概率pc交換兩點(diǎn)之間的基因值并產(chǎn)生新的個體。兩點(diǎn)交叉操作如圖2 所示。③變異算子。采用單點(diǎn)變異的方法，按均勻分布隨機(jī)產(chǎn)生變異點(diǎn)位置，以概率pm對基因值進(jìn)行變異操作產(chǎn)生新的種群。單點(diǎn)變異操作如圖3 所示。

圖2 兩點(diǎn)交叉操作Fig.2 Two-point Crossover

圖3 單點(diǎn)變異操作Fig.3 One-point Mutation

步驟5：迭代次數(shù)t=t+ 1，判斷程序終止條件。如果達(dá)到最大迭代次數(shù)則終止程序，否則返回步驟2。

3 算例分析

3.1 問題生成

隨機(jī)生成6 個城際鐵路車站，各個站間客流OD 量在[0，500]間隨機(jī)生成，得到城際鐵路站間下行方向客流OD 分布如表1 所示。

表1 城際鐵路站間下行方向客流OD 分布 人Tab.1 OD distribution of down direction between stations

假設(shè)所有的客流OD 量中，有30%的乘客選擇“大站停”列車，30%的乘客選擇“擇站停”列車，剩余40%的乘客選擇“站站停”列車。根據(jù)該比例以及表1 所示的客流OD 分布，可得到乘坐各種停站模式列車的OD 間客流量。

各個車站的站間距如表2所示。根據(jù)實(shí)際情況，設(shè)車站服務(wù)頻率不小于3 列，車站設(shè)備能力不大于20 列。

表2 各個車站的站間距 kmTab.2 Distance between stations

3.2 問題求解

設(shè)置遺傳算法的相關(guān)參數(shù)。其中，種群規(guī)模為20，交叉概率為0.8，變異概率為0.1，最大迭代次數(shù)為100，利用遺傳算法求解，得到城際鐵路列車停站方案如表3 所示。停站方案中，“大站停”列車共?？? 站，“擇站?！绷熊嚬餐？? 站，“站站?！绷熊嚬餐？?4 站，停站方案共6 種。

表3 城際鐵路列車停站方案Tab.3 Intercity train stop scheme

4 結(jié)束語

由于列車停站方案優(yōu)化問題的復(fù)雜性，需要考慮經(jīng)濟(jì)社會等多方面因素，很多問題尚待深入研究。由于城際鐵路中部分車站等級較高，應(yīng)優(yōu)先考慮大站停列車停站方案。另外，除了以最大化鐵路部門運(yùn)營收益和最小化旅客出行時間為目標(biāo)函數(shù)外，還可以將最大化列車滿載率作為目標(biāo)函數(shù)，充分利用列車運(yùn)能，減少能力虛靡。