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

Murat DENER, M. Ali AKCAYOL, Sinan TOKLU, Ömer Faruk BAY
3.098 1.390

Ö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

Tam metin:

PDF


Referanslar


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.




Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.