基于雙層規(guī)劃的老城區(qū)自行車專用道網(wǎng)絡(luò)設(shè)計(jì)

王 豐，劉昊翔，2

（1.合肥工業(yè)大學(xué)，汽車與交通工程學(xué)院，合肥 230009；2.合肥工業(yè)大學(xué)，安徽省智慧交通車路協(xié)同工程研究中心，合肥 230009）

0 引 言

隨著社會(huì)經(jīng)濟(jì)的迅速發(fā)展，私家車的保有量逐年增加，老舊城區(qū)的交通擁堵問題變得日益嚴(yán)重。尤其是老城區(qū)人口居住量大，有大量的短距離出行需求，比如，出門買菜、接送小孩、“最后一公里”等。國內(nèi)大部分城市的老城區(qū)由于歷史和經(jīng)濟(jì)原因，道路狹窄且密集，且部分特殊區(qū)域，如城中村、傳統(tǒng)老街等，由于道路空間的限制，公共交通站點(diǎn)覆蓋率較低，導(dǎo)致有限的道路供給無法滿足大量的出行需求，很容易造成老城區(qū)機(jī)非車流混合且極易擁堵的交通狀況。已有研究表明[1-3]，在老城區(qū)中合理地規(guī)劃自行車路網(wǎng)，可以提高自行車出行的分擔(dān)率，同時(shí)能減少機(jī)動(dòng)車出行，從而有效地緩解交通擁堵。如何在老城區(qū)合理地規(guī)劃自行車專用設(shè)施，是政府部門進(jìn)行交通規(guī)劃的難題。

自行車作為一種慢行交通方式，其基礎(chǔ)配套設(shè)施的規(guī)劃是城市交通規(guī)劃領(lǐng)域的重要組成部分，2017 年，劉蘭輝等人[4]基于上海南匯新城自行車交通流和自行車道路設(shè)施的現(xiàn)場(chǎng)調(diào)查和分析，從路網(wǎng)連續(xù)性、路面平整度等角度提出了完善自行車交通設(shè)施的措施與建議。2018年，李翔[5]提出了由以“車”為本到以“人”為本的理念，并基于這種理念對(duì)廣州市自行車交通相關(guān)的道路規(guī)劃和設(shè)計(jì)提出優(yōu)化建議。2019年，許珂源等人[6]在研究慢行交通中提出在中心城區(qū)通過修建自行車專用道可以提供更加便利和綠色的出行方式，自行車可被作為短途通勤和多種出行方式間接駁的重要出行方式之一。楊永平和陳春羽[7]分析了國內(nèi)外自行車發(fā)展及趨勢(shì)，提出了自行車專用路的設(shè)計(jì)要點(diǎn)，為后續(xù)自行車專用路的發(fā)展提供了參考。2020年，黃玥和干宏程[8]從自行車出行路徑選擇行為影響因素、模型方法、實(shí)驗(yàn)調(diào)查方法以及應(yīng)用場(chǎng)景等方面系統(tǒng)梳理了自行車出行路徑選擇偏好的研究成果。許乃星和陳亮[9]深入分析自行車專用路的網(wǎng)絡(luò)分級(jí)、規(guī)劃原則、設(shè)置形式、寬度與坡度、節(jié)點(diǎn)通過方式、出入口與銜接、服務(wù)配套等建設(shè)技術(shù)指標(biāo)，為自行車專用路規(guī)劃與建設(shè)提供了指導(dǎo)。以上以慢行交通為背景的研究主要從定性研究的角度，從車道寬度、路面平整度、機(jī)非隔離帶、自行車道的連通性等方面分析了自行車基礎(chǔ)配套設(shè)施的合理度，并結(jié)合實(shí)際提出了優(yōu)化建議。

除了定性研究以外，也有學(xué)者從定量的數(shù)學(xué)建模角度對(duì)自行車網(wǎng)絡(luò)設(shè)計(jì)問題進(jìn)行了分析研究。2017 年，宋青等人[10]在對(duì)真實(shí)騎行者路徑選擇行為深入分析的基礎(chǔ)上，提出了基于Open Street Map 的城市自行車網(wǎng)絡(luò)的構(gòu)建方法及基于其上的多判據(jù)自行車路徑優(yōu)化的數(shù)學(xué)模型，并給出了求解該模型的一種基于聚類的最優(yōu)多判據(jù)路徑規(guī)劃方法。Mauttone[11]等人以最小化用戶和規(guī)劃者的費(fèi)用為目標(biāo)函數(shù)，建立了一個(gè)混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了一個(gè)遺傳算法對(duì)模型進(jìn)行求解，采用算例分析驗(yàn)證了算法和模型的有效性。2018年，Chen[12]采用網(wǎng)絡(luò)流技術(shù)和數(shù)學(xué)規(guī)劃方法，針對(duì)現(xiàn)有的自行車網(wǎng)絡(luò)系統(tǒng)，構(gòu)建了自行車網(wǎng)絡(luò)設(shè)計(jì)模型。該模型的目標(biāo)是在滿足相關(guān)運(yùn)營約束的前提下，使騎自行車者的出行時(shí)間最小化，將提出的模型表述為混合整數(shù)多商品網(wǎng)絡(luò)流問題，還提出了一種高效的算法以求解提出的大規(guī)模現(xiàn)實(shí)問題模型，測(cè)試結(jié)果表明所提模型和求解算法的有效性。2019 年，Shui 和Chan[13]以最小化所有出行者的出行時(shí)間為目標(biāo)函數(shù)，考慮投資預(yù)算約束和覆蓋所有出行點(diǎn)的約束，建立了一個(gè)優(yōu)化數(shù)學(xué)模型，并結(jié)合遺傳算法和兩階段求解方法對(duì)問題進(jìn)行求解。Zuo和Wei[14]考慮自行車的連通性和對(duì)其他出行的影響，以最小化系統(tǒng)總阻抗為目標(biāo)，采用多準(zhǔn)則決策分析方法對(duì)路網(wǎng)進(jìn)行決策，算例分析表明該方法能提高出行者選擇自行車出行的比率。Liu等[15]建立了一個(gè)基于隨機(jī)用戶均衡的自行車網(wǎng)絡(luò)設(shè)計(jì)雙層規(guī)劃模型，以最大化系統(tǒng)總效益為目標(biāo)，考慮投資預(yù)算約束建立了數(shù)學(xué)模型，并通過對(duì)數(shù)學(xué)模型的線性化處理，提出了一個(gè)基于混合整數(shù)線性規(guī)劃的全局優(yōu)化算法，以及一個(gè)基于代理模型的全局優(yōu)化數(shù)學(xué)啟發(fā)式算法對(duì)問題進(jìn)行有效求解。2020 年，He 等人[16]基于GPS 提供的共享單車騎行軌跡數(shù)據(jù)，考慮投資預(yù)算、道路長度、效益最大化這三個(gè)約束條件，以自行車道的覆蓋范圍最大化為目標(biāo)函數(shù)建立數(shù)學(xué)優(yōu)化模型，旨在為政府提供自行車道的規(guī)劃方案，并采用貪婪啟發(fā)式算法對(duì)問題進(jìn)行求解，算例分析結(jié)果表明了算法和模型的有效性。Zhu 等人[17]基于時(shí)空可達(dá)性約束，考慮可達(dá)性、建設(shè)成本、出行者出行成本預(yù)算、交叉點(diǎn)個(gè)數(shù)等因素，建立了多目標(biāo)優(yōu)化數(shù)學(xué)模型，并遵循兩階段原則設(shè)計(jì)一個(gè)啟發(fā)式算法對(duì)問題進(jìn)行求解。2021 年，Oliveira 等人[18]綜合考慮車道舒適度、安全性、路徑客觀性、網(wǎng)絡(luò)連接性、投資預(yù)算，利用網(wǎng)絡(luò)多目標(biāo)優(yōu)化和混合整數(shù)線性規(guī)劃的概念，建立自行車專用道網(wǎng)絡(luò)設(shè)計(jì)的數(shù)學(xué)模型，并實(shí)現(xiàn)最優(yōu)策略的求解，結(jié)果分析表明自行車專用道的建立可以有效促進(jìn)自行車替代部分機(jī)動(dòng)車出行。

以上定量研究皆是通過建立最優(yōu)化數(shù)學(xué)模型來描述自行車專用道網(wǎng)絡(luò)設(shè)計(jì)問題，優(yōu)化目標(biāo)包括最小化系統(tǒng)總成本、出行阻抗、投資預(yù)算、連通性、多目標(biāo)優(yōu)化等，并針對(duì)不同的建模方式和問題背景設(shè)計(jì)不同的求解算法。但是以上眾多研究中，還沒有學(xué)者針對(duì)老城區(qū)的道路現(xiàn)狀，考慮出行者的選擇行為提出自行車專用道的設(shè)計(jì)方法。一般來說，基于雙層規(guī)劃的方法建立數(shù)學(xué)模型可以在下層模型中考慮出行者的出行選擇行為，因此可以更加準(zhǔn)確地描述交通系統(tǒng)中出行者與決策部門之間的相互關(guān)系。許多學(xué)者研究了基于雙層規(guī)劃的交通網(wǎng)絡(luò)設(shè)計(jì)問題[19-20]，并在最優(yōu)定價(jià)、公交排班、多目標(biāo)優(yōu)化等[21-22]領(lǐng)域取得廣泛的應(yīng)用。

本文在當(dāng)前的自行車網(wǎng)絡(luò)設(shè)計(jì)研究基礎(chǔ)上，結(jié)合國內(nèi)城市老城區(qū)中短距離出行需求多、道路密、機(jī)非混合等特點(diǎn)，考慮到自行車的出行特性可很好地契合老城區(qū)的交通環(huán)境，有效緩解老城區(qū)的交通擁堵的特點(diǎn)，提出一個(gè)新的自行車網(wǎng)絡(luò)設(shè)計(jì)問題。即采用新建自行車專用道和禁行機(jī)動(dòng)車的方式構(gòu)建連通的自行車交通網(wǎng)絡(luò)，目標(biāo)是提供更為便利的自行車基礎(chǔ)設(shè)施，以達(dá)到促進(jìn)自行車出行和緩解交通擁堵的目的。建立了雙層規(guī)劃模型描述該問題，上層模型為連通性約束下的決策模型，目標(biāo)函數(shù)為最小化系統(tǒng)總建設(shè)成本，下層模型為描述出行者彈性需求的Logit 模型和自行車、機(jī)動(dòng)車的UE 交通分配模型。提出了改進(jìn)的遺傳算法對(duì)該雙層規(guī)劃模型進(jìn)行求解，并在遺傳算法中嵌入了自適應(yīng)平均算法（SRAM）[23]和Frank-Wolfe[24]算法，分別求解Logit 模型和UE 交通分配模型。算例部分對(duì)所提出模型和算法的可行性和有效性進(jìn)行了分析說明。

與已有研究相比，本文的研究貢獻(xiàn)如下：

（1）采用新建自行車專用道和利用現(xiàn)有的道路禁行機(jī)動(dòng)車的方式構(gòu)建自行車網(wǎng)絡(luò)，并增加自行車網(wǎng)絡(luò)連通性的約束，可以最大程度地保證自行車出行的便利性和安全性。

（2）所提出的模型中考慮了需求彈性和路徑選擇，比采用固定需求可以更好地緩解交通擁堵問題。

（3）提出一個(gè)改進(jìn)的遺傳算法求解雙層規(guī)劃模型，并嵌入Frank-Wolfe 算法和SRAM 算法有效地求解下層問題。

1 數(shù)學(xué)建模

政府主導(dǎo)自行車基礎(chǔ)設(shè)施網(wǎng)絡(luò)的規(guī)劃，根據(jù)OD 需求和交通網(wǎng)絡(luò)現(xiàn)狀，決策在現(xiàn)有道路網(wǎng)絡(luò)上如何構(gòu)建連通的自行車專用道網(wǎng)絡(luò)，降低系統(tǒng)的交通出行總費(fèi)用。自行車專用道改造方案主要有兩種：一是在道路空間足夠的路段上，花費(fèi)資金建設(shè)新的道路作為自行車專用道；二是在道路空間狹小，且平行路段較多的路段上，對(duì)機(jī)動(dòng)車道路采取機(jī)動(dòng)車禁行措施。改造目標(biāo)旨在最小化系統(tǒng)總成本情況下，構(gòu)建一個(gè)連通的自行車專用道網(wǎng)絡(luò)。即從所有OD 對(duì)的起訖點(diǎn)集合中任一點(diǎn)出發(fā)均可通過自行車專用道到達(dá)起訖點(diǎn)中另一任意點(diǎn)。出行者會(huì)隨著道路網(wǎng)上的自行車專用道修建情況和OD 對(duì)之間阻抗的變化而改變出行模式和路徑選擇，即考慮選擇使用機(jī)動(dòng)車或者自行車出行，并決策所使用的路徑。由此可見，政府的決策方案將影響出行者的出行模式和路徑選擇，而出行者的出行行為也會(huì)反過來影響政府決策。因此，本文所提出的問題可以構(gòu)建為一個(gè)雙層規(guī)劃模型，其框架結(jié)構(gòu)如圖1所示。

圖1 雙層規(guī)劃模型框架圖Fig.1 Framework of the bi-lever programming model

為了便于建模和理解做出如下假設(shè)：（1）OD對(duì)之間總出行需求已知且恒定，自行車與機(jī)動(dòng)車出行需求之間存在彈性；（2）道路類型改變后，OD間的總出行需求不變；（3）自行車與機(jī)動(dòng)車分別只能在自行車專用道與機(jī)動(dòng)車道上行駛；（4）不考慮其他類型車輛對(duì)自行車和機(jī)動(dòng)車的影響。

本文符號(hào)定義如表1所示。

表1 參數(shù)及變量含義Tab.1 Definition of parameters and variables

續(xù)表1

1.1 上層自行車專用道規(guī)劃模型

上層自行車專用道規(guī)劃模型站在政府管理者的角度，以系統(tǒng)總費(fèi)用最小為目標(biāo)函數(shù)，以自行車網(wǎng)絡(luò)連通性為主要約束條件，其數(shù)學(xué)模型如下：

模型中目標(biāo)函數(shù)（1）旨在最小化系統(tǒng)總費(fèi)用，其中第一項(xiàng)是自行車專用道的建設(shè)費(fèi)用，第二項(xiàng)是機(jī)動(dòng)車和自行車的出行總阻抗，σ是出行者的時(shí)間價(jià)值系數(shù)。約束（2）表示路段a上新建自行車專用道和禁行機(jī)動(dòng)車策略只能采用其一。約束（3）和（4）均表示從所有的OD 對(duì)起訖點(diǎn)集合中任選兩個(gè)點(diǎn)r和e，在r、e之間均存在連通的自行車專用道相連。最終的決策方案中，所有起訖點(diǎn)的任意兩點(diǎn)之間都可以通過自行車專用道相連，這符合連通網(wǎng)絡(luò)的定義。約束（4）表示連接r、e之間的自行車可行路徑上的路段均為自行車專用道，即zrea=1 的前提條件是xa=1 或者ya=1。換句話說，該路段如果是自行車專用道，那么表示新建了自行車專用道，或者采取了機(jī)動(dòng)車禁行措施。約束（5）表示xa、ya、zrea均是0-1變量。

1.2 下層需求方式劃分和交通分配模型

考慮到老城區(qū)短距離出行需求多，道路空間狹小，公共交通覆蓋率不高等情況，故在本文研究中簡(jiǎn)單地將所有的機(jī)動(dòng)車都視作小汽車處理，模型下層只考慮自行車和小汽車的出行模式。給定一個(gè)可行的自行車專用道網(wǎng)絡(luò)設(shè)計(jì)方案，在OD 總需求已知的情況下，下層模型可以預(yù)測(cè)出行者對(duì)自行車和小汽車出行模式的選擇，進(jìn)而預(yù)測(cè)小汽車網(wǎng)絡(luò)和自行車網(wǎng)絡(luò)各自的流量分配。假設(shè)用戶對(duì)小汽車出行和自行車出行方式的選擇服從Logit 模型，而用戶的出行路徑選擇服從UE 均衡準(zhǔn)則，則下層的用戶出行行為模型如下所示。

（1）需求劃分模型：

約束（6）表示選擇機(jī)動(dòng)車和自行車的出行者總和等于OD 對(duì)之間總需求；約束（7）用Logit 模型描述出行者選擇自行車出行的概率；約束（8）表示OD 對(duì)w之間的自行車出行需求。

（2）自行車的UE交通分配模型：

約束（10）表示OD 對(duì)之間總需求與各路徑流量的守恒關(guān)系；約束（11）表示自行車路段流量和路徑流量的關(guān)系；約束（12）限制了各自行車路徑流量都為非負(fù)。

在UE 交通分配問題中，我們采用了基于美國聯(lián)邦公路局（Bureau of public road，BPR）開發(fā)的阻抗函數(shù)，即BPR[25]函數(shù)來描述路段阻抗，其中α和β為模型參數(shù)，分別取值0.15 和4。根據(jù)已有涉及自行車阻抗的研究，本文為了使自行車的阻抗更加符合實(shí)際情況，在BPR 函數(shù)中加入了自行車阻抗系數(shù)φ（0<φ<1），并且在3.4 小節(jié)中對(duì)該系數(shù)的影響做了分析說明。約束（13）表示自行車阻抗計(jì)算公式，xa=1 或者ya=1 表示路段a上有自行車專用道自行車可以通行，否則表示路段上無自行車專用道，自行車無法通行，通行時(shí)間為無窮大。

（3）機(jī)動(dòng)車的UE交通分配模型：

機(jī)動(dòng)車的UE 交通分配模型（14）～（18）與自行車出行類似。在約束（18）中，ya=1 表示路段a被禁行，則該路段上機(jī)動(dòng)車的走行時(shí)間為無窮大；ya=0 表示未禁行，則采用標(biāo)準(zhǔn)的BPR 函數(shù)計(jì)算機(jī)動(dòng)車的路段走行時(shí)間。

2 求解算法

由于雙層規(guī)劃模型是一個(gè)NP-hard 問題[26]，許多學(xué)者從求解算法方面對(duì)該類模型進(jìn)行了大量研究[27-33]。本文所提出模型帶有連通性的約束條件，并且下層問題包含模式劃分和交通分配模型，因此為了有效求解該模型，采用基于遺傳算法（Genetic Algorithm, GA）[34]的求解算法框架，并提出檢查和更新網(wǎng)絡(luò)連通性的策略，對(duì)下層的Logit模型和UE 交通分配分別采用自適應(yīng)平均算法（SRAM）及Frank-Wolfe算法進(jìn)行有效求解。

本文所提出的基于GA 的算法框架如圖2 所示，其中嵌入的SRAM 算法和Frank-Wolfe 算法具體流程分別在后面2.2 和2.3 中進(jìn)行敘述。

圖2 算法框架Fig.2 Algorithm framework

遺傳算法求解網(wǎng)絡(luò)設(shè)計(jì)：

輸入：種群規(guī)模m、交叉概率pc、變異概率pm、最大迭代次數(shù)kmax生成m個(gè)初始解（染色體）構(gòu)成初始種群Φˉ0，初始化迭代次數(shù)k = 0用SRAM算法分別對(duì)種群Φˉ0中所有個(gè)體求解，得到每個(gè)個(gè)體的目標(biāo)函數(shù)值，可根據(jù)目標(biāo)函數(shù)值計(jì)算適應(yīng)度，并置ubest為Φˉ0中的最優(yōu)解。根據(jù)輪盤賭原則按照適應(yīng)度大小從Φˉ0中挑選出m個(gè)個(gè)體得到新的一組解Φ0 While k

2.1 遺傳算法

遺傳算法是通過模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程搜索最優(yōu)解。從一個(gè)初代種群開始，按照適者生存和優(yōu)勝劣汰的原理，根據(jù)個(gè)體的適應(yīng)度選擇個(gè)體進(jìn)行組合交叉和變異，逐代演化產(chǎn)生出越來越好的解。遺傳算法中的種群由多個(gè)個(gè)體，即染色體組成，每個(gè)染色體由一組基因構(gòu)成。在本文中，每個(gè)染色體代表模型的一個(gè)解，即自行車的網(wǎng)絡(luò)設(shè)計(jì)方案。染色體上的基因表示解中每個(gè)路段是否有專用道，是新建專用道還是禁行小汽車，本文中基因的取值有0、1、2三種情況，0表示小汽車禁行（相當(dāng)于ya= 1），1表示新建自行車專用道（相當(dāng)于xa= 1），2 表示仍是小汽車道（相當(dāng)于xa+ya=0）。例如，圖3給出了一個(gè)有15個(gè)基因的染色體，該染色體共有6 條路段為新建專用道，4 條路段為小汽車禁行，5條路段仍是小汽車專用道。

圖3 染色體示例Fig.3 Chromosome example

2.1.1 解的初始化

在遺傳算法開始時(shí)，首先要產(chǎn)生一組種群大小為K的初始解，即K個(gè)連通的自行車專用道設(shè)計(jì)方案，其中，每個(gè)可行解均由以下兩個(gè)步驟產(chǎn)生。

首先，產(chǎn)生連通的自行車基礎(chǔ)網(wǎng)絡(luò)。為了便于描述，將給定的m個(gè)OD 對(duì)標(biāo)上序號(hào)，即第一對(duì)OD對(duì)為O1D1，第二對(duì)為O2D2，…，第m對(duì)為OmDm。從第一個(gè)起點(diǎn)O1中找到一條連到終點(diǎn)D1的路徑，該路徑為當(dāng)前小汽車最短路或者次短路，當(dāng)O1D1間有大于2條以上路徑時(shí)，則隨機(jī)采用最短路或者次短路。然后再從已連接專用道的節(jié)點(diǎn)中選一個(gè)點(diǎn)J，使J離下一個(gè)起點(diǎn)O2最近，找到J到起點(diǎn)O2的最短路徑，再從起點(diǎn)O2按照同樣的方法找一條連到終點(diǎn)D2的路徑，接下來再去連接第三個(gè)起點(diǎn)O3，從O3連到D3后，再去連第4個(gè)起點(diǎn)O4……這樣循環(huán)直到把所有的OD對(duì)都覆蓋到。這樣即得到了一個(gè)所有點(diǎn)都是連通的且OD對(duì)之間也是連通的一個(gè)解。

其次，在當(dāng)前連通的路網(wǎng)上，設(shè)置自行車專用道和禁行路段。設(shè)置初始概率P0，針對(duì)上一步產(chǎn)生的路網(wǎng)當(dāng)中的每一個(gè)路段a隨機(jī)產(chǎn)生一個(gè)概率pa，若pa>P0,則該路段采用禁行措施，否則新建自行車專用道。

執(zhí)行以上兩個(gè)步驟可以得到一組可行解。再從所有OD 對(duì)的起點(diǎn)中選O2O2作為起點(diǎn)，分別找到O2D2的路徑再連到O3，找到O3D3的路徑連到O4…找到OmDm的路徑，連到O1，這可以得到另一組可行解。重復(fù)執(zhí)行同樣的操作，直到得到K個(gè)初始可行解。

圖4 演示了有3個(gè)OD 對(duì)需求的初始解生成過程，圖中所有路段皆可通行。給三個(gè)OD 對(duì)隨機(jī)排序：O1D1為1→9（藍(lán)色）、O2D2為2→8（綠色）、O3D3為3→7（紅色），如圖4（a）所示。首先，要找O1到D1的連通路徑，采用最短路和次短路的方法可以找到O1到D1間有兩條路徑，假設(shè)隨機(jī)選用了次短路，該路徑為1→4→5→8→9，如圖4（b）所示。其次，找到1、4、5、8、9 節(jié)點(diǎn)中距第二個(gè)OD 對(duì)的起點(diǎn)2 最近的點(diǎn)，假設(shè)這個(gè)點(diǎn)是5，則連接5→2 之間的最短路徑，如圖4（c）所示；再按照最短路和次短路的方法找到OD 對(duì)2→8 之間的路徑，假設(shè)隨機(jī)選取了2→8 間的最短路，該路徑為2→5→8，如圖4（d）所示。此時(shí)已連接專用道的節(jié)點(diǎn)有1、2、4、5、8、9，再從這些節(jié)點(diǎn)中找到離第三個(gè)OD對(duì)的起點(diǎn)3最近的點(diǎn)，假設(shè)找到的這個(gè)點(diǎn)為2，則連接2→3 之間的最短路徑，如圖4（e）所示；再按照最短路和次短路的方法找到OD 對(duì)3→7 之間的路徑，假設(shè)隨機(jī)選取了3→7 間的最短路，該路徑為3→2→5→8→7，如圖4（f）所示。注，圖中某些節(jié)點(diǎn)之間有多條不同顏色的路徑，如圖4（f）中的2→5節(jié)點(diǎn)間，有三種不同的顏色，這表示該路段上只有一條自行車專用道，這條自行車專用道被多個(gè)OD 對(duì)同時(shí)使用，而不是在這個(gè)路段上修建了多條自行車專用道。

完成以上步驟后可得到一個(gè)滿足連通性條件的自行車道網(wǎng)絡(luò)，再對(duì)連通網(wǎng)絡(luò)上的每一個(gè)路段a按照隨機(jī)概率的方式，即可確定每個(gè)路段是采用新建自行車專用道還是禁行機(jī)動(dòng)車道，至此可以得到一個(gè)完整可行的自行車專用道網(wǎng)絡(luò)作為第一個(gè)初始解。按照同樣的方式，從第二個(gè)OD 對(duì)的起點(diǎn)開始執(zhí)行操作，可以得到第二個(gè)初始解，重復(fù)以上操作，直到得到K個(gè)初始解。

2.1.2 選擇操作

在遺傳算法的迭代過程中，每計(jì)算完一組解的目標(biāo)函數(shù)值后，需要通過選擇操作，從當(dāng)前這組解中選出一組新的解。本文采用輪盤賭的方法，以每個(gè)解的目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度，這樣目標(biāo)函數(shù)值較小的解被選中的概率更大，可以保證更優(yōu)的解被選中加入到下一代種群中。以Sr表示每個(gè)解被選中的概率，Or表示每個(gè)解的目標(biāo)函數(shù)值，m表示種群的規(guī)模，即解的數(shù)量，則Sr可表示如下：

2.1.3 交叉操作

為了保證解的收斂速度更快以及不陷入局部最優(yōu)解，在選擇操作結(jié)束后，需要對(duì)得到的染色體分別進(jìn)行交叉操作。針對(duì)本文所提出的模型設(shè)計(jì)了一個(gè)最短路交叉算子：在兩個(gè)父代染色體φ1、φ2中任選一個(gè)相同的OD 對(duì)，分別找到兩個(gè)染色體中該OD對(duì)之間的自行車最短路徑pwφ1、pwφ2，然后交換兩個(gè)最短路徑中的路段所對(duì)應(yīng)的解的片段，這樣即得到兩個(gè)新的染色體；在K個(gè)解的交叉操作中，分別選取第1個(gè)解與第2個(gè)解交叉，第3個(gè)解與第4個(gè)解交叉……第K個(gè)解與第1個(gè)解交叉。

圖5和圖6以一個(gè)9節(jié)點(diǎn)網(wǎng)絡(luò)為例說明了最短路交叉算子的具體執(zhí)行過程。該9 節(jié)點(diǎn)網(wǎng)絡(luò)包含兩個(gè)OD 對(duì)，分別是1→9 和3→7，其中藍(lán)線和紅線表示連通各OD 對(duì)的自行車專用道路徑（包括新建專用道和機(jī)動(dòng)車禁行道路），其余黑線表示機(jī)動(dòng)車道。圖5 中（a）、（b）兩圖分別表示兩個(gè)不同的解，左邊表示父代染色體為1 時(shí),右邊表示父代染色體為2 時(shí)。在父代染色體1 中，OD 對(duì)1→9 之間的路徑為1→2→5→8→9，OD 對(duì)3→7 之間的路徑為3→2→5→4→7；在父代染色體2 中，OD 對(duì)1→9 之間的路徑為1→4→5→8→9，OD 對(duì)3→7 之間的路徑為3→6→9→8→7。選取OD 對(duì)1→9 為例，交換其自行車最短路徑所包含的路段對(duì)應(yīng)的解的片段，即將父代染色體1 中藍(lán)線與父代染色體2 中藍(lán)線交換可得圖6所示的子代染色體。注意，圖6（a）在交叉算子執(zhí)行后產(chǎn)生了不連通的自行車專用道網(wǎng)絡(luò)。

圖5 父代染色體圖Fig.5 Parent chromosomes

圖6 子代染色體圖Fig.6 Children chromosomes

2.1.4 檢查和修正操作

為了保證解的可行性，在交叉算子執(zhí)行后，必須檢查每個(gè)染色體的自行車網(wǎng)絡(luò)連通性，以保證解的可行性。因此，設(shè)計(jì)了相應(yīng)的連通性檢查和修正算子如下：按照OD 對(duì)順序，檢查每一個(gè)OD 對(duì)的起點(diǎn)是否能連通到網(wǎng)絡(luò)上OD 對(duì)起訖點(diǎn)中的任意點(diǎn)，若所有起點(diǎn)均能連通到其他點(diǎn)，則該網(wǎng)絡(luò)滿足連通性約束；否則找到這個(gè)不連通的點(diǎn)，并找到與不連通點(diǎn)相連的自行車專用道中離起點(diǎn)最近的節(jié)點(diǎn)，將該節(jié)點(diǎn)與起點(diǎn)用自行車專用道連接起來，專用道隨機(jī)采用禁行或者新建的策略，再從每一個(gè)OD 對(duì)的起點(diǎn)開始檢查，直到網(wǎng)絡(luò)連通。

以圖6 為例檢查網(wǎng)絡(luò)連通性。首先以子代染色體2 為例，從第一個(gè)OD 對(duì)的起點(diǎn)1 開始檢查，1可以連接到點(diǎn)3、7、9；再以第二個(gè)OD 對(duì)的起點(diǎn)3開始檢查，3 可以連接到1、7、9。檢查完所有OD對(duì)的起點(diǎn)，每個(gè)起點(diǎn)均連通，因此該自行車網(wǎng)絡(luò)滿足連通性要求。

再以子代染色體1 為例，從第一個(gè)OD 對(duì)起點(diǎn)1 開始檢查，1 連接不到3，因此找到與3 相連的某一點(diǎn)D′，與起點(diǎn)1 相連的某一點(diǎn)O′，使O′→D′距離最短。以圖6 為例假設(shè)D′為2，O′為5，則將2→5用自行車專用道連接起來，連通性修正后如圖7所示，此時(shí)1—3 之間則滿足連通性的要求。為了保證其他點(diǎn)也完全相連，每檢查并更新一次連通性后，需要再次按照OD 對(duì)順序的起點(diǎn)開始檢查。因此再次從第一個(gè)OD 對(duì)起點(diǎn)1 開始檢查，1 可以連接到3、7、9；再檢查第二個(gè)OD 對(duì)起點(diǎn)3，3 可以連接到1、7、9。此時(shí)檢查完畢，整個(gè)自行車專用道設(shè)計(jì)滿足連通性要求，則父代兩條染色體經(jīng)過交叉后得到滿足連通性條件的子代染色體1和2。

圖7 連通的子代染色體Fig.7 Connected children chromosome

2.1.5 變異操作

變異操作可以產(chǎn)生新的基因，擴(kuò)大解的搜索范圍，有助于避免陷入局部最優(yōu)解?？紤]到交叉操作后得到的部分解中會(huì)存在冗余的自行車專用道，因此本文提出了兩種變異算子。變異算子（1）：在當(dāng)前染色體中，隨機(jī)找一個(gè)OD 對(duì)，檢查該OD 對(duì)之間是否存在2 條以上的自行車專用道路徑，若有則更改次短路上的所有路段為機(jī)動(dòng)車道，具體更改方式如圖8的描述所示，次短路由K短路的方法產(chǎn)生，然后檢查和更新自行車專用道網(wǎng)絡(luò)的連通性，方法與2.1.4 所述相同；若無則在該OD對(duì)之間執(zhí)行變異算子（2）。變異算子（2）：設(shè)定一個(gè)初始概率P0，在當(dāng)前染色體中隨機(jī)選擇一個(gè)OD對(duì)之間的最短自行車專用道路徑。在當(dāng)前路徑的每條路段上，對(duì)每一條路段a產(chǎn)生一個(gè)0-1 之間的隨機(jī)數(shù)pa，若pa>P0,則當(dāng)前路段發(fā)生變異。變異規(guī)則為：若當(dāng)前路段為新建自行車道，則改為禁行；若當(dāng)前路段為禁行，則改為新建自行車道。該算子的設(shè)計(jì)方式不僅可以保證解的可行性，還可以更大程度地減少一些不必要的自行車道，從而可以減少建設(shè)成本和提高機(jī)動(dòng)車的通行效率。

圖8展示了變異算子（1）的執(zhí)行過程。該道路網(wǎng)絡(luò)上有3 個(gè)OD 對(duì)，分別是1→9、3→4、3→7。假設(shè)當(dāng)前變異找到的OD對(duì)為1→9，變異前如圖8（a）所示。可知1→9有兩條路徑分別是最短路1→2→5→8→9 和次短路1→2→5→6→9。因此，將1→2→5→6→9 從自行車網(wǎng)絡(luò)上刪去，因?yàn)?→2→5 也包含于路徑1→2→5→8→9中，因此僅刪除5→6→9 即可，然后得到圖8（b）。再采用2.1.4 中檢查和更新網(wǎng)絡(luò)連通性的方法，可得到變異后最終的結(jié)果，如圖8（c）所示。

圖8 變異前、變異中、變異后的道路網(wǎng)絡(luò)Fig.8 Road networks before,during and after mutation

2.2 自適應(yīng)平均算法

自適應(yīng)平均算法（SRAM）是經(jīng)Liu等[23]改進(jìn)相繼平均算法得到的求解隨機(jī)用戶均衡分配的有效算法。該算法對(duì)相繼平均算法中的迭代步長做出了改進(jìn)，相比于給定的迭代步長，自適應(yīng)平均算法中的迭代步長與當(dāng)前解決方案和可行解決方案的距離有關(guān)。避免了相繼平均算法在迭代初期由于步長過大導(dǎo)致的目標(biāo)函數(shù)值到一定的迭代次數(shù)后才下降的缺陷，修正了相繼平均算法在經(jīng)過多次迭代后，迭代步長非常小而使得收斂速度變慢的問題。

為了得到自行車和機(jī)動(dòng)車之間出行模式劃分的比例，本文采用自適應(yīng)平均算法對(duì)Logit 模型進(jìn)行求解。自適應(yīng)平均算法主要包含兩個(gè)重要步驟：一是確定搜索下降方向與迭代步長；二是更新路段流量方案。算法計(jì)算步驟如下所示：

自行車和機(jī)動(dòng)車需求分配的SRAM算法：

輸入：參數(shù)δ、γ、ε令Γ =[T w b , ?w ∈w]，初始化一個(gè)分配的起始概率Γ0（本文中初始化Γ0=0.3），設(shè)置迭代次數(shù)n=1，根據(jù)Frank-Wolfe計(jì)算得到Γ1，令下降方向G0=Γ1, β0=1 While‖ ‖Gn - 1 >ε do根據(jù)Γn計(jì)算機(jī)動(dòng)車和自行車的需求d nb 、d n v，然后再用Frank-Wolfe算法計(jì)算自行車與機(jī)動(dòng)車各自的UE交通分配，得臨時(shí)概率Γ'n，既有下降方向Gn=Γ'n -Γn If‖ ‖Gn ≥‖ ‖Gn-1 then βn=βn-1+δ Else βn=βn-1+γ End if確定步長μn=1/βn更新Γn+1=Γn+μnGn置n=n+1 End while輸出：路段阻抗和Γn

2.3 Frank-Wolfe算法

本文將Frank-Wolfe算法嵌入自適應(yīng)平均算法中分別計(jì)算自行車與小汽車各自的UE 交通分配。Frank-Wolfe 算法是Frank 和Wolfe（1956）[24]提出的求解線性約束下的非線性規(guī)劃問題的一種算法。

Frank-Wolfe 算法應(yīng)用在UE 交通分配時(shí)計(jì)算流程如下：

輸入：精度ε>0基于所有路段的自由流走行時(shí)間，做全有全無交通分配，得到初始的路段流量s0，置迭代次數(shù)k = 0 while G(sk) >ε do以sk為輸入，做全有全無交通分配，得到路段流量s'k置可行下降方向dk = s'k - sk進(jìn)行一維搜索得到最優(yōu)步長λk更新路段流量sk + 1 = sk + λkdk置k = k + 1 end while輸出：sk

該算法在初始化過程中用最短路做全有全無交通分配的時(shí)候，自行車和小汽車路段的阻抗均采用阻抗函數(shù)中的自由流時(shí)間計(jì)算。在UE 交通分配問題的求解過程中，采用式（20）所示的間隙函數(shù)（Gap Function）來評(píng)價(jià)解的精度：

3 算例分析

采用算例分析對(duì)提出算法和模型的準(zhǔn)確性及有效性進(jìn)行分析，以Sioux Falls 網(wǎng)絡(luò)為例進(jìn)行測(cè)試。假設(shè)網(wǎng)絡(luò)上所有的路段都既可以禁行也可以新建機(jī)動(dòng)車專用道，網(wǎng)絡(luò)包含了24 個(gè)節(jié)點(diǎn)和76 條路徑、20個(gè)OD對(duì)，見圖9所示。

圖9 Sioux Falls網(wǎng)絡(luò)Fig.9 Sioux Falls road network

OD 對(duì)之間的需求如表2 所示，每條路段上機(jī)動(dòng)車的自由流走行時(shí)間、路段建設(shè)費(fèi)用如表3 所示。本文提出的所有算法均采用C#編程。在遺傳算法中，設(shè)置種群規(guī)模大小為70，交叉概率為0.7，變異概率為0.3，選擇第一種和第二種變異的概率都分別為0.5，在變異過程中，新建自行車道變?yōu)榻械篮徒械雷優(yōu)樾陆ㄗ孕熊嚨赖母怕识挤謩e為0.5，自行車專用道的通行能力Qb為1600，機(jī)動(dòng)車道的通行能力Qv為1850，最大迭代次數(shù)通過實(shí)驗(yàn)可設(shè)置為3 000 次，自行車的阻抗系數(shù)為0.3，時(shí)間價(jià)值系數(shù)為0.3，θ值為1。在SRAM 算法中，設(shè)置初始的自行車出行概率為0.3，參數(shù)δ= 1.5,γ= 0.01,ε= 0.2。

表2 各OD對(duì)之間的出行需求Tab.2 Travel demandsof different OD pairs

表3 Sioux Falls網(wǎng)絡(luò)中各路段信息Tab.3 Road segments information in the sioux falls network

3.1 模型結(jié)果

Sioux Falls 網(wǎng)絡(luò)求解的結(jié)果如圖10 所示，紅色的為禁行路段，藍(lán)色的為新建自行車專用道路段，包括8 條禁行道路和48 條新建自行車道。從圖10 中可以看出，自行車專用道網(wǎng)絡(luò)覆蓋到了OD 對(duì)所有的起訖點(diǎn)。

圖10 連通的自行車專用道網(wǎng)絡(luò)Fig.10 Connected bike network

圖11 展示了目標(biāo)函數(shù)的收斂過程。遺傳算法在前1 200 次的迭代過程中，結(jié)果收斂較快，之后保持不變，最終收斂在313 765.60 百元處，整個(gè)收斂過程耗時(shí)約10 min。

圖11 目標(biāo)函數(shù)收斂圖Fig.11 Objective function convergence

3.2 模型對(duì)比

表4對(duì)比了自行車網(wǎng)絡(luò)規(guī)劃前、后路網(wǎng)擁擠程度和總阻抗的變化。第二列展示了自行車網(wǎng)絡(luò)規(guī)劃前的結(jié)果，第三列展示了考慮固定需求的模型規(guī)劃自行車網(wǎng)絡(luò)的結(jié)果，即各OD 對(duì)之間的出行需求是固定的，第四列展示了本文所提出模型的結(jié)果。

表4 路網(wǎng)擁擠程度和機(jī)動(dòng)車總阻抗對(duì)比Tab.4 Road network congestion and total vehicle impedance

本文采用的對(duì)整個(gè)網(wǎng)絡(luò)路段的機(jī)動(dòng)車平均擁擠程度的評(píng)價(jià)指標(biāo)公式表示為：

式中：fa表示路段a上的機(jī)動(dòng)車流量；ca表示路段a上機(jī)動(dòng)車的通行能力；A表示路網(wǎng)上機(jī)動(dòng)車道的總數(shù)量。自行車平均擁擠程度評(píng)價(jià)指標(biāo)同理。

由結(jié)果可知在路網(wǎng)上建設(shè)自行車專用道后可以有效減少系統(tǒng)的總阻抗并降低機(jī)動(dòng)車道的平均擁擠程度。本文所提出的需求劃分模型，可以更為準(zhǔn)確地預(yù)測(cè)模式需求，并在此基礎(chǔ)之上進(jìn)一步降低系統(tǒng)總阻抗。

3.3 自行車專用道建設(shè)成本的影響分析

下面分析自行車專用道建設(shè)成本變化時(shí)，自行車專用道網(wǎng)絡(luò)的設(shè)計(jì)情況。在自行車專用道原建設(shè)成本的基礎(chǔ)上，分別以原成本的2 倍、3 倍、4倍、5 倍作為建設(shè)成本，規(guī)劃結(jié)果如圖12 所示。結(jié)果顯示，隨著建設(shè)成本的增加，禁行的機(jī)動(dòng)車道的數(shù)量緩慢增加，而新建自行車專用道數(shù)量則逐漸減少直至不變。這說明當(dāng)路段的建設(shè)成本較小時(shí)，傾向于選擇新建專用道，而當(dāng)路段的建設(shè)成本較大時(shí)，則傾向于選擇禁行機(jī)動(dòng)車的方案。表5展示了不同建設(shè)成本下的最優(yōu)自行車路網(wǎng)規(guī)劃方案的影響。結(jié)果顯示，無論是機(jī)動(dòng)車路網(wǎng)的平均擁擠程度，還是機(jī)動(dòng)車和自行車的阻抗均有所增加，這說明自行車專用道的建設(shè)費(fèi)用會(huì)對(duì)路網(wǎng)以及出行阻抗產(chǎn)生較大影響。

表5 不同建設(shè)成本下道路擁擠情況和出行阻抗Tab.5 Road congestion and travel impedance under different construction costs

圖12 不同建設(shè)成本下的不同建設(shè)規(guī)劃Fig.12 Construction plans under different construction costs

3.4 自行車阻抗系數(shù)的影響分析

在其他參數(shù)相同的情況下，分別選取自行車阻抗系數(shù)φ為0.1、0.3、0.5、0.7、0.9進(jìn)行自行車專用道網(wǎng)絡(luò)規(guī)劃，結(jié)果如圖13所示。

圖13 總阻抗隨阻抗系數(shù)的變化Fig.13 Variation in the total impedance with impedance coefficient

觀察發(fā)現(xiàn)，隨著系數(shù)的增高，自行車和機(jī)動(dòng)車的總阻抗也隨之增加。這是因?yàn)樵谧孕熊囎杩瓜禂?shù)和需求劃分的Logit 模型共同作用下，由于系數(shù)的增加，自行車的阻抗隨之增加，Logit模型中選擇自行車出行的概率會(huì)減小，而選擇機(jī)動(dòng)車出行的概率會(huì)增大，導(dǎo)致機(jī)動(dòng)車的阻抗也隨之增加。由此說明，自行車阻抗權(quán)重系數(shù)會(huì)影響需求劃分，進(jìn)而影響最終的規(guī)劃結(jié)果，因而在實(shí)際規(guī)劃中，需要考慮自行車的阻抗影響。

3.5 交叉和變異概率對(duì)目標(biāo)函數(shù)的影響

在遺傳算法中，交叉和變異概率過高或者過低都會(huì)影響解的收斂。變異概率太小難以產(chǎn)生新的基因，而變異概率太大則會(huì)使算法成為隨機(jī)搜索。染色體的交叉可以產(chǎn)生新的個(gè)體，交叉概率較小時(shí)，產(chǎn)生新個(gè)體的速度較慢，從而收斂較慢；而當(dāng)交叉概率較大時(shí)，會(huì)使高適應(yīng)度的個(gè)體很快被破壞，從而導(dǎo)致收斂效果變差。在迭代次數(shù)都設(shè)為3 000 次，為了保證測(cè)試的準(zhǔn)確性，同時(shí)改變交叉和變異概率的情況下，測(cè)試了不同的交叉和變異概率對(duì)收斂速度的影響。由圖14 可知，在不同的交叉和變異概率下，最小目標(biāo)函數(shù)值存在差異。其中，在變異概率為0.1 而交叉概率為0.3 時(shí)，目標(biāo)函數(shù)值最小（值為304 351.31）。因此在本研究中，交叉、變異概率分別取0.3、0.1較為合適。

圖14 目標(biāo)函數(shù)值隨交叉和變異概率的變化Fig.14 Variation in objective function value with crossover and mutation probabilities

4 總結(jié)

本文提出了一個(gè)基于雙層規(guī)劃模型的老城區(qū)自行車專用道網(wǎng)絡(luò)設(shè)計(jì)問題，上層決策專用道的規(guī)劃，下層分別用Logit 模型和UE 交通分配描述了出行方式選擇行為和路徑選擇行為，并提出嵌入了SRAM 和Frank-Wolfe 的GA 算法對(duì)模型準(zhǔn)確求解。通過算例分析得到了以下結(jié)論：（1）本文所提模型和算法可以有效求解自行車專用道網(wǎng)絡(luò)設(shè)計(jì)。（2）與沒有需求劃分的模型對(duì)比可知，本文提出的模型可以有效地降低路網(wǎng)上的總阻抗，從而緩解交通擁堵。（3）自行車路段的建設(shè)成本、自行車出行阻抗系數(shù)均會(huì)影響最終的自行車網(wǎng)絡(luò)規(guī)劃方案。（4）交叉和變異概率會(huì)影響解的精度，分析表明本文交叉概率取值0.3，變異概率取值0.1較為合適。然而本研究中只考慮了自行車和機(jī)動(dòng)車的出行方式，為了更加符合實(shí)際需求，后續(xù)可以從多種交通方式組合出行、下層問題基于SUE 交通分配求解等方面展開更多的研究。