Abstract
In this study balancing is taken into consideration in formation of groups according to 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. First model aims to minimize total travel distance. 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 for balanced groupings 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.
References
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).
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).
E. Balas, and M. Padberg, Set Partitioning: A Survey, SIAM Review, 18, 710–760, (1976).
Gershkoff, Optimizing Flight Crew Schedules, Interfaces, 19, 29–43, (1989)
R.E. Marsten, An Algorithm for Large Set Partitioning Problems, Management Science, 20, 774–787, (1974).
R. Marsten and F. Shepardson, Exact solution of crew Scheduling Problems using the set partitioning model: recent successful applications, Networks, 11, 165–177, (1981).
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).
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).
J.E. Beasley and K. Jornsten, Enhancing an algorithm for set covering problems. European Journal of Operational Research, 58. 293–300, (1992).
C.Mannino and A. Sassano, Solving hard set covering problems, Operations Research Letters, Volume 18, Issue 1, 1-5, (1995).
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).
K. Hoffman and M. Padberg, Solving airline crew scheduling problems by branch-and cut. Management Science, 39, 657–682, (1993).
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).
I.D. Elhallaoui, Villeneuve, F. Soumis and G. Desaulniers, Dynamic aggregation of set-partitioning constraints in column generation, Operations Research, 53, 632–645, (2005).
M.L. Fisher and P. Kedia, Optimal solution of set covering/partitioning problems using dual heuristics., Management Science, 36, 674–688, (1990).
T.J. Chan and C.A. Yano, A multiplier adjustment approach for the set partitioning problem. Operations Research, 40, S40–S47, (1992).
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).
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).
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).
F.J. Vasko and G.R. Wilson, An efficient heuristic for large set covering problems. Naval Research Logistics Quarterly, 31, 163–171, (1984).
M. Ball and A. Roberts, A graph partitioning approach to airline crew scheduling. Transportation Science, 17, 4–31, (1985).
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).
J.E. Beasley, A Lagrangian heuristic for set-covering problems. Naval Research Logistics, 37, 151–164, (1990).
L.W. Jacobs and M.J. Brusco, A simulated annealing-based heuristic for the set-covering problem (Working Paper), Operations Management and Information Systems Department, Northern Illinois University, Dekalb, IL (March 1993).
S. Sen, Minimal cost set covering using probabilistic methods. In: Proc. 1993 ACM/SIGAPP Symposium on Applied Computing, 157–164, (1993).
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).
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).
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).
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).
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).
P.C. Chu and J.E. Beasley, Constraint handling in genetic algorithms: the set partitioning problem, Journal of Heuristics, 4, 323–357, (1998).
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).
J. Kelly and J. Xu, A set partitioning based heuristic for the vehicle routing problem, INFORMS Journal on Computing, 11, 161–172, (1999).
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)
İ. 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).
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).
A. Joseph, A Concurrent Processing Framework for the Set Partitioning Problem, Computers&Operations Research, 29, 1375-1391, (2002).
D.E. Goldberg, Genetic Algorithms in Search Optimization and Machine Learning, Addison Wesley Publishing Company, USA, (1989).
C.R. Reeves, Modern Heuristic Techniques for Combinatorial Problems, Mcgraw-Hill Book Company Inc., Europe, (1995).
O. Braysy, M. Gendreau, Vehicle Routing Problem with Time Windows, Part II: Metaheuristics, Transportation Science, 39 (1), 119-139, (2005).
I. 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).
T. Keskintürk, Portföy Seçiminde Markowitz Modeli Için Yeni Bir Genetik Algoritma Yaklaşımı, Yönetim, 18 (56), 81, (2007).
Keywords
Details
| Primary Language | Turkish |
|---|---|
| Journal Section | Makaleler |
| Authors | |
| Publication Date | October 22, 2012 |
| Published in Issue | Year 2012 Volume: 41 Issue: 1 |