Iterated modified tabu search based equitable coloring for scheduling cricket world cup tournament

Abstract

In this article, an Iterated Modified Tabu Search (IMTS) approach is presented by improving certain aspects of general Tabu Search to enhance the approximation of the Equitable coloring problem (ECP) problem for a real-world problem of scheduling the ICC Cricket World Cup tournament. The proposed IMTS introduces new point generation mechanisms and parameter updating rules to achieve this objective of tournament scheduling. The IMTS algorithm defines different k-ECP instances and utilizes the search process to determine the optimal solution for instance of k-ECP by estimating the minimum k-coloring value. An illustration of resolving the Cricket World Cup tournament scheduling problem using the proposed IMTS algorithm is provided. Also, an assessment of the IMTS is also performed on a commonly used benchmark instances. Both the results illustrate that the IMTS provided comparatively better solution with high quality and computational efficiency.

Keywords

• Equitable coloring problem
• Iterated Modified Tabu Search
• Scheduling Problem
• Cricket World Cup
• Computational Efficiency

Supporting Institution

nil

Project Number

nil

Thanks

nil

References

1. [1] Jonathan L Gross and Jay Yellen. Graph theory and its applications. CRC Press, 2005.
2. [2] LR Foulds. Graph theory applications. Springer Science & Business Media, 2012.
3. [3] Narsingh Deo. Graph theory with applications to engineering and computer science. Courier Dover Publications, 2017.
4. [4] P. M. Pardalos, T. Mavridou, and J. Xue. The graph coloring problem: A bibliographic survey. In Handbook of combinatorial optimization, pages 1077–1141. Springer, 1998.
5. [5] T. Vredeveld and J. K. Lenstra. On local search for the generalized graph coloring problem. Operations Research Letters, 31(1):28–34, 2003.
6. [6] H. Furmanczyk and M. Kubale. Equitable coloring of graphs. Contemporary mathematics, 352:35–54, 2006.
7. [7] H. Furmańczyk. Equitable coloring of graph products. Opuscula Mathematica, 26(1):31–44, 2006.
8. [8] H. Furmańczyk and M. Kubale. Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling. Archives of Control Sciences, 25(1):109–116, 2015.

9. [9] A. Drexl and S. Knust. Sports league scheduling: graph-and resource-based models. Omega, 35(5):465–471, 2007.
10. [10] R. Lewis and J. Thompson. On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research, 38(1):190–204, 2011.
11. [11] Z. Yan, W. Wang, and X. Zhang. Equitable colorings of cartesian products with balanced complete multipartite graphs. Discrete Applied Mathematics, 180:200–203, 2015.
12. [12] L. Bahiense, Y. Frota, T. F. Noronha, and C. C. Ribeiro. A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives. Discrete Applied Mathematics, 164:34–46, 2014.
13. [13] P. San Segundo. A new dsatur-based algorithm for exact vertex coloring. Computers & Operations Research, 39(7): 1724–1733, 2012.
14. [14] I. Mendez-Diaz, G. Nasini, and D. Severin. A polyhedral approach for the equitable coloring problem. Discrete Applied Mathematics, 164:413–426, 2014.
15. [15] I. Mendez-Diaz, G. Nasini, and D. Severin. An exact dsatur based algorithm for the equitable coloring problem. Electronic Notes in Discrete Mathematics, 44:281–286, 2013.
16. [16] I. Mendez-Diaz, G. Nasini, and D. Severin. A dsatur based algorithm for the equitable coloring problem. Computers & Operations Research, 57:41–50, 2015.
17. [17] I. Mendez-Diaz, G. Nasini, and D. Severin. A tabu search heuristic for the equitable coloring problem. In International Symposium on Combinatorial Optimization. Springer, 2014.
18. [18] W. Wang, J. K. Hao, and Q. Wu. Tabu search with feasible and infeasible searches for equitable coloring. Engineering Applications of Artificial Intelligence, 71:1–14, 2018.
19. [19] X. Lai, J. K. Hao, and F. Glover. Backtracking based iterated tabu search for equitable coloring. Engineering Applications of Artificial Intelligence, 46:269–278, 2015.
20. [20] W. Sun, J. K. Hao, W. Wang, and Q. Wu. Memetic search for the equitable coloring problem. Knowledge-Based Systems, page 105000, 2019.
21. [21] P. Galinier and A. Hertz. A survey of local search methods for graph coloring. Computers & Operations Research, 33(9): 2547–2562, 2006.
22. [22] P. Galinier, Z. Boujbel, and MC. Fernandes. An efficient memetic algorithm for the graph partitioning problem. Annals of Operations Research, 191(1):1–22, 2011.
23. [23] P. Galinier, J. P. Hamiez, J. K. Hao, and D. Porumbel. Recent advances in graph vertex coloring. In Handbook of optimization, pages 505–528. Springer, 2013.
24. [24] S. An, S. Yang, S. L. Ho, T. Li, and W. Fu. A modified tabu search method applied to inverse problems. A modified tabu search method applied to inverse problems, 47(5):1234–1237, 2010.
25. [25] R. Lewis and J. Thompson. On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research, 38(1):190–204, 2011.