張　珊,　樊慧敏

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

?

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

張珊,樊慧敏*

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

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

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

0引言

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

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

1.1前提假設(shè)

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

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

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

1.2交叉口的選擇

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

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

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

1.3模型的建立

1.3.1上層規(guī)劃模型

(1)

(2)

(3)

(4)

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

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

xa----路段a的車流量;

ta----車輛通過路段a的時間函數(shù);

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

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

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

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

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

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

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

目標函數(shù)表示的是整個路網(wǎng)所有車輛運行的時間總和最小。

1.3.2下層規(guī)劃模型

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

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

(5)

(6)

(7)

(8)

(9)

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

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

qrs----連接O-D對r-s的出行需求;

1.4模型的求解

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

求解步驟如下:

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

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

3)適度函數(shù)

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

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

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

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

7)終止條件

Fmax----所有個體中的最大適應值。

2實例論證

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

圖1道路路網(wǎng)

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

表1　交叉口運行情況表

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

3結(jié)語

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

參考文獻：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Bi-levelprogrammingmodelforleftturnrestrictioninurbantraffic

ZHANGShan,FANHuimin*

(SchoolofBasicSciences,ChangchunUniversityofTechnology,Changchun130012,China)

Abstract：Theimpactofleftturnonthetrafficnetworkisstudied,andamathematicalmodelisestablishedwiththebi-levelprogramming.Thegeneticalgorithmisusedtoobtaintheoptimalsolutionforthemodel.

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

收稿日期：2015-12-05

基金項目：國家自然科學基金資助項目(11126239，11401046)

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

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

中圖分類號：U121

文獻標志碼：A

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