圖染色問題在信號燈相位設(shè)置中的應(yīng)用

1、 圖染色問題在信號燈相位設(shè)置中的應(yīng)用 雷競雄 李嘉鈺 文竹 代家林 孫峰【Summary】交通擁堵是城市發(fā)展中常出現(xiàn)的問題，路口的交通信號燈設(shè)置不合理是造成擁堵的原因之一.本文以樂山市市中區(qū)老城區(qū)為例，探討了圖染色問題在交通信號燈設(shè)置中的應(yīng)用.首先本文將信號燈相位設(shè)置轉(zhuǎn)變?yōu)閳D的染色問題，然后給出了一些擁堵路口信號燈相位設(shè)置的具體建議.【Key】圖;染色;交通信號燈;相位一、引言隨著經(jīng)濟(jì)的增長和城市的發(fā)展，幾乎每個(gè)城市都會(huì)有交通擁堵現(xiàn)象.在樂山市，老城區(qū)部分道路就有較為嚴(yán)重的擁堵現(xiàn)象部分路口交通信號燈設(shè)置不合理導(dǎo)致同時(shí)獲得通行的車流相互沖突.圖論中的圖染色理論能夠初步解決這個(gè)問題.目前已經(jīng)有應(yīng)用

2、圖論中染色問題來解決城市交通信號燈設(shè)計(jì)的方案1，但是大多數(shù)方案只停留在不同路口的色數(shù)計(jì)算層面2，并未實(shí)際運(yùn)用于具體路口的交通擁堵的改善.本文選取部分樂山老城區(qū)路口，分析當(dāng)前交通模式圖，并將交通流轉(zhuǎn)化為圖論中的圖，通過圖色數(shù)來達(dá)到優(yōu)化相位設(shè)計(jì)的目的.二、圖論及染色問題介紹下面我們引用一些圖論方面的相關(guān)定義.三、染色問題在交通信號燈設(shè)計(jì)中的應(yīng)用本文將探討圖染色問題在交通信號燈相位設(shè)置中的應(yīng)用.圖1是某丁字路口及其交通流的示意圖，該路口無紅綠燈控制，路口只允許機(jī)動(dòng)車駛出.a，b，c，d表示汽車通行的交通流，e表示行人交通流（人行道）.我們可以把如圖1所示的路口及交通流轉(zhuǎn)化為圖，將各交通流（包含行人與

3、車的交通流）視為各個(gè)頂點(diǎn)，而且兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們所對應(yīng)的交通流是相沖突的，即是在實(shí)際交通模式圖中兩交通流是相交的.按此方法，圖1交通模式圖可轉(zhuǎn)化為如圖2所示的圖論中的圖.合理的信號燈設(shè)計(jì)應(yīng)該使得同時(shí)獲得通行的交通流不產(chǎn)生沖突.為了避免同時(shí)通行的交通流不沖突，相位的個(gè)數(shù)應(yīng)盡可能地少.即是把圖2中的全部點(diǎn)分成個(gè)數(shù)盡可能少的點(diǎn)的集合，且同一集合中的點(diǎn)彼此不相鄰.再進(jìn)一步講，即是計(jì)算出圖的點(diǎn)色數(shù)，把圖中所有點(diǎn)分成集合數(shù)與色數(shù)相同的點(diǎn)的獨(dú)立集.圖2的色數(shù)（G）=3，圖2的所有頂點(diǎn)可劃分為個(gè)數(shù)為3的點(diǎn)獨(dú)立集a，eb，cd.再將同一個(gè)點(diǎn)獨(dú)立集中所對應(yīng)的交通流劃分到一個(gè)相位中，得相位一通行路徑為a，e，

4、相位二通行路徑為b，c，相位三通行路徑為d.從而在相位個(gè)數(shù)最少的情況下避免在某個(gè)相位中交通流相互沖突的現(xiàn)象發(fā)生.四、樂山市市中區(qū)老城區(qū)一些路口信號燈設(shè)置建議隨著經(jīng)濟(jì)的增長和城市的發(fā)展，幾乎每個(gè)城市都有交通擁堵現(xiàn)象，而路口信號燈的設(shè)置對交通擁堵的影響很明顯.樂山市老城區(qū)一些路口的信號燈設(shè)置不盡合理，如黃家山丁字路口、陽光廣場十字路口、梅西百貨處十字路口等，這導(dǎo)致了上下班高峰期道路擁堵加劇.本文將運(yùn)用圖論染色原理探討一下這些路口信號燈的相位設(shè)置.1.黃家山丁字路口信號燈設(shè)置建議.黃家山丁字路口由人民南路、叮咚街和海棠路交叉構(gòu)成，具體交通流如圖3所示.此路口是一個(gè)典型的丁字路口，無紅綠燈控制，路口道

5、路狹窄，交通流b，d，f交叉嚴(yán)重.不考慮此丁字路口右轉(zhuǎn)的情況，即在任何相位皆可右轉(zhuǎn)通行，將當(dāng)前模式圖轉(zhuǎn)化為如圖4所示的圖.色數(shù)（G）=3，圖4中所有點(diǎn)可劃分為三個(gè)獨(dú)立集b，c，kd，gf，h，得如下相位設(shè)計(jì).相位一：路口處人行道綠燈，即交通流k獲得通行許可;路口，處機(jī)動(dòng)車直行綠燈，即交通流b，c 獲得通行許可.相位二：路口處人行道綠燈，即交通流g獲得通行許可;路口處機(jī)動(dòng)車左轉(zhuǎn)綠燈，即交通流d獲得通行許可.相位三：路口處人行道綠燈，即交通流h獲得通行許可;路口處機(jī)動(dòng)車左轉(zhuǎn)綠燈，即交通流f獲得通行許可.2.梅西百貨處十字路口信號燈設(shè)置建議.梅西百貨十字路口是由嘉定中路與嘉定北路、柏楊中路與致江路交

6、叉構(gòu)成，具體交通流如圖5所示.此十字路口較寬，路口處的人行道被天橋所替代.當(dāng)前有如圖6所示相位為2的紅綠燈設(shè)計(jì)，相位一：路口，處機(jī)動(dòng)車綠燈，路口，處人行道綠燈，獲得通行的路徑有a，c，d，e，g，k，m，n，y，q;相位二：路口，處機(jī)動(dòng)車綠燈，路口處人行道綠燈，獲得通行的路徑有a，b，d，f，g，h，m，t，z.從當(dāng)前相位設(shè)計(jì)中可以明顯看出交通流c，e之間、k，n之間、b，t之間、h，f之間沖突嚴(yán)重.在十字路口相位設(shè)計(jì)中一般不考慮右轉(zhuǎn)，即在任何相位皆可右轉(zhuǎn)通行.將當(dāng)前模式圖轉(zhuǎn)化為如圖7所示的圖.色數(shù)（G）=4，圖7中所有點(diǎn)可劃分為四個(gè)獨(dú)立集n，e，y，qc，kb，h，zf，t，得如下相位設(shè)計(jì).

7、相位一：路口，處人行道綠燈，即交通流y，q獲得通行許可;路口，處機(jī)動(dòng)車直行綠燈，即交通流e，n獲得通行許可.相位二：路口，處機(jī)動(dòng)車左轉(zhuǎn)綠燈，即交通流k，c獲得通行許可.相位三：路口處人行道綠燈，即交通流z獲得通行許可;路口，處機(jī)動(dòng)車直行綠燈，即交通流h，b獲得通行許可.相位四;路口，處機(jī)動(dòng)車左轉(zhuǎn)綠燈，即交通流t，f獲得通行許可.3.陽光廣場十字路口信號燈設(shè)置建議.陽光廣場十字路口是由人民東路與人民南路、人民西路與大橋西街交叉構(gòu)成，具體交通流如圖8所示.此十字路口中路口到路口的右轉(zhuǎn)是一條單獨(dú)的車道，獨(dú)立于此十字路口之外.當(dāng)前有如圖9所示相位為2的交通運(yùn)行模式，相位一：路口，處機(jī)動(dòng)車綠燈，路口，處

8、人行道綠燈，獲得通行的路徑有a，b，f，g，h，m，t，x，z;相位二：路口，處機(jī)動(dòng)車綠燈，路口，處人行道綠燈，獲得通行的路徑有a，c，e，g，k，m，n，y，q.從當(dāng)前相位設(shè)計(jì)可以明顯看出交通流b，t之間、h，f之間、c，e之間、k，n之間沖突嚴(yán)重.另外，此十字路口中路口較狹窄，使得這些交通流擁堵程度進(jìn)一步加深.同樣地，在此十字路口不考慮右轉(zhuǎn)，將當(dāng)前模式圖轉(zhuǎn)化為如圖10所示的圖.色數(shù)（G）=4，圖10中所有點(diǎn)可劃分為四個(gè)獨(dú)立集b，h，x，zf，tn，e，y，qc，k，得如下相位設(shè)計(jì).相位一：路口，處人行道綠燈，即交通流x，z獲得通行許可;路口，處機(jī)動(dòng)車直行綠燈，即交通流h，b獲得通行許可.相

9、位二：路口，處機(jī)動(dòng)車左轉(zhuǎn)綠燈，即交通流t，f獲得通行許可.相位三：路口，處人行道綠燈，即交通流y，q獲得通行許可;路口，處機(jī)動(dòng)車直行綠燈，即交通流e，n獲得通行許可.相位四：路口，處機(jī)動(dòng)車左轉(zhuǎn)綠燈，即交通流k，c獲得通行許可.五、總結(jié)本文初步且系統(tǒng)地對樂山市老城區(qū)部分路口交通擁堵問題做出了分析、研究和處理，具體到個(gè)別有代表性的丁字路口、十字路口等.本文通過把交通流轉(zhuǎn)化為圖，再用圖論染色的相關(guān)知識展開說明，從而改變紅綠燈的相位控制模式，以達(dá)到避免機(jī)動(dòng)車與行人同時(shí)獲得通行許可時(shí)出現(xiàn)的沖突現(xiàn)象.但本文在研究的過程中，由于老城區(qū)本身的環(huán)境和社會(huì)因素的限制，忽略了道路寬度、人口密度等一些有可能會(huì)對研究結(jié)

10、果起到影響的條件，這也是我們在今后進(jìn)行研究時(shí)需要考慮的主要問題.在研究本文的過程中，我們通過與其他論文的對比和與其他學(xué)者的交流發(fā)現(xiàn)，我們選擇了圖論染色的方法，使得研究變得簡單、具體，且能夠有效解決問題，為以后的研究確定了一個(gè)大的框架.但該方法忽略了一些環(huán)境會(huì)帶來的影響，對得到的研究成果能不能更好地、更高效地解決實(shí)際問題還需要到實(shí)踐中具體操作，從而在后期的研究中加以改正和補(bǔ)充說明.【Reference】1劉攀，徐志攀，張曉銘.多岔路口交通信號燈控制系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)J.電腦知識與技術(shù)，2010（01）：208-209.2尹麗子，崔瀟，于冰.圓染色在交通信號燈相位優(yōu)化設(shè)計(jì)中的應(yīng)用J.山東大學(xué)學(xué)報(bào)（工學(xué)版），2006（05）：107-112.3肖會(huì)敏，臧振春，崔春生.運(yùn)籌學(xué)及應(yīng)用M.北京：清華大學(xué)出版社，2017.4尹琳娟.圖論