(3.239.192.241) 您好!臺灣時間:2021/03/02 19:45
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳宣文
研究生(外文):Shiuan-wen Chen
論文名稱:圖形模型下交通號誌設定演算法
論文名稱(外文):Algorithms for the Traffic Light Setting Problem on the Graph Model
指導教授:楊昌彪楊昌彪引用關係
指導教授(外文):Chang-Biau Yang
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:63
中文關鍵詞:演算法圖形模型交通號誌
外文關鍵詞:graph modelalgorithmtraffic light
相關次數:
  • 被引用被引用:0
  • 點閱點閱:167
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近年來由於車子數量迅速地增加,各個城市面臨嚴重的交通擁擠問題。交通號誌設定問題主要是研究如何設定各個路口上的交通號誌使得車子的全部等待時間為最少。我們使用一個簡單的圖形模型來表示城市的交通網路,並且提出和分析交通號誌設定問題在此模型上的一些性質。首先我們利用這些性質提出了一個分支界定演算法(the branch and bound algorithm)來求得交通號誌設定問題的最佳解。另外,我們也使用了基因演算法、粒子族群最佳化演算法以及螞蟻演算法在此模型中找到近似最佳解。在此圖形模型中,我們還增加車子轉彎的假設條件讓此模型更現實化。在實驗中,藉由比較這些演算法對於交通號誌設定問題的影響,結果顯示出基因演算法是一個好的策略在我們的模型中來求得較好的解。最後,我們也轉換台灣高雄市的部份地圖在我們的圖形模型中並且測試比較各個演算法。
As the number of vehicles increases rapidly, traffic congestion has become a serious problem in a city. Over the past years, a considerable number of studies have been made on traffic light setting. The traffic light setting problem is to investigate how to set the given traffic lights such that the total waiting time of vehicles on the roads is minimized. In this thesis, we use a graph model to represent the traffic network. On this model, some characteristics of the setting problem can be presented and analyzed. We first devise a branch and bound algorithm for obtaining the optimal solution of the traffic light setting problem. In addition, the genetic algorithm (GA), the particle swarm optimization (PSO) and the ant colony optimization (ACO) algorithm are also adopted to get the near optimal solution. Then, to extend this model, we add the assumption that each vehicle can change its direction. By comparing the results of various algorithms, we can study the impact of these algorithms on the traffic light setting problem. In our experiments, we also transform the map of Kaohsiung city into our graph model and test each algorithm on this graph.
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0
Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Related Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 The Branch and Bound Strategy . . . . . . . . . . . . . . . . . . . . 6
2.3 Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . 11
2.5 Ant Colony Optimization Algorithm . . . . . . . . . . . . . . . . . . 13
Chapter 3. The Traffic Graph Model and Its Properties . . . . . . . 17
3.1 The Traffic Graph Model . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 The Stable Traffic Graph Model . . . . . . . . . . . . . . . . . . . . . 20
3.3 The Definition of Our Problem . . . . . . . . . . . . . . . . . . . . . 22
Chapter 4. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1 Input Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 The Branch and Bound Method . . . . . . . . . . . . . . . . . . . . . 26
4.3 The Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4 The Particle Swarm Optimization Method . . . . . . . . . . . . . . . 31
4.5 The Ant Colony Optimization Algorithm . . . . . . . . . . . . . . . . 34
Page
Chapter 5. The Extended Traffic Graph Model . . . . . . . . . . . . . 37
Chapter 6. Experimental Results and Discussion . . . . . . . . . . . . 39
Chapter 7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
[1] O. Biham, A. Middleton, and D. Levine, “Self-organization and a dynam-
ical transition in traffic-flow models,” Physical Review A, Vol. 46, No. 10,
pp. R6124–R6127, Nov. 1992.
[2] E. Brockfeld, R. Barlovic, A. Schadschneider, and M. Schreckenberg, “Optimiz-
ing traffic lights in a cellular automaton model for city traffic,” Physical Review
E, Vol. 64, No. 5, p. 056132, Oct. 2001.
[3] D. Chowdhury and A. Schadschneider, “Self-organization of traffic jams in
cities: Effects of stochastic dynamics and signal periods,” Physical Review E,
Vol. 59, No. 2, pp. R1311–R1314, Feb. 1999.
[4] J.-F. Dong, Optimizing the Traffic Signal Setting Problem on the Graph Model.
Master Thesis, National Sun Yat-Sen University, Kaohsiung, Taiwan, July 2006.
[5] R. M. D’Souza, “Geometric structure of coexisting phases found in the biham-
middleton-levine traffic model,” Physical Review E, Vol. 71, 2005.
[6] E. Elbeltagi, T. Hegazy, and D. Grierson, “Comparison among five
evolutionary-based optimization algorithms,” Advanced Engineering Informat-
ics, Vol. 19, pp. 43–53, 2005.
[7] M. E. Fouladvand and M. Nematollahi, “Optimization of green-times at an
isolated urban crossroads,” The European Physical Journal B, Vol. 22, pp. 395–
401, 2001.
[8] M. E. Fouladvand and N. H. Radja, “Optimized traffic flow at a single urban
crossroads: dynamical symmetry breaking,” tech. rep., Institute for Studies in
Theoretical Physics and Mathematics, 2001.
[9] M. E. Fouladvand, Z. Sadjadi, and M. R. Shaebani, “Optimized traffic flow at
a single intersection: traffic responsive signalization,” Journal of Physical A:
Mathematical and General, Vol. 37, pp. 561–576, 2004.
51
[10] D. W. Huang and W. N. Huang, “Optimization of traffic lights at crossroads,”
International Journal of Modern Physics C, Vol. 14, pp. 539–548, 2003.
[11] T. Kalganova, G.Russell, and A. Cumming, “Multiple traffic signal control
using a genetic algorithm,” Proc. of the Fourth International Conference on
Artificial Neural Networks and Genetic Algorithms (ICANNGA’99)., Portoroz,
Slovenia, pp. 220–228, 1999.
[12] J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proceedings of
the IEEE international conference on neural networks, Vol. 4, Perth, Australia,
pp. 1942–1948, 1995.
[13] R. C. T. Lee, S. S. Tseng, R. C. Chang, and Y. T. Tsai, Introduction to the
Design and Analysis of Algorithms. McGraw-Hill, 2005.
[14] I. McKendrick, “Applications of fuzzy logic control,” Proc. of ISA Interna-
tional England Section Conference, Advances in Control II, The Application of
Advanced and Expert Systems for On-Line Process Control, Birmingham, UK,
p. 15, Apr. 1992.
[15] Z. Michalewicz, Genetic algorithms + data structures = evolution programs.
Springer-Verlag, London, UK, 1996.
[16] K. Nagel and M. Schreckenberg, “A cellular automaton model for freeway traf-
fic,” Journal of Physical I France, Vol. 2, pp. 2221–2229, 1992.
[17] I. Porche, M. Sampath, R. Sengupta, Y.-L. Chen, and S. Lafortune, “A decen-
tralized scheme for real-time optimization of traffic signals,” Proceedings of the
1996 IEEE International Conference on Control Applications, Dearborn, MI,
pp. 582–589, Sept. 1996.
[18] T. Riedel and U. Brunner, “A control algorithm for traffic lights,” Proc. of the
First IEEE Conference on Control Applications, Dayton, OH, USA, pp. 901–
906, Sept. 1992.
[19] B. D. Schutter and B. D. Moor, “Optimal traffic light control for a single
intersection,” International symposium on nonlinear theory and its applications
(NOLTA ’97), San Diego, California, pp. 1085–1088, June 1997.
[20] C. B. Yang and Y. J. Yeh, “The model and properties of the traffic light prob-
lem,” Proc. of International Conference on Algorithms, Kaohsiung, Taiwan,
pp. 19–26, Dec. 1996.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔