城市道路交叉口信號配時多目標(biāo)優(yōu)化方法研究

郭鵬飛，徐海黎，樹愛兵，潘臘青，沈　標(biāo)

（1.南通大學(xué) 機械工程學(xué)院，江蘇 南通　226019；2.公安部交通管理科學(xué)研究所，江蘇 無錫　214151；3.南京藍(lán)泰交通設(shè)施有限責(zé)任公司，江蘇 南京　210019）

城市道路交叉口信號配時多目標(biāo)優(yōu)化方法研究

郭鵬飛1，徐海黎1，樹愛兵2，潘臘青1，沈標(biāo)3

（1.南通大學(xué) 機械工程學(xué)院，江蘇 南通226019；2.公安部交通管理科學(xué)研究所，江蘇 無錫214151；3.南京藍(lán)泰交通設(shè)施有限責(zé)任公司，江蘇 南京210019）

摘要：針對目前交叉口信號配時優(yōu)化目標(biāo)單一、綜合運行效率不高的問題，提出一種交叉口信號配時多目標(biāo)優(yōu)化方法?？紤]綠燈時間、周期長度和飽和度等約束條件，通過加權(quán)系數(shù)法定義代價函數(shù)，使交叉口的延誤時間、停車次數(shù)和通行能力在某種程度上達(dá)到最優(yōu)。基于免疫克隆算法在處理多目標(biāo)問題中具有最優(yōu)解分布寬廣性、均勻性好等特點，引入環(huán)境變異算子，提出環(huán)境變異免疫克隆算法對模型求解，增強了算法的全局搜索能力，提高了解的質(zhì)量。仿真結(jié)果表明，與傳統(tǒng)配時方法和改進粒子群算法相比，該文方法能有效減少信號交叉口的延誤時間和停車次數(shù)，提高交叉口的運行效率。

關(guān)鍵詞：交叉口；信號配時；多目標(biāo)優(yōu)化；環(huán)境變異免疫克隆算法

信號交叉口常用的性能評價指標(biāo)有停車次數(shù)、通行能力、延誤、排隊長度、飽和度等［1］。然而，目前國內(nèi)文獻中多以一個性能指標(biāo)（通常是總延誤）對交叉口進行配時優(yōu)化，既無法滿足現(xiàn)實情況中需要滿足多項性能指標(biāo)兼顧的要求，也沒有考慮不同交通狀態(tài)下對多個性能指標(biāo)有所側(cè)重要求，具有一定的局限性［2］。因此，信號交叉口的配時優(yōu)化問題實質(zhì)上是一個多目標(biāo)優(yōu)化的問題。

多目標(biāo)優(yōu)化問題（Multi?objective Optimization Prob?lems，MOP）是指具有兩個及以上的目標(biāo)函數(shù)的最優(yōu)化問題［3］。這些優(yōu)化目標(biāo)往往彼此間難以直接比較，甚至相互對立，一個目標(biāo)的改善甚至有可能引起另一個目標(biāo)性能的降低，因而難以同時達(dá)到最優(yōu)。

針對這些問題，本文選取延誤時間、停車次數(shù)和最大通行能力作為信號控制目標(biāo)，建立了相應(yīng)的單交叉口多目標(biāo)優(yōu)化信號配時優(yōu)化模型，并提出了基于環(huán)境變異免疫控制算法（Environment Mutation Immune Clone Al?gorithm，EMICA）的多目標(biāo)控制方法。通過該算法協(xié)調(diào)好這三個控制目標(biāo)的平衡，從而得到實時的多目標(biāo)最優(yōu)解，進而得到最佳的控制策略。

1　交叉口多目標(biāo)信號配時優(yōu)化模型

本文在研究單點道路交叉口的信號配時時，假設(shè)交通流數(shù)據(jù)（如每個車道的機動車交通量）已經(jīng)獲得，非機動車及行人已轉(zhuǎn)換成當(dāng)前交通量。

1.1多目標(biāo)信號配時模型

交叉口信號控制的優(yōu)化目標(biāo)包括延誤時間、停車次數(shù)、最大通行能力、飽和度、油耗、尾氣排放等。其中尤以前4項最為重要，一般來說其他項均可以由這幾項導(dǎo)出［4?5］。因此，本文把交叉口的總延誤、總停車次數(shù)、最大通行能力三個指標(biāo)作為優(yōu)化對象，以飽和度為約束，利用加權(quán)的方法合并成目標(biāo)函數(shù)并求解。假設(shè)交叉口信號有n個相位，下面是信號配時中需要優(yōu)化三個指標(biāo)的函數(shù)表達(dá)式，將各相位的有效綠燈時間作為自變量：

（1）延誤時間計算。延誤時間是指在交叉口處由于交通流沖突或信號燈控制引起的行駛時間損失。韋伯斯特（Webster）提出了延誤時間的計算公式［6?7］如下：

式中：Di表示第i相位的車輛平均延誤時間，單位為s；C為周期，單位為s；λi為綠信比表示第i相位有效綠燈時間與信號周期的比值；yi為第i相位的相位流量比；qi為第i相位的相位車流到達(dá)率，單位為pcu/h。

（2）停車率計算。采用穩(wěn)態(tài)模型［8?9］計算進入交叉口每輛車輛的平均停車次數(shù)，如式（2）所示：

式中：Hi表示第i相位的車輛平均起停次數(shù)；Ni表示在未飽和交叉口，某相位的平均滯留車輛數(shù)。

（3）通行能力計算。采用HCM2000理論［5，10］，先將交叉口各進口道劃分為若干車道組，然后計算各車道組的通行能力：

式中：Qi表示第i相位的通行能力；Si為車道組i的飽和流率。

1.2目標(biāo)函數(shù)

將以上三個函數(shù)通過加權(quán)的方法轉(zhuǎn)化為目標(biāo)函數(shù)進行求解：

式中，ξi表示第i個目標(biāo)函數(shù)的權(quán)重系數(shù)。

為了使建立的優(yōu)化模型更好地符合實際狀況，模型應(yīng)能夠根據(jù)不同交通狀態(tài)對各指標(biāo)有所側(cè)重：如交通狀態(tài)趨向擁擠時要確保發(fā)揮路口的最大通行能力，而非擁擠狀態(tài)時應(yīng)盡可能減少路口信號控制的延誤和停車次數(shù)。首先評判這幾個指標(biāo)的相對重要性，根據(jù)式（5）、式（6）建立相應(yīng)的模糊矩陣R=r（i，j），其中r（i，j）表示i相對于 j的重要性，并根據(jù)式（7）、式（8）求解。

令：

進行歸一化后可得：

這種利用模糊矩陣的加權(quán)系數(shù)法對三個性能指標(biāo)進行平衡，大大降低了交警設(shè)置指標(biāo)權(quán)重的復(fù)雜程度和主觀性，從而通過調(diào)整 ξi的值使得交叉口在不同交通狀態(tài)下均能在某種程度上達(dá)到最優(yōu)。

1.3約束條件

為了保證行人和行車安全，需要在配時前添加一定的約束條件，由式（9）～式（11）給出。

（1）綠燈時間約束［1］。一般情況下，有效綠燈時間最小不小于12 s，最大不大于100 s。

（2）周期約束［1］。信號周期過短會對行人車輛安全通過交叉口造成威脅，過大也不會增加通行能力，所以一般最短信號周期時長可取30～40 s，最大不大于180 s。

（3）飽和度約束［1］。因在過飽和情況下，采用優(yōu)化算法往往也難以起到良好的優(yōu)化效果，而飽和度在0.7 和0.9之間時，交叉口可以獲得較好的運行條件，故飽和度取0.7～0.9。

2　信號配時優(yōu)化算法

本文所要解決的多目標(biāo)約束優(yōu)化問題可以定義如下［11］：

2.1代價函數(shù)設(shè)計

由于配時優(yōu)化模型中約束條件的存在，需要進行約束處理。而罰函數(shù)法是處理約束條件最常用的方法之一，故采用罰函數(shù)的方式來處理，代價函數(shù)可寫為：

式中：rg為懲罰系數(shù)；?（A）為罰函數(shù)。

雖然罰函數(shù)法有著簡單易行的優(yōu)點，但實際上選取合適的懲罰系數(shù)相當(dāng)困難。懲罰系數(shù)rg太小可能導(dǎo)致懲罰力度過小，影響優(yōu)化函數(shù)的尋優(yōu)方向［11?12］；懲罰系數(shù)rg過大則會引發(fā)計算的困難容易引起早熟收斂［13］；因此，如何選擇合適的懲罰系數(shù)rg或懲罰函數(shù)的形式是解決有約束優(yōu)化問題的關(guān)鍵。罰函數(shù)可以調(diào)節(jié)個體的適應(yīng)度值，對群體的排序產(chǎn)生影響。文獻［14］中采用概率排序的形式，使得群體在目標(biāo)函數(shù)和約束條件中得到動態(tài)的平衡。本文在參考文獻［14］核心思想的同時，也制定了以下三條規(guī)則，以能夠保證目標(biāo)函數(shù)值小、約束條件值也不大個體的基因也有機會在群體中傳播［11?12］：

（1）當(dāng)兩個個體都符合約束條件時，目標(biāo)函數(shù)值小的排序靠前；

（2）當(dāng)兩個個體有一個不符合約束條件時，目標(biāo)函數(shù)值小而且約束條件值小的排序靠前；

（3）當(dāng)兩個個體有一個不符合約束條件且目標(biāo)函數(shù)值小與約束條件值小條件不同時成立時，則以約束條件的比值為概率，隨機排序。

2.2環(huán)境變異免疫克隆算法算子描述

免疫克隆算法是近年來新興的進化算法之一。人們受生物免疫系統(tǒng)的啟發(fā)，通過對免疫應(yīng)答過程及免疫細(xì)胞克隆的模擬而提出的一種啟發(fā)式搜索算法。它提供噪聲忍耐、自組織、記憶等學(xué)習(xí)機理，具有保持群分布多樣性的特點［15］。免疫克隆算法較成功地解決了多目標(biāo)優(yōu)化中最優(yōu)解分布的寬廣性、均勻性及向著最優(yōu)Pa?reto?前端逼近等問題。本文借鑒了免疫克隆算法在解決多目標(biāo)優(yōu)化問題中的優(yōu)勢，并基于以前的工作，利用EMICA算法來解決有交叉口信號控制的優(yōu)化問題。本文信號配時優(yōu)化算法的核心就是EMICA算法。基于EMICA算法的多目標(biāo)尋優(yōu)步驟如下，詳細(xì)步驟［12］如下：

（1）初始化。初始化抗體群，設(shè)定算法參數(shù)，抗體號i=1，進化代數(shù)t=0；

（2）疫苗選擇TCs。在人類免疫系統(tǒng)中，抗原一般指問題及其約束，抗體一般是指問題的候選解［16?17］，疫苗則是由先驗知識而得到的對最佳個體基因的估計。在EMICA算法中將每代親和度最高的抗體認(rèn)為是疫苗：

式中：APt為第t代的抗體集；N為種群規(guī)模。

式中，Ik為k維單位行矩陣；k為克隆規(guī)模。

式中：E為環(huán)境變量；r1為學(xué)習(xí)系數(shù)；r2為遺忘系數(shù)；r3為修改系數(shù)。

（7）判斷。判斷是否滿足終止條件，不滿足終止條件則返回步驟（3），并將前一個時刻的最終抗體群作為下一個時刻的初始種群，若滿足終止條件則算法結(jié)束。

3　仿真結(jié)果及分析

為了驗證本文方法的有效性，以典型的四相位信號交叉口為例（即假設(shè)右轉(zhuǎn)車流不受信號控制），計算各相位的有效綠燈時間，信號控制方案如圖1所示，交叉口各進口各向交通量如表1所示［8］，其中非機動車交通量已經(jīng)換算為標(biāo)準(zhǔn)小轎車交通量。

程序采用VC++6.0語言編寫。參數(shù)設(shè)置：群體規(guī)模N=200，克隆規(guī)模k=5，變異概率pm=0.01，環(huán)境變量學(xué)習(xí)參數(shù)r1=random（0.0，1.2），環(huán)境變量遺忘參數(shù)r2=ran?dom（0.6，0.7），環(huán)境變量修改參數(shù)r3=random（0.0，1.4）。采用連續(xù)100代不能提高群體的最優(yōu)解時停止為算法終止條件。其中，最小周期和最大周期分別為40 s和180 s，總損失時間為16 s，飽和度限制在0.7～0.9之間。原配時方案得到的結(jié)果，利用文獻［8］提出的改進粒子群算法優(yōu)化得到的結(jié)果，及采用本文提出的算法優(yōu)化后的結(jié)果如表2所示。

圖1　相位信號交叉口信號控制方案

表1　交叉口各進口交通量

表2　優(yōu)化結(jié)果比較

由表2可以看出，與原有配時方案相比，經(jīng)過兩種算法優(yōu)化后總延誤和總停車次數(shù)兩個指標(biāo)均得到一定程度的改善。原方案的總延誤為16 648 s，經(jīng)改進粒子群算法優(yōu)化后最小延誤為10 683 s，比原方案減少了35.8%，而經(jīng)本文算法優(yōu)化后的最小延誤為9 883 s，較原方案降低了40.6%。原方案總停車次數(shù)為212次，經(jīng)改進粒子群算法優(yōu)化后最小停車次數(shù)為170次，比之前降低了19.8%，而經(jīng)本文算法優(yōu)化后的最小停車次數(shù)為163次，較原方案降低了23.1%?？梢钥闯鲈诳傃诱`和總停車次數(shù)兩個指標(biāo)上，本文算法的優(yōu)化結(jié)果均好于改進粒子算法得到的結(jié)果。但由于交叉口周期時長的減小，從而使交叉口最大通行能力有所下降，可由于本文不探討交叉口過飽和度的通行狀態(tài)，一般達(dá)不到交叉口的最大通行能力，可以說交叉口最大通行能力的略微下降對整個交叉口的運行效率幾乎無影響。綜上所述，兩種算法在優(yōu)化結(jié)果上均取得了較好的結(jié)果，但本文算法在處理交叉口信號控制多目標(biāo)優(yōu)化的綜合性能要強于改進粒子群算法優(yōu)化。

4　結(jié)　論

進行信號配時優(yōu)化時，綜合考慮了交叉口的總延誤時間、總停車次數(shù)和最大通行能力三個常用評價指標(biāo)，并應(yīng)用加權(quán)的方法定義了目標(biāo)函數(shù)，克服了以往優(yōu)化方法目標(biāo)過于單一的缺點，更加符合實際環(huán)境中多項性能指標(biāo)的控制需求。使用模糊矩陣的方法來確定三個性能指標(biāo)的權(quán)重系數(shù)，簡化了人們對指標(biāo)權(quán)重判斷的復(fù)雜性和主觀性，解決了在不同交通狀態(tài)下確定權(quán)重的方法一致性問題。算法性能上，引入了多目標(biāo)問題求解上有諸多優(yōu)勢的免疫克隆算法，并在其中融合了環(huán)境變異算子，將環(huán)境對個體進化的影響積累到克隆變異操作中，提高了免疫克隆算法的搜索效率和穩(wěn)定性。對典型的四相位信號交叉口信號配時的仿真結(jié)果表明，與現(xiàn)有算法相比，本文算法更能夠得到高質(zhì)量的解，有助于緩解交通擁堵的狀況。下一步的研究工作是將提出的基于環(huán)境變異免疫克隆算法的交叉口信號控制多目標(biāo)優(yōu)化方法在實際交叉口中加以應(yīng)用，利用前期開發(fā)的視頻車檢器獲取交通流量等信息，從而使交叉口通行更為順暢，同時也更加節(jié)能和環(huán)保。

參考文獻

［1］王錦錦.改進交叉口性能評價及多目標(biāo)優(yōu)化配時研究［D］.重慶：重慶大學(xué)，2012.

［2］曹成濤，徐建閩.單交叉口交通多目標(biāo)控制方法［J］.計算機工程與應(yīng)用，2010，46 （16）：20?22.

［3］王光遠(yuǎn).城市交通信號多目標(biāo)自適應(yīng)控制［D］.大連：大連理工大學(xué)，2010.

［4］蘇長慧，夏桂梅.基于改進微粒群算法的單點信控交叉口配時優(yōu)化［J］.太原科技大學(xué)學(xué)報，2014，35（3）：198?201.

［5］曹娟娟，卲維.基于改進粒子群算法的多目標(biāo)單交叉口信號優(yōu)化控制［J］.長沙大學(xué)學(xué)報，2012，26（2）：69?71.

［6］伍尚昆，陳翠宜，祝勝林.基于多種群蟻群算法的交叉路口信號配時優(yōu)化［J］.計算機應(yīng)用與軟件，2014，31（5）：83?88.

［7］崔明月，劉紅釗，劉偉，等.改進的非劣遺傳算法在多目標(biāo)優(yōu)化中的應(yīng)用［J］.南陽師范學(xué)院學(xué)報，2014，13（12）：8?12.

［8］劉金明.基于多目標(biāo)規(guī)劃的城市道路交叉口信號配時研究［D］.北京：北京交通大學(xué)，2011.

［9］肖婧，王科俊，畢曉君.交叉口混合交通流高維多目標(biāo)信號優(yōu)化控制［J］.公路交通科技，2014，31（11）：108?115.

［10］陳小紅.混合交通環(huán)境下城市道路交通信號控制優(yōu)化模型研究［D］.北京：北京交通大學(xué)，2012.

［11］徐海黎，解祥榮，莊健，等.工業(yè)機器人的最優(yōu)時間與最優(yōu)能量軌跡規(guī)劃［J］.機械工程學(xué)報，2010，46（9）：19?25.

［12］徐海黎，朱志松，王恒，等.環(huán)境變異免疫克隆算法解決有約束優(yōu)化問題［J］.系統(tǒng)仿真學(xué)報，2011，23（11）：2412?2416.

［13］焦李成，尚榮華，馬文萍，等.多目標(biāo)優(yōu)化免疫算法、理論和應(yīng)用［M］.北京：科學(xué)出版社，2010：114.

［14］RUNARSSON Thomas Philip，YAO Xin.Stochastic ranking for constrained evolutionary optimization［J］.IEEE transac?tions on evolutionary computation（S1089?778X），2000，4（3）：284?294.

［15］尚榮華，焦李成，公茂果，等.免疫克隆算法求解動態(tài)多目標(biāo)優(yōu)化問題［J］.軟件學(xué)報，2007，18（11）：2700?2711.

［16］秦亮，張文廣，史賢俊，等.基于免疫克隆算法的多目標(biāo)聚類方法［J］.信息與控制，2013，42（1）：8?12.

［17］林滸，彭勇.面向多目標(biāo)優(yōu)化的適應(yīng)度共享免疫克隆算法［J］.控制理論與應(yīng)用，2011，28（2）：206?214.

中圖分類號：TN911?34；U491

文獻標(biāo)識碼：A

文章編號：1004?373X（2016）16?0019?04

doi：10.16652/j.issn.1004?373x.2016.16.005

作者簡介：郭鵬飛（1990—），男，江蘇邳州人，碩士研究生。主要研究方向為機電系統(tǒng)的智能控制與信息處理。徐海黎（1973—），女，江蘇海安人，教授，博士。主要研究方向為機電系統(tǒng)的智能控制與信息處理。樹愛兵（1980—），男，助理研究員，碩士。主要研究方向為交通信號控制、交通信息集成。

收稿日期：2015?12?24

基金項目：2013年度國家火炬計劃立項項目（6002013GH010579）；科技型中小企業(yè)技術(shù)創(chuàng)新（12C26213202144）

Multi?objective optimization method for signal timing of urban traffic intersection

GUO Pengfei1，XU Haili1，SHU Aibing2，PAN Laqing1，SHEN Biao3
（1.School of Mechanical Engineering，Nantong University，Nantong 226019，China；2.Traffic Management Research Institute of Public Security Ministry，Wuxi 214151，China；3.Nanjing Lantai Traffic Establishment Co.，Ltd.，Nanjing 210019，China）

Abstract：To solve the problems of single optimization objective and low efficiency in signal timing，a novel multi?objective optimization method for signal timing of intersections is proposed.In consideration of constraint conditions of green?light dura?tion，cycle length and saturability，the cost function is defined by weighted coefficient method to make delay time，parking times and traffic capacity of intersections optimum to some extent.Based on the characteristics of uniformity and wide?distribu?tion of optimal solution while immune clone algorithm（ICA）is used to solve multi?objective problems，a new environment muta?tion operator was introduced，and the environment mutation ICA was proposed for model solution，which enhanced the global searching ability of the algorithm and improved the solution quality.The simulation results reveal that，compared with the tradi?tional timing method and inertia weight particle swarm algorithm，the presented method can efficiently reduce average delay，parking times of intersections，and improve the efficiency of traffic signal control.

Keywords：intersection；signal timing；multi?objective optimization；environment mutation immune clone algorithm