图染色问题在信号灯相位设置中的应用

雷竞雄 李嘉钰 文竹 代家林 孙峰

【摘要】交通拥堵是城市发展中常出现的问题，路口的交通信号灯设置不合理是造成拥堵的原因之一.本文以乐山市市中区老城区为例，探讨了图染色问题在交通信号灯设置中的应用.首先本文将信号灯相位设置转变为图的染色问题，然后给出了一些拥堵路口信号灯相位设置的具体建议.

【关键词】图;染色;交通信号灯;相位

一、引 言

随着经济的增长和城市的发展，几乎每个城市都会有交通拥堵现象.在乐山市，老城区部分道路就有较为严重的拥堵现象——部分路口交通信号灯设置不合理导致同时获得通行的车流相互冲突.图论中的图染色理论能够初步解决这个问题.目前已经有应用图论中染色问题来解决城市交通信号灯设计的方案[1]，但是大多数方案只停留在不同路口的色数计算层面[2]，并未实际运用于具体路口的交通拥堵的改善.本文选取部分乐山老城区路口，分析当前交通模式图，并将交通流转化为图论中的图，通过图色数来达到优化相位设计的目的.

二、图论及染色问题介绍

下面我们引用一些图论方面的相关定义.

三、染色问题在交通信号灯设计中的应用

本文将探讨图染色问题在交通信号灯相位设置中的应用.图1是某丁字路口及其交通流的示意图，该路口无红绿灯控制，路口①只允许机动车驶出.a，b，c，d表示汽车通行的交通流，e表示行人交通流（人行道）.

我们可以把如图1所示的路口及交通流转化为图，将各交通流（包含行人与车的交通流）视为各个顶点，而且两个顶点相邻当且仅当它们所对应的交通流是相冲突的，即是在实际交通模式图中两交通流是相交的.按此方法，图1交通模式图可转化为如图2所示的图论中的图.

合理的信号灯设计应该使得同时获得通行的交通流不产生冲突.为了避免同时通行的交通流不冲突，相位的个数应尽可能地少.即是把图2中的全部点分成个数尽可能少的点的集合，且同一集合中的点彼此不相邻.再进一步讲，即是计算出图的点色数，把图中所有点分成集合数与色数相同的点的独立集.图2的色数χ（G）=3，图2的所有顶点可划分为个数为3的点独立集{a，e}{b，c}{d}.再将同一个点独立集中所对应的交通流划分到一个相位中，得相位一通行路径为a，e，相位二通行路径为b，c，相位三通行路径为d.从而在相位个数最少的情况下避免在某个相位中交通流相互冲突的现象发生.

四、乐山市市中区老城区一些路口信号灯设置建议

随着经济的增长和城市的发展，几乎每个城市都有交通拥堵现象，而路口信号灯的设置对交通拥堵的影响很明显.乐山市老城区一些路口的信号灯设置不尽合理，如黄家山丁字路口、阳光广场十字路口、梅西百货处十字路口等，这导致了上下班高峰期道路拥堵加剧.本文将运用图论染色原理探讨一下这些路口信号灯的相位设置.

1.黄家山丁字路口信号灯设置建议.

黄家山丁字路口由人民南路、叮咚街和海棠路交叉构成，具体交通流如图3所示.

此路口是一个典型的丁字路口，无红绿灯控制，路口②道路狭窄，交通流b，d，f交叉严重.不考虑此丁字路口右转的情况，即在任何相位皆可右转通行，将当前模式图转化为如图4所示的图.

色数χ（G）=3，图4中所有点可划分为三个独立集{b，c，k}{d，g}{f，h}，得如下相位设计.相位一：路口①处人行道绿灯，即交通流k获得通行许可;路口②，③处机动车直行绿灯，即交通流b，c 获得通行许可.相位二：路口③处人行道绿灯，即交通流g获得通行许可;路口①处机动车左转绿灯，即交通流d获得通行许可.相位三：路口②处人行道绿灯，即交通流h获得通行许可;路口③处机动车左转绿灯，即交通流f获得通行许可.

2.梅西百货处十字路口信号灯设置建议.

梅西百货十字路口是由嘉定中路与嘉定北路、柏杨中路与致江路交叉构成，具体交通流如图5所示.

此十字路口较宽，路口①处的人行道被天桥所替代.当前有如图6所示相位为2的红绿灯设计，相位一：路口①，③处机动车绿灯，路口②，④处人行道绿灯，获得通行的路径有a，c，d，e，g，k，m，n，y，q;相位二：路口⑥，⑧处机动车绿灯，路口⑦处人行道绿灯，获得通行的路径有a，b，d，f，g，h，m，t，z.从当前相位设计中可以明显看出交通流c，e之间、k，n之间、b，t之间、h，f之间冲突严重.

在十字路口相位设计中一般不考虑右转，即在任何相位皆可右转通行.将当前模式图转化为如图7所示的图.

色数χ（G）=4，图7中所有点可划分为四个独立集{n，e，y，q}{c，k}{b，h，z}{f，t}，得如下相位設计.相位一：路口②，④处人行道绿灯，即交通流y，q获得通行许可;路口①，③处机动车直行绿灯，即交通流e，n获得通行许可.相位二：路口①，③处机动车左转绿灯，即交通流k，c获得通行许可.相位三：路口③处人行道绿灯，即交通流z获得通行许可;路口②，④处机动车直行绿灯，即交通流h，b获得通行许可.相位四;路口②，④处机动车左转绿灯，即交通流t，f获得通行许可.

3.阳光广场十字路口信号灯设置建议.

阳光广场十字路口是由人民东路与人民南路、人民西路与大桥西街交叉构成，具体交通流如图8所示.

此十字路口中路口②到路口③的右转是一条单独的车道，独立于此十字路口之外.当前有如图9所示相位为2的交通运行模式，相位一：路口②，④处机动车绿灯，路口①，③处人行道绿灯，获得通行的路径有a，b，f，g，h，m，t，x，z;相位二：路口⑤，⑦处机动车绿灯，路口⑥，⑧处人行道绿灯，获得通行的路径有a，c，e，g，k，m，n，y，q.从当前相位设计可以明显看出交通流b，t之间、h，f之间、c，e之间、k，n之间冲突严重.另外，此十字路口中路口①较狭窄，使得这些交通流拥堵程度进一步加深.

同样地，在此十字路口不考虑右转，将当前模式图转化为如图10所示的图.

色数χ（G）=4，图10中所有点可划分为四个独立集{b，h，x，z}{f，t}{n，e，y，q}{c，k}，得如下相位设计.相位一：路口①，③处人行道绿灯，即交通流x，z获得通行许可;路口②，④处机动车直行绿灯，即交通流h，b获得通行许可.相位二：路口②，④处机动车左转绿灯，即交通流t，f获得通行许可.相位三：路口②，④处人行道绿灯，即交通流y，q获得通行许可;路口①，③处机动车直行绿灯，即交通流e，n获得通行许可.相位四：路口①，③处机动车左转绿灯，即交通流k，c获得通行许可.

五、总 结

本文初步且系统地对乐山市老城区部分路口交通拥堵问题做出了分析、研究和处理，具体到个别有代表性的丁字路口、十字路口等.本文通过把交通流转化为图，再用图论染色的相关知识展开说明，从而改变红绿灯的相位控制模式，以达到避免机动车与行人同时获得通行许可时出现的冲突现象.但本文在研究的过程中，由于老城区本身的环境和社会因素的限制，忽略了道路宽度、人口密度等一些有可能会对研究结果起到影响的条件，这也是我们在今后进行研究时需要考虑的主要问题.在研究本文的过程中，我们通过与其他论文的对比和与其他学者的交流发现，我们选择了图论染色的方法，使得研究变得简单、具体，且能够有效解决问题，为以后的研究确定了一个大的框架.但该方法忽略了一些环境会带来的影响，对得到的研究成果能不能更好地、更高效地解决实际问题还需要到实践中具体操作，从而在后期的研究中加以改正和补充说明.

【参考文献】

[1]刘攀，徐志攀，张晓铭.多岔路口交通信号灯控制系统的设计与实现[J].电脑知识与技术，2010（01）：208-209.

[2]尹丽子，崔潇，于冰.圆染色在交通信号灯相位优化设计中的应用[J].山东大学学报（工学版），2006（05）：107-112.

[3]肖会敏，臧振春，崔春生.运筹学及应用[M].北京：清華大学出版社，2017.

[4]尹琳娟.图论染色问题应用研究[D].西安：西安电子科技大学，2009.

[5]朱求长.运筹学及其运用[M].武汉：武汉大学出版社，2012.

[6]陈吉珍，宁爱兵，支志兵，等.图论中最大独立集问题的精确算法[J].计算机工程与应用，2016（01）：20-22，109.

[7]丁来浩.图的几类染色问题以及超图中的彩色匹配[D].济南：山东大学，2018.