徐光明，史峰，羅湘，秦進(jìn)

(中南大學(xué)交通運(yùn)輸工程學(xué)院，長沙410075)

基于策略均衡分配的公交線網(wǎng)規(guī)劃優(yōu)化方法0

徐光明，史峰*，羅湘，秦進(jìn)

(中南大學(xué)交通運(yùn)輸工程學(xué)院，長沙410075)

本文將軌道交通旅客換乘網(wǎng)絡(luò)應(yīng)用于描述高峰時(shí)段的公交換乘網(wǎng)絡(luò)，并采用基于有效頻率的策略均衡客流分配方法對(duì)公交用戶出行選擇行為進(jìn)行均衡分析；綜合考慮乘客和公交公司兩方面的利益，建立公交線網(wǎng)規(guī)劃的雙層規(guī)劃模型；提出求解模型的模擬退火算法，設(shè)計(jì)了刪除線路、生成線路、替換線路、延伸線路、縮短線路、拼接線路和拆分線路等7種線路調(diào)整及頻率調(diào)整進(jìn)行鄰域搜索.算例分析表明，該模型與算法具有良好的優(yōu)化效果.

交通工程；策略均衡；雙層規(guī)劃；公交線網(wǎng)設(shè)計(jì)；模擬退火算法

1 引言

城市公共交通是居民的重要出行方式.良好的公交線網(wǎng)規(guī)劃能為城市居民提供安全、方便、舒適、經(jīng)濟(jì)和快捷的服務(wù)，緩解交通擁堵問題.公交線網(wǎng)規(guī)劃問題包含客流分配和公交線網(wǎng)規(guī)劃方案評(píng)價(jià)等問題，是一個(gè)復(fù)雜的組合優(yōu)化問題，且具有非線性和非凸的特點(diǎn).

對(duì)于公交線網(wǎng)優(yōu)化設(shè)計(jì)，于濱等[1，2]考慮以直達(dá)客流量、平均換乘次數(shù)及客流密度三者效益最大為目標(biāo)的公交線網(wǎng)優(yōu)化模型.韓印等[3]提出逐條預(yù)選與搜索、優(yōu)化成網(wǎng)的啟發(fā)式算法.郭志勇等[4]提出了基于田字形道路網(wǎng)絡(luò)結(jié)構(gòu)下“一路一線直行式”公交服務(wù)系統(tǒng)模式.莫一魁等[5]以換乘次數(shù)最少、單位長度運(yùn)送的客流量最大為目標(biāo)分別建立優(yōu)化模型.

客流分配的客觀真實(shí)直接影響著公交線網(wǎng)方案的評(píng)價(jià).乘客乘車選擇行為分析是公交線網(wǎng)規(guī)劃的基礎(chǔ)，其難點(diǎn)在于解決共線、能力約束及擁擠效應(yīng)等問題.在現(xiàn)有公交線網(wǎng)設(shè)計(jì)研究中，客流分配一般將OD需求簡(jiǎn)單分配在最短路或候選路徑上.于濱等[2]在公交線網(wǎng)優(yōu)化中，引入聯(lián)合發(fā)車頻率進(jìn)行客流分配，但是沒有考慮線路能力和擁擠效應(yīng).在客流分配研究方面，史峰等[6]設(shè)計(jì)的換乘網(wǎng)絡(luò)能夠同時(shí)表現(xiàn)線路能力限制和旅客的換乘行為. Cominetti、Cepeda等[7，8]指出乘客選擇已確定好的具有“吸引力”的公交線集中最先隨機(jī)到達(dá)的公交線出行，選擇公交線路的概率與發(fā)車頻率有關(guān).

本文采用策略均衡客流分配方法進(jìn)行公交線網(wǎng)規(guī)劃，考慮共線、能力約束和擁擠效應(yīng)，通過更加細(xì)致描述公交用戶需求出行選擇，使客流分配結(jié)果與現(xiàn)實(shí)結(jié)果基本一致，讓公交線網(wǎng)規(guī)劃更好地滿足公交用戶需求.基于公交換乘網(wǎng)絡(luò)，對(duì)公交用戶出行選擇行為進(jìn)行策略均衡分析；綜合考慮乘客和公交公司兩方面的利益，建立了公交線網(wǎng)規(guī)劃的雙層規(guī)劃模型；設(shè)計(jì)求解模型的模擬退火算法，并通過刪除線路、生成線路、替換線路、延伸線路、縮短線路、拼接線路和拆分線路等7種方法進(jìn)行線網(wǎng)鄰域搜索，同時(shí)匹配相應(yīng)的線路頻率調(diào)整.

2 換乘網(wǎng)絡(luò)設(shè)計(jì)

給定城市公共交通道路網(wǎng)絡(luò)(N0,A0)，其中N0為公交車站集，A0為道路路段集,路段a∈A0的里程為l(a).當(dāng)公交線網(wǎng)給定后，即給定公交線路集為G，公交線路g∈G公交車的平均行駛速度為vg.為便于考慮具有線路能力約束和擁擠效應(yīng)的乘客乘車選擇行為分析，構(gòu)造如下?lián)Q乘網(wǎng)絡(luò)：

一條公交線路對(duì)應(yīng)的換乘網(wǎng)絡(luò)記為(N,A)，如圖1（a）所示，其中N為節(jié)點(diǎn)集(N0?N)，A為弧段集(A0?A).節(jié)點(diǎn)集N=N0∪N1，虛線上的節(jié)點(diǎn)為公交站節(jié)點(diǎn)N0，其余節(jié)點(diǎn)為線路停站節(jié)點(diǎn)N1；一系列連續(xù)的線路停站節(jié)點(diǎn)集合構(gòu)成一條線路，相鄰的線路停站節(jié)點(diǎn)構(gòu)成乘車弧，線路停站節(jié)點(diǎn)和公交站節(jié)點(diǎn)由上下車弧連接，公交站節(jié)點(diǎn)間的虛線為換乘走行弧.圖1（b）為兩條公交線組成的換乘網(wǎng)絡(luò).

圖1 一條公交線路和兩條公交線路對(duì)應(yīng)的換乘網(wǎng)絡(luò)Fig.1 The transfernetworksofonebus lineand twobus lines

基于換乘網(wǎng)絡(luò)，弧段基本屬性有弧段的費(fèi)用ta(v)、能力ca及有效頻率fa(v).上車弧和乘車弧具有能力約束，等于線路的載客能力，其他弧段均無能力約束.由于乘客的等待候車過程只發(fā)生在上車弧，故上車弧有效頻率fa(v)≥0，其他弧段的有效頻率fa(v)=∞.Cepeda等[8]給出了有效頻率函數(shù)的具體表達(dá)式：

式中fa為弧段a的固有頻率；va為上車弧段流量；va'為通過上車弧后線路上的流量，明顯va'≥va；β為校準(zhǔn)參數(shù).

3 基于策略均衡的客流分配

策略思想[7,8]是指乘客在車站每次選擇具有吸引力的公交線路集到達(dá)目的地，使得所選擇的線路集的期望費(fèi)用最小，這樣的公交線路集稱為一個(gè)策略.如果乘客不能單方面改變自己的策略出行而減少其策略期望費(fèi)，這種狀態(tài)稱為策略均衡狀態(tài)[7,8].

假定乘客采用策略思想出行，則節(jié)點(diǎn)i處目的地為d∈D的所有客流采用多個(gè)策略si∈γi后達(dá)到策略均衡，其中γi為策略集合.圖2為任意節(jié)點(diǎn)i∈N處且目的地為d∈D的乘客在節(jié)點(diǎn)i的共線選擇問題.

圖2 任意節(jié)點(diǎn)i到目的地d的共線選擇問題Fig.2 Common-linesofnode from node i to d

記D為目的地節(jié)點(diǎn)集合，任意節(jié)點(diǎn)i≠d∈D的起始點(diǎn)到達(dá)終點(diǎn)d的OD需求為假定乘客完全掌握路網(wǎng)信息，通過弧段a且目的地車站為d的流量其中表示任意目的地的客流在所有弧段上的一種分配方案.采用策略si∈γi的乘客在節(jié)點(diǎn)i處選擇弧段a的概率為

乘客選擇策略si的期望出行費(fèi)用等于平均等待時(shí)間與期望弧段費(fèi)用之和

基于出行策略的概念，乘客在任意節(jié)點(diǎn)i處都希望通過選擇期望出行費(fèi)用最小的出行策略到達(dá)目的地.根據(jù)Wardrop第一原則，當(dāng)達(dá)到均衡條件時(shí)，出行策略上的流量為均衡策略流，則有

由上可知，通過求解該均衡問題可以確定節(jié)點(diǎn)i的最小期望出行費(fèi)用可以由下游節(jié)點(diǎn)ja遞歸計(jì)算得到，滿足式（7）廣義貝爾曼等式.

式（1）–式（7）構(gòu)建了任意節(jié)點(diǎn)i到單一目的地d的局部均衡配流模型.所有不同目的地客流間相互競(jìng)爭(zhēng)，只有當(dāng)每個(gè)目的地d的客流在任意節(jié)點(diǎn)到達(dá)均衡時(shí)，才到達(dá)網(wǎng)絡(luò)均衡，求解算法可以參考Com inetti[7].

4 公交線網(wǎng)規(guī)劃的雙層規(guī)劃模型

公交線網(wǎng)規(guī)劃的目的是使出行者、營運(yùn)單位和城市交通系統(tǒng)三者受益，保證出行者的出行費(fèi)用最少、營運(yùn)單位的運(yùn)營費(fèi)用最少和運(yùn)送的客流量最多，使得系統(tǒng)的收益最大.

出行者總費(fèi)用是指包括車站候車等待時(shí)間費(fèi)用、車內(nèi)運(yùn)行時(shí)間費(fèi)用、票價(jià)、換乘費(fèi)用、走行費(fèi)用等乘客廣義出行費(fèi)用.在策略均衡配流中，由于需求是固定的線路能力約束，如果出行需求沒有滿足（即能力不夠）或不可達(dá)，那么出行者必須通過走行到其它公交車站坐車或者全程通過走路到達(dá)目的地，這樣使得出行者費(fèi)用中的走行費(fèi)用會(huì)大幅度增加，總費(fèi)用也會(huì)隨著大幅度增加.出行者總費(fèi)用等于均衡條件下最優(yōu)策略費(fèi)用與客流需求的乘積：

公交車在運(yùn)營費(fèi)用統(tǒng)一費(fèi)用計(jì)入單位車公里成本，記單位車公里成本c.公交運(yùn)營成本還包括線路的管理費(fèi)用，單條線路的管理費(fèi)為Cy，所以公交車運(yùn)營費(fèi)用為：

如果采用固定票價(jià)，即每個(gè)人上車一次的票價(jià)為p，則總票價(jià)為：

引入各目標(biāo)函數(shù)的權(quán)重因子λi,i=1,2,3.建立公交線網(wǎng)規(guī)劃方案的雙層規(guī)劃模型.

上層規(guī)劃：

式中C1通過下層規(guī)劃的客流分配方法求得.式（11）表示線路長度限制，lmin和lmax為線路長度的下限和上限值，一般分別取5 km和15 km左右；lg為公交線路g的長度.式（12）為線路非直線系數(shù)限制，lg為公交線路g的長度(km)；zg為線路起、終點(diǎn)站間最短路長度(km)；η為上限值，一般取1.4.式（13）為復(fù)線條數(shù)限制，N(i,j)為路段(i,j)∈A0上的復(fù)線數(shù)，其中δ(i,j,g)為線路路段關(guān)聯(lián)函數(shù)，當(dāng)線路g經(jīng)過路段(i,j)時(shí)，δ(i,j,g)為1，否則為0；N?為上限值，一般取5.式（14）為平均換乘次數(shù)限制，表示所有上車弧流量的和；m為上限值.式（15）為頻率限制，fmin和fmax為線路運(yùn)營頻率的下限和上限；fg為公交線路g的運(yùn)營頻率.

5 求解雙層規(guī)劃模型的模擬退火算法

5.1 初始線網(wǎng)生成方法

首先，在城市道路交通網(wǎng)絡(luò)上配流，將高峰時(shí)段各個(gè)OD間的客流分配到城市道路交通網(wǎng)絡(luò)中，獲得基于城市道路網(wǎng)絡(luò)上各個(gè)路段的客流量.

其次，對(duì)各個(gè)路段進(jìn)行判斷，以獲得路段上可開行的線路數(shù).對(duì)所有路段進(jìn)行判定，若某個(gè)路段e上的客流量為ve，則該路段上所能開行的線路數(shù)為：

最后，對(duì)可開行線路的路段進(jìn)行組合，得到初始公交線網(wǎng).找出xe最大的路段，若兩端相鄰路段上的xe都達(dá)到開行要求，滿足線路限制約束，選擇xe較大的路段進(jìn)行組合，重復(fù)上述操作直到不能延伸組合為止，從而得到一條線路，在該線路上相應(yīng)道路上的xe減去1.按照上述操作生成多條線路，并設(shè)置公交線網(wǎng)中線路頻率為最大頻率.

5.2 線路調(diào)整方法

公交線網(wǎng)規(guī)劃問題是一個(gè)復(fù)雜的多目標(biāo)組合優(yōu)化問題，為了求得全局范圍內(nèi)的優(yōu)解，采用模擬退火算法進(jìn)行求解.按以下幾種方法調(diào)整線路，構(gòu)建模擬退火算法的搜索鄰域.

（1）刪除線路.

（2）生成線路.

當(dāng)線路有變化，進(jìn)行基于策略均衡的客流分配，對(duì)所有走行弧的流量進(jìn)行判定，按初始解的生成方法，重新生成部分線路，一起作為原方案的一個(gè)鄰域解.

（3）替換線路.

（4）延伸線路.

（5）縮短線路.

（6）拼接線路.

隨機(jī)選擇兩條線路，在這兩條線路中，若其中一條公交線路完全被另一條公交線路包含，或者這兩條公交線路的其中兩個(gè)端點(diǎn)相同，或者在這兩條公交線路各自的端點(diǎn)處，兩條公交線路有幾個(gè)路段重合，則將這兩條公交線路拼接成一條公交線路.

（7）拆分線路.

在搜索鄰域解的過程中，每次都隨機(jī)刪除部分線路，并生成新的線路，并按一定概率對(duì)線路進(jìn)行替換、延伸、縮短、拼接和拆分等操作.每進(jìn)行一次操作，都對(duì)得到的線路進(jìn)行判斷，若不滿足約束條件，則返回到操作前的結(jié)果；對(duì)于新加入的線路設(shè)置其頻率為最大頻率.

通過領(lǐng)域搜索得到滿足約束條件的線路，然后通過客流分配，獲得各公交線路的路段斷面客流平均值和標(biāo)準(zhǔn)差σ(g)，綜合考慮客流分布特征、線路客流量和線路能力的關(guān)系，對(duì)公交線路做以下頻率調(diào)整：

6 算例分析

在Sioux Falls網(wǎng)絡(luò)的基礎(chǔ)上，適當(dāng)調(diào)整后構(gòu)建網(wǎng)絡(luò)如圖3所示，原OD量乘以0.6后作為高峰時(shí)段客流量，路段長度在圖3中標(biāo)注在相應(yīng)實(shí)線的一側(cè)，公交車額定載客85人.車輛速度20 km/h，人走行速度4 km/h.線路最大長度為17 km，最小長度為8 km；線路運(yùn)行最大頻率為30輛/h，最小頻率為6輛/h.目標(biāo)函數(shù)的權(quán)重因子λ1=1,λ2=1,λ3=1.目標(biāo)函數(shù)中運(yùn)營時(shí)間為16 h，單位車小時(shí)成本Cv=62.5，各條線路固定費(fèi)用Cy=10 000，票價(jià)2元/人.

通過初始線網(wǎng)生成方法得到初始線網(wǎng)，線路覆蓋24個(gè)車站，覆蓋率為100%，覆蓋30條路段，覆蓋率為78.95%.8條線路的非直線系數(shù)都在1.4以下，復(fù)線條數(shù)、線路長度還有頻率均滿足約束條件.換乘系數(shù)1.63次，滿足約束條件.優(yōu)化的公交線網(wǎng)方案的目標(biāo)函數(shù)值為3.122 0×105，其中乘客出行總成本2.310 6×105，運(yùn)營者的總成本為1.560 0×105，同時(shí)票價(jià)收入為7.486 2×104.生成的初始線網(wǎng)如圖3（公交車行駛路線用虛線表示，始末站由小圓圈表示）和表1所示.

圖3 初始公交線網(wǎng)規(guī)劃方案Fig.3 The initialpublic transitnetwork planning scheme

用Matlab實(shí)現(xiàn)算法，優(yōu)化計(jì)算所獲得的公交線網(wǎng)規(guī)劃方案如圖4所示.優(yōu)化公交線網(wǎng)規(guī)劃方案由7條公交線路組成如表1所示.

采用這個(gè)公交線網(wǎng)規(guī)劃方案，線路覆蓋24個(gè)車站，覆蓋率為100%，覆蓋30條路段，覆蓋率為78.95%.7條線路的非直線系數(shù)都在1.4以下，復(fù)線條數(shù)、線路長度還有頻率均滿足約束條件.換乘系數(shù)為1.501 2次，滿足約束條件.優(yōu)化的公交線網(wǎng)方案的目標(biāo)函數(shù)值為2.835 7×105，其中乘客出行總成本2.173 3×105，運(yùn)營者的總成本為1.370 0×105，同時(shí)票價(jià)收入為7.076 0×104.上述結(jié)果表明，優(yōu)化方法生成的公交線網(wǎng)具有良好的服務(wù)和經(jīng)濟(jì)指標(biāo).

表1 公交線網(wǎng)規(guī)劃方案信息Table 1 The data of public transitnetwork planning schemes

圖4 優(yōu)化公交線網(wǎng)規(guī)劃方案Fig.4 The public transitnetwork planning scheme

7 研究結(jié)論

采用基于有效頻率的策略均衡客流分配，能表現(xiàn)共線、線路能力限制和換乘行為問題，使得均衡分析結(jié)果與現(xiàn)實(shí)結(jié)果基本一致.公交線網(wǎng)規(guī)劃的雙層規(guī)劃模型綜合考慮了乘客和公交公司兩方面的因素，以系統(tǒng)效益最大化為目標(biāo)，均衡了各方面的利益.模擬退火求解算法通過構(gòu)造刪除線路、生成線路、替換線路、延伸線路、縮短線路、拼接線路和拆分線路等7種搜索鄰域及相應(yīng)的頻率調(diào)整，使得算法具有較大的搜索空間和較高的搜索效率，保證所生成的公交線網(wǎng)具有良好的服務(wù)和經(jīng)濟(jì)指標(biāo).算例分析表明該模型與算法具有良好的優(yōu)化效果.

[1]于濱,楊永志,楊忠振,等.基于直達(dá)客流密度最大的公交線網(wǎng)優(yōu)化[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2009,41(2): 205-207.[YU B,YANG Y Z,YANG Z Z,etal.Transit network optimization based on direct passenger flow density maximization[J].Journal of Harbin Institute of Technology,2009,41(2):205-207.]

[2]于濱,劉鴻婷,閆博,等.公交線路網(wǎng)優(yōu)化的雙層模型及其解法[J].吉林大學(xué)學(xué)報(bào),2010,40(2):402-405. [YU B,LIU H T,YAN B,et al.Bi-levelmodel for bus route network optimization and its solution[J].Journal of Jilin University,2010,40(2):402-405.]

[3]韓印,李維斌,李曉峰.城市公交線網(wǎng)調(diào)整優(yōu)化PSO算法[J].中國公路學(xué)報(bào),1999,12(3):100-104.[HAN YIN,LIW B,LIX F.The algorithm PSO of adjustment and optimization for public traffic network[J].China Journal of Highway and Transport,1999,12(3):100-104.]

[4]郭志勇,王煒,陳學(xué)武.“一路一線直行式”公交系統(tǒng)理論框架體系研究[J].交通運(yùn)輸系統(tǒng)工程與信息, 2009,9(4):159-165.[GUO Z Y,WANGW,CHEN X W.Framework of“One road one line with straight driving public transportation system”[J].Journal of Transportation Systems Engineering and Information Technology,2009,9(4):159-165.]

[5]莫一魁,鄧軍,晏克非.城市公交主干線網(wǎng)布局優(yōu)化模式與方法研究[J]．合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,32(6):818-821.[MO Y K,DENG J,YAN K F.Study on planningmethodsof urban arterialbus route networks[J]．Journal of Hefei University of Technology (Natural Science),2009,32(6):818-821.][6]史峰,鄧連波.旅客換乘網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)[J]．鐵道科學(xué)與工程學(xué)報(bào),2004,1(1):78-82．[SHIF,DENG L B. Optimal design of passenger transfer network[J].Journal ofRailway Scienceand Engineering,2004,1(1):78-82.]

[7]Cominetti R,Correa J.Common-lines and passenger assignment in congested transit networks[J]. Transportation Science,2001,35(3):250-267.

[8]Cepeda M,Cominetti R,Florian M.A frequency-based assignment model for congested transit networks with strict capacity constraints:characterization and computation of equilibria[J].Transportation Research PartB,2006,40(6):437-459.

Method of Public Transit Network Planning Based on Strategy Equilibrium Transit Assignment

XU Guang-ming，SHI Feng，LUO Xiang，QIN Jin

(School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

The rail passenger transfer network is used to describe the bus transfer network of the peak period, on which equilibrium analysis of passenger travelling choice behavior is made based on the strategy equilibrium transit assignment. Considering the interests of passengers and the bus companies, a bi- level programming model of public transit network planning is established. Simulated annealing algorithm is designed to solve the model, through seven searching methods: deleting routes, generating routes, substituting routes, extending routes, curtailing routes, combining routes and dismantling routes to search the neighborhood solutions. The example shows that the model and algorithm are well efficient for optimizing the public transit network.

traffic engineering; strategy equilibrium; bi-level programming; public transit network design; simulated annealing algorithm

1009-6744（2015）03-0140-06

U491.1+2

A

2014-11-19

2015-03-02錄用日期：2015-03-11

國家自然科學(xué)基金項(xiàng)目(U1334207，71171200，71101155)；湖南省研究生科研創(chuàng)新項(xiàng)目資助(CX2014B062).

徐光明(1986-)，男，湖南岳陽人，博士生.＊通信作者：shifeng@csu.edu.cn