Konkav maliyetli ulaştırma problemi için genetik algoritma tabanlı sezgisel bir yaklaşım

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.

A heuristic approach based on genetic algorithm for concave cost transportation problem

Concave Cost Transportation Problem (CCTP) is one of the widely employed problems in real applications. In this problem, the unit cost is decreasing in the amount that is transported. Since these types of problems are nonlinear, it is difficult to solve them to optimality. In literature, metaheuristic techniques such as genetic algorithm, simulated annealing and tabu search have been successfully applied for solving these problems. In this study, we develop a new hybrid algorithm based on genetic algorithms for the problem. The efficiency and effec¬tiveness of the algorithm are investigated using twelve randomly generated test problems in which the number of suppliers and customers changes between 4 and 40. Comparisons with other heuristics based on simulated annealing, threshold acceptance and linear threshold acceptance shows that developed hybrid GA improves solution quality by 0.3% and 5% for four problems.

___

  • 1.Hitchcock, F.L., "The Distribution of a from Several Sources to Numerous Locations", Journal of Mathematical Physic, Cilt 20, 224-230, 1941.
  • 2.Winston, W.L., Operations Research: Applications and Algorithm, Third Edition, Duxbury Press, California, 1994.
  • 3.Ahuja, R.K., Magnanti, T.L., Orlin,J.B., Network flows, Prentice Hall, Upper Saddle River, New Jersey, 1993.
  • 4.Yan, S., Luo, S.C., "Probabilistic Local Search Algorithms for Concave Cost Transportation Network Problems", European Journal of Operational Research, Cilt 117, 511-521,1999.
  • 5.Larsson, T., Migdalas, A., Ronnqvist, M., "A Lagrangian Heuristic for the Capacitated Concave Minimum Cost Network Flow Problem", European Journal of Operational Research, Cilt 78, 116-129,1994.
  • 6.Erickson, R.E., Monma, C.L., Veinott, A.F., "Send-And-Split Method for Minimum Concave Cost Network Fows", Teknik Rapor, No 33, Department of Operations Research, Stanford University, Stanford, 1986.
  • 7.Florian, M., Klein, M., "Deterministic Production Planning with Concave Cost and Capacity Constraints", Management Science, Cilt 8, 12-20, 1971.
  • 8.Gallo, G., Sodini, C, "Adjacent Extreme Flows and Application to Min Concave Cost Flow Problems", Networks, Cilt 9, 95-121, 1979.
  • 9.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.
  • 10.Holland, J.H., Adaptation in Natural and Artificial Systems, Ann Arbor, University of Michigan Press, 1975.
  • 11.Chen, C.L., Vempati, V.S., Aljaber, N., "An Application of Genetic Algorithms for flow shop problems", European Journal of Operation Research, Cilt 80, 389-396, 1995.
  • 12.Reeves, C.R., "A Genetic Algorithms for Flowshop Sequencing", Computers and Operations Research, Cilt 22, Sayı I, 5-13, 1995.
  • 13.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.
  • 14.Murata, T., Ishibuchi, H., Tanaka, H., "Genetic Algorithms for Flow Shop Scheduling Problems", Computers and Industrial Enginering, Cilt 30, Sayı 4, 1061-1071,1996.
  • 15.Chen, C.L., Neppalli, R.V., Aljaber, N., "Genetic Algorithms Applied to the Continuous Flow Shop Problem", Computers and Industrial Engineering, Cilt 30, Sayı 4, 919-929, 1996.
  • 16.Dengiz, B., Altıparmak, F., Smith, A.E., "Local Search Genetic Algorithm for Optimal Design of Reliable Networks", IEEE Transactions on Evolutionary Computation, Cilt I, Sayı 3, 179-188, 1997.
  • 17.Dengiz, B., Altıparmak, F., Smith, A.E.,"Efficient Optimization of All Terminal Reliable Networks, Using an Evolutionary Approaches, IEEE Transactions on Reliability, Cilt 46, Sayı I, 18-26, 1997.
  • 18.Altıparmak, F., Dengiz, B., Smith, A.E., "Reliability Optimization of Computer Communication Networks Using Genetic Algorithms", IEEE International Conference on Systems, Man, and Cybernetics, Cilt 5,4676-4681, 1998.
  • 19.Katayama, K., Sakamoto, H., Narihisa, H., "The Efficiency of Hybrid Mutation Genetic Algorithm for the Traveling Salesman Problem", Mathematical and Computer Modelling, Cilt 31, 197-203, 2000.
  • 20.Borthfeldt, A., Gehring, H., "A Hybrid Genetic Algorithm for the Container Loading Problem", European Journal of Operational Research, Cilt 131,143-161,2001.
  • 21.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.
  • 22.Choi, I.C., Kim, S.I., Kim, H.S., "A Genetic Algorithm with A Mixed Region Search For the Asymmetric Traveling Salesman Problem", Computers & Operations Research, Cilt 30, Sayı 5, 773-786, 2003.
  • 23.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.
  • 24.Vignaux, G. A., Michalewicz, Z., "A Genetic Algorithm for the Linear Transportation Problem", IEEE Transactions on System, Man and Cybernetics, Cilt 21, Sayı 2, 1991.
  • 25.Gen, M., Li, Y., "Spanning Tree Based Genetic Algorithm for Bicriteria Fixed Charge Transportation Problem", Proceedings of the Congress on Evolutionary Computation, Washington DC, 2265-2271, 1999.
  • 26.Gen, M., Ida, K., Li, Y, "Bicriteria Transportation Problem by Hybrid Genetic Algorithm", Computers and Industrial Engineering, Cilt 35, Sayı 1-2, 363-366,1998.
  • 27.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.
  • 28.Gottlieb, J., Paulmann, L., "Genetic Algorithm for the Fixed Charge Transportation Problems", Proceedings of the IEEE International Conference on Evolutionary Computations, Anchorage, 330-335,1998.
  • 29.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.
  • 30.Gottlieb, J., Eckert, C, "A Comparison of Two Representations for trie Fixed Charge Transportation Problem", Lecture Notes in Computer Science, Cilt 1917, 345-354,2000.
  • 31.Eckert, C, Gottlieb, J., "Direct Representation and Variation Operators For the Fixed Charge Transportation Problem", Lecture Notes in Computer Science, Cilt 2439, 77-87,2002.
  • 32.Goldberg, D.E., Genetic Algorithms: in Search, Optimization and Machine Learning, Addison-Wesley, 1989.
  • 33.Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, Berlin, Heidelberg, 1992.
  • 34.Gen, M., Cheng, R., Genetic Algorithms and Engineering Optimization, John Wiley & Sons, New York, 2000.
  • 35.Prüfer, H., "Neuer Beweis eines Satzes ueber Permutationen", Archiv für Mathematik und Physik, Cilt 27, 742-744,1918.
  • 36.Zhou, G., Gen, M., "A Note on Genetic Algorithms for the Degree-Constrained Spanning Tree Problem", Networks, Cilt 30, 91-95,1997.
  • 37.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.
  • 38.Krishnamoorthy, M., Ernst, A.T., "Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree", Journal Of Heuristics, Cilt 7, 587-611,2001.
  • 39. 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.
Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi-Cover
  • ISSN: 1300-1884
  • Yayın Aralığı: Yılda 4 Sayı
  • Başlangıç: 1986
  • Yayıncı: Oğuzhan YILMAZ