Yıl 2011,
Cilt: 26 Sayı: 4, 0 - , 20.02.2013
Ö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
Kaynakça
- Dijkstra, E.W., “A Note on Two Problems in
- Connection with Graphs”, Numerische
- Mathematik, Vol 1, 269–271, 1959.
- Dantzig, G.B., “On the Shortest Route Through a
- Network”, Management Science, 187–190, 1960.
- Floyd, R.W., “Algorithm 97: Shortest Path”,
- Communications of the ACM 5, 1962.
- Beasley, D., Bull, D.R., and Martin, R.R., 1993a.
- “An Overview of Genetic Algorithms: Part 1”,
- Fundamentals. University Computing, Vol
- (2), 58–69, UK, 1993.
- Beasley, D., Bull, D.R., and Martin, R.R., 1993b.
- “An Overview of Genetic Algorithms: Part 2”,
- Research Topics University Computing, Vol
- (4), 170–181, UK, 1993.
- Bingul, Z., Sekmen, A.S. and Zein, S., “An
- Application of Multi-Dimensional Optimization
- Problems Using Genetic Algorithms”,
- Proceedings of the IASTED International
- Conference Intelligent Systems and Control,
- Santa Barbara, CA, USA, 1999.
- Bingul, Z., Sekmen, A.S. and Zein, S., “Genetic
- Algorithms Applied to Real Time Multi-objective
- Optimization Problems”, IEEE SoutheastCon
- Conference, Nashville, TN, USA, 2000.
- Drezner, Z. and Wesolowsky, G.O., “Network
- Design: Selection and Design of Links and
- Facility Location”, Transportation Research
- Part A: Policy and Practice, Vol 37, No 3, 241–
- , 2003.
- Xiaoyu J., “Models and Algorithm for Stochastic
- Shortest Path Problem”, Applied Mathematics
- and Computation, Vol 170, No 1, 503–514,
- -
- Daniele C., Martine L., Martha Salazar N.,
- “Reduction Approaches for Robust Shortest Path
- Problems”, Computers &Operations Research,
- Vol 38, No 11, 1610–1619, 2011.
- Bellman, E., “On a Routing Problem”, Appl.
- Math., Vol 16, 87–90, 1958.
- Dijkstra, E.W., “A Note on Two Problems in
- Connection with Graphs”, Numer. Math. 1, Vol
- , 269–271, 1959.
- Dreyfus, S., “An Appraisal of Some Shortest Path
- Algorithms”, Oper. Res., Vol 17, No 3, 395–412,
- -
- Wook, C., Ramakrishna, R.S., “A Genetic
- Algorithm for Shortest Path Routing Problem and
- the Sizing of Populations”, IEEE Transactions
- on Evolutionary Computation, Vol 6, No 6,
- -
- Munemoto, M., Takai, Y., Sato, Y., “A Migration
- Scheme for the Genetic Adaptive Routing Algorithm,” IEEE Int. Conf. Systems, Man, and
- Cybernetics, 2774–2779, 1998.
- Inagaki, J., Haseyama, M., Kitajima, H., “A
- Genetic Algorithm for Determining Multiple
- Routes and Its Applications,” IEEE Int. Symp.
- Circuits and Systems, 137–140, 1999.
- Liu, W., Wang, L.P., “Solving the Shortest Path
- Routing Problem Using Noisy Hopfield Neural
- Networks”, WRI International Conference on
- Communications and Mobile Computing:
- CMC 2009, Vol 2, 299-302, 2009.
- Gen, M., Lin, L., “A New Approach for Shortest
- Path Routing Problem by Random Key-Based
- GA”, Gecco 2006: Genetic and Evolutionary
- Computation Conference, Vol 1 and 2 , 1411–
- , 2006.
- Lin, L., Gen, M., Cheng, R.W.,” Priority-Based
- Genetic Algorithm for Shortest Path Routing
- Problem in OSPF”, Proceedings of the Third
- International Conference on Information and
- Management Sciences, Vol 3, 411–418, 2004.
- Current, J.R., Velle, C.S.R., Cohon, J.L., “The
- Maximum Covering/Shortest Path Problem: A
- Multiobjective Network Design and Routing
- Formulation”, European Journal of Operational
- Research, Vol 21(2), 189–199, 1985.
- Chabrier, A., “Vehicle Routing Problem with
- Elementary Shortest Path Based Column
- Generation”, Computers & Operations
- Research, Vol 33(10), 2972–2990, 2006.
- Misra, S., Oommen, B.J., “Dynamic Algorithms
- for the Shortest Path Routing Problem: Learning
- Automata-Based Solutions”, IEEE Transactions
- On Systems Man and Cybernetics Part BCybernetics,
- Vol 35(6), 1179–1192, 2005.
- Cai, X., T. Kloks, C.K. Wong, “Time-Varying
- Shortest Path Problems with Constraints”,
- Networks, Vol 29, No 3, 141-150, 1997.
- Orda, A., R. Rom., “Minimum Weight Paths in
- Time-Dependent Networks”, Networks, Vol 21,
- –319, 1991.
- Halpern, J., “Shortest Route with Time Dependent
- Length of Edges and Limited Delay Possibilities
- in Nodes”, Mathematical Methods of
- Operations Research, Vol 21, No 3, 117–124,
- -
- Cooke, K.L., Halsey E., “The Shortest Route
- Through a Network with Time-Dependent
- Internodal Transit Times”, Journal of
- Mathematical Analysis and Applications, Vol
- , No 3, 493–498, 1966.
Yıl 2011,
Cilt: 26 Sayı: 4, 0 - , 20.02.2013
Öz
Kaynakça
- Dijkstra, E.W., “A Note on Two Problems in
- Connection with Graphs”, Numerische
- Mathematik, Vol 1, 269–271, 1959.
- Dantzig, G.B., “On the Shortest Route Through a
- Network”, Management Science, 187–190, 1960.
- Floyd, R.W., “Algorithm 97: Shortest Path”,
- Communications of the ACM 5, 1962.
- Beasley, D., Bull, D.R., and Martin, R.R., 1993a.
- “An Overview of Genetic Algorithms: Part 1”,
- Fundamentals. University Computing, Vol
- (2), 58–69, UK, 1993.
- Beasley, D., Bull, D.R., and Martin, R.R., 1993b.
- “An Overview of Genetic Algorithms: Part 2”,
- Research Topics University Computing, Vol
- (4), 170–181, UK, 1993.
- Bingul, Z., Sekmen, A.S. and Zein, S., “An
- Application of Multi-Dimensional Optimization
- Problems Using Genetic Algorithms”,
- Proceedings of the IASTED International
- Conference Intelligent Systems and Control,
- Santa Barbara, CA, USA, 1999.
- Bingul, Z., Sekmen, A.S. and Zein, S., “Genetic
- Algorithms Applied to Real Time Multi-objective
- Optimization Problems”, IEEE SoutheastCon
- Conference, Nashville, TN, USA, 2000.
- Drezner, Z. and Wesolowsky, G.O., “Network
- Design: Selection and Design of Links and
- Facility Location”, Transportation Research
- Part A: Policy and Practice, Vol 37, No 3, 241–
- , 2003.
- Xiaoyu J., “Models and Algorithm for Stochastic
- Shortest Path Problem”, Applied Mathematics
- and Computation, Vol 170, No 1, 503–514,
- -
- Daniele C., Martine L., Martha Salazar N.,
- “Reduction Approaches for Robust Shortest Path
- Problems”, Computers &Operations Research,
- Vol 38, No 11, 1610–1619, 2011.
- Bellman, E., “On a Routing Problem”, Appl.
- Math., Vol 16, 87–90, 1958.
- Dijkstra, E.W., “A Note on Two Problems in
- Connection with Graphs”, Numer. Math. 1, Vol
- , 269–271, 1959.
- Dreyfus, S., “An Appraisal of Some Shortest Path
- Algorithms”, Oper. Res., Vol 17, No 3, 395–412,
- -
- Wook, C., Ramakrishna, R.S., “A Genetic
- Algorithm for Shortest Path Routing Problem and
- the Sizing of Populations”, IEEE Transactions
- on Evolutionary Computation, Vol 6, No 6,
- -
- Munemoto, M., Takai, Y., Sato, Y., “A Migration
- Scheme for the Genetic Adaptive Routing Algorithm,” IEEE Int. Conf. Systems, Man, and
- Cybernetics, 2774–2779, 1998.
- Inagaki, J., Haseyama, M., Kitajima, H., “A
- Genetic Algorithm for Determining Multiple
- Routes and Its Applications,” IEEE Int. Symp.
- Circuits and Systems, 137–140, 1999.
- Liu, W., Wang, L.P., “Solving the Shortest Path
- Routing Problem Using Noisy Hopfield Neural
- Networks”, WRI International Conference on
- Communications and Mobile Computing:
- CMC 2009, Vol 2, 299-302, 2009.
- Gen, M., Lin, L., “A New Approach for Shortest
- Path Routing Problem by Random Key-Based
- GA”, Gecco 2006: Genetic and Evolutionary
- Computation Conference, Vol 1 and 2 , 1411–
- , 2006.
- Lin, L., Gen, M., Cheng, R.W.,” Priority-Based
- Genetic Algorithm for Shortest Path Routing
- Problem in OSPF”, Proceedings of the Third
- International Conference on Information and
- Management Sciences, Vol 3, 411–418, 2004.
- Current, J.R., Velle, C.S.R., Cohon, J.L., “The
- Maximum Covering/Shortest Path Problem: A
- Multiobjective Network Design and Routing
- Formulation”, European Journal of Operational
- Research, Vol 21(2), 189–199, 1985.
- Chabrier, A., “Vehicle Routing Problem with
- Elementary Shortest Path Based Column
- Generation”, Computers & Operations
- Research, Vol 33(10), 2972–2990, 2006.
- Misra, S., Oommen, B.J., “Dynamic Algorithms
- for the Shortest Path Routing Problem: Learning
- Automata-Based Solutions”, IEEE Transactions
- On Systems Man and Cybernetics Part BCybernetics,
- Vol 35(6), 1179–1192, 2005.
- Cai, X., T. Kloks, C.K. Wong, “Time-Varying
- Shortest Path Problems with Constraints”,
- Networks, Vol 29, No 3, 141-150, 1997.
- Orda, A., R. Rom., “Minimum Weight Paths in
- Time-Dependent Networks”, Networks, Vol 21,
- –319, 1991.
- Halpern, J., “Shortest Route with Time Dependent
- Length of Edges and Limited Delay Possibilities
- in Nodes”, Mathematical Methods of
- Operations Research, Vol 21, No 3, 117–124,
- -
- Cooke, K.L., Halsey E., “The Shortest Route
- Through a Network with Time-Dependent
- Internodal Transit Times”, Journal of
- Mathematical Analysis and Applications, Vol
- , No 3, 493–498, 1966.
Toplam 103 adet kaynakça vardır.
Ayrıntılar
| Birincil Dil | Türkçe |
|---|---|
| Bölüm | Makaleler |
| Yazarlar | |
| Yayımlanma Tarihi | 20 Şubat 2013 |
| Gönderilme Tarihi | 20 Şubat 2013 |
| Yayımlandığı Sayı | Yıl 2011 Cilt: 26 Sayı: 4 |