基于出行效率提升的公共交通線網優(yōu)化研究*

揭遠朋 馮雪松 解振全 劉 異 朱曉靜

(北京交通大學城市交通復雜系統(tǒng)理論與技術教育部重點實驗室1) 北京 100044)(北京交通大學交通運輸學院2) 北京 100044)(中鐵第四勘察設計院集團有限公司線路站場設計研究處3) 武漢 430063)

0 引 言

城市公共交通的網絡布局會影響居民出行對公共交通的選擇，也制約著城市公共交通系統(tǒng)功能的發(fā)揮和城市經濟的發(fā)展.

國外學者近些年以提升乘客公共交通出行的整體效率為目標，在優(yōu)化公共交通線網的過程中盡可能減少乘客公共交通出行的總時耗和換乘次數.Fan等[1]以減少乘客公共交通出行時間和換乘次數為目標，并提出使用爬山法和模擬退火這兩種元啟發(fā)式算法優(yōu)化公共交通線網.Nikolich等[2]進一步完善數學模型，他們在研究中考慮了不能滿足運載的公共交通出行，并給這些不能滿足運載的公共交通出行一個較大的懲罰時間.Nayeem等[3]也使用了和相同的數學模型，不同的是該研究提出了基于精英保留策略的遺產算法對模型進行求解.結果表明，該研究使用的算法相比以往的算法能得到更好的優(yōu)化效果，并節(jié)約了計算時間.Zhao等[4]提出的優(yōu)化模型不僅考慮了公交換乘和不能滿足運載的公交出行，還考慮乘客的等待時間.該研究的優(yōu)化結果不僅確定了各條公交線路的走向，同時還確定了各條公交線路上公交車輛的發(fā)車頻率.國內學者主要通過不同的目標對公共交通線網的優(yōu)化設計進行研究.于濱等[5]提出了上層模型以直達客流密度最大為目標的公交線網雙層優(yōu)化模型.該優(yōu)化模型考慮公交線網的變化對乘客出行行為的影響，并在下層模型中對公交客流進行再分配.周媛等[6]從乘客利益、企業(yè)效益及社會環(huán)境的角度出發(fā)，以公共交通效率最大化為總目標，建立公交線網優(yōu)化模型，并提出基于遺傳禁忌算法的公交線網優(yōu)化算法.俞禮軍等[7]設計的最優(yōu)模型解決現有公交線網優(yōu)化求解算法中存在的很少考慮相鄰線路的換乘和求解出的不同線路有大量站點重復等問題.

現有研究成果在優(yōu)化設計城市公共交通線網的過程中一般先將公共交通系統(tǒng)抽象成為一個數學模型，然后運用相應的算法對問題進行求解[8-10].本文也采用相同的研究思路，從乘客出行的角度出發(fā)，以乘客出行對公共交通的需求為依據,以減少乘客出行的總時耗為目標，構造城市公共交通線網的優(yōu)化模型，并對研究區(qū)域的現狀公交線網進行優(yōu)化調整，以提高研究區(qū)域內乘客公共交通出行的整體效率.

1 建立模型

1.1 基本假設

本文構建城市公共交通線網優(yōu)化模型的基本假設如下：①公共交通線網上任意兩個站點間的乘客出行需求不變；②公共交通線網各線路上運力供給可滿足相應的出行需求；③公共交通線網上任意相鄰可連接的兩個站點間的在車旅行時間不變；④公共交通線網上任意兩個站點間的乘客在考慮換乘時間的情況下，都選擇兩個站點之間耗時最少的出行路徑；⑤優(yōu)化前后公共交通線網上站點數量和線路條數不變[11-17].

設公共交通線網為G={N,L}.式中：N為公共交通線網中站點的集合；L為連接兩個相鄰可連接站點的路段；R為公共交通線網上初始線路集合；qod為站點o與站點q之間的公共交通出行量，站點o為乘客公共交通出行的起點，站點q為乘客公共交通出行的終點，乘客在站點o與站點q之間的出行路徑為pathod，則

(1)

(2)

(3)

1.2 公共交通出行的換乘時間

將站點o與站點d之間時耗最少的出行路徑記為Dpathod，站點o與站點d之間乘客選擇Dpathod出行過程中乘坐線路的條數記為σod.若σod=0，表示站點o與站點d之間沒有出行路徑，即公共交通線網上站點o與站點d不可連通，σod的計算見式(4).根據乘客出行過程中乘坐線路的條數σod，可計算站點o與站點d之間乘客選擇時耗最少的路徑Dpathod出行的換乘次數δod，δod的計算見式(5).

(4)

δod=σod-1

(5)

在目標函數中計算乘客出行總時耗時，本文只統(tǒng)計換乘次數不超過兩次的公共交通出行的在車旅行時間和換乘時間，則若δod≤2，記Δod=1；若δod>2，記Δod=0，見式(6).如果兩個站點之間時耗最少的出行路徑的換乘次數超過兩次，本文會給在這兩個站點之間的公共交通出行一個較大的懲罰時間ω1.根據以往的研究，取ω1為100.00 min加上公共交通線網上所有乘客以最短路徑直達出行的平均時耗.則若δod>2，記▽od=1；若δod≤2，記▽od=0，見式(7).

(6)

(7)

公共交通出行中途換乘時，乘客需要下車步行到換乘站點并等待公共交通車輛，因此本文將乘客公共交通出行一次換乘的平均時間考慮為由一次換乘平均走行時間和一次換乘平均等待時間構成.公共交通線網上所有不超過兩次換乘的公共交通出行的總換乘時間記為TTR1，TTR1的計算見式(8).公共交通線網上所有超過兩次換乘的公共交通出行的總懲罰時間記為TTR2，TTR2的計算見式(9).

TTR1=(tw+tc)∑o,d∈NqodδodΔod?o,d∈N

(8)

TTR2=ω1∑o,d∈Nqodod?o,d∈N

(9)

式中：tw為公共交通線網上公共交通出行一次換乘的平均走行時間，min；tc為公共交通線網上公共交通出行一次換乘的平均等車時間，min.

1.3 公共交通出行的在車旅行時間

站點o與站點d之間的乘客選擇時耗最少的路徑Dpathod出行的在車旅行時間記為tod，為

(10)

式中：tij為相鄰可連接站點i與站點j之間的在車旅行時間，min.

公共交通線網上所有不超過兩次換乘的公共交通出行的總在車旅行時間記為TIV，為

TIV=∑o,d∈NqodtodΔod?o,d∈N

(11)

1.4 目標函數

本文以公共交通線網上所有乘客出行的總時耗最小為目標構造城市公共交通線網優(yōu)化模型的目標函數，為

minT=TIV+TTR1+TTR2

(12)

(13)

(14)

式中：T為公共交通線網上所有乘客的出行總時耗，分鐘；Q為公共交通線網上公共交通出行總量，人次.

式(12)為優(yōu)化模型的目標函數，表示公共交通線網上乘客出行的總時耗最少；式(13)為公共交通線網上任意兩個站點間可有路徑出行，即公共交通線網在優(yōu)化后各個站點可連通；式(14)為公共交通線網上所有站點間的出行需求量之和為公共交通線網上的出行總量.

2 算法設計

2.1 遺傳算法操作方式

1) 編碼 根據城市公共交通線網優(yōu)化問題的特征，本文采用實數編碼的形式，先將公共交通線網上所有初始線路的站點數字編號串在一起，相異線路的數字編號組用0隔開.每條線路的數字編號組可以當作一個基因片段，將所有的線路組在一起可以構成一個個體，一個個體代表一個公共交通線網方案.假設個體的基因序號為12 9 4 15 8 5 0 13 6 8 14 0 1 10 3 5 14 0 4 11 2 7 10 1，則表示該公共交通線網有4條線路，第一條線路途徑站點的數字編號為12 9 4 15 8 5，第二條線路途徑站點的數字編號為13 6 8 14，第三條線路途徑站點的數字編號為1 10 3 5 14，第四條線路途徑站點的數字編號為4 11 2 7 10 1.

2) 初始種群生成 本文先將研究區(qū)域現狀的公共交通線路進行編碼，然后構成一個初始個體.如果種群的個體規(guī)模為N，將初始個體復制N次，這N個相同的個體構成本文遺傳算法所需的初始種群.

3) 選擇 選擇是從舊群體中以一定概率選擇優(yōu)良個體組成新種群，新種群通過繁殖得到下一代個體，本文使用輪賭盤法進行選擇操作.輪賭盤法是一種放回式隨機采樣方法，每個個體被選擇進入下一代的概率等于該個體的適應度值占整個種群中個體適應度值和的比例，個體的適應度值越高，該個體被選擇的概率就越大，進入下一代的概率就越大.假設在M個體中第m個個體的適應度值為Fm，則個體被選擇概率pm為

(15)

式中：Fi為種群中第i個體的適應度值，i=1、2…M.

本文以優(yōu)化模型目標函數值的倒數作為適應度函數來計算種群中個體的適應度值，假設種群中第m個個體的適應度值為Fm，則Fm表示在第m個個體所代表的公共交通線網上所有乘客出行總時耗的倒數.

4) 交叉 將種群中選出的個體進行兩兩交叉，第一個個體與第二個個體進行交叉，第三個個體與第四個個體進行交叉，依此類推.如果選擇出來的個體數量為奇數，則最后一個個體不進行交叉運算.為了使交叉后公共交通線網上每條線路的各站點間可連通，父個體和母個體在交叉過程會交換整條線路，不進行線路中單個站點的交叉.

交叉的原則是首先確實一個交叉概率Pc，然后遍歷父個體或者母個體每個基因片段，并給每個基因片段一個在[0，1]區(qū)間均勻分布的隨機數Rc.若Rc≤Pc，則父個體和母個體該位置的基因片段進行交叉運算；若Rc>Pc，則父個體和母個體該位置的基因片段不進行交叉運算.為了盡可能實現單點交叉，即父個體和母個體在交叉運算過程中只交換一個基因片段，本文取交叉概率Pc=1/R，R為個體中基因片段的個數.

5) 變異 由于初始種群的所有個體都相同，遺傳算法在第一次迭代變異之前所執(zhí)行的交叉運算并不能改變種群中各個體的基因序號，只有第一次迭代中的變異過程才能使種群中的個體發(fā)生改變.本文以個體中基因片段代表的線路所途徑站點中兩兩站點間OD(origin destination)交通量之和的倒數為適應度值，根據基因片段適應度值的大小，以輪賭盤法選擇出一個基因片段所代表的線路進行變異操作.首先確定變異概率值Pm，并遍歷從種群中選出的每個個體，并給定每個個體一個[0 1]區(qū)間內均勻分布的隨機數Rm.若Rm≤Pm，則該個體進行線路變異；若Rm>Pm，則該個體進行站點變異.

①線路變異方式 首先確定一個概率分界值Pl，然后給定所選出的基因片段一個[0，1]區(qū)間內均勻分布的隨機數Rl.若Rl≤Pl，則進行線路整體變化；若Rl>Pl，則進行線路部分變化.

線路整體變化 在{0,1}集合中隨機選擇一個元素k，若k=0，則保留線路首站；若k=1，則保留線路末站.然后將保留下的站點作為一個端點，根據該端點與公共交通線網上其他站點之間的最短路徑所途徑站點中兩兩站點間的OD交通量之和的大小，以輪賭盤法選擇出另一個端點，并以兩個端點間的最短路徑作為變化后的線路.

線路部分變化 除該基因片段所代表的線路首末站外，將線路中其他站點的編號形成一個站點集合，并在站點集合中隨機選出兩個站點編號，然后這兩個站點之間的最短路徑替換線路該兩個站點之間現有的路徑.

②站點變異方式 首先確定一個概率分界值Pt，然后給定選出的基因片段一個[0，1]區(qū)間內均勻分布的隨機數Rt.若Rt≤Pt，則在線路上增加或刪除站點；若Rt>Pt，則在線路上替換中間站點.

增加或刪除站點 在{0,1}集合中隨機選擇一個元素k，若k=0，則選擇線路的首站；若k=1，則選擇線路的末站.然后確定一個概率分界值Pd，并給定選出的基因片段一個[0 1]區(qū)間內均勻分布的隨機數Rd.若Rd≤Pd，則刪除所選擇的站點；若Rd>Pd，則在所選擇的站點外延伸一個站點，延伸的這個站點要能與選擇的該線路的首站或者末站相鄰可連接.

替換中間站點 以基因片段所代表的線路的中間站點到該線路其他站點OD交通量之和的倒數為適應度值，根據基因片段適應度值的大小，以輪賭盤法選擇一個中間站點進行替換.替換的新站點必須與線路該位置前后兩個站點相鄰可連接.

2.2 流程設計

本文基于遺傳算法設計求解城市公共交通線網優(yōu)化模型的算法，算法的流程見圖1.

圖1 公共交通線網優(yōu)化的算法流程

3 案例分析

本文以我國某新興城市化區(qū)域X為研究范圍，以X境內的現狀公交線網為研究對象.X境內的現狀公交線網有39條公交線路，該39條公交線路共途徑344個不同的公交站點和458個不同的路段.本文以2016年3月21日X境內的公交出行OD交通量為研究數據，運用所設計的城市公共交通線網優(yōu)化模型和求解算法對X境內的現狀公交線網進行優(yōu)化調整.為了比較通過本文設計的優(yōu)化模型優(yōu)化后的公交線網相比初始公交線網是否更能方便乘客出行，是否提高了乘客的整體出行效率，本文設定了5個指標對公交線網進行評價.該五個指標分別為直達公交出行比例、1次換乘公交出行比例、兩次換乘公交出行比例、2次以上換乘公交出行比例和一次公交出行平均時間.本文使用C++語言編寫模型和算法的程序然后進行優(yōu)化求解，其中求解算法中各參數值的選取見表1.

表1 遺傳算法中各參數的值

根據2016年3月21日X境內乘客公交出行IC(Intelligent Card)卡刷卡記錄數據統(tǒng)計，X境內公交線網上所有乘客1次公交換乘花費的平均走行時間與平均等車時間之和取約為10.00 min.據此，X境內公交線網優(yōu)化前后5個評價指標的計算結果對比見表2.

表2 公交線網換乘時間為變量的優(yōu)化結果 %

由表2可知，相比于X境內的初始公交線交線網，優(yōu)化后公交線網的直達的公交出行比例雖減少了約4.01%，但僅需一次換乘的公交出行比例增加了兩倍有余；與此同時，需兩次換乘的公交出行比例減少了約88.18%，且需要兩次以上換乘的公交出行完全消失.優(yōu)化后的公交線網減少了換乘次數過多的公交出行和時間過長的公交換乘.X境內一日公交出行交通量總數約為7.57萬人次，他們在優(yōu)化后的公交線網上一次公交出行的平均時間減少了約3.40%，整個公交線網上所有乘客的總出行時耗節(jié)省超過5.00×104min.通過綜合比較分析可以得知，本文以換乘時間為變量的公共交通線網優(yōu)化模型對X境內的公交線網進行優(yōu)化調整，可以減少須多次換乘的公交出行比例，減少公交線網所有乘客的出行總時耗，提高乘客的整體出行效率.

4 結 論

1) 本文提出的城市公共交通線網優(yōu)化模型將公共交通出行的換乘時間設為變量，該變量取值則須根據所研究區(qū)域的公共交通線網換乘時耗具體情況的調查統(tǒng)計確定，這樣處理能更好貼近現實的優(yōu)化城市公共交通線網.

2) 使用遺傳算法對所構建的城市公共交通線網的優(yōu)化模型進行求解，并設計了站點變異和線路變異兩個變異方法，能在迭代優(yōu)化過程中更好對城市公共交通線路進行變動和調整，并能更快地尋找到公共交通線網的最優(yōu)方案.

3) 通過實例分析，本文提出的城市公共交通優(yōu)化模型和設計的求解算法可以有效減少換乘次數過多的公共交通出行和時間過長的公共交通出行換乘，減少乘客一次公共交通出行的平均時間，進而提高公共交通線網上所有乘客的整體出行效率.

[1] FAN W, MACHEMEHL R B. Using a simulated annealing algorithm to solve the transit route network design problem[J]. Journal of Transportation Engineering,2006,132(2):122-132.

[2] NIKOLIC M, TEODOROVIC D. Transit network design by bee colony optimization[J]. Expert Systems with Applications,2013,41(16):7200-7209.

[3] NAYEEM A M, RAHMAN M K, RAHMAN M S. Transit network design by genetic algorithm with elitism[J]. Transportation Research Part C: Emerging Technologies, 2014,46:30-45.

[4] ZHAO H, XU W T, JIANG R. The Memetic algorithm for the optimization of urban transit network[J]. Expert Systems with Applications,2015,42:3760-3773.

[5] 于濱,劉鴻婷,閆博,等.公交線網優(yōu)化的雙層模型及其解法[J].吉林大學學報(工學版),2010,40(2):402-405.

[6] 周媛,鄧衛(wèi),胡啟洲.基于遺傳禁忌算法的城市公交線網優(yōu)化研究[J].武漢理工大學學報(交通科學與工程版),2011, 35(1):42-45.

[7] 俞禮軍,梁明萍.基于整數非線性規(guī)劃的城市常規(guī)公交線網優(yōu)化設計[J].中國公路學報,2016,29(2):108-115.

[8] KECHAGIOPOULOS P N, BELIGIANNIS G N. Solving the urban transit routing problem using a particle swarm optimization based algorithm[J]. Applied Soft Computing,2014,21(3):654-676.

[9] 李雙,郭海洋,張琦.基于TransCAD的城市公共交通線路優(yōu)化研究[J].科技視界,2014(33):144-145.

[10] 魏素豪,宗剛.基于線路“異質性”假設的軸輻式公共交通網絡優(yōu)化研究[J].運籌與管理,2017(10):42-48.

[11] 杜文舉,張建剛,俞建寧.復雜公交社團網絡模型的穩(wěn)定性研究[J].計算機工程與應用,2017(23):39-46.

[12] 史路.城市公共交通線路模擬優(yōu)化[J].公路交通技術,2014(2):111-114,118.

[13] 潘福全,馬雨秋,張麗霞,等.基于限時免費換乘的公交線網優(yōu)化模型與求解算法[J].科學技術與工程,2016(2):239-243.

[14] 王宇寧.基于公共服務需求導向的軌道線網規(guī)劃優(yōu)化研究[J].都市快軌交通,2016(2):13-17.

[15] 李育君.淺談城市軌道交通提高乘客自助出行效率的可行性措施[J].低碳世界,2017，35(1):288-289.

[16] 朱宇婷.考慮乘客出行效率的城市軌道交通列車開行方案優(yōu)化研究[D].北京：北京交通大學,2016.

[17] 郭露露,蘇國鋒,路堃,等.基于復雜網絡理論的北京地鐵網絡脆弱性評估[J].工業(yè)安全與環(huán)保,2017(11):30-34.