城市交通中左轉(zhuǎn)禁限的雙層規(guī)劃模型

張　珊,　樊慧敏

(長(zhǎng)春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院， 吉林 長(zhǎng)春　130012)

?

城市交通中左轉(zhuǎn)禁限的雙層規(guī)劃模型

張珊,樊慧敏*

(長(zhǎng)春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院， 吉林 長(zhǎng)春130012)

摘要：研究了左轉(zhuǎn)禁限對(duì)交通路網(wǎng)的影響,并應(yīng)用雙層規(guī)劃建立數(shù)學(xué)模型,通過(guò)遺傳算法對(duì)模型進(jìn)行求解,從而得到最優(yōu)解。

關(guān)鍵詞：交叉口; 左轉(zhuǎn)禁限; 雙層規(guī)劃; 遺傳算法

0引言

交通網(wǎng)絡(luò)是一個(gè)城市的血脈,它與居民的生活息息相關(guān),所以交通擁堵成為急需解決的一個(gè)問(wèn)題,我國(guó)很多學(xué)者基于交通網(wǎng)絡(luò)提出了轉(zhuǎn)彎禁限措施,并對(duì)其進(jìn)行建模求解。例如,陳寬民[1]等對(duì)交通流中左轉(zhuǎn)車(chē)流在交叉口的沖突特點(diǎn)做了詳細(xì)的分析;王偉娟[2]等對(duì)交叉口的禁左限制做了深入研究;龍科軍[3]和龍建成[4]等對(duì)交通網(wǎng)絡(luò)中左轉(zhuǎn)禁限問(wèn)題建立了雙層規(guī)劃模型,并研究了如何用遺傳算法對(duì)雙層規(guī)劃模型求解。但是這些研究理論以及其在實(shí)踐中的應(yīng)用并不十分完善,也存在著許多問(wèn)題[5]。例如,我們通常都是在平面交叉口[6]的前提下考慮左轉(zhuǎn)禁限問(wèn)題的,而對(duì)于其他形式的交叉口并沒(méi)有考慮,或者是在對(duì)轉(zhuǎn)彎禁限研究的過(guò)程中忽略了行人對(duì)交通網(wǎng)絡(luò)的影響。文中以交叉口是否設(shè)置左轉(zhuǎn)禁限為變量,建立了雙層規(guī)劃模型,上層規(guī)劃以交通路網(wǎng)中車(chē)流運(yùn)行的總時(shí)間最小為目標(biāo)函數(shù),下層規(guī)劃以靜態(tài)用戶均衡模型作為目標(biāo)函數(shù),通過(guò)改進(jìn)的遺傳算法對(duì)模型進(jìn)行求解,從而得到最適合進(jìn)行左轉(zhuǎn)禁限的交叉口。

1雙層規(guī)劃模型的建立

1.1前提假設(shè)

為了方便考慮和建立模型,不妨假設(shè)[7]:

1)在交通網(wǎng)絡(luò)中,每條道路的通行能力都是一定的。

2)城市的交通網(wǎng)絡(luò)在實(shí)施左轉(zhuǎn)禁限后,路網(wǎng)中的車(chē)道劃分以及信號(hào)燈的調(diào)整符合新的交通運(yùn)行情況。

1.2交叉口的選擇

在左轉(zhuǎn)禁限問(wèn)題中交叉口的選擇至關(guān)重要,如果交叉口選擇不當(dāng),不僅耗費(fèi)大量的人力物力,而且會(huì)給出行者帶來(lái)極大的不方便。如何備選合適的交叉口可以依據(jù)以下幾點(diǎn)考慮:

1)觀察與交叉口相鄰的道路,如果交叉口與其相鄰的道路關(guān)系單一,呈放射性形狀,那么由于此交叉口的獨(dú)立性不適宜設(shè)置禁限;如果交叉口與其相鄰的道路關(guān)系復(fù)雜且充分冗余,呈網(wǎng)狀形狀,那么此交叉口處可以考慮設(shè)置禁限。

2)一般選擇車(chē)流量大的交叉口進(jìn)行設(shè)限,而對(duì)于車(chē)流量小的交叉口不予考慮[8]。

1.3模型的建立

1.3.1上層規(guī)劃模型

(1)

(2)

(3)

(4)

式中:xab----路段a轉(zhuǎn)向到路段b的車(chē)流量;

tab----車(chē)輛由路段a轉(zhuǎn)向到路段b時(shí)的時(shí)間函數(shù);

xa----路段a的車(chē)流量;

ta----車(chē)輛通過(guò)路段a的時(shí)間函數(shù);

y----0-1變量,當(dāng)y=1時(shí),表示禁止左轉(zhuǎn),當(dāng)y=0時(shí),表示左轉(zhuǎn);

Sa----路段a的飽和度;

Sab----交叉口ab處的飽和度;

ca----路段a的通行能力;

cab----交叉口ab處的通行能力;

A----所有路段的集合;

xa,xab----y的隱函數(shù)。

目標(biāo)函數(shù)表示的是整個(gè)路網(wǎng)所有車(chē)輛運(yùn)行的時(shí)間總和最小。

1.3.2下層規(guī)劃模型

1952年著名學(xué)者Wardrop提出了交通網(wǎng)絡(luò)平衡定義的第一原理和第二原理，奠定了交通流分配的基礎(chǔ)。許多研究學(xué)者根據(jù)這一原理分析了交通網(wǎng)絡(luò)流的平衡問(wèn)題[9-11],下層規(guī)劃模型可采用用戶均衡分配模型[12-13]。

目標(biāo)函數(shù)表示整個(gè)路網(wǎng)上的交通流量最小。

(5)

(6)

(7)

(8)

(9)

式中:R----出發(fā)點(diǎn)的集合;

S----目的地的集合;

qrs----連接O-D對(duì)r-s的出行需求;

1.4模型的求解

雙層規(guī)劃問(wèn)題是一個(gè)NP-hard問(wèn)題,這使得對(duì)雙層規(guī)劃模型的求解十分困難。由于文中所建立的雙層規(guī)劃模型包含了大量的二進(jìn)制變量,而且需要處理大量的數(shù)據(jù)尋求全局最優(yōu)解,所以,文中決定選用遺傳算法[14-16]來(lái)求解雙層規(guī)劃模型。

求解步驟如下:

1)編碼。選定n個(gè)交叉口并按順序排列,隨機(jī)產(chǎn)生一個(gè)長(zhǎng)度為n的二進(jìn)制串表示一個(gè)個(gè)體,其中每一位對(duì)應(yīng)一個(gè)交叉口。編碼1表示對(duì)應(yīng)的交叉口禁左,編碼0表示不禁左。

2)產(chǎn)生初始種群。一般隨機(jī)產(chǎn)生20～50個(gè)群體。

3)適度函數(shù)

式中:G0----沒(méi)有禁左的情況下交通網(wǎng)絡(luò)的總阻抗。

4)選擇。根據(jù)優(yōu)勝劣汰的法則采用輪盤(pán)賭對(duì)種群進(jìn)行選擇,選出的優(yōu)良個(gè)體作為父代繁殖子孫。

5)將種群中的個(gè)體配對(duì)。隨機(jī)選定一個(gè)交叉位,將所有配對(duì)的染色體組該位置的基因互換。

6)變異。隨機(jī)在基因串上選取一個(gè)位置,使該位置上的數(shù)字邏輯相反,即“1”變成“0”,“0”變成“1”。

7)終止條件

Fmax----所有個(gè)體中的最大適應(yīng)值。

2實(shí)例論證

選取太原市某一區(qū)域路段為研究對(duì)象,應(yīng)用文中模型對(duì)其制定禁限方案。道路路網(wǎng)如圖1所示。

圖1道路路網(wǎng)

把圖中的交叉口按順序進(jìn)行編碼,得到備選方案集h,種群數(shù)取50,交叉率為pc=0.5,變異率為pm=0.1,迭代50次。交叉口交通運(yùn)行情況見(jiàn)表1。

表1　交叉口運(yùn)行情況表

借助Matlab對(duì)模型求解得最優(yōu)解為h={0011110000100000}。

3結(jié)語(yǔ)

研究了城市交通路網(wǎng)中交叉口設(shè)置左轉(zhuǎn)禁限的問(wèn)題,根據(jù)交通路網(wǎng)中交通流的特性建立了雙層規(guī)劃模型,并通過(guò)遺傳算法對(duì)其求解。以太原市某一局域網(wǎng)為例,根據(jù)文中所建立的模型通過(guò)Matlab工具得出了相應(yīng)的禁限路口。

參考文獻(xiàn)：

[1]陳寬民,羅志忠.平面交叉口左轉(zhuǎn)車(chē)流的特性分析及對(duì)策研究[J].公路交通技術(shù),2006,4(2):114-118.

[2]王娟.網(wǎng)絡(luò)變結(jié)構(gòu)控制在交叉口流向禁限管理中的應(yīng)用[D].上海:同濟(jì)大學(xué),2008.

[3]龍科軍.道路網(wǎng)路交叉口禁左交通組織優(yōu)化[J].北京工業(yè)大學(xué)學(xué)報(bào),2011,6(6):876-881.

[4]龍建成.城市道路交通擁堵傳播規(guī)律及消散控制策略研究[J].上海理工大學(xué)學(xué)報(bào),2011,33(6):701-710.

[5]張紅軍.基于交通瓶頸的動(dòng)態(tài)交通分配模型[J].系統(tǒng)工程理論與實(shí)踐,2006,26(4):125-129.

[6]盧明宇，王興.交叉口交通擁堵分析與對(duì)策[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào),2015,36(3):327-332.

[7]高自友,任華玲.城市動(dòng)態(tài)交通流分配模型與算法[M].北京:人民交通出版社,2005.

[8]胡致涌,楊榮華.城市交通控制中的智能計(jì)算[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2013,34(6):681-685.

[9]劉法勝，吳大為，傅白白.組合式Wardrop條件下的交通網(wǎng)絡(luò)流平衡[J].中國(guó)公路學(xué)報(bào)，2000，13(1)：98-99.

[10]徐建閩，許倫輝.交通分配問(wèn)題中用戶優(yōu)化平衡模型的算法研究[J].中國(guó)公路學(xué)報(bào)，1998，11(4)：93-99.

[11]杜先漢.基于單向和禁左的區(qū)域交通組織研究[D].西安:西安交通大學(xué)，2009.

[12]李江.交通工程學(xué)[M].北京:人民交通出版社，2002.

[13]張紅軍.城市道路交叉口轉(zhuǎn)彎禁限研究[D].蘭州:蘭州交通大學(xué)，2013.

[14]袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京:科學(xué)出版社，1997.

[15]張文修，梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)[M].西安:西安交通大學(xué)出版社，2003.

[16]王小平，曹立明.遺傳算法----理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社，2002.

Bi-levelprogrammingmodelforleftturnrestrictioninurbantraffic

ZHANGShan,FANHuimin*

(SchoolofBasicSciences,ChangchunUniversityofTechnology,Changchun130012,China)

Abstract：Theimpactofleftturnonthetrafficnetworkisstudied,andamathematicalmodelisestablishedwiththebi-levelprogramming.Thegeneticalgorithmisusedtoobtaintheoptimalsolutionforthemodel.

Keywords：intersection;leftturnprohibition;bi-levelprogramming;geneticalgorithm.

收稿日期：2015-12-05

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(11126239，11401046)

作者簡(jiǎn)介：張珊(1980-)，女，漢族，吉林松原人，長(zhǎng)春工業(yè)大學(xué)副教授,博士，主要從事最優(yōu)化理論與算法方向研究,E-mail:zhangshan@ccut.edu.cn. *通訊作者：樊慧敏(1990-)，女，漢族，山西原平人，長(zhǎng)春工業(yè)大學(xué)碩士研究生，主要從事最優(yōu)化理論與算法方向研究,E-mail:409847404@qq.com.

DOI:10.15923/j.cnki.cn22-1382/t.2016.3.02

中圖分類(lèi)號(hào)：U121

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-1374(2016)03-0217-04