交通號誌維修路線排程問題之研究--以臺南縣為例

Abstract

交通號誌系統在道路交通管制中扮演關鍵性的角色。良好的交通號誌之設計與運作，可節省投入交通管制的人力，並降低車輛肇事率。但目前國內交通號誌管理單位以人工安排維修路線的方式，仍無法滿足民眾對其維修效率的期盼。本研究旨在發展一套快速、高效率之交通號誌維修路線排程方法，藉以提昇號誌維修效率，促使整體交通號誌系統功能維持最佳狀態，減輕交通號誌故障對交通之衝擊。 本研究透過實際瞭解交通號誌維修程序，分析影響號誌維修路線之因素，及維修工作安排之特性，建立屬越野尋縱問題(Orienteering Problem, OP)之號誌維修路線排程數學模式。因OP為NP-hard問題，本研究乃以啟發式解法發展求解方法，以期能在合理的時間內完成求解。本研究所發展之啟發式解法程序包括：1)以最小成本插入法產生起始解；2)以節點交換法產生鄰域解以搜尋最佳解。另為跳離區域搜尋法常陷入區域最佳解之狀況，在產生鄰域解過程分別加入禁制搜尋法(Tabu search)及門檻接受法(Threshold Accepting )。經本研究所搜集例題之測試結果分析，無論採用TA或SA對起始解之改善程度,並無甚大差別；在TA+P與SA+P之測試模組測試結果比較中，以setting(1)參數值測試所得目標值較優於以setting(2)之測試結果。至於測試平均所費CPU時間則以TA+P模組最少，SA模組所費時間最多。

Traffic signal is the most important facility for traffic control. A superior maintenance plan could reduce operations costs and the impacts caused by traffic signal failures. The dispatcher arranges the maintenance route manually, which hardly satisfies the requirement for signal repair. The goal of this study is to develop a rapid and efficient method for solving signal repair routing problems. We will take the real case of Tainan county as an example. By interviewing the person who manages the repair duties, we analyses the character of repair routes and the factors which influence repair routing. An Orienteering Problem (OP) based mathematical model is then formulated. However, this problem is a NP-hard problem. Thus, we focus on developing an heuristics algorithm to obtain a good solution in a reasonable amount of time. The proposed algorithm includes two procedures: 1).The cheapest insertion procedure for obtaining the initial solution; 2).The nodes interchange procedure for searching optimum solution by generating neighbor solution. For improving solution to approach optimum solution, this study combines neighbor generating procedure with Tabu search / Threshold Accepting. The testing results show that out proposed algorithm result in tremendously improvement of the service routes design.