KONKAV MALİYETLİ ULAŞTIRMA PROBLEMİ İÇİN GENE-TİK ALGORİTMA TABANLI SEZGİSEL BİR YAKLAŞIM

Yıl 2005, Cilt: 20 Sayı: 4, 0 - , 10.04.2013

İsmail Karaoğlan Fulya Altıparmak

Öz

Konkav Maliyetli Ulaştırma Problemi (KMUP), gerçek hayatta sık karşılaşılan problemlerden birisidir. Doğrusal maliyetli problemlerin aksine, KMUP’de taşınacak miktar arttıkça birim taşıma maliyeti azalmaktadır. Bu tür problemlerde doğrusal olmayan maliyet fonksiyonundan dolayı klasik optimizasyon yöntemleri ile en iyi çözüme ulaşmak mümkün olmayabilir. Son yıllarda, genetik algoritmalar, tavlama benzetimi ve tabu arama gibi genel amaçlı sezgisel yöntemlerin bu tür zor problemlerin çözümünde başarıyla kullanıldığı görülmektedir. Bu çalışmada, KMUP için genetik algoritmalara dayalı bir karma sezgisel algoritma (karma GA) geliştirilmiştir. Algoritmanın etkinliği, tedarikçi ve müşteri sayısının 4 ile 40 arasında değiştiği ve rassal olarak üretilen 12 problem üzerinde incelenmiştir. Geliştirilen karma GA, literatürde bu problem için geliştirilmiş olan tavlama benzetimi, eşik kabulü ve doğrusal eşik kabulü yöntemine dayalı sezgisel algoritmalar ile karşılaştırılmıştır. Karşılaştırma sonucunda, geliştirilen karma GA ile dört problem için çözüm kalitesinde %0.3 ile %5 arasında iyileşmenin olduğu görülmüştür.

Anahtar Kelimeler

Ulaştırma problemi, genetik algoritmalar, yayılan ağaç, tavlama benzetimi, eşik kabulü.

Kaynakça

• Hitchcock, F.L., “The Distribution of a Product from Several Sources to Numerous Locations”, Journal of Mathematical Physic, Cilt 20, 224-230, 1941.
• Winston, W.L., Operations Research: Applica-tions and Algorithm, Third Edition, Duxbury Press, California, 1994.
• Ahuja, R.K., Magnanti, T.L., Orlin,J.B., Network flows, Prentice Hall, Upper Saddle River, New Jersey, 1993.
• Yan, S., Luo, S.C., “Probabilistic Local Search Algorithms for Concave Cost Transportation Net-work Problems”, European Journal of Opera-tional Research, Cilt 117, 511-521, 1999.
• Larsson, T., Migdalas, A., Ronnqvist, M., “A Lagrangian Heuristic for the Capacitated Con-cave Minimum Cost Network Flow Problem”, European Journal of Operational Research, Cilt 78, 116-129, 1994.
• Erickson, R.E., Monma, C.L., Veinott, A.F., “Send-And-Split Method for Minimum Concave Cost Network Fows”, Teknik Rapor, No 33, De-partment of Operations Research, Stanford Uni-versity, Stanford, 1986.
• Florian, M., Klein, M., “Deterministic Production Planning with Concave Cost and Capacity Con-straints”, Management Science, Cilt 8, 12-20, 1971.
• Gallo, G., Sodini, C., “Adjacent Extreme Flows and Application to Min Concave Cost Flow Prob-lems”, Networks, Cilt 9, 95-121, 1979.
• Gallo, G., Sandi, C., Sodini, C., “An Algorithm for the Min Concave Cost Flow Problem”, European Journal of Operational Research, Cilt 4, 248-255, 1980.
• Holland, J.H., Adaptation in Natural and Artifi-cial Systems, Ann Arbor, University of Michigan Press, 1975.
• Chen, C.L., Vempati, V.S., Aljaber, N., “An Ap-plication of Genetic Algorithms for flow shop problems”, European Journal of Operation Re-search, Cilt 80, 389-396, 1995.
• Reeves, C.R., “A Genetic Algorithms for Flowshop Sequencing”, Computers and Operations Research, Cilt 22, Sayı 1, 5-13, 1995.
• Murata, T., Ishibuchi, H., Tanaka, H., “Multi-Objective Genetic Algorithms and Its Applications to Flow Shop Scheduling”, Computers and In-dustrial Engineering, Cilt 30, Sayı 4, 957-968, 1996.
• Murata, T., Ishibuchi, H., Tanaka, H., “Genetic Algorithms for Flow Shop Scheduling Problems”, Computers and Industrial Enginering, Cilt 30, Sayı 4, 1061-1071, 1996.
• Chen, C.L., Neppalli, R.V., Aljaber, N., “Genetic Algorithms Applied to the Continuous Flow Shop Problem”, Computers and Industrial Engineer-ing, Cilt 30, Sayı 4, 919-929, 1996.
• Dengiz, B., Altıparmak, F., Smith, A.E., “Local Search Genetic Algorithm for Optimal Design of Reliable Networks”, IEEE Transactions on Evo-lutionary Computation, Cilt 1, Sayı 3, 179-188, 1997.
• Dengiz, B., Altıparmak, F., Smith, A.E.,”Efficient Optimization of All Terminal Reliable Networks, Using an Evolutionary Approaches, IEEE Trans-ac¬tions on Reliability, Cilt 46, Sayı 1, 18-26, 1997.
• Altıparmak, F., Dengiz, B., Smith, A.E., “Reliabil-ity Optimization of Computer Communica-Tion Networks Using Genetic Algorithms”, IEEE In-ternational Conference on Systems, Man, and Cybernetics, Cilt 5, 4676-4681, 1998.
• Katayama, K., Sakamoto, H., Narihisa, H., “The Efficiency of Hybrid Mutation Genetic Algorithm for the Traveling Salesman Problem”, Mathema-tical and Computer Modelling, Cilt 31, 197-203, 2000.
• Borthfeldt, A., Gehring, H., “A Hybrid Genetic Algorithm for the Container Loading Problem”, European Journal of Operational Research, Cilt 131, 143-161, 2001.
• Berger, J., Barkaoui, M., “A Parallel Hybrid Ge-netic Algorithm for the Vehicle Routing Problem with Time Windows”, Computers & Operations Research, Cilt 31, Sayı 12, 2037-2053, 2004.
• Choi, I.C., Kim, S.I., Kim, H.S., “A Genetic Algo-rithm with A Mixed Region Search For the Asymmetric Traveling Salesman Problem”, Computers & Operations Research, Cilt 30, Sayı 5, 773-786, 2003.
• Michalewicz, Z., Vignaux, G. A., Hobbs, M., “A non-Standard Genetic Algorithm for the Nonlinear Transportation Problem”, ORSA Journal of Computing, Cilt 3, Sayı 4, 307-316, 1991.
• Vignaux, G. A., Michalewicz, Z., “A Genetic Algorithm for the Linear Transportation Problem”, IEEE Transactions on System, Man and Cy-bernetics, Cilt 21, Sayı 2, 1991.
• Gen, M., Li, Y., “Spanning Tree Based Genetic Algorithm for Bicriteria Fixed Charge Transporta-tion Problem”, Proceedings of the Congress on Evolutionary Computation, Washington DC, 2265-2271, 1999.
• Gen, M., Ida, K., Li, Y, “Bicriteria Transportation Problem by Hybrid Genetic Algorithm”, Comput-ers and Industrial Engineering, Cilt 35, Sayı 1-2, 363-366, 1998.
• Li, Y.Z., M. Gen, “Spanning Tree-Based Genetic Algorithm For Bicriteria Transportation Problem With Fuzzy Coefficients”, Australian Journal of Intelligent Information Processing Systems, Cilt 4, Sayı 3, 220-229, 1998.
• Gottlieb, J., Paulmann, L., “Genetic Algorithm for the Fixed Charge Transportation Problems”, Pro-ceedings of the IEEE International Conference on Evolutionary Computations, Anchorage, 330-335, 1998.
• Syarif, A., Gen, M., “Solving Exclusionary Side Constrained Transportation Problem by Using Hybrid Spanning Tree-Based Genetic Algorithm”, Journal of Intelligent Manufacturing, Cilt 14, 389-399, 2003.
• Gottlieb, J., Eckert, C., “A Comparison of Two Representations for the Fixed Charge Transporta-tion Problem”, Lecture Notes in Computer Sci-ence, Cilt 1917, 345-354, 2000.
• Eckert, C., Gottlieb, J., “Direct Representation and Variation Operators Fort He Fixed Charge Trans-portation Problem”, Lecture Notes in Computer Science, Cilt 2439, 77-87, 2002.
• Goldberg, D.E., Genetic Algorithms: in Search, Optimization and Machine Learning, Addison-Wesley, 1989.
• Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, Berlin, Heidelberg, 1992.
• Gen, M., Cheng, R., Genetic Algorithms and Engineering Optimization, John Wiley & Sons, New York, 2000.
• Prüfer, H., “Neuer Beweis eines Satzes ueber Permutationen“, Archiv für Mathematik und Physik, Cilt 27, 742-744, 1918.
• Zhou, G., Gen, M., “A Note on Genetic Algorithms for the Degree-Constrained Spanning Tree Problem”, Networks, Cilt 30, 91-95, 1997.
• Zhou, G., Gen, M., “Approach to the Degree-Constrained Minimum Spanning Tree Problem Using Genetic Algorithm”, Engineering Design and Automation, Cilt 3, 157-165, 1997.
• Krishnamoorthy, M., Ernst, A.T., “Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree”, Journal Of Heuristics, Cilt 7, 587-611, 2001.
• Lo, C.C., Chang, W.H., “A Multiobjective Hybrid Genetic Algorithm for the Capacitated Multipoint Network Design Problem”, IEEE Transactions on System, Man and Cybernetics Part B, Cilt 30, Sayı 3, 461-470, 2000.