You are here

Küme bölme problemlerinde genetik algoritma ile mesafe dengelenmesi

Genetic algorithm for distance balancing in set partitioning problems

Journal Name:

Publication Year:

Abstract (2. Language): 
In this study balancing is taken into consideration in the formation of groups according to the total travel distance as a set partitioning problem (SPP). Fitness functions that can test imbalance are proposed and mathematical models including these fitness functions are presented. In order to make balanced groupings, four different fitness functions are used. The first model aims to minimize total travel distance. The other two models are used for balancing and the last one constitutes a precedent as a multi-objective decision making problem. Genetic Algorithms (GAs) which is a meta-heuristic technique is used for the solution of the proposed models. Data is taken from the study of Akyurt et al. [1] and is used to balance groups in Football Leagues. Different groups are formed according to these models; effects of the results are examined among themselves and compared with the current situation. Additionally, all results are displayed on the maps.
Abstract (Original Language): 
Bu çalışmada Set Partitioning Problemlerinde (SPP) mesafeye göre gruplandırma yapılırken denge unsuru göz önünde bulundurulmuştur. Dengesizliği test edebilecek fitness functionlar önerilerek bu fonksiyonları içeren matematiksel modeller kurulmuştur. Dengeli gruplandırmayı yapabilmek için 4 farklı fitness function kullanılmıştır. İlk model toplam mesafeyi minimum kılmayı hedeflemiştir. Diğer iki model dengeleme için kullanılmıştır, son model ise çok amaçlı karar verme problemine örnek oluşturmaktadır. Modeller bir meta-sezgisel yöntem olan Genetik Algoritmalar (GAs) ile çözülmüştür. Çalışmada, kullanılan veriler Akyurt vd. [1] yaptıkları çalışmadan alınmış ve Futbol Liglerinde dengeli gruplama üzerine uygulanmıştır. Tüm bu modellere göre farklı gruplandırmalar yapılmış; sonuçların kendi aralarında etkileri incelenmiş ve mevcut durum ile ayrı ayrı karşılaştırılmıştır. Ayrıca tüm sonuçlar harita üzerinde gösterilmiştir.
47-61

REFERENCES

References: 

[1] I.Z. Akyurt, T. Keskintürk, B. Kiremitçi and S. Kiremitçi, Determination of Teams in
Groups of Turkish Football Federation Third League Classification Groups by Genetic
Algorithms. VIII. International Logistics and Supply Chain Congress, Istanbul,
Turkey, (2010).
[2] E. Balas, and M.W. Padberg, Set Partitioning: A Survey. In N. Christofides, A.
Mingozzi, P. Toth and C. Sandi (eds.), Combinatorial Optimization. John Wiley,
151–210, (1979).
[3] E. Balas, and M. Padberg, Set Partitioning: A Survey. SIAM Review, 18, 710–760,
(1976).
[4] Gershkoff, Optimizing Flight Crew Schedules. Interfaces, 19, 29–43, (1989).
[5] R.E. Marsten, An Algorithm for Large Set Partitioning Problems. Management
Science, 20, 774–787, (1974).
[6] R. Marsten, and F. Shepardson, Exact Solution of Crew Scheduling Problems Using
the Set Partitioning Model: Recent Successful Applications. Networks, 11, 165–177,
(1981).
[7] E. El-Darzi and G. Mitra, Solution of Set Covering and Set Partitioning Problems
Using Assignment Relaxations. Journal of Operations Research Society, 483-493,
(1992).
[8] E. El-Darzi and G. Mitra, Graph Theoretic Relaxations of Set Covering and Set
Partitioning Problems. European Journal of Operational Research, 87, 109–121,
(1995).
[9] J.E. Beasley and K. Jornsten, Enhancing an Algorithm for Set Covering Problems.
European Journal of Operational Research, 58, 293–300, (1992).
[10] C.Mannino and A. Sassano, Solving Hard Set Covering Problems. Operations
Research Letters, Volume 18, Issue 1, 1-5, (1995).
[11] D. Wedelin, An Algorithm for Large Scale 0-1 Integer Programing with Applications
to Airline Crew Scheduling. Annals of Operations Research, 57, 283–301, (1995).
[12] K. Hoffman and M. Padberg, Solving airline crew scheduling problems by branchand cut. Management Science, 39, 657–682, (1993).
[13] P. Avella, M. Boccia and A. Sforza, Solving a Fuel Delivery Problem by Heuristic and
Exact Approaches. European Journal of Operations Research, 152, 170–179,
(2004).
[14] I.D. Elhallaoui, Villeneuve, F. Soumis and G. Desaulniers, Dynamic Aggregation of
Set-Partitioning Constraints in Column Generation. Operations Research, 53, 632–
645, (2005).S. Kiremitci, İ.Z. Akyurt/ İstanbul Üniversitesi İşletme Fakültesi Dergisi 41, 1, (2012) 47-61 © 2012
60
[15] M.L. Fisher and P. Kedia, Optimal Solution of Set Covering/Partitioning Problems
Using Dual Heuristics. Management Science, 36, 674–688, (1990).
[16] T.J. Chan and C.A. Yano, A Multiplier Adjustment Approach for the Set Partitioning
Problem. Operations Research, 40, 40–47, (1992).
[17] T. Grossman and A. Wool, Computational Experience with Approximation
Algorithms for the Set Covering Problem. European Journal of Operational
Research, Volume 101, Issue 1, 81-92, (1997).
[18] E.K. Baker, L.D. Bodin, W.F. Finnegan and R.J. Ponder, Efficient Heuristic Solutions
to an Airline Crew Scheduling Problem. AIIE Transactions, 11, 79–85, (1979).
[19] E. Balas and A. Ho, Set Covering Algorithms Using Cutting Planes, Heuristics and
Subgradient Optimization: A Computational Study. Mathematical Programming
Study, 12, 37–60, (1980).
[20] F.J. Vasko and G.R. Wilson, An Efficient Heuristic for Large Set Covering Problems.
Naval Research Logistics Quarterly, 31, 163–171, (1984).
[21] M. Ball and A. Roberts, A Graph Partitioning Approach to Airline Crew Scheduling.
Transportation Science, 17, 4–31, (1985).
[22] D.M. Ryan and J.C. Falkner, On the Integer Properties of Scheduling Set
Partitioning Models. European Journal of Operational Research, 35, 422–456,
(1988).
[23] J.E. Beasley, A Lagrangian Heuristic for Set-Covering Problems. Naval Research
Logistics, 37, 151–164, (1990).
[24] L.W. Jacobs and M.J. Brusco, A Simulated Annealing-Based Heuristic for The SetCovering Problem (Working Paper), Operations Management and Information
Systems Department, Northern Illinois University, Dekalb, IL, March, (1993).
[25] S. Sen, Minimal Cost Set Covering Using Probabilistic Methods. In: Proc. 1993
ACM/SIGAPP Symposium on Applied Computing, 157–164, (1993).
[26] A. Atamtürk, G.L. Nemhauser and M.W.P. Savelsbergh, A Combined Lagrangian,
Linear Programming and Implication Heuristic for Large-Scale Set Partitioning
Problems. Journal of Heuristics, 1, 247–259, (1995).
[27] G. E. Liepins, M. R. Hilliard, M. Palmer, and M. Monow, Greedy Genetics, in
Grefenstette J. J., editor, Genetic Algorithm and Their Applications: Proceedings of
the Second International Conference on Genetic Algorithms, July, (1987).
[28] G. E. Liepins, M. R. Hilliard, J. Richardson, and M. Palmer, Genetic algorithms
applications to set covering and traveling salesman problems, in Brown (ed),
Operations Research and Artificial Intelligence: The Integration of Problem-Solving
Strategies, Kluwer Academic Publishers, (1990).
[29] K.S. Al Sultan, M.F. Hussain and J.S. Nizami, A Genetic Algorithm for the Set
Covering Problem. Journal of the Operational Research Society, 47, 702-709,
(1996).
[30] D. Levine, A Parallel Genetic Algorithm For The Set Partitioning Problem. In: I.H.
Osman and J.P. Kelly, Editors, Meta-heuristics: theory and applications, Kluwer
Academic Publishers, Dordrecht 23–35, (1996).
[31] P.C. Chu and J.E. Beasley, Constraint Handling in Genetic Algorithms: The Set
Partitioning Problem. Journal of Heuristics, 4, 323–357, (1998).S. Kiremitci, İ.Z. Akyurt/ İstanbul Üniversitesi İşletme Fakültesi Dergisi 41, 1, (2012) 47-61 © 2012
61
[32] J.E. Beasley, P.C. Chu, A Genetic Algorithm for the Set Covering Problem. European
Journal of Operational Research, Volume 94, Issue 2, 392-404, (1996).
[33] J. Kelly and J. Xu, A Set Partitioning Based Heuristic for The Vehicle Routing
Problem. INFORMS Journal on Computing, 11, 161–172, (1999).
[34] M. Lewis, G. Kochenberger and B. Alidae, A New Modeling and Solution Approach
for the Set-Partitioning Problem. Computers&Operations Research, Volume 35,
Issue 3, 807-813, (2008)
[35] İ. Güngör and E.U. Küçüksille, Küme Bölme Problemlerinin Genetik Algoritmayla
Optimizasyonu: Türkiye İkinci Futbol Ligi Uygulması. Review of Social Economics &
Business Studies, 5 (6), 381-394, (2005).
[36] T. Keskintürk, M.B. Yıldırım and M. Barut, An Ant Colony Optimization Algorithm for
Load Balancing in Parallel Machines with Sequence-Dependent Setup Times.
Computers & Operations Research, (article in Press).
[37] A. Joseph, A Concurrent Processing Framework for the Set Partitioning Problem.
Computers&Operations Research, 29, 1375-139, (2002).
[38] D.E. Goldberg, Genetic Algorithms in Search Optimization and Machine Learning.
Addison Wesley Publishing Company, USA, (1989).
[39] C.R. Reeves, Modern Heuristic Techniques for Combinatorial Problems. Mcgraw-Hill
Book Company Inc., Europe, (1995).
[40] O. Braysy, M. Gendreau, Vehicle Routing Problem with Time Windows, Part II:
Metaheuristics. Transportation Science, 39, 1, 119-139, (2005).
[41] İ.Z. Akyurt, T. Keskintürk, M.V. Arıkan, Determining The Parameters Of Periodic
Optional Replenishment Model With Genetic Algorithm. International Logistics And
Supply Chain Congress, Istanbul, Turkey, (2009).
[42] T. Keskintürk, Portföy Seçiminde Markowitz Modeli Için Yeni Bir Genetik Algoritma
Yaklaşımı. Yönetim, 18 (56), 81, (2007).

Thank you for copying data from http://www.arastirmax.com