圖染色問題在信號燈相位設置中的應用

雷競雄 李嘉鈺 文竹 代家林 孫峰

【摘要】交通擁堵是城市發展中常出現的問題，路口的交通信號燈設置不合理是造成擁堵的原因之一.本文以樂山市市中區老城區為例，探討了圖染色問題在交通信號燈設置中的應用.首先本文將信號燈相位設置轉變為圖的染色問題，然后給出了一些擁堵路口信號燈相位設置的具體建議.

【關鍵詞】圖;染色;交通信號燈;相位

一、引?言

隨著經濟的增長和城市的發展，幾乎每個城市都會有交通擁堵現象.在樂山市，老城區部分道路就有較為嚴重的擁堵現象——部分路口交通信號燈設置不合理導致同時獲得通行的車流相互沖突.圖論中的圖染色理論能夠初步解決這個問題.目前已經有應用圖論中染色問題來解決城市交通信號燈設計的方案[1]，但是大多數方案只停留在不同路口的色數計算層面[2]，并未實際運用于具體路口的交通擁堵的改善.本文選取部分樂山老城區路口，分析當前交通模式圖，并將交通流轉化為圖論中的圖，通過圖色數來達到優化相位設計的目的.

二、圖論及染色問題介紹

下面我們引用一些圖論方面的相關定義.

三、染色問題在交通信號燈設計中的應用

本文將探討圖染色問題在交通信號燈相位設置中的應用.圖1是某丁字路口及其交通流的示意圖，該路口無紅綠燈控制，路口①只允許機動車駛出.a，b，c，d表示汽車通行的交通流，e表示行人交通流（人行道）.

我們可以把如圖1所示的路口及交通流轉化為圖，將各交通流（包含行人與車的交通流）視為各個頂點，而且兩個頂點相鄰當且僅當它們所對應的交通流是相沖突的，即是在實際交通模式圖中兩交通流是相交的.按此方法，圖1交通模式圖可轉化為如圖2所示的圖論中的圖.

合理的信號燈設計應該使得同時獲得通行的交通流不產生沖突.為了避免同時通行的交通流不沖突，相位的個數應盡可能地少.即是把圖2中的全部點分成個數盡可能少的點的集合，且同一集合中的點彼此不相鄰.再進一步講，即是計算出圖的點色數，把圖中所有點分成集合數與色數相同的點的獨立集.圖2的色數χ（G）=3，圖2的所有頂點可劃分為個數為3的點獨立集{a，e}{b，c}g0gggggg.再將同一個點獨立集中所對應的交通流劃分到一個相位中，得相位一通行路徑為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.