ZAMANA BAĞLI DİNAMİK EN KISA YOL PROBLEMİ İÇİN GENETİK ALGORİTMA TABANLI YENİ BİR ALGORİTMA

Öz

En kısa yol problemi için çok sayıda araştırma yapılmakta ve ortaya konulan çözümler başta bilgisayarmühendisliği ve endüstri mühendisliği olmak üzere çok farklı alanlarda uygulanmaktadır. Bu makalede yolmaliyetleri zamana bağlı dinamik olarak değişen en kısa yol probleminin çözümü için genetik algoritmakullanılarak yeni bir algoritma geliştirilmiştir. Önerilen algoritma ile literatürde yer alan algoritmalarınkarşılaştırılması için örnek bir uygulama geliştirilmiştir. Benzetim sonuçları geliştirilen algoritmanın dahabaşarılı olduğunu göstermiştir.

Anahtar Kelimeler

• Genetik algoritma, En kısa yol problemi, Ağlar

Kaynakça

1. Dijkstra, E.W., “A Note on Two Problems in
2. Connection with Graphs”, Numerische
3. Mathematik, Vol 1, 269–271, 1959.
4. Dantzig, G.B., “On the Shortest Route Through a
5. Network”, Management Science, 187–190, 1960.
6. Floyd, R.W., “Algorithm 97: Shortest Path”,
7. Communications of the ACM 5, 1962.
8. Beasley, D., Bull, D.R., and Martin, R.R., 1993a.

9. “An Overview of Genetic Algorithms: Part 1”,
10. Fundamentals. University Computing, Vol
11. (2), 58–69, UK, 1993.
12. Beasley, D., Bull, D.R., and Martin, R.R., 1993b.
13. “An Overview of Genetic Algorithms: Part 2”,
14. Research Topics University Computing, Vol
15. (4), 170–181, UK, 1993.
16. Bingul, Z., Sekmen, A.S. and Zein, S., “An
17. Application of Multi-Dimensional Optimization
18. Problems Using Genetic Algorithms”,
19. Proceedings of the IASTED International
20. Conference Intelligent Systems and Control,
21. Santa Barbara, CA, USA, 1999.
22. Bingul, Z., Sekmen, A.S. and Zein, S., “Genetic
23. Algorithms Applied to Real Time Multi-objective
24. Optimization Problems”, IEEE SoutheastCon
25. Conference, Nashville, TN, USA, 2000.
26. Drezner, Z. and Wesolowsky, G.O., “Network
27. Design: Selection and Design of Links and
28. Facility Location”, Transportation Research
29. Part A: Policy and Practice, Vol 37, No 3, 241–
30. , 2003.
31. Xiaoyu J., “Models and Algorithm for Stochastic
32. Shortest Path Problem”, Applied Mathematics
33. and Computation, Vol 170, No 1, 503–514,
34. -
35. Daniele C., Martine L., Martha Salazar N.,
36. “Reduction Approaches for Robust Shortest Path
37. Problems”, Computers &Operations Research,
38. Vol 38, No 11, 1610–1619, 2011.
39. Bellman, E., “On a Routing Problem”, Appl.
40. Math., Vol 16, 87–90, 1958.
41. Dijkstra, E.W., “A Note on Two Problems in
42. Connection with Graphs”, Numer. Math. 1, Vol
43. , 269–271, 1959.
44. Dreyfus, S., “An Appraisal of Some Shortest Path
45. Algorithms”, Oper. Res., Vol 17, No 3, 395–412,
46. -
47. Wook, C., Ramakrishna, R.S., “A Genetic
48. Algorithm for Shortest Path Routing Problem and
49. the Sizing of Populations”, IEEE Transactions
50. on Evolutionary Computation, Vol 6, No 6,
51. -
52. Munemoto, M., Takai, Y., Sato, Y., “A Migration
53. Scheme for the Genetic Adaptive Routing Algorithm,” IEEE Int. Conf. Systems, Man, and
54. Cybernetics, 2774–2779, 1998.
55. Inagaki, J., Haseyama, M., Kitajima, H., “A
56. Genetic Algorithm for Determining Multiple
57. Routes and Its Applications,” IEEE Int. Symp.
58. Circuits and Systems, 137–140, 1999.
59. Liu, W., Wang, L.P., “Solving the Shortest Path
60. Routing Problem Using Noisy Hopfield Neural
61. Networks”, WRI International Conference on
62. Communications and Mobile Computing:
63. CMC 2009, Vol 2, 299-302, 2009.
64. Gen, M., Lin, L., “A New Approach for Shortest
65. Path Routing Problem by Random Key-Based
66. GA”, Gecco 2006: Genetic and Evolutionary
67. Computation Conference, Vol 1 and 2 , 1411–
68. , 2006.
69. Lin, L., Gen, M., Cheng, R.W.,” Priority-Based
70. Genetic Algorithm for Shortest Path Routing
71. Problem in OSPF”, Proceedings of the Third
72. International Conference on Information and
73. Management Sciences, Vol 3, 411–418, 2004.
74. Current, J.R., Velle, C.S.R., Cohon, J.L., “The
75. Maximum Covering/Shortest Path Problem: A
76. Multiobjective Network Design and Routing
77. Formulation”, European Journal of Operational
78. Research, Vol 21(2), 189–199, 1985.
79. Chabrier, A., “Vehicle Routing Problem with
80. Elementary Shortest Path Based Column
81. Generation”, Computers & Operations
82. Research, Vol 33(10), 2972–2990, 2006.
83. Misra, S., Oommen, B.J., “Dynamic Algorithms
84. for the Shortest Path Routing Problem: Learning
85. Automata-Based Solutions”, IEEE Transactions
86. On Systems Man and Cybernetics Part BCybernetics,
87. Vol 35(6), 1179–1192, 2005.
88. Cai, X., T. Kloks, C.K. Wong, “Time-Varying
89. Shortest Path Problems with Constraints”,
90. Networks, Vol 29, No 3, 141-150, 1997.
91. Orda, A., R. Rom., “Minimum Weight Paths in
92. Time-Dependent Networks”, Networks, Vol 21,
93. –319, 1991.
94. Halpern, J., “Shortest Route with Time Dependent
95. Length of Edges and Limited Delay Possibilities
96. in Nodes”, Mathematical Methods of
97. Operations Research, Vol 21, No 3, 117–124,
98. -
99. Cooke, K.L., Halsey E., “The Shortest Route
100. Through a Network with Time-Dependent
101. Internodal Transit Times”, Journal of
102. Mathematical Analysis and Applications, Vol
103. , No 3, 493–498, 1966.