考慮乘客出發(fā)時刻的城市軌道列車時刻表優(yōu)化

朱宇婷， 毛保華， 史芮嘉， 戎亞萍， 趙欣苗

（1.北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044；2.北京交通大學(xué) 城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100044）

列車開行方案作為城市軌道（以下簡稱城軌）交通運(yùn)營組織工作的重要組成部分，是協(xié)調(diào)各部門工作、保證客運(yùn)服務(wù)質(zhì)量和經(jīng)濟(jì)效益的前提與基礎(chǔ)。因此，如何制定合理的列車開行方案成為廣大專家學(xué)者的研究重點(diǎn)。

國內(nèi)外對城軌列車開行方案優(yōu)化問題展開許多研究。文獻(xiàn)［1］建立列車開行方案多目標(biāo)優(yōu)化模型，分步確定列車編組長度及各階段列車開行數(shù)量；文獻(xiàn)［2］建立基于彈性需求的多目標(biāo)雙層規(guī)劃模型，對不同時段內(nèi)的列車開行對數(shù)進(jìn)行優(yōu)化；文獻(xiàn)［3］以列車實(shí)載率最大為目標(biāo)，建立列車日班次運(yùn)行計(jì)劃的優(yōu)化模型；文獻(xiàn)［4］以各方式成本和外部成本最小為目標(biāo)，建立地鐵發(fā)車間隔的數(shù)學(xué)優(yōu)化模型；文獻(xiàn)［5］以乘客及運(yùn)輸企業(yè)成本最小為目標(biāo)，以乘客需求、列車追蹤間隔和可用車底數(shù)為約束，構(gòu)建城軌交通大小交路模式下的列車開行方案雙目標(biāo)規(guī)劃模型；文獻(xiàn)［6］對城軌列車運(yùn)行圖計(jì)算機(jī)編制方法進(jìn)行研究，并給出行車間隔、車底數(shù)量、運(yùn)行周期等重要參數(shù)的計(jì)算方法。但上述文獻(xiàn)多以小時OD客流量或小時斷面客流量為輸入條件，對客流需求的時變特征考慮不足，從而限制模型的優(yōu)化效果。

為進(jìn)一步提高城軌交通服務(wù)水平，一些研究將客流需求的時變特性納入開行方案優(yōu)化中。文獻(xiàn)［7］以詳細(xì)的客流到達(dá)分布為輸入條件，以乘客等待時間最小為目標(biāo)，建立城軌列車開行方案優(yōu)化模型，以優(yōu)化始發(fā)站列車發(fā)車時刻；文獻(xiàn)［8］在文獻(xiàn)［7］的基礎(chǔ)上，增加運(yùn)輸供給水平等約束條件，并給出更為通用的乘客感知等待時間計(jì)算方法；文獻(xiàn)［9］進(jìn)一步對模型進(jìn)行擴(kuò)展，將其運(yùn)用到跨站列車開行方案優(yōu)化上；文獻(xiàn)［10］以時變客流需求為輸入條件，構(gòu)建3個城軌列車開行方案優(yōu)化模型，即不考慮容量約束的非均衡開行方案優(yōu)化模型、考慮容量約束的非均衡開行方案優(yōu)化模型以及考慮容量約束的均衡開行方案優(yōu)化模型，并對3個模型的優(yōu)化效果進(jìn)行對比分析；文獻(xiàn)［11］在同時考慮列車及站臺容量約束的基礎(chǔ)上，建立考慮客流時變特性的列車發(fā)車時刻優(yōu)化模型；文獻(xiàn)［12］考慮列車運(yùn)行時間、停站時間等不確定性后，以乘客到達(dá)分布規(guī)律為輸入條件，建立城軌始發(fā)站列車發(fā)車時刻優(yōu)化模型。然而，上述文獻(xiàn)均假設(shè)乘客的到達(dá)分布已知且相對穩(wěn)定，現(xiàn)實(shí)中難以成立。文獻(xiàn)［13－15］表明，公共交通的開行方案將對乘客的出行選擇行為產(chǎn)生一定影響，尤其在高峰時期，受列車容量的限制，為在期望時刻到達(dá)目的地，乘客將根據(jù)列車開行方案及其他乘客的出行安排調(diào)整自身的出發(fā)時刻。

本文以上述研究成果為基礎(chǔ)，通過引入時空拓展網(wǎng)絡(luò)，將列車時刻表優(yōu)化問題轉(zhuǎn)化為弧容量設(shè)定問題，在充分考慮乘客出發(fā)時刻選擇行為的基礎(chǔ)上，構(gòu)建雙層優(yōu)化模型及相關(guān)求解算法，從而實(shí)現(xiàn)城軌交通時刻表的優(yōu)化。

1 問題描述及網(wǎng)絡(luò)結(jié)構(gòu)抽象

1.1 問題描述

某城軌線路共有n個車站，用N表示線路上的車站集合，NTr表示該線路上的換乘車站集合，有NTrN。所有列車由始發(fā)站1發(fā)車，經(jīng)由車站2，車站3，…，車站n－1等，最終抵達(dá)終點(diǎn)站n。

令（Ts，Te］表示城軌列車運(yùn)營時段。該時段內(nèi)有一定數(shù)量的列車由始發(fā)站發(fā)車，且有確定數(shù)量的乘客從起點(diǎn)oi（i∈｛1，2，…，n－1｝）出發(fā)，前往車站i乘坐城軌列車，并希望在期望時刻到達(dá)目標(biāo)車站j（j∈｛i＋1，i＋2，…，n｝）后前往終點(diǎn)dj。由于城軌線路部分車站為換乘車站，同時服務(wù)于一般到達(dá)客流和換乘客流，而這兩類客流的到達(dá)特性存在明顯差異，即一般到達(dá)客流的到達(dá)分布在時間上表現(xiàn)出一定的連續(xù)性，而換乘客流則隨列車的到達(dá)呈現(xiàn)脈沖式的到達(dá)規(guī)律。為更好地考慮兩類客流的出行特性，進(jìn)一步將乘客起點(diǎn)oi分為兩類，即一般出行起點(diǎn)oi，1和換乘出行起點(diǎn)oi，2。顯然，當(dāng)且僅當(dāng)i∈NTr時，換乘出行起點(diǎn)oi，2才存在客流需求。令O、D 分別表示乘客出行起、終點(diǎn)集合，OUntr表示一般出行起點(diǎn)集合，OTr表示換乘出行起點(diǎn)集合，有oi，1∈OUntrO，oi，2∈OTrO，di∈D。同時，為便于建模，將各OD對間的乘客按目標(biāo)車站的期望到達(dá)時刻進(jìn)行分組，令g為乘客分組號索引。城軌線路及乘客起訖點(diǎn)示意圖，見圖1。

圖1 城軌線路及乘客起訖點(diǎn)示意圖

1.2 網(wǎng)絡(luò)結(jié)構(gòu)抽象

乘客的出行過程不僅具有空間屬性，還具有時間屬性。為更清晰地描述乘客出行過程，對乘客起訖點(diǎn)及車站節(jié)點(diǎn)進(jìn)行時間拓展，構(gòu)建時空拓展網(wǎng)絡(luò)，見圖2。

定義時空拓展網(wǎng)絡(luò)G＝（V，E）。V為節(jié)點(diǎn)集合，包含出行起點(diǎn)集合i∈N，m∈［1，2］，t∈（Ts，Te］｝、出行終點(diǎn)集合i∈N，t∈（Ts，Te］｝以及虛擬站點(diǎn)集合Te］｝。式中：和分別為t時刻的出行起點(diǎn)oi，m、出行終點(diǎn)di以及城軌交通車站i；E 為弧集合，包含列車運(yùn)行弧、乘客走行 弧 Ewalk＝∈ O′，it′∈ N′｝∪及乘客等待弧Ewait＝乘客通過?。╥，j）∈E 的費(fèi)用為ci，j。

基于建立的時空拓展網(wǎng)絡(luò)，列車時刻表優(yōu)化問題可等價(jià)為運(yùn)行弧的容量設(shè)定問題，即當(dāng)t時刻有列車自始發(fā)站發(fā)車時，將所有與該次列車相關(guān)的運(yùn)行弧的容量設(shè)為列車容量，反之，設(shè)為0。

基本假設(shè)為：

假設(shè)1 乘客嚴(yán)格按照“先到先服務(wù)”的原則排隊(duì)乘車；

假設(shè)2 列車載客能力相同，且運(yùn)行過程中不允許出現(xiàn)在車人數(shù)大于列車最大載客能力的情況，即當(dāng)在車人數(shù)達(dá)到列車最大容量時，車站剩余乘客將無法搭乘該次列車，而需排隊(duì)等待下次列車；

圖2 時空拓展網(wǎng)絡(luò)示意圖

根據(jù)假設(shè)2，同一OD對且具有相同出發(fā)時刻的乘客在圖2所示的時空拓展網(wǎng)絡(luò)圖中也可能分配到不同 的 出 行 路 徑 上 。 令表示在t時刻出發(fā)的OD對od 間第g 組乘客的人數(shù)；表示t時刻出發(fā)的OD對od間第g組乘客的出行路徑集合，有k∈

假設(shè)3 不考慮乘客走行時間。

2 列車時刻表雙層優(yōu)化模型

城軌運(yùn)營組織涉及需求明顯不同而又相互影響的兩類決策者，即供給方（運(yùn)營決策部門）及需求方（乘客）。運(yùn)營決策部門需要根據(jù)乘客的出行需求制定相應(yīng)的列車時刻表，最大限度地降低系統(tǒng)總費(fèi)用；而乘客則根據(jù)列車時刻表對出發(fā)時刻進(jìn)行調(diào)整，最大限度地降低出行成本。因此，為更加清晰地描述供需雙方的相互作用，采用雙層優(yōu)化模型［16］進(jìn)行建模。

2.1 上層模型

上層模型以供需雙方的綜合費(fèi)用最小為優(yōu)化目標(biāo)，即追求運(yùn)營總成本及乘客出行成本之和為最小。

（1）運(yùn)營成本

與列車時刻表相關(guān)的運(yùn)營成本主要包括車輛使用費(fèi)和車輛運(yùn)營費(fèi)。其中，車輛使用費(fèi)指車輛使用過程中產(chǎn)生的損耗費(fèi)、折舊費(fèi)等；車輛運(yùn)營費(fèi)指車輛運(yùn)營過程中產(chǎn)生的電費(fèi)、人工費(fèi)等。運(yùn)營總成本為［17］

式中：α為車輛單位運(yùn)營時間使用費(fèi)，近似等于車輛購置費(fèi)用與車輛使用時限的比值，元·（車輛·h）－1；β為車輛單位走行公里運(yùn)營費(fèi)，近似等于車輛運(yùn)營過程中產(chǎn)生的電費(fèi)、人工費(fèi)等與車輛走行公里的比值，元·（車輛·km）－1；b 為列車編組長度，輛；r1，n為車站1到車站n的列車運(yùn)行時間；L為城軌線路長度；xt為0－1決策變量，當(dāng)t時刻有列車從始發(fā)站發(fā)車時取值為1，否則取0。

一般而言，由于基本運(yùn)營條件（如線路坡度、曲線半徑、站間距等）不同，不同運(yùn)營線路的車輛使用費(fèi)用和車輛運(yùn)營費(fèi)存在差異。因此，進(jìn)行具體線路優(yōu)化時，根據(jù)實(shí)際情況，調(diào)研核定相關(guān)參數(shù)的取值。

（2）乘客出行成本

乘客出行成本主要包括城軌交通票價(jià)、候車時間換算費(fèi)用、乘車時間換算費(fèi)用、乘客的早到／晚到懲罰費(fèi)用以及早出發(fā)懲罰費(fèi)用。

候車時間換算費(fèi)用指乘客等車過程中感知到的出行費(fèi)用，在時空拓展網(wǎng)絡(luò)上表現(xiàn)為乘客經(jīng)過乘客等待弧產(chǎn)生的費(fèi)用為

式中：cit，it′為乘客通過乘客等待?。╥t，it′）∈Ewait產(chǎn)生的候車時間換算費(fèi)用，元；η1為乘客的候車時間價(jià)值，元／h；（t′－t）為乘客等待?。╥t，it′）的弧長。

乘車時間換算費(fèi)用是指乘客因乘車時間消耗而感知到的出行費(fèi)用，在時空拓展網(wǎng)絡(luò)上表現(xiàn)為乘客經(jīng)過列車運(yùn)行弧產(chǎn)生的費(fèi)用。列車實(shí)際運(yùn)行時間是影響乘車時間換算費(fèi)用最主要的因素，但文獻(xiàn)［18］認(rèn)為，車內(nèi)擁擠將造成乘客乘車時間的感知偏差，進(jìn)而影響乘車時間換算費(fèi)用的感知結(jié)果。因此，乘客通過運(yùn)行?。╥t，jt′）∈Erun的費(fèi)用為

式中為乘客通過?。╥t，jt′）產(chǎn)生的乘車時間換算費(fèi)用，元；η2為乘客的乘車時間價(jià)值，元／h；ri，j為車站i、j（i，j∈N）間的列車運(yùn)行時間；為運(yùn)行?。╥t，jt′）與t″時刻從始發(fā)站發(fā)車列車的關(guān)系，當(dāng)該次列車經(jīng)過?。╥t，jt′）時，令，否 則 為 0為 列 車運(yùn)行?。╥t，jt′）的擁擠系數(shù)，計(jì)算方法為［18］

式中：fit，jt′為弧（it，jt′）上通過的乘客人數(shù)，人；S1、S2分別為車輛座位數(shù)及額定載客人數(shù)，人／輛；γ1、γ2為擁擠費(fèi)用修正系數(shù)。

擁擠為乘客帶來的不僅是乘車時間感知的偏差，當(dāng)擁擠達(dá)到一定程度后，乘客將面臨因列車滿載而滯留等待下一次列車的情況。該過程在抽象網(wǎng)絡(luò)中可描述為乘客無法通過達(dá)到容量上限的列車運(yùn)行弧，而當(dāng)面臨該問題時，只能通過乘客等待弧轉(zhuǎn)至下1條列車運(yùn)行弧出行。

早到／晚到懲罰費(fèi)用指乘客在期望到達(dá)時刻以外的時刻到達(dá)目的地感知到的懲罰費(fèi)用［14］，即乘客實(shí)際到達(dá)時刻距期望到達(dá)時刻越遠(yuǎn)，感知到的懲罰費(fèi)用越高。因此

式中：pt（o，d，g）為 OD 對od 間第g 組乘客在t時刻到達(dá)目的地感知到的早到／晚到懲罰費(fèi)用，元；η3、η4分別為乘客早到和晚到的單位時間懲罰成本，元／h（g）為OD對od間第g組乘客的期望到達(dá)時刻。

早出發(fā)懲罰費(fèi)用指乘客在期望的最晚出發(fā)時刻之前出發(fā)產(chǎn)生的懲罰費(fèi)用，即乘客出發(fā)時刻越早，感知到的懲罰費(fèi)用越高，為［14］

式中為OD對od間第g組乘客在t時刻出發(fā)的早出發(fā)懲罰費(fèi)用，元；η5為乘客早出發(fā)產(chǎn)生的單位時間懲罰成本，元／h（g）為OD 對od間第g組乘客的最晚出發(fā)時刻，有（g）＝t＊od（g）－rod。

由于乘客的早到／晚到懲罰費(fèi)用及早出發(fā)懲罰費(fèi)用分別發(fā)生在乘客到達(dá)目的地及從起點(diǎn)出發(fā)的瞬間，即屬于節(jié)點(diǎn)費(fèi)用，為便于計(jì)算，將上述兩個懲罰費(fèi)用合并到乘客走行弧費(fèi)用中，則根據(jù)假設(shè)3，有OD對oi，mdj間第g組乘客通過走行弧的費(fèi)用為

式中和分別為乘客通過弧，it′）和（jt，）產(chǎn)生的懲罰費(fèi)用。

對于非換乘客流而言，任意t時刻出發(fā)的OD對od（o∈OUntr）間第g 組乘客的出行總成本C1t（o，d，g）為

式中：πko，d，g，t（）為t時刻出發(fā)的OD對od間第g組乘客通過路徑k的人數(shù)，人；υ為城軌交通票價(jià)，元。

對換乘客流，由于只能隨列車到達(dá)而到達(dá)。因此，無法選擇換出線路列車到達(dá)時刻以外的時刻出行，則任意t時刻出發(fā)的OD對od（o∈OTr）間第g組乘客的出行總成本C2t（o，d，g） 有

式中：Ttableo為o（o∈OTr）站乘客換出線路的列車到達(dá)時刻集合。

（3）建立上層模型

以運(yùn)營成本及乘客出行成本之和最小為目標(biāo)，建立上層優(yōu)化模型

式中：hmax、hmin分別為列車最大、最小發(fā)車間隔；HF為首班車最晚發(fā)車時刻；HL為末班車最早發(fā)車時刻；θ為車輛最大載客率。式（10）為乘客和運(yùn)營單位綜合費(fèi)用最?。皇剑?1）、式（12）為發(fā)車間隔上下限約束；式（13）、式（14）分別為首、末班車發(fā)車時間約束；式（15）為運(yùn)輸供給約束，即各區(qū)間運(yùn)營能力不得小于各區(qū)間出行需求；式（16）為0－1整數(shù)決策變量的邏輯約束。

2.2 下層模型

下層模型為考慮乘客出發(fā)時刻選擇的動態(tài)配流模型。軌道交通中，乘客總是希望選擇出行成本最小的出發(fā)時刻出行，然而隨著選擇某出發(fā)時刻的乘客數(shù)量增加，乘客滯留等待時間及出行擁擠程度增加，從而導(dǎo)致出行成本上升，進(jìn)而促使乘客重新選擇。因此，與道路交通均衡配流問題類似，城軌交通客流出發(fā)時刻選擇可以描述為相互反饋的動態(tài)平衡過程。根據(jù)Wardrop第一原理，平衡狀態(tài)描述為在所有可供選擇的出發(fā)時刻中，乘客選擇的所有出發(fā)時刻的出行費(fèi)用相等，且不大于未被選擇的出發(fā)時刻?；谖墨I(xiàn)［14－15］，建立下層模型目標(biāo)

式中：Y1為變量yt（o，d，g）（o∈OUntr）組成的向量；Y2為變量yt（o，d，g）（o∈OTr）組成的向量；C1（Y1）和C2（Y2）分別為向量Y1和Y2對應(yīng)的費(fèi)用向量；γ為向量Y1和Y2組成的集合，有

其中，qod（g）為OD對od 間第g組乘客包含的總?cè)藬?shù)。

同時，時間拓展網(wǎng)絡(luò)中各OD流量、路段流量以及路徑流量滿足以下約束條件

式中為弧與路徑的關(guān)聯(lián)變量，當(dāng)?。╥，j）在t時刻出發(fā)的OD對od間第g組乘客通過的路徑k上，則＝1；否則為0。

式（18）決定弧與路徑之間的相關(guān)關(guān)系；式（19）決定t時刻出發(fā)的OD對od間第g組乘客的人數(shù)，同時決定由換乘出行起點(diǎn)出發(fā)的乘客不能選擇換出線路列車到達(dá)時刻以外的時刻出行；式（20）為容量約束，保證各運(yùn)行弧的實(shí)際客流量不超過最大載客率；式（21）～式（23）為非負(fù)約束，保證不同時刻出發(fā)的客流量、所有路徑流量以及所有弧流量為非負(fù)值。

雖然本文建立的軌道交通網(wǎng)絡(luò)動態(tài)配流模型與道路交通網(wǎng)絡(luò)動態(tài)配流模型具有相同的建模思路，但兩者在具體配流過程中存在較大差異，主要表現(xiàn)在以下3個方面：

（1）載運(yùn)工具運(yùn)動規(guī)律不同。道路交通網(wǎng)絡(luò)中，載運(yùn)工具（小汽車）主要按照乘客出行意愿活動，其配流過程為將小汽車分配至各網(wǎng)絡(luò)路段上。軌道交通網(wǎng)絡(luò)中，載運(yùn)工具（列車）的運(yùn)動過程不以乘客的出行意愿為轉(zhuǎn)移，而是完全按照時刻表規(guī)律性運(yùn)動，配流過程為將乘客分配到不同的列車上，也可描述為將乘客分配到不同的列車運(yùn)行弧上；

（2）配流優(yōu)先次序不同。道路交通網(wǎng)絡(luò)中，出行者按照到達(dá)時間順序的先后具有不同的優(yōu)先權(quán)，而軌道交通網(wǎng)絡(luò)的配流優(yōu)先權(quán)不僅體現(xiàn)在時間層面上，更體現(xiàn)在空間層面上，即上游車站客流相較于下游車站享有更高的優(yōu)先權(quán)；

（3）擁擠產(chǎn)生的延誤效果不同。道路交通網(wǎng)絡(luò)中，擁擠主要引發(fā)路段運(yùn)行時間的延長；而軌道交通網(wǎng)絡(luò)中，擁擠不影響路段運(yùn)行時間，而影響乘客感知出行時間及因列車滿載產(chǎn)生的乘客滯留等待時間。

基于上述分析，建立客流分配原則：優(yōu)先分配上游車站客流；相同車站，優(yōu)先分配早出發(fā)客流；當(dāng)列車運(yùn)行弧達(dá)到容量上限時，該弧段將無法進(jìn)一步加載客流，車站剩余乘客將通過等待弧分配至下一條列車運(yùn)行弧。

模型可行解證明及詳細(xì)配流過程見文獻(xiàn)［14－15］。

3 求解算法

城軌列車時刻表優(yōu)化問題的求解規(guī)模極易膨脹，若采用傳統(tǒng)的最優(yōu)化算法，求解結(jié)果及收斂速度均難以達(dá)到應(yīng)用需求。遺傳算法以生物進(jìn)化為原型，具有良好的全局搜索能力和可并行性，能夠在指定時間范圍內(nèi)尋得最優(yōu)解。因此，本文采用遺傳算法對建立的模型進(jìn)行求解。

模型求解思路：對上層模型的決策變量進(jìn)行編碼，并作為已知條件輸入下層模型，通過MSA算法，計(jì)算乘客出發(fā)時刻集合，再將該集合作為輔助變量輸回上層模型，求得相應(yīng)的適應(yīng)度函數(shù)值，最終，經(jīng)過選擇、交叉和變異等操作，得到模型最優(yōu)解。

3.1 MSA算法計(jì)算過程

采用MSA算法對下層模型求解，具體步驟：

Step1 令Y［0］＝0，計(jì)算C（Y［0］），得到 OD 對od間第g組客流的初始出發(fā)時刻t＊［1］，令k＝1，賦值＝qodg（），得到向量Y［1］；

Step2 計(jì)算C（Y［k］）。重新選擇OD對內(nèi)各組客流的出發(fā)時刻t＊［k］，構(gòu)造附加向量；

Step3 收斂判斷。如果ε，則計(jì)算結(jié)束；否則，令Y［k＋1］＝k＝k＋1，返回Step2。

3.2 遺傳算法關(guān)鍵步驟設(shè)計(jì)

（1）染色體編碼及初始染色體生成

由于模型決策變量xt為0－1變量，因此，直接采用0－1二進(jìn)制編碼方式對染色體進(jìn)行編碼。同時，為簡化求解難度，對時間變量t進(jìn)行離散化處理，即將其轉(zhuǎn)化為（Te－Ts）／δ個離散的時間節(jié)點(diǎn)。其中，δ為離散時間間隔。則染色體可表示為（ω1，ω2，…，ωm，…，ω（Te－Ts）／δ）。其中，ωm為第m 個基因的決策結(jié)果，即“ωm＝1”表示第Ts＋mδ時刻列車發(fā)車，“ωm＝0”表示不發(fā)車。

另外，受約束（10）～約束（14）限制，可行解空間相對有限，隨機(jī)生成的解極易出現(xiàn)發(fā)車間隔過小或過大的情況，進(jìn)而大大降低有效初始種群的獲取速度。為防止該現(xiàn)象，提出初始染色體生成方法為

Step1 令θ1＝1，θ2＝（HF－Ts）／δ；

Step2 從第θ1至θ2個基因中隨機(jī)選擇某基因位置a，并將ωa賦值為1，第θ1至a－1個基因賦值為0；

Step3 若a＋hmin／δ＞（Te－Ts）／δ，則結(jié)束，否則轉(zhuǎn)Step4；

Step4 令

θ1＝a＋hmin／δ

θ2＝min｛a＋hmax／δ，（Te－Ts）／δ｝轉(zhuǎn)Step2。

（2）適應(yīng)度函數(shù)值確定

構(gòu)建的模型為最小化優(yōu)化。因此，在每次迭代運(yùn)算中，根據(jù)式（9）計(jì)算得出模型目標(biāo)值后，需要通過下式進(jìn)行轉(zhuǎn)化

式中：Evalν為染色體v的適應(yīng)度；為染色體v的目標(biāo)值為染色體種群規(guī)模。

由式（24）可以發(fā)現(xiàn)，模型目標(biāo)值越小，適應(yīng)度函數(shù)值越大，個體染色體質(zhì)量越優(yōu)。

（3）選擇操作

采用“輪盤賭”策略從父代染色體種群中選出子染色體。具體步驟為

Step1 令P0＝0，計(jì)算每個染色體v的累積選擇概率Pv，則

Step2 隨機(jī)生成實(shí)數(shù)a∈（0，1］，將其與累積選擇概率Pv進(jìn)行對比，選出第v個染色體（滿足Pv－1＜a≤Pv）加入子染色體種群。如此重復(fù)，直至選出pop＿size個子染色體。

（4）交叉操作

確定染色體交叉概率pc，從染色體種群中選擇2個染色體，隨機(jī)生成實(shí)數(shù)a∈（0，1］，若a≤pc，則再隨機(jī)生成1個整數(shù)d∈［1，（Te－Ts）／δ］，將2個染色體的第d至（Te－Ts）／δ個基因進(jìn)行對位互換，獲得2個新的子染色體。

（5）變異操作

確定染色體變異概率pm，選擇1個染色體，隨機(jī)生成實(shí)數(shù)a∈（0，1］；若a≤pm，則再隨機(jī)生成1個整數(shù)d∈［1，（Te－Ts）／δ］，令ωd＝1－ωd。由于受發(fā)車間隔的限制，染色體中值為0的基因個數(shù)遠(yuǎn)多于值為1的基因個數(shù)，若完全隨機(jī)的對變異基因進(jìn)行選擇，則變異基因從0變?yōu)?的概率將遠(yuǎn)大于從1變?yōu)?的概率，即變異方向?qū)⒁栽黾恿熊囬_行對數(shù)為主。為均衡變異方向，使得變異過程中，列車開行對數(shù)增加和減少的概率一致，提出變異基因的選擇方法為隨機(jī)產(chǎn)生實(shí)數(shù)a′∈（0，1］，若a′≤0.5，則從值為0的基因中隨機(jī)選擇1個基因；反之，從值為1的基因中隨機(jī)選擇1個基因。

3.3 算法步驟

Step1 初始化。設(shè)定種群規(guī)模、交叉概率、變異概率、最大進(jìn)化代數(shù)及MSA算法的收斂精度，生成初始種群，置進(jìn)化代數(shù)為0；

Step2 通過MSA算法推算各染色體對應(yīng)的乘客到達(dá)分布，并以此為基礎(chǔ)，計(jì)算染色體適應(yīng)度；

Step3 根據(jù)染色體適應(yīng)度及“輪盤賭”原則，以較大概率選出父代中具有高適應(yīng)度的染色體組成子代染色體種群；

Step4 根據(jù)交叉概率及交叉原則，按染色體編號依次選擇2個染色體進(jìn)行結(jié)合，以產(chǎn)生具備雙親特性的染色體后代；

Step5 根據(jù)變異概率及變異原則，對染色體實(shí)施變異，以產(chǎn)生新的染色體；

Step6 終止判斷。若達(dá)到最大進(jìn)化代數(shù)，計(jì)算結(jié)束，輸出最優(yōu)解，否則，進(jìn)化代數(shù)加1，轉(zhuǎn)Step2。

4 數(shù)值算例

4.1 參數(shù)輸入

選擇案例：線路全長33km，共包含7個車站，列車由始發(fā)車站1發(fā)車，經(jīng)由車站2、車站3、…、車站6，最終抵達(dá)終點(diǎn)站7，見圖3。設(shè)定車站4為換乘車站，換乘銜接線路在7：00～20：30間以10min為間隔向車站4運(yùn)送乘客。線路區(qū)間運(yùn)行時間相同，均為8 min。出行總需求為213 600人次，各OD詳細(xì)出行需求及期望到達(dá)時刻見表1。其中，車站4有50%的出行需求為換乘需求。要求首班車發(fā)車時間6：30，末班車發(fā)車時間21：00。取b＝6輛，S1＝42人／輛，S2＝245人／輛，α＝1元／（輛·min），β＝30元／（輛·km）［2］。根據(jù)文獻(xiàn)［19－20］，取η1＝45元／h，η2＝30元／h，η3＝10元／h，η4＝30元／h，η5＝6元／h。全程統(tǒng)一票價(jià)為2元。其他參數(shù)見表2。

圖3 算例線路圖

表1 乘客出行需求

表2 算例參數(shù)取值

4.2 求解結(jié)果

通過Matlab 2010b編程實(shí)現(xiàn)模型與算法的求解過程，參數(shù)取值：種群規(guī)模40、交叉概率0.9、變異概率0.2、最大進(jìn)化代數(shù)70、MSA 算法的收斂精度（ε）0.01。經(jīng)實(shí)驗(yàn)發(fā)現(xiàn)，在Intel（R）Celeron（R）CPU G1620＠2.70GHz，RAM 2.00GB的運(yùn)算環(huán)境，優(yōu)化算法耗時23.4h，能夠在43代后開始收斂，收斂過程見圖4。

圖4 遺傳算法收斂過程

圖5為優(yōu)化得到的列車時刻表。該時刻表共計(jì)安排138次列車。其中，首班車發(fā)車時刻6：30，末班車發(fā)車時刻21：00。同時，為展示MSA算法的收斂性，以最優(yōu)列車時刻表為例，給出算法收斂情況，見圖6。

圖5 最優(yōu)列車時刻表

圖6 最優(yōu)列車時刻表下的MSA算法收斂過程

為驗(yàn)證模型的優(yōu)越性，表3列出不同優(yōu)化方法得到的最優(yōu)列車開行列數(shù)（F）、企業(yè)運(yùn)營成本（z1）、乘客出行總成本（z2）及系統(tǒng)總成本（ZU＝z1＋z2）。最大斷面法對應(yīng)的最優(yōu)列車發(fā)車時刻表，在滿足基本約束（10）～約束（13）的基礎(chǔ)上，以“滿足小時最大斷面客流量”、“列車平均滿載率在［80%，90%］區(qū)間內(nèi)”為原則計(jì)算得到。單層優(yōu)化法是指不考慮列車時刻表對乘客出發(fā)時刻反饋的優(yōu)化方法，即假定乘客到達(dá)分布已知且穩(wěn)定，本文以最大斷面法算得的時刻表對應(yīng)的乘客到達(dá)分布為輸入進(jìn)行優(yōu)化。

表3 不同優(yōu)化方法的結(jié)果對比

從表3可以發(fā)現(xiàn)，優(yōu)化后的列車發(fā)車時刻表雖然在一定程度上增加運(yùn)營費(fèi)用（比最大斷面法高出21.1%），但有效降低乘客出行費(fèi)用（分別比最大斷面法和單層優(yōu)化法得到的乘客出行費(fèi)用降低7.6%和1.7%）及系統(tǒng)總費(fèi)用（分別降低3.6%和1.5%）。說明本文提出的優(yōu)化模型具有一定的優(yōu)越性。

本文優(yōu)化模型中，乘客期望到達(dá)時刻是影響列車時刻表的重要因素。因此，當(dāng)其他參數(shù)不變的前提下，對表1中以8：00為期望到達(dá)時刻的乘客進(jìn)行重新分組，以觀察不同乘客期望到達(dá)時刻分組下最優(yōu)開行方案及相關(guān)費(fèi)用的變化情況。表4和圖7給出具體分組情況及與之相對應(yīng)的最優(yōu)時刻表。考慮到重新分組后的乘客均分布在6：30～7：30從始發(fā)站出發(fā)的列車上，而其他期望到達(dá)時刻的乘客均分布在7：30之后出發(fā)的列車上，即兩者之間不存在相互影響。因此，表4和圖7僅對6：30～7：30出發(fā)的列車進(jìn)行討論，z1、z2和ZU也僅針對上述列車進(jìn)行統(tǒng)計(jì)。

對表4和圖7進(jìn)行分析，可以發(fā)現(xiàn)：

（1）乘客期望到達(dá)時刻對列車時刻表具有顯著影響，從圖7可以看出，不同情景下的最優(yōu)列車時刻表呈現(xiàn)出明顯的不同，說明精準(zhǔn)細(xì)致的客流調(diào)查是制定優(yōu)質(zhì)列車開行方案的基礎(chǔ)。

表4 不同期望到達(dá)時刻分組及其對應(yīng)的優(yōu)化結(jié)果

圖7 不同情景下的最優(yōu)時刻表及各次列車的滿載率情況

（2）隨乘客期望到達(dá)時刻離散化程度的提高（即由情景1的1組過渡到情景3的3組），列車超載與低載客現(xiàn)象減少，見圖7。情景1中列車滿載率大于100%的運(yùn)行區(qū)間數(shù)有11個，滿載率小于30%的運(yùn)行區(qū)間數(shù)有31個；情景2中列車滿載率大于100%的運(yùn)行區(qū)間數(shù)有6個，滿載率小于30%的運(yùn)行區(qū)間數(shù)有23個；情景3中列車滿載率大于100%的運(yùn)行區(qū)間數(shù)有5個，滿載率小于30%的運(yùn)行區(qū)間數(shù)有21個。

（3）綜合費(fèi)用、乘客出行總費(fèi)用及運(yùn)營費(fèi)用隨乘客期望到達(dá)時刻離散化程度的提高而下降，見表4。與情景1相比，情景2和情景3的綜合費(fèi)用分別下降7.9%和10.6%，乘客出行總費(fèi)用分別下降8.1%和11.4%，運(yùn)營費(fèi)用均下降7.1%。

5 結(jié)論

本文的主要工作及研究結(jié)論為：

（1）針對單條城軌線路，通過構(gòu)建時空拓展網(wǎng)絡(luò)，將列車開行方案優(yōu)化問題轉(zhuǎn)化為弧容量設(shè)定問題；在充分考慮乘客出發(fā)時刻選擇行為的基礎(chǔ)上，構(gòu)建城軌列車時刻表雙層優(yōu)化模型。上層以運(yùn)營單位及乘客綜合費(fèi)用最小為目標(biāo)，建立列車時刻表優(yōu)化模型；下層在考慮列車容量強(qiáng)約束的基礎(chǔ)上，建立考慮乘客出發(fā)時刻選擇的均衡配流模型。

（2）根據(jù)模型特點(diǎn)設(shè)計(jì)遺傳算法和MSA算法對上、下層模型進(jìn)行求解，并通過算例驗(yàn)證模型及算法的有效性。結(jié)果表明，遺傳算法和MSA算法均能快速收斂；且與最大斷面法和單層優(yōu)化法相比，本文模型具有一定的優(yōu)越性，優(yōu)化得到的時刻表能夠比較有效地降低乘客出行費(fèi)用、減少系統(tǒng)總費(fèi)用。相關(guān)部門在制定列車時刻表時，可以通過考慮列車時刻表與乘客出行需求之間的相互影響，合理預(yù)測不同時刻表下的乘客出發(fā)時刻分布規(guī)律，進(jìn)而達(dá)到提高服務(wù)水平、降低系統(tǒng)總費(fèi)用的目的。

（3）對乘客期望到達(dá)時刻進(jìn)行靈敏度分析，結(jié)果顯示，乘客期望到達(dá)時刻對列車時刻表具有顯著影響，說明精準(zhǔn)細(xì)致的客流調(diào)查是制定優(yōu)質(zhì)列車開行方案的基礎(chǔ)，相關(guān)部門在制定列車時刻表前，宜做好客流調(diào)查工作；隨乘客期望到達(dá)時刻離散化程度的提高，列車超載與低載客現(xiàn)象減少，綜合費(fèi)用、乘客出行總費(fèi)用及運(yùn)營費(fèi)用有所下降，說明在離散化乘客期望到達(dá)時刻（如錯峰上下班等）的同時，調(diào)整列車時刻表，將有助于提高乘客出行效率、降低企業(yè)運(yùn)營成本。

參考文獻(xiàn)：

［1］DENG L，ZENG Q，GAO W，et al.Optimization of Train Plan for Urban Rail Rransit in the Multi－routing Mode［J］.Journal of Modern Transportation，2011，19（4）：233－239.

［2］鄧連波，曾強(qiáng)，高偉，等.基于彈性需求的城市軌道交通列車開行方案研究［J］.鐵道學(xué)報(bào)，2012，34（12）：16－25.DENG Lianbo，ZENG Qiang，GAO Wei et al.Research on Train Plan of Urban Rail Transit with Elastic Demand［J］.Journal of the China Railway Society，2012，34（12）：16－25.

［3］孫焰，施其洲，趙源，等.城市軌道交通列車開行方案的確定［J］.同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，32（8）：1 005－1 008.SUN Yan，SHI Qizhou，ZHAO Yuan，et al.Method on Making Train Running－plan for Urban Railway Traffic［J］.Journal of Tongji University：Natural Science，2004，32（8）：1 005－1 008.

［4］GALLO M，MONTELLA B，D’ACIERNO L.The Transit Network Design Problem with Elastic Demand and Internalisation of External Costs：An Application to Rail Frequency Optimization ［J］.Transportation Research Part C：Emexging Technologies，2011，19（6）：1 276－1 305.

［5］王媛媛，倪少權(quán).城市軌道交通大小交路模式列車開行方案的優(yōu)化［J］.鐵道學(xué)報(bào)，2013，35（7）：1－8.WANG Yuanyuan，NI Shaoquan.Optimization of Train Schedules of Full－length ＆ Short－turn Operation Modes in Urban Rail Transit［J］.Journal of the China Railway Society，2013，35（7）：1－8.

［6］徐瑞華，江志彬，朱效潔，等.城市軌道交通列車運(yùn)行圖計(jì)算機(jī)編制的關(guān)鍵問題研究［J］.城市軌道交通研究，2005，8（5）：31－35.XU Ruihua，JIANG Zhibin，ZHU Xiaojie，et al.Key Problems in Computer Compilation of Train Diagram in UMT［J］.Urban Mass Transit，2005，8（5）：31－35.

［7］?；菝?，陳明明，張明輝.城市軌道交通列車開行方案的優(yōu)化理論及方法［J］.中國鐵道科學(xué)，2011，32（4）：128－133.NIU Huimin，CHEN Mingming，ZHANG Minghui.Optimization Theory and Method of Train Operation Scheme for Urban Rail Transit［J］.China Railway Science，2011，32（4）：128－133.

［8］NIU H，ZHOU X.Optimizing Urban Rail Timetable under Time－dependent Demand and Oversaturated Conditions［J］.Transportation Research Part C：Emerging Technologies，2013，36（11）：212－230.

［9］NIU H，ZHOU X，GAO R.Train Scheduling for Minimizing Passenger Waiting Time with Time－dependent Demand and Skip－stop Patterns：Nonlinear Integer Programming Models with Linear Constraints［J］.Transportation Research Part B：Methodological，2015，76（6）：117－135.

［10］SUN L，JIN J G，LEE D H，et al.Demand－driven Timetable Design for Metro Services［J］.Transportation Re－search Part C：Emerging Technologies，2014，46（9）：284－299.

［11］ZHU Y T，MAO B H，LIU L，et al.Timetable Design for Urban Rail Line with Capacity Constraints［J］.Discrete Dynamics in Nature and Society，2015：1－11.

［12］HASSANNAYEBIE，SAJEDINEJAD A，MARDANI S.Urban Rail Transit Planning Using a Two－stage Simulation－based Optimization Approach［J］.Simulation Modelling Practice and Theory，2014，49（11）：151－166.

［13］TIAN Q，HUANG H J，YANG H.Equilibrium Properties of the Morning Peak－period Commuting in a Many－toone Mass Transit System ［J］.Transportation Research Part B：Methodological，2007，41（6）：616－631.

［14］HAMDOUCHY，LAWPHONGPANICH S.Schedulebased Transit Assignment Model with Travel Strategies and Capacity Constraints［J］.Transportation Research Part B：Methodological，2008，42（7）：663－684.

［15］朱宇婷，毛保華，李明高，等.考慮列車容量的軌道交通客流分配模型［J］.交通運(yùn)輸系統(tǒng)工程與信息，2013，13（6）：134－139.ZHU Yuting，MAO Baohua，LI Minggao，et al.Railway Assignment Model with Vehicle Capacity Constraints［J］.Journal of Transportation Systems Engineering and Information Technology，2013，13（6）：134－139.

［16］YANG H，YAGAR S.Traffic Assignment and Signal Control in Saturated Road Networks［J］.Transportation Research Part A：Policy ＆ Practice，1995，29（2）：125－139.

［17］王永亮，張星臣，徐彬，等.城市軌道交通網(wǎng)絡(luò)化列車開行方案優(yōu)化方法［J］.中國鐵道科學(xué)，2012，33（5）：120－126.WANG Yongliang，ZHANG Xingcheng，XU Bin，et al.Optimization Method for the Network Train Operation Plan of Urban Rail Transit［J］.China Railway Science，2012，33（5）：120－126.

［18］SI B，ZHONG M，YANG X，et al.Urban Transit Assignment Model Based on Augmented Network with Invehicle Congestion and Transfer Congestion ［J］.Journal of Systems Science ＆ Systems Engineering，2011，20（2）：155－172.

［19］田瓊，黃海軍.高峰期出行動態(tài)均衡及其經(jīng)濟(jì)行為研究［M］.北京：科學(xué)出版社，2010：70.

［20］HAMDOUCH Y，HO H W，SUMALEE A，et al.Schedule－based Transit Assignment Model with Vehicle Capacity and Seat Availability［J］.Transportation Research Part B：Methodological，2011，45（10）：1 805－1 830.