随着社会经济的迅速发展, 城市中的机动车辆不断增加, 导致城市交通量猛增, 无论是在发达国家还是发展中国家, 交通拥挤加剧、交通事故频繁、交通环境恶化等问题变得日趋严重.交叉口往往是城市交通瓶颈所在地, 当交通流量达到一定程度时, 需设置信号控制灯, 以便从时间上分离相互冲突、交织的交通流, 使车辆在交叉口运行通畅、减少交通事故、减少或避免交叉口的拥堵.交通信号配时是减少城市交通延误、提高道路利用率、减少交通事故以及环境污染的最有效方法之一, 是减小城市道路网络上的车辆延误、有效利用道路设施、降低交通事故、减小环境污染和燃油消耗等的有效手段, 是城市交通管理最有力的工具.由于信号配时直接决定路口的通行能力及路口延误时间, 因而必然影响道路使用者的路径选择行为, 从而最终影响到路网上的交通流分配, 而交通流的分配形态又反过来影响交叉口的信号配时, 信号灯的合理配时是实现有效控制的关键.信号配时就是根据交叉口的道路情况及交叉口各进口道车辆流向和流量来确定信号周期时长在各相位的分配方案.

Allsop最早于1974年提出了基于平衡交通分配的区域信号配时问题^[1], 将交叉口信号控制与道路使用者的路径选择问题相结合. Fisk在1984年提出了一般形式的二层规划模型^[2], 其中下层是一个非线性互补问题, Yang and Yagar研究了拥挤排队网络中区域信号配时的二层规划模型^[3], 下层是带路段容量约束的平衡交通分配问题, 文献[4]则建立了基于一般相位结构的区域信号配时二层规划模型, 下层是一个随机用户平衡分配模型.以上对于信号配时问题的研究中, 其下层都是平衡交通分配问题, 本文针对文献[4]中的信号配时模型, 提出一种新的求解算法, 对下层问题采用非平衡交通分配.

文献[4]提出的基于一般相位结构下的区域信号配时二层规划模型：

上层信号配时模型

$ \begin{eqnarray*} && \min\sum\limits_{a\in A}[x_at_a(x_a, \lambda_{j(a)})+\sum\limits_{i\in I_{j(a)}}x_{ai}d_{ai}(x_{ai}, \lambda_{ij(a)})], \\ && {\hbox{ s.t.}}\left\{ \begin{array}{ll} \sum\limits_{i\in I_{j(a)}}\lambda_{ij(a)}=1,&\forall a\in A, \\ \lambda_{ij(a)}^{\min}\le\lambda_{ij(a)}\le\lambda_{ij(a)}^{\max}, &\forall i\in I_{j(a)}, \forall a\in A, \end{array} \right. \end{eqnarray*} $

其中 $x_a$为路段 $a$上总的车流量, $j(a)$表示路段 $a$对应的交叉口(即路段 $a$的出口), $I_{j(a)}$为交叉口 $j(a)$的相位集合, 而 $m=|I_{j(a)}|$表示 $I_{j(a)}$中所含相位个数; $X_a=(x_{a1}, x_{a2}, \cdots, x_{am})$是路段 $a$上车流按相位分流后构成的车流向量, $\lambda_{j(a)}=(\lambda_{1j(a), \lambda_{2j(a)}, \cdots, \lambda_{mj(a)}})$为路段 $a$对应的交叉口的各相位绿信比向量; $t_a(x_a, \lambda_{j(a)})$表示路段 $a$上的行驶时间, 其函数关系式已知; 而 $d_{ai}(x_{ai}, \lambda_{ij(a)})$为路段 $a$上第 $i$相位车流在交叉口遭遇的延误, 其表达式也已知; 上层模型中的 $x_a, x_{ai}$等需要通过求解下层模型来获得.

下层随机用户平衡分配模型

$ \begin{eqnarray*}&& \min\sum\limits_\omega\sum\limits_kf_k^{\omega}(lnf_k^{\omega}-1)+\alpha\sum\limits_{a\in A}\int_0^at_a(\omega, \lambda_{ij(a)})d\omega, \\ && {\hbox{ s.t.}}\left\{ \begin{array}{ll} \sum\limits_kf_k^{\omega}=q_{\omega},&\forall \omega\in W, \\ f_k^{\omega}>0, &\forall k\in R_{\omega}, \forall \omega\in W, \\ \sum\limits_\omega\sum\limits_k\delta_{ak}^{\omega}f_k^{\omega}=x_a, &\forall a\in A, \\ \sum\limits_\omega\sum\limits_k\delta_{ak}^{\omega i}=x_{ai}, & \forall i\in I_{j(a)}, \forall a\in A, \\ x_{ai}\le\lambda_{ij(a)}s_{ai}, &\forall i\in I_{j(a)}, \forall a\in A, \end{array} \right. \end{eqnarray*} $

其中 $s_{ai}$表示路段 $a$对应于第 $i$相位车流的饱和流量.

本文中的路段行驶时间函数为 $ t_a(x_a, \lambda_{j(a)})=t_a^0[1+\alpha(\frac{x_a}{c_a})^{\beta}], $其中 $c_a=\sum\limits_{i\in {j(a)}}\delta_{ai}\lambda_{ij(a)}s_{ai}+\theta_as_{a0}$, 而 $\delta_{ai}= \left\{\begin{array}{ll} 1, & \text{若路段}\mathit{a} \text{有车流汇入交叉口}\mathit{j}\text{(}\mathit{a}\text{)} \text{的第}\mathit{i} \text{相位车流}, \\ 0, &\mbox{否则}, \end{array}\right.$ $s_{a0}$表示路段 $a$右转车流对应的饱和流量, $\theta_a(0\le\theta_a\le1)$是依据路段 $a$的右转车道实际使用率而适当选取的调节因子, 一般, 右转车流越大, 其值越大. $d_{ai}(x_{ai}, \lambda_{ij(a)})$采用如下形式:

$ d_{ai}(x_{ai}, \lambda_{ij(a)})=0.38T\frac{(1-\lambda_{ij(a)})^2}{1-\frac{x_{ai}}{s_{ai}}}+173\frac{(x_{ai})^2}{(\lambda_{ij(a)})^2(s_{ai})^2}[\frac{x_{ai}}{\lambda_{ij(a)}}-1+\\ \sqrt{(\frac{x_{ai}}{\lambda_{ij(a)}}-1)^2+\frac{16x_{ai}}{\lambda_{ij(a)}(s_{ai})^2}}]. $

上层问题由于没有明确的解析表达式, 多采用启发式算法, 本文采用遗传算法, 在求解下层模型时, 采用文献[5]提出的非平衡交通分配的拟Frank-Wolfe迭代算法求解.算法在每轮迭代中, 将按全有全无方法在当前最短路上分配的交通量与前一轮迭代所得到的交通量进行加权得到新一轮的路径分配交通量, 而各O-D对的加权系数则依据Logit原则来确定.文献[5]中证明了该算法的收敛性且计算实例显示算法的分配结果与平衡分配非常接近.

遗传算法中, 编码方法采用实数编码(即浮点数编码), 个体即为信号配时向量, 适应度函数直接取为上层模型中的目标函数.

遗传操作采用基本的三种遗传操作算子, 即选择、交叉和变异.选择算子采用比例选择算子, 也叫赌盘选择, 是指每个个体被选中并遗传到下一代的概率与该个体的适应度大小成正比.交叉算子采用算术交叉, 即假设在两个个体 $X^t, Y^t$之间进行算术交叉, 则交叉运算后所产生出的两个新个体是 $ \left\{\begin{array}{l} X^{t+1}=\gamma Y^t+(1-\gamma)X^t, \\ Y^{t+1}=\gamma X^t+(1-\gamma)Y^t, \end{array}\right.$其中 $\gamma$为一个常数.

变异算子选则均匀变异, 并适当地选取交叉概率和变异概率.为了加速进化, 本文算法中还采用了保存最佳个体策略.

算法迭代步骤:

步骤1  初始化.设置最大进化代数 $T$, 群体规模 $M$, 交叉概率 $p_c$, 变异概率 $p_m$, 置 $t=0$, 随机产生 $M$个个体作为初始群体 $P(0)$.

步骤2  将当前群体 $P(t)$中每个个体用非平衡分配的拟Frank-Wolfe算法求解下层规划问题的最优解.

步骤3  将上层规划的目标函数作为适应度函数评价所有个体.

步骤4  根据群体中每个个体的适应度值, 对 $P(t)$做选择运算、交叉运算和变异运算, 并在交叉和变异过程中采用保存最佳个体策略, 经过三种运算后得到下一代群体 $P(t+1)$.

步骤5  终止条件判断.若 $t\le T$, 则 $t=t+1$, 转步骤2；否则停止计算, 输出最优解.

为了便于比较, 本文采用文献[6]中的道路网络图, 如图 1.网络中共有四个O-D对：1-12、9-4、12-1、4-9.需求量分别为300、400、350、350；网络中共有34条路段, 路段的最大通行能力均取为300辆/小时.网络有34条路段, 分别在图中用数字编号, 共有40条有效路径, 路径形式时间函数中 $\alpha=0.5, \beta=4$.各路段的自由流运行时间 $t_a^0$如表 1、表 2所示.

假定只考虑在交叉口6、7设置信号灯, 信号相位结构如文献[6]中图 2所示, $\theta=10$, 信号周期取为60秒, 绿信比的上下界取为

$ \lambda^{\min}=\frac{1}{6}(1, 1, 1, 1, 1, 1, 1, 1), ~~ \lambda^{\max}=\frac{1}{2}(1, 1, 1, 1, 1, 1, 1, 1). $

上述算例采用本文提出的算法进行求解, 为方便记本文的算法为 $GW$, 并将计算结果与文献[6]中的TA1算法进行比较, 结果见表 3和表 4.

$GW$算法的计算时间为3.40秒, 上层问题的目标函数值为 $2.2940\times 10^6$, $TA1$算法的计算时间为5秒, 上层问题的目标函数值为 $2.3008\times 10^6$, 本文算法的计算结果略好于 $TA1$算法.数值实验说明本文的算法是有效的, 适于求解这类问题.