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

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

【摘要】交通擁堵是城市發(fā)展中常出現(xiàn)的問題，路口的交通信號燈設(shè)置不合理是造成擁堵的原因之一.本文以樂山市市中區(qū)老城區(qū)為例，探討了圖染色問題在交通信號燈設(shè)置中的應(yīng)用.首先本文將信號燈相位設(shè)置轉(zhuǎn)變?yōu)閳D的染色問題，然后給出了一些擁堵路口信號燈相位設(shè)置的具體建議.

【關(guān)鍵詞】圖;染色;交通信號燈;相位

一、引?言

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

二、圖論及染色問題介紹

下面我們引用一些圖論方面的相關(guān)定義.

三、染色問題在交通信號燈設(shè)計中的應(yīng)用

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

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

合理的信號燈設(shè)計應(yīng)該使得同時獲得通行的交通流不產(chǎn)生沖突.為了避免同時通行的交通流不沖突，相位的個數(shù)應(yīng)盡可能地少.即是把圖2中的全部點(diǎn)分成個數(shù)盡可能少的點(diǎn)的集合，且同一集合中的點(diǎn)彼此不相鄰.再進(jìn)一步講，即是計算出圖的點(diǎn)色數(shù)，把圖中所有點(diǎn)分成集合數(shù)與色數(shù)相同的點(diǎn)的獨(dú)立集.圖2的色數(shù)χ（G）=3，圖2的所有頂點(diǎn)可劃分為個數(shù)為3的點(diǎn)獨(dú)立集{a，e}{b，c}j5i0abt0b.再將同一個點(diǎn)獨(dú)立集中所對應(yīng)的交通流劃分到一個相位中，得相位一通行路徑為a，e，相位二通行路徑為b，c，相位三通行路徑為d.從而在相位個數(shù)最少的情況下避免在某個相位中交通流相互沖突的現(xiàn)象發(fā)生.

四、樂山市市中區(qū)老城區(qū)一些路口信號燈設(shè)置建議

隨著經(jīng)濟(jì)的增長和城市的發(fā)展，幾乎每個城市都有交通擁堵現(xiàn)象，而路口信號燈的設(shè)置對交通擁堵的影響很明顯.樂山市老城區(qū)一些路口的信號燈設(shè)置不盡合理，如黃家山丁字路口、陽光廣場十字路口、梅西百貨處十字路口等，這導(dǎo)致了上下班高峰期道路擁堵加劇.本文將運(yùn)用圖論染色原理探討一下這些路口信號燈的相位設(shè)置.

1.黃家山丁字路口信號燈設(shè)置建議.

黃家山丁字路口由人民南路、叮咚街和海棠路交叉構(gòu)成，具體交通流如圖3所示.

此路口是一個典型的丁字路口，無紅綠燈控制，路口②道路狹窄，交通流b，d，f交叉嚴(yán)重.不考慮此丁字路口右轉(zhuǎn)的情況，即在任何相位皆可右轉(zhuǎn)通行，將當(dāng)前模式圖轉(zhuǎn)化為如圖4所示的圖.

色數(shù)χ（G）=3，圖4中所有點(diǎn)可劃分為三個獨(dú)立集{b，c，k}{d，g}{f，h}，得如下相位設(shè)計.相位一：路口①處人行道綠燈，即交通流k獲得通行許可;路口②，③處機(jī)動車直行綠燈，即交通流b，c 獲得通行許可.相位二：路口③處人行道綠燈，即交通流g獲得通行許可;路口①處機(jī)動車左轉(zhuǎn)綠燈，即交通流d獲得通行許可.相位三：路口②處人行道綠燈，即交通流h獲得通行許可;路口③處機(jī)動車左轉(zhuǎn)綠燈，即交通流f獲得通行許可.

2.梅西百貨處十字路口信號燈設(shè)置建議.

梅西百貨十字路口是由嘉定中路與嘉定北路、柏楊中路與致江路交叉構(gòu)成，具體交通流如圖5所示.

此十字路口較寬，路口①處的人行道被天橋所替代.當(dāng)前有如圖6所示相位為2的紅綠燈設(shè)計，相位一：路口①，③處機(jī)動車綠燈，路口②，④處人行道綠燈，獲得通行的路徑有a，c，d，e，g，k，m，n，y，q;相位二：路口⑥，⑧處機(jī)動車綠燈，路口⑦處人行道綠燈，獲得通行的路徑有a，b，d，f，g，h，m，t，z.從當(dāng)前相位設(shè)計中可以明顯看出交通流c，e之間、k，n之間、b，t之間、h，f之間沖突嚴(yán)重.

在十字路口相位設(shè)計中一般不考慮右轉(zhuǎn)，即在任何相位皆可右轉(zhuǎn)通行.將當(dāng)前模式圖轉(zhuǎn)化為如圖7所示的圖.

色數(shù)χ（G）=4，圖7中所有點(diǎn)可劃分為四個獨(dú)立集{n，e，y，q}{c，k}{b，h，z}{f，t}，得如下相位設(shè)計.相位一：路口②，④處人行道綠燈，即交通流y，q獲得通行許可;路口①，③處機(jī)動車直行綠燈，即交通流e，n獲得通行許可.相位二：路口①，③處機(jī)動車左轉(zhuǎn)綠燈，即交通流k，c獲得通行許可.相位三：路口③處人行道綠燈，即交通流z獲得通行許可;路口②，④處機(jī)動車直行綠燈，即交通流h，b獲得通行許可.相位四;路口②，④處機(jī)動車左轉(zhuǎn)綠燈，即交通流t，f獲得通行許可.

3.陽光廣場十字路口信號燈設(shè)置建議.

陽光廣場十字路口是由人民東路與人民南路、人民西路與大橋西街交叉構(gòu)成，具體交通流如圖8所示.

此十字路口中路口②到路口③的右轉(zhuǎn)是一條單獨(dú)的車道，獨(dú)立于此十字路口之外.當(dāng)前有如圖9所示相位為2的交通運(yùn)行模式，相位一：路口②，④處機(jī)動車綠燈，路口①，③處人行道綠燈，獲得通行的路徑有a，b，f，g，h，m，t，x，z;相位二：路口⑤，⑦處機(jī)動車綠燈，路口⑥，⑧處人行道綠燈，獲得通行的路徑有a，c，e，g，k，m，n，y，q.從當(dāng)前相位設(shè)計可以明顯看出交通流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)可劃分為四個獨(dú)立集{b，h，x，z}{f，t}{n，e，y，q}{c，k}，得如下相位設(shè)計.相位一：路口①，③處人行道綠燈，即交通流x，z獲得通行許可;路口②，④處機(jī)動車直行綠燈，即交通流h，b獲得通行許可.相位二：路口②，④處機(jī)動車左轉(zhuǎn)綠燈，即交通流t，f獲得通行許可.相位三：路口②，④處人行道綠燈，即交通流y，q獲得通行許可;路口①，③處機(jī)動車直行綠燈，即交通流e，n獲得通行許可.相位四：路口①，③處機(jī)動車左轉(zhuǎn)綠燈，即交通流k，c獲得通行許可.

五、總?結(jié)

本文初步且系統(tǒng)地對樂山市老城區(qū)部分路口交通擁堵問題做出了分析、研究和處理，具體到個別有代表性的丁字路口、十字路口等.本文通過把交通流轉(zhuǎn)化為圖，再用圖論染色的相關(guān)知識展開說明，從而改變紅綠燈的相位控制模式，以達(dá)到避免機(jī)動車與行人同時獲得通行許可時出現(xiàn)的沖突現(xiàn)象.但本文在研究的過程中，由于老城區(qū)本身的環(huán)境和社會因素的限制，忽略了道路寬度、人口密度等一些有可能會對研究結(jié)果起到影響的條件，這也是我們在今后進(jìn)行研究時需要考慮的主要問題.在研究本文的過程中，我們通過與其他論文的對比和與其他學(xué)者的交流發(fā)現(xiàn)，我們選擇了圖論染色的方法，使得研究變得簡單、具體，且能夠有效解決問題，為以后的研究確定了一個大的框架.但該方法忽略了一些環(huán)境會帶來的影響，對得到的研究成果能不能更好地、更高效地解決實際問題還需要到實踐中具體操作，從而在后期的研究中加以改正和補(bǔ)充說明.

【參考文獻(xiàn)】

[1]劉攀，徐志攀，張曉銘.多岔路口交通信號燈控制系統(tǒng)的設(shè)計與實現(xiàn)[J].電腦知識與技術(shù)，2010（01）：208-209.

[2]尹麗子，崔瀟，于冰.圓染色在交通信號燈相位優(yōu)化設(shè)計中的應(yīng)用[J].山東大學(xué)學(xué)報（工學(xué)版），2006（05）：107-112.

[3]肖會敏，臧振春，崔春生.運(yùn)籌學(xué)及應(yīng)用[M].北京：清華大學(xué)出版社，2017.

[4]尹琳娟.圖論染色問題應(yīng)用研究[D].西安：西安電子科技大學(xué)，2009.

[5]朱求長.運(yùn)籌學(xué)及其運(yùn)用[M].武漢：武漢大學(xué)出版社，2012.

[6]陳吉珍，寧愛兵，支志兵，等.圖論中最大獨(dú)立集問題的精確算法[J].計算機(jī)工程與應(yīng)用，2016（01）：20-22，109.

[7]丁來浩.圖的幾類染色問題以及超圖中的彩色匹配[D].濟(jì)南：山東大學(xué)，2018.