基于遺傳算法的大小交路開行方案優(yōu)化模型研究

摘" 要：近年來，我國城市軌道交通快速發(fā)展，并成為城市公共交通的重要組成部分。城市軌道主要采用大小交路方案，即將軌道交通線路劃分為2條大小不同的交路，可以更好地應(yīng)對客流不均勻的情況，大小交路運營模式是我國城市軌道交通運用得最廣泛的運營管理方式，在面對龐大的客流量和復(fù)雜的車站數(shù)據(jù)時，需要將企業(yè)的運營成本盡可能最小化和乘客服務(wù)水平盡可能最大化，在此基礎(chǔ)上決定列車開行方案成為城市軌道交通運營的重要一環(huán)，故該文旨在解決大小交路模式下的列車開行方案問題。

關(guān)鍵詞：多目標(biāo)動態(tài)規(guī)劃；遺傳算法；列車時刻表優(yōu)化問題；大小交路；優(yōu)化模型

中圖分類號：U239.5" " " 文獻(xiàn)標(biāo)志碼：A" " " " " 文章編號：2095-2945（2023）31-0063-04

Abstract： In recent years， urban rail transit in China has developed rapidly and become an important part of urban public transport. The urban track mainly adopts the long amp; short routing scheme， that is， the rail transit line is divided into two intersections of different sizes， which can better deal with the uneven passenger flow. The operation mode of long amp; short routings is the most widely used mode of operation and management of urban rail transit in China. In the face of huge passenger flow and complex station data， it is necessary to minimize the operating cost of enterprises and maximize the level of passenger service as much as possible. On this basis， determining the train operation plan has become an important part of urban rail transit operation， so the purpose of this paper is to solve the problem of train operation plan under long amp; short routing mode.

Keywords： multi-objective dynamic programming; genetic algorithm; train schedule optimization; long amp; short routing; optimization model

在城市軌道交通系統(tǒng)中，合理的運行區(qū)間和開行數(shù)量對于提高運行效率和乘客出行體驗至關(guān)重要。為了盡可能減少企業(yè)運營成本和實現(xiàn)服務(wù)水平最大化，確定了大小交路運營模式，本文依據(jù)OD客流量、車站數(shù)據(jù)（包括車站能否作為折返站，車站之間的距離），以小交路區(qū)間劃分和大小交路開行數(shù)量為決策變量，以企業(yè)運營成本最小化和服務(wù)水平最大化為目標(biāo)函數(shù)，以大小交路比例約束、最小列車追蹤間隔、最大/小列車發(fā)車間隔、最大/小交路經(jīng)過車站數(shù)量和小交路起始點等作約束條件，建立列車開行方案優(yōu)化模型，并將目標(biāo)函數(shù)逐層剖析分解得到其數(shù)學(xué)表達(dá)式，而由于多目標(biāo)優(yōu)化模型難于求解，于是將2個目標(biāo)函數(shù)轉(zhuǎn)化為以成本為基本單位的單目標(biāo)優(yōu)化模型，并通過遺傳算法求出最優(yōu)解[1]。

1" 列車開行方案的影響因素分析

1.1" 乘客需求

一段時間內(nèi)在某區(qū)域的乘客出行需求即客流需求決定了交通的需求，交通的需求關(guān)系到交路劃分及行車數(shù)量[2]。OD客流量為起始點與目的地之間的客流量，在城市軌道交通系統(tǒng)中常使用斷面客流量和OD客流量描述一段時間內(nèi)某區(qū)域的客流需求，便于后續(xù)數(shù)學(xué)模型的建立。

1.2" 運營成本

城市軌道交通運行中列車運行過程需要消耗能源的成本、企業(yè)需在列車運營中設(shè)置人力的成本，企業(yè)購置列車等硬件設(shè)備的成本均為運營成本[3]，可見列車的數(shù)量和列車運行的總距離可直接影響企業(yè)的運營成本。

1.3" 軌道交通線路特點

實際生活中軌道交通并非所有車站都能作為小交路的起始站、車站間距與列車行駛距離成正比、在實際生活中會制定相應(yīng)的停車和發(fā)車間隔標(biāo)準(zhǔn)，限定了列車最小停站、發(fā)車時間和最大停站、發(fā)車時間，這些都作為軌道交通線路特點[4]。

2" 基于遺傳算法的大小交路優(yōu)化模型建立與求解

2.1" 模型假設(shè)

本文根據(jù)大小交路的運營模式特點，為簡化該模型的建立，故提出假設(shè)如下。

假設(shè)一：假設(shè)乘客均衡到達(dá)車站等候發(fā)車，無滯留在車站的乘客。

假設(shè)二：假設(shè)列車自身硬件條件相同，線路采用一條小交路的模式。

假設(shè)三：所有列車采用站站停的方式且只考慮單向車程問題。

假設(shè)四：所有乘客均選擇直達(dá)列車出現(xiàn)，不出現(xiàn)換乘情況。

假設(shè)五：列車在線路上勻速運行，速度為45 km/h，列車定員均為1 860人。

2.2" 符號說明

符號說明見表1。

2.3" 模板建立與求解

2.3.1" 目標(biāo)函數(shù)構(gòu)建

將乘客體驗度量化為乘客出行成本，因此本文以企業(yè)運營成本最小化和乘客出行成本最小化為目標(biāo)函數(shù)[5]。

1）乘客出行成本。乘客在車時間為

Z1=T1+T2+T3 。

本文考慮所有車輛在某個車站停留的總時間由乘客上下車所需時間構(gòu)成，故第i個車站上下車乘客總數(shù)及第i個車站經(jīng)過的車輛總數(shù)為

在第i個車站未下車的乘客數(shù)量為

故所有乘客停站總時間為

乘客列車純運行時間為所有乘客在列車行駛途中花費的總時間（不包括停站時間）

乘客上下車花費總時間為

乘客等待時間為

綜上所述，乘客出行成本目標(biāo)函數(shù)Z為

minZ=ω1·Z1+ω2·Z2，

式中：ω1為乘客在車時間成本；ω2為乘客在站候車時間成本，元/s。

2）企業(yè)運營成本。企業(yè)運營成本可分為固定運營成本和可變運營成本，固定運營成本為列車數(shù)，可變運營成本為列車行車總公里。

列車數(shù)為

F1=f1+f2

列車行車總公里為

綜上所述，企業(yè)運營成本目標(biāo)函數(shù)為

minF=θ1F1+θ2F2

式中：θ1為每列車投入的與行走公里無關(guān)的成本，元/列；θ2為列車每公里可變運營成本，元/km。

2.3.2" 約束條件構(gòu)建

1）為使大小交路列車等間隔發(fā)車，大小交路開行數(shù)比例必須為1∶m或者m∶1（m為正整數(shù)）

2）發(fā)車間隔時間約束為

式中：3 600表示1 h。

3）滿足客流需求約束為

4）車輛停站時間約束為

I2min≤ti≤I2max

式中："I2min為最短停車時間約束，I2max為最長停車時間約束。

5）小交路端點位置約束：1≤alt;b≤n。

6）小交路起始點約束：Ka=1，Kb=1。

將多目標(biāo)約束優(yōu)化模型轉(zhuǎn)化為單目標(biāo)優(yōu)化模型[6]。由于各優(yōu)化目標(biāo)均與成本有關(guān)，可將企業(yè)運營成本和乘客出行成本相加為總成本，進(jìn)而將多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)規(guī)劃

minG=Z+F=ω1·Z1+ω2·Z2+θ1F1+θ2F2

本文將權(quán)重系數(shù)設(shè)為

ω1=ω2=9.92，θ1=6000，θ2=142.14。

2.3.3" 算法求解

本文采用遺傳算法來求解該優(yōu)化問題的最優(yōu)解，算法步驟如下。

Input：OD客流需求，車站區(qū)間長度，最大（?。┌l(fā)車間隔，最大（?。┩？繒r間，小交路可經(jīng)過車站數(shù)。

Output：小交路區(qū)間[a，b]，大交路開行數(shù)量f1，小交路開行數(shù)量f2。

Step 1：初始化迭代次數(shù)ITERATION，交叉變異概率，初始種群數(shù)。

Step 2：生成初始種群，開始迭代第一次iteration=1。

Step 3：目標(biāo)函數(shù)計算，計算適應(yīng)度并進(jìn)行染色體選擇、交叉和變異。

Step 4：記錄全局最優(yōu)解，iteration=iteration+1。

Step 5：若iterationlt;ITERATION，則轉(zhuǎn)入Step 3，否則繼續(xù)。

Step 6：輸出結(jié)果。

3" 算例測試

為驗證模型和算法的有效性，本文以某城市軌道交通線路為例，選取該線路客流數(shù)據(jù)，對開行方案進(jìn)行優(yōu)化。使用開源數(shù)據(jù)集進(jìn)行測試。該算例線路全長40.168 km，共開設(shè)車站30座，線路區(qū)間長度（km）和該區(qū)間斷面客流量（人）、車站是否能作為折返站等數(shù)據(jù)見表2、3。

由表4、表5可看出當(dāng)開行數(shù)量不變，小交路區(qū)間擴(kuò)大時，乘客候車時間和在車時間減少，列車行車總公里在增加，即乘客出行成本降低，企業(yè)運營成本增加。權(quán)衡服務(wù)水平和企業(yè)運營成本，尋求二者的最佳平衡點，即可實現(xiàn)企業(yè)與乘客的雙贏[7]。

4" 結(jié)束語

本文通過建立基于遺傳算法的列車開行方案優(yōu)化模型，解決我國城市軌道交通規(guī)模不斷擴(kuò)大的情況下合理劃分小交路區(qū)間和大小交路列車開行方案，從而使企業(yè)成本和乘客出行成本最小化。

參考文獻(xiàn)：

[1] 安志龍，馬麗，崔虎，等.基于遺傳算法的城市軌道交通大小交路模式列車開行方案研究[J].河南科技，2022，41（18）：6-10.

[2] 魏博超.基于大小交路的城軌列車行車間隔優(yōu)化研究[D].蘭州：蘭州交通大學(xué)，2022.

[3] 張春田，戚建國，楊立興，等.基于不確定旅客需求的高速鐵路魯棒列車開行方案研究[J].交通運輸系統(tǒng)工程與信息，2022，22（1）：115-123.

[4] 宗會明，何舟，楊慶媛，等.基于SP方法的重慶居民軌道交通出行時間價值及影響因素分析[J].現(xiàn)代城市研究，2014（2）：115-120.

[5] 張海，呂苗苗，倪少權(quán).基于非均勻發(fā)車間隔的大小交路時刻表優(yōu)化模型[J].交通運輸系統(tǒng)工程與信息，2022，22（6）：224-233.

[6] 袁家偉.基于大小交路方案的城市軌道交通列車時刻表與車底運用計劃協(xié)同優(yōu)化研究[D].北京：北京交通大學(xué)，2021.

[7] 肖遠(yuǎn)芯.城市軌道交通列車運行策略多目標(biāo)優(yōu)化研究[D].成都：西南交通大學(xué)，2021.