臺灣博碩士論文加值系統

交通號誌時序設定問題是如何設定紅綠燈的時間，使車輛在十字路口等待
時間降至最少。此問題相當複雜，因此，我們首先將問題加以簡化。假設
每個路口的紅綠燈週期均相同（一半時間為綠燈，另一半時間為紅燈），
設為Ｔ，每個交叉點（頂點）只有一個燈號，且不考慮車流量問題及車輛
轉彎問題。我們發現圖形的著色問題（ coloring problem ）是我們問題
的特例。而圖形的K-Colorability問題，在 $K$ $\geq$ $3$ 時是 NP-
complete。故我們的問題在 $T$ $\geq$ $3$ 時是NP-complete。在這份
報告中，我們將提出一個方法去找尋一個多邊形的最小懲罰值 (penalty)
。最後，我們將推薦一個 heuristic 演算法來解決在一個交通網路上，
交通號誌的時序設定問題。

The timing setting problem is: set the timings of traffic
lights such that the waiting time of cars on intersections of
roads is minimized. This problem is very sophisticated. Thus,
we shall first simplify the problem. We assume that the periods
of the traffic lights on all intersections of roads are the
same and the period is denoted as $T$. Besides, the green light
is on during one half of the period and the red light is on
during another half of the period. We do not consider the
traffic flow and vehicles turning their directions. We find
that the graph vertex coloring problem is a special case of our
problem. And, the $k$-colorability problem on a graph is NP-
complete if $k$ $\geq 3$. Hence, our problem is NP-complete for
$T \geq 3$. In this thesis, we will give a method to find the
minimum penalty of a polygon and a polynomial-time algorithm to
find the minimum penalty of a path. Finally, we will propose a
heuristic algorithm to solve the traffic light problem.