自动化系杨凯棣-个人答辩陈述在线视频

下面请作报告

各位老师各位同学大家下午好

我是自动化系系统工程研究所

杨凯棣

我的导师是李力副教授

我的论文题目是

孤立过饱和交叉口信号配时

问题研究

我的硕士论文

是基于我这两个工作来做的

我其中一篇已经发表在了

Transportation Research Part C上

然后另外一篇在投Control Engineering Practice

我要介绍的是

孤立过饱和交叉口信号配时问题研究

那什么是信号配时问题呢

信号配时问题是

通过配置交叉口的信号灯参数

提高交叉口附近

行人和车辆的通行能力

那么这个信号灯参数

一般来说包括周期的长度

相位差和绿信比

绿信比就是指绿灯的时间

和周期长度的比值

然后衡量交叉口附近行人

和车辆的通行能力的指标

主要是用总的延误来衡量

那孤立交叉口

实际上是忽略其它交叉的影响

这一般就是

比如说其它交叉口的

和这个交叉口相距比较远

然后这样的话

这个好处是

可以假定到达的流率

会是一个定值

都是一个常数

都已知这个数

那么过饱和交叉口

是指在任何一个时间

在任何一个

对于所有方向上的车流

它的初始的排队车辆

然后加上到达的车辆

会超出这个交叉口的容量

也就是说在下一个周期

还会有车辆在这个方向上排队

我的研究意义主要分为两个方面

第一个方面是

交叉口是城市交通中的一个瓶颈

它容易发生拥堵

然后是城市交通管理中的

一个重要的环节

实际上是由于

竞争车流的一些影响

会使车辆

在通过交叉口的时候

会经过更长的时间

如果信号配时的这个策略

不当的话

可能会产生一些大面积拥堵

比如说这张图中的情形

然后这样的话

拥堵会传播到其它的路口

然后另外的一个意义是

交叉口信号控制

是缓解交通拥堵的

一个比较经济有效的措施

实际上是因为它的成本

会比较低

现在有很多研究者

在做这个孤立过饱和

交叉口这一块的研究

然后目标通常是用

总的延误来衡量

总的延误实际上

是这张图中所示

纵坐标是这个车辆数

横坐标是时间

那这张图中有两条曲线

一条曲线是到达曲线

它是表示从某一个时间开始

然后就是到达这个交叉口的

车辆数和时间的关系

然后另外一条曲线是离开曲线

它表示的是从某一个时刻开始

离开这个交叉口的

车辆数和时间的关系

然后这两条曲线之间的面积是

就是总的延误

那么我们可以看到离开曲线

实际上它会受到信号控制的影响

在红灯的时候离开

没有车辆离开交叉口

所以它是一条水平线

到绿灯的时候

有车辆离开这个交叉口

然后这样的话

实际上这个总延误

是一个非常复杂的函数

它非凸

然后所以非常难于求解

而这只是对于其中一个车流来看

如果多个车流的话

那这个延误的函数

会变得非常复杂

所以说孤立交叉口

这个配时问题的难点

就是处理非凸的延误函数

那目前有一派的想法是

通过一些近似算法来求解

他们就认为

这个延误函数非常复杂

那我去求一个近似解

然后还有一种方式

是用一个比较好的延误函数

来近似这个延误

最早的这个人提出了

近似延误公式

而目前更多的

可能是采用凸函数来近似

那主要模型有两种

一个是最优控制模型

一个是线性规划模型

最优控制模型

是最早是由Gazis提出

他考虑了非常简单的场景

然后后来后面这两个人

他是把Gazis那个

假设放宽了一些

得到一些更

一般一点的结论

然后通常的求解方式是

Pontryagin最大值原理

而线性规划模型

是这几年是由

比如他们是用一个

比较平滑的一些曲线

来近似复杂的一些曲线

然后得到了一个

实际上是一个线性规划的模型

叫多阶段信号配时模型

然后后来就是

工业工程系的赵老师

在单周期的情况下

提出一种快速求解的算法

他们证明这个算法

对于单周期情况下是最优的

但是他并没有把这个用到

多个周期的情况

到底就是表现怎么样不知道

关于这两种模型之间的关系

也有很多人在做研究

比如说上面的人

他提出了一个比较复杂的模型

然后利用最优控制

来求得一个近似解

那他并没有考虑

近似解和原问题最优解

之间的关系

然后还有就是我们实验室的邹师兄提出了

用图解法研究

如何从最优控制模型的解

得到线性规划模型的解

但他考虑问题非常

考虑情况非常非常简单

就是两个车轮同时放光的情况

这是在一般的交叉口

信号配时问题中

很少出现的一个情况

本文的工作

就是以车辆的总延误

作为优化目标

用绿信比作为主要优化参数

对孤立过饱和交叉口进行研究

然后我的研究主要分为两个部分

第一个部分是

建立一个多阶段信号配时模型

然后用一种在线算法

来求解该模型

并探讨这个在线算法的最优性

另外一部分是

在一种比较简单的交通场景之下

还比较这个多阶段信号配时模型

和传统的最优控制模型

然后证明两者在一定意义之下

具有一定的等价性

第一部分是提出了

多阶段信号配时模型

然后再利用了一种在线算法

叫做递归贪婪算法

多阶段信号配时模型

就是这个样子

然后其中的参数是

我们用k来表示周期，p来表示相位

每个相位之下

可能会有很多的车流

比如说这张图里边会有

就有从左向右的车流

和一个从右向左的车流

从左向右车流称作m1

我们用λ来表示

到达的车辆

我们用ν来表达

离开的车辆

然后用X来表示

这个交叉口排队的车辆

然后用s表示

这个交叉口它的那个容量

实际上就是饱和的离开流率

然后eta

是我的决策变量

即绿信比

在这个模型之中

我们假设周期长度

是一个常数

它的目标是总延误

第一个约束是

所有的绿信比加起来

它必须小于一个常数

这个常数一般是小于1的

然后第二个

第二个是

就是绿信比它会有一个下界

这实际上是因为

车量通过交叉口需要一定的时间

所以说绿灯时间不能太短

然后第三个是

就是离开这个交叉口的

车量总数

不能超过交叉口的容量

也不能超过交叉口的需求

然后第四个是

队列之间的一个变化的关系

实际上是下一个周期的

队列长度

等于这个周期的队列长度

加上到达的车辆数

减去离开的车辆数

这实际上是一个线性规划模型

当然我们可以用

一些传统的线性规划模型的算法

来进行求解

比如说单纯形法 比如说内点法

但实际上由于未来的流率

一般来说我们并不知道

其实说我们很难

就是去求解一个离线的模型

所以一般来说

我们要用在线的算法来求解

就是实际上在线的话

我们就把这个多周期的问题

分解成一个一个的周期

然后每个周期之间

来通过队列长度来互相耦合

实际上就是得到

右边这样一个小的模型

然后对于每一个周期的模型

我们当然采用

就是赵磊老师他提出的

贪婪算法求解

然后把这个整个算法的框架

叫做递归贪婪算法

我们下一部分是

就是讨论这个递归贪婪算法

对于这个多阶段

信号配时模型的最优性

于是它这个在线算法

我们可以想

一般来说都不是最优

因为我们并不知道未来的信息

也并不知道未来的流率是怎么样的

但我们提出了一种

一个条件 叫做保序条件

然后我们证明

在这个保序条件之下

最优性可以得到保证

我们先通过一个反例来说明

一般的情况之下

这个在线算法的最优性

并不能得到保证

这是一个两周期的模型

每个周期中有三个相位

然后具体参数

就是像PPT上所示的这样

然后我们求得这个最优解

和递归贪婪解

如表所示

因为这个问题

实际上是一个最小化的问题

我们可以通过目标函数来看到

递归贪婪解并不是一个

并不是最优解

接下来我们提出一个保序条件

然后

并且证明在保序条件之下

递归贪婪算法是最优性的

在提出保序条件之前

我们先引入一个比较重要的参数

叫清空时间比

它实际上是表示

就是在某一个周期

每一个相位之中

所有的车辆

就是某一个车流中

所有的车辆

包括到达的车辆和排队的车辆

然后要把这些车辆全部清空

所需要的时间占总周期的比例

也就是说比如说

就是如果这个相位中的绿信比

要大于这个清空时间比的话

那这个车流的所有的车辆

都可以被清空

如果这个绿信比

小于这个清空时间比的话

那肯定会有车辆还剩余

这张图实际上表示的就是

离开这个交叉口的车辆

和这个绿信比

还有清空时间比之间的一些关系

清空时间比

实际上它反映的是一个

就是这个交叉口某一个方向的

繁忙程度

就是它就是某一个方向的

一个过饱和程度

那实际上对于每一个方向的车流

都有这么样一个清空时间比

那么对于任何一个周期

任何一个相位

然后这些清空时间比

就有一个顺序

如果这些清空时间比的顺序

和周期是无关的

那我们就认为这个交叉口

是满足保序条件的

那就实际上说

比如说有一个方向

车流mi

另外一个方向车流mj

如果mi的清空时间比

一直都不大于mj的清空时间比

那么这个保序条件就满足

这实际上就是说

如果一个交叉口

中的某一个方向

它一直是比较繁忙

一直是处于比较过饱和的状态

那它就一直相对其它的方向

要更繁忙一些

就这样的情况是

保序条件刻画的是这样的情况

它的物理意义实际上就是

各流清空时间的顺序保持不变

而它的本质实际上

就是对到达的流率的随机性

来加以限制

实际上是假设当前的交通状态

和未来交通状态

具有某一类的相似性

实际上有这种相似性的话

最优性很容易保证

而在实际之中

保序条件一般来说

对于过饱和的情况比较强的这种

交叉口一般来说可以满足的

因为就是实际上

对过饱和的这种交叉口

然后不同方向上的交通需求

相对会保持稳定

我们核心结论是这个定理

实际上就是

递归贪婪解对于

在保序条件之下

对于多阶段信号配时模型

是最优的

然后这个定理证明非常复杂

这个主要具体的流程

是这张图所表示的这样

它的核心是

广义KKT条件 就是

找到一个（对偶）向量

满足广义KKT条件

我们回去看刚才的反例

实际上刚才的反例

并不满足保序条件

因为就是看前两个清空时间比

周期1的时候

b11是小于b21的

然后在周期2的时候会反过来

然后我们可以改变一些

其它的参数

保序条件满足

然后这样

我们可以看到

修改过的这个例子之中

递归贪婪解

就是全局最优的

第二部分问题是

第二部分的研究是

去比较这个

多阶段信号配时模型

即线性规划模型

和传统最优控制模型

实际上我们可以

我们比较的场景

是一个非常非常简单的交通场景

这个交通场景包括

两条单行道交汇

成了一个孤立交叉口

每一个单行道上

都有一列车流

都是信号灯控制的

实际上这个

这个交通场景非常简单的

它的很多文献中经常会被采用

因为这种场景之下

可能容易得到解析解

然后它比较便于说明和比较

然后在这个场景之下

可以建立最优控制模型

和多阶段信号配时模型

多阶段信号配时模型

就是之前讲的那样

然后最优控制模型

它的目标函数也是延误

然后实际上对于最优控制模型

它的假设是假设这个周期长度

趋于0

就是然后这样的话

就可以得到一个

就是用常微分方程

来描述这个交叉口的动态特性

而实际上

如果假设这个周期长度

趋于0之后

我们相当于忽略了这个

周期内部的一些

比较复杂的特性

然后这样的话

实际上就是把每个周期

看作了一个整体

包括回过头来一看

多阶段信号配时模型

它也是一样的

就是它实际上是假设

每个周期之间离开流率

都是一个定值

然后这样也是把一个周期

看作是一个整体

然后比较这两个模型

形式上来说它们也是非常接近的

然后后来我们看它们的解之间

到底存在什么样的关系

我们首先求到

求得这个最优控制模型的解

然后如这个表所示

实际上它是一个

就是具有一些bang-bang的特性

就是配时策略中

都是先一个比较大的数

然后后来放比较小的一个值

当然有些情况

是没有这个转折

没有转折的情况可以把它看做一个退化的情况

那比较的话

我们对最优控制解

进行一个离散化 离散化的方式

实际上在周期开始的时候

进行采样

所以离散化的解我们把它称作

称为离散近似解

那后面我们就要比较

离散近似解

和多阶段信号配时模型

最优解之间的关系

我们先看一个数值例子

这个数值例子的参数如表所示

解如图所示

实际上我们可以看到

这两个解并不吻合

然后但是它的解

在形式上有一定的相似之处

然后它们的不同点

主要是在于

在于转折周期的位置

和转折周期内部

信号配时策略。

误差的来源主要是

就是来源于离散化

因为对最优性控制模型

它求得的转折的时间点

很可能位于某一个周期的中间

然后如果位于中间的话

那这样它可能有误差

一直向后传递

如果传递到后面

的周期比较多的话

总误差就会比较大

然后它可以改变

转折周期的位置

和转折周期内部的信号配时策略

然后我们用一个定理

来说明这个

多阶段信号配时模型的解

在简单场景之下

确实是有这个bang-bang

控制的特性

然后后面用一个非常简单的

梯度下降的算法

把这个最优控制的解调整为

多阶段信号配时模型的解

然后实际上这个

这个算法一般是两步到四步就可以结束

然后这样的话

我们就建立了

多阶段信号配时模型

和最优控制模型之间的关系

我们的结论

结论就是针对孤立交叉口

建立了信号配时策略

然后利用一种分段线性的函数

然后来近似交叉口离开曲线

然后建立了一个

一个线性规划模型

然后本文的贡献

主要是两个方面

然后第一个方面是

就是用一个在线算法

来优化车辆总延误

然后给出了最优性的讨论

然后给出一个反例来说明

一般情况下这个算法不是最优的

然后再给出了一个

特殊的保序条件

然后说明在保序条件之下

这个算法是最优的

而且说明了

这个保序条件的物理意义

另一个方面的贡献是

就比较了多阶段信号配时模型

和传统的最优控制模型

然后说明了这两者之间

它们之间有一定的关联

然后后续的研究

我们可以从这么几个方面

来入手

因为本来实际上是假设

周期长度是给定的

每个周期内部是一个常数

那实际上我们可以

把这个周期长度

也考虑到模型里

但是如果我们把优化模型

把这个周期长度

看作一个变量的话

它会改变这个模型的性质

这个模型就变成了一个

非凸的模型

那实际上我们可以考虑

用另外一种想法

就是我们通过一些其它的方式

优化出一些周期长度

然后把这个周期长度

看作一个已知的常量

带到这个模型里

这样的话

之前的讨论就全部都全部都适用

然后另外一种是引入随机性

而实际上就是

刚才说那个交叉口

它是具有一定的那个随机性的

然后我们可以直接提出

线性规划模型

可以非常方便的推广到

随机优化的情形

这样的话

可以对这个随机性来加以控制

另外一点实际上

实际上那个交叉口的到达的曲线

到达的流率和离开的流率

都是具有一定的

具有一定的规律

如果我们利用这些规律的话

我们可以

就有可能得到一些更好的

一种在线算法

其实有了这个周期长度

和随机性之后

然后就可以做一些实际的研究

比如说找一个交叉口

然后来做一些就是仿真

或者实验中的验证

如果验证情况好的话

我们把它推广到网络的控制

利用一些交叉口之间的一些

就是一些流量之间的关系

或者宏观交通

或者一些其它的交通模型

来进行一些网络上的控制

我的这个陈述就到这里

谢谢各位老师