裴金漪

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州730070）

1 模型建立

1.1 符號定義

設(shè)客運(yùn)專線網(wǎng)路G＝｛S，E，C｝，其中S為車站集合，S中有N個車站。物理路網(wǎng)邊集合E＝｛emn｜m，n∈S｝，每條物理路網(wǎng)邊的實(shí)際通過能力C＝｛cmn｜m，n∈E｝。車站m和n之間運(yùn)行線的開行方案可以表示為lmn＝｛ρmn，μmn，vmn，fmn｝，其中ρmn為該運(yùn)行線的停站方案，μmn為旅客列車類型，vmn為旅客列車的開行速度，fmn∈N為開行頻率。因此，關(guān)于客運(yùn)專線網(wǎng)路G的開行方案可以表示成為L＝｛lmn｜m，n∈S｝。

設(shè)車站m，n之間的可能運(yùn)行線路為εk∈ρmn，其中ρmn為m，n之間可能運(yùn)行線的條數(shù)。為了便于分析討論，假設(shè)乘客全部偏向于選擇最近的道路出行。在此基礎(chǔ)上所有的開行方案都應(yīng)盡量滿足任意m，n間的旅客出行需求，即沒有換乘的情況。采用Dijstra算法在已知客運(yùn)專線網(wǎng)路G上搜尋m，n之間的最短開行路線，將εmn∈ρmn作為m，n之間的開行線。因此，lmn＝｛εmn，μmn，vmn，fmn｝可以用來表示經(jīng)過Dijstra算法搜索后的開行方案。

設(shè)m，n之間開行列車的動車組數(shù)和車廂的編成量數(shù)分別為K1，mn和K2，mn。Amn為車廂定員，每節(jié)車動車組或機(jī)車的固定和變動費(fèi)用為U1，mn和U2，mn，每節(jié)車廂的固定和變動費(fèi)用為C1，mn和C2，mn。設(shè)每條運(yùn)行線所需車底數(shù)為＾nmn＝（fmn＾tmn／T），其中＾tmn為運(yùn)行線lmn的估計(jì)周轉(zhuǎn)時間，T為路網(wǎng)G的運(yùn)行周期。

圖1 支配解和Pareto邊界

設(shè)nodesmn為運(yùn)行線lmn上的停站數(shù)目，tmn為停站時間，?tmn為等待時間，停站時間、等待時間和運(yùn)價率與開行速度和旅客列車類型相關(guān)。當(dāng)該運(yùn)行線上的列車類型和開行速度確定后，nodesmn，tmn和?tmn皆為常量。

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

根據(jù)以上的符號定義，極小化鐵路部門運(yùn)營總成本可表示為

式中:dmn為m，n間的開行距離。

極小化系統(tǒng)的旅客票價總成本為

式中:Flowmn為實(shí)際客流量，Pmn為該運(yùn)行線上的運(yùn)價率。

極小化旅客旅行總時間為

為了讓算法得到更好的收斂性值，我們對目標(biāo)函數(shù)進(jìn)行標(biāo)準(zhǔn)化，則有公式

式中:k＝1，2，3；Scalek＝max（Zkj）N（N－1），為目標(biāo)函數(shù)的標(biāo)準(zhǔn)化參數(shù)。

1.3 約束條件

物理路網(wǎng)邊上的開行頻率之和小于該路網(wǎng)邊的實(shí)際通過能力

式中:xmn為決策變量，當(dāng)εmn通過物理路邊emn時，xmn＝1，否則為0。

車站m，n之間的開行方案滿足其間的客流量要求

另外，在實(shí)際情況中，一條運(yùn)行線只能開行一個頻率的列車。該約束條件在遺傳算法中會自動表達(dá)在”染色體”結(jié)構(gòu)中，因此，無需額外寫出。

2 NSGA－II算法的建立

2.1 Pareto邊界及非支配解

在NSGA－II算法中，將所有由非支配（Nondominated）點(diǎn)組成的曲線稱為Pareto邊界。在圖1中，對于點(diǎn)2來說，點(diǎn)3在兩個極小化目標(biāo)上均優(yōu)于點(diǎn)2，因此，點(diǎn)2被點(diǎn)3支配。Pareto邊界上的點(diǎn)由極小化鐵道公司總成本和極小化旅客旅行總成本構(gòu)成，是一種多目標(biāo)函數(shù)優(yōu)化問題，Pareto邊界上的點(diǎn)代表了在某一妥協(xié)方案（通過權(quán)重系數(shù)將多目標(biāo)優(yōu)化轉(zhuǎn)化為單目標(biāo)優(yōu)化）下的開行方案。也就是說如果得到了Pareto邊界，便得到了所有可能的“最優(yōu)解”。

2.2 Dijstra最短路徑算法

在進(jìn)行開行方案的設(shè)計(jì)之前，首先要確定任意兩個車站間的開行路線。假設(shè)所有旅客都選擇最短的路徑出行，采用Dijstra算法在已知路網(wǎng)G上搜尋任意兩車站所對應(yīng)的最短路徑，其具體做法為:

1）首先根據(jù)G確定車站之間的距離矩陣D，D為N×N的對稱矩陣，在D中將實(shí)際相連（即emn存在）的距離記為實(shí)際距離，將實(shí)際不直接相連的車站間距離記為正無窮（Infinity）；

2）利用Dijstra算法更新D中的值直到所有的站間距離d＝Infinity，當(dāng)找到了所有車站對的最短開行路徑后，ρmn也就能夠確定了。

2.3 遺傳算法設(shè)計(jì)

染色體采用二進(jìn)制編碼，分為開行頻率f和開行等級μ兩部分，分別采用二進(jìn)制編碼。對于開行頻率子串:每條運(yùn)行線對應(yīng)唯一的開行頻率，假設(shè)開行頻率取fi∈［0，F(xiàn)］，i＝1，2，3，…，N（N－1）。其中F∈N（F為自然數(shù)）表示開行頻率的上限，N為車站數(shù)。因此，為了表述每條運(yùn)行線開行頻率所需的二進(jìn)制數(shù)為Binf＝ln（F＋1）／ln（2）。開行頻率子串的長度可以表述為N（N－1）·Binf。對于開行等級字串，開行等級不僅對應(yīng)著開行列車類型μ，還包括開行速度v，停站時間t等信息。設(shè)一共有Nμ種列車類型，每種類型對應(yīng)的開行速度一共有Nv種（由于開行速度確定后停站時間、等待時間等信息也會自動確定，所以，只需要確定開行速度即可），因此，表述每條運(yùn)行線所需要的二進(jìn)制數(shù)為Binv＝ln（NμN(yùn)v＋1）／ln（2），開行等級子串的長度為N（N－1）·Binv，染色體的結(jié)構(gòu)如圖2所示。開行等級矩陣V中存儲著不同類型的列車開行速度、等待時間、停站時間等信息，當(dāng)染色體隨機(jī)生成后，可通過二進(jìn)制轉(zhuǎn)換成十進(jìn)制來檢索矩陣V中的信息，并將其換算成需要的列車信息。

圖2 染色體結(jié)構(gòu)示意圖

NSGA－II算法的具體流程如圖3所示，當(dāng)種群數(shù)量為P的染色體生成后，需要進(jìn)行交叉變異來生成新的數(shù)量為P的種群。交叉和變異均在每一運(yùn)行線染色體段上單獨(dú)進(jìn)行，交叉概率為80%，編譯概率取10%。將進(jìn)行過交叉變異的P個個體和原始的P個個體結(jié)合成種群數(shù)量為2P的種群Q，下一步需要確定2P個個體的非支配等級（Non－dominated level），以便于進(jìn)行非支配等級劃分。

非支配等級的確定可以通過下述方法確定:在種群Q中確定所有非支配個體，并將這些個體標(biāo)記為level 0；在剩下的所有個體中確定非支配個體，將其標(biāo)記為level 1；如此重復(fù)直到所有個體都含有l(wèi)evel標(biāo)記；如果某一個體不滿足約束條件，該個體的非支配等級levelk＝levelk＋levelmax＋1，其中l(wèi)evelk為該個體未進(jìn)行約束分析時的非支配等級。

當(dāng)Q中所有個體的非支配等級確定后，為使最后的解相對均勻地分布在所需要的Pareto邊界上，需要確定每一個非支配等級下個體的擁擠等級（Crowding distance）。設(shè)個體i－1，i和i＋1的非支配等級相同，為，且k＝i－1，i，i＋1為三個個體標(biāo)準(zhǔn)化后的目標(biāo)函數(shù)值，則個體i的擁擠距離為

利用非支配等級和擁擠距離可進(jìn)行選擇操作，選擇進(jìn)行下一代遺傳變異操作的個體。具體做法為:將Q中的所有個體按照非支配等級從低向高排列；選出非支配等級小于k的所有個體，且k應(yīng)滿足小于等級k的個體數(shù)都小于P，小于等級k＋1的個體數(shù)都大于P；計(jì)算非支配等級k中所有個體的擁擠距離，并按照從大到小排列；在Q中選出前P個個體作為新的親代個體。

圖3 NSGA－II算法流程示意圖

3 算例分析

為驗(yàn)證以上理論的正確性，構(gòu)建簡單的鐵路客運(yùn)專線路網(wǎng)模型，利用MATLAB進(jìn)行數(shù)值模擬、路網(wǎng)模型及相關(guān)數(shù)據(jù)參考。圖4為客運(yùn)專線路網(wǎng)示意圖，物理路網(wǎng)邊上的信息為站間距離和路邊實(shí)際運(yùn)行能力。旅客旅行總成本的加權(quán)因子β＝0.5，運(yùn)行周期T＝60min。遺傳算法的個體數(shù)P為300，運(yùn)行代數(shù)為50代。表1為運(yùn)用算法優(yōu)化后得到的最優(yōu)運(yùn)行線。

圖4 客運(yùn)專線路網(wǎng)模型

表1 開行路線表

圖5 第50代種群與初始種群分布

圖6 為第50代個體分布示意圖，從圖6中可以看到大部分個體已經(jīng)發(fā)生重合并且分布在大致三個區(qū)域（如虛線圓形區(qū)域所示）。暫且將這三個區(qū)域按照升序，稱為類別一，類別二和類別三（見表2，表3，表4）。分別在三種類別中挑選出非支配等級最低的個體作為代表來分析三類解的特點(diǎn)。

圖6 第50代種群分布類別示意圖

表2 類別一開行方案

表3 類別二開行方案

表4 類別三開行方案

表2～表4分別列出了三類開行方案，表5給出了三類解情況下目標(biāo)函數(shù)的對比值。通過分析所得數(shù)據(jù)可以發(fā)現(xiàn)一類解對應(yīng)的鐵路公司開行總成本最低，在一類解下B類、C類列車站的比重較大（15／28），這種情況下相應(yīng)的旅客出行票價成本和時間成本也較高，對旅客的出行帶來很大的不便。這類解可以運(yùn)用在客流量大、客運(yùn)壓力大的情況下，同時，鐵路公司運(yùn)營欠佳時也可以采用。第三類解的情況與之相反，鐵路公司收入最少，乘客的旅行成本最低，這種情況可以看作是乘客出行要求較高的情形，例如春運(yùn)期間需要最大限度地降低旅客出行成本的情況。相對于類別一和類別三，類別二屬于較為中和的方案，適用于一般、無特殊事件情況下的開行方案。

表5 三類解目標(biāo)函數(shù)值對照表

4 結(jié)束語

首先利用Dijstra最短路徑搜尋算法在已知客運(yùn)專線路網(wǎng)上搜尋最短開行路徑。然后在確定的開行線路上運(yùn)用NSGA－II多目標(biāo)優(yōu)化算法進(jìn)行開行方案的優(yōu)化。對開行方案的“染色體”編碼采用兩段式，并對其分別進(jìn)行了交叉操作和變易操作。最后，對得到的優(yōu)化結(jié)果進(jìn)行分類處理，并討論了三類解在實(shí)際問題中的意義。該方法并不能將Dijstra算法運(yùn)用在迭代循環(huán)中，實(shí)驗(yàn)證明這種嘗試是不收斂的，所以，本文并不能根據(jù)實(shí)際的開行結(jié)果選擇最短路徑。下一步的研究工作就是嘗試如何將選線方案與開行方案進(jìn)行聯(lián)合優(yōu)化，將Dijstra算法整合到迭代循環(huán)中。

［1］牛惠民，陳明明，張明輝.城市軌道交通列車開行方案的優(yōu) 化 理 論 及 方 法 ［J］.中 國 鐵 道 科 學(xué)，2011，32（4）:128－133.

［2］鄧連波，史峰.旅客列車開行方案評價指標(biāo)體系［J］.中國鐵道科學(xué)，2006，27（3）:106－110.

［3］Bussieck，M.R.，P.Kreuzer，and U.T.Zimmermann，Optimal lines for railway systems［J］.European Journal of Operational Research，1997，96（1）:54－63.

［4］Dijkstra，E.W.，A note on two problems in connexion with graphs［J］.Numerische mathematik，1959，1（1）:269－271.

［5］Deb，K.，et al.，A fast and elitist multiobjective genetic algorithm:NSGA－II［J］.Evolutionary Computation，IEEE Transactions on，2002，6（2）:182－197.

［6］李引珍，何瑞春，郭耀煌，等.多目標(biāo)網(wǎng)絡(luò)相異路徑的Pareto解及其遺傳算法［J］.系統(tǒng)工程學(xué)報(bào)，2008，28（3）:264－268.

［7］賈曉秋，關(guān)曉宇.客運(yùn)專線網(wǎng)絡(luò)列車開行方案模型與算法研究［J］.系統(tǒng)工程學(xué)報(bào)，2011，26（2）:216－221.

［8］曾瑋，王佟.基于列車時刻表的城際鐵路客流分配研究［J］.交通科技與經(jīng)濟(jì)，2014，16（2）:24－26.