
Dr Rhyd Lewis
Senior Lecturer
- Email:
- lewisr9@cardiff.ac.uk
- Telephone:
- +44 (0)29 2087 4856
- Location:
- M/1.32, Maths and Education Building , Senghennydd Road, Cardiff, CF24 4AG
- Media commentator
- Available for postgraduate supervision
Rhyd Lewis is a reader at the School of Mathematics.
Administrative duties
School
- Director of the MSc in Operational Research and Applied Statistics, and the MSc in Operational Research, Applied Statistics and Risk
- Fellow of the Cardiff University Data Innovation Research Institute
- Member of Operational Research Group and the Planning and Optimisation Group
National/International
- Associate editor for the International Journal of Metaheuristics
- Program committee member for the following conferences: Evolutionary Computation in Combinatorial Optimisation (EvoCop), the Practice and Theory of Automated Timetabling (PATAT), the Metaheuristics International Conference (MIC), and the Genetic and Evolutionary Computation Conference (GECCO).
Personal website
Rhyd Lewis is a reader research at the School of Mathematics, Cardiff University, Wales. He holds a PhD in computing and operational research (Edinburgh Napier University, 2006) and is the author of the book Graph Colouring: Algorithms and Applications (Springer, 2015).
Professional memberships
- Fellow of the Higher Education Academy
2019
- Lewis, R., Thiruvady, D. and Morgan, K. 2019. Finding happiness: An analysis of the maximum happy vertices problem. Computers and Operations Research 103, pp. 265. (10.1016/j.cor.2018.11.015)
2018
- Hawa, A. L., Lewis, R. and Thompson, J. M. 2018. Heuristics for the score-constrained strip-packing problem. Presented at: COCOA 2018: International Conference on Combinatorial Optimization and Applications, Atlanta, GA, USA, 15-17 December 2018 Presented at Kim, D., Uma, R. N. and Zelikovsky, A. eds.Combinatorial Optimization and Applications: 12th International Conference, COCOA 2018, Atlanta, GA, USA, December 15-17, 2018, Proceedings, Vol. 11346. Lecture Notes in Computer Science Springer Verlag pp. 449., (10.1007/978-3-030-04651-4_30)
- Lewis, R. 2018. Two example optimisation problems from the world of education. Presented at: OR Society Annual Conference (OR60), Lancaster, UK, 11-13 Sep 2018.
- Lewis, R. and Smith-Miles, K. 2018. A heuristic algorithm for finding cost-effective solutions to real-world school bus routing problems. Journal of Discrete Algorithms 52-53, pp. 2-17. (10.1016/j.jda.2018.11.001)
- Hardy, B., Lewis, R. and Thompson, J. M. 2018. Tackling the edge dynamic graph colouring problem with and without future adjacency information. Journal of Heuristics 24(3), pp. 321-343. (10.1007/s10732-017-9327-z)
- Lewis, R., Smith-Miles, K. and Phillips, K. 2018. The school bus routing problem: An analysis and algorithm. Presented at: IWOCA 2017: 28th International Workshop on Combinatorial Algorithms, Newcastle, NSW, Australia, 17-21 July 2017 Presented at Brankovic, L., Ryan, J. and Smyth, W. F. eds.Combinatorial Algorithms: 28th International Workshop, IWOCA 2017, Newcastle, NSW, Australia, July 17-21, 2017, Revised Selected Papers. Lecture Notes in Computer Science Springer pp. 287-298., (10.1007/978-3-319-78825-8_24)
2017
- Lewis, R. and Holborn, P. 2017. How to pack trapezoids: exact and evolutionary algorithms. IEEE Transactions on Evolutionary Computation 21(3), pp. 463-476. (10.1109/TEVC.2016.2609000)
2016
- Lewis, R. and Carroll, F. 2016. Creating seating plans: a practical application. Journal of the Operational Research Society 67(11), pp. 1353-1362. (10.1057/jors.2016.34)
- Padungwech, W., Thompson, J. and Lewis, R. 2016. Investigating edge-reordering procedures in a tabu search algorithm for the capacitated arc routing problem. Presented at: HM 2016: International Workshop on Hybrid Metaheuristics, Plymouth, UK, 8-10 June 2016 Presented at Blesa, M. J., Blum, C. and Cangelosi, A. eds.Hybrid Metaheuristics: 10th International Workshop, HM 2016, Plymouth, UK, June 8-10, 2016, Proceedings, Vol. 9668. Lecture Notes in Computer Science Cham: Springer pp. 62-74., (10.1007/978-3-319-39636-1_5)
- Hardy, B., Lewis, R. and Thompson, J. M. 2016. Modifying colourings between time-steps to tackle changes in dynamic random graphs. Presented at: EvoCOP 2016: European Conference on Evolutionary Computation in Combinatorial Optimization, Porto, Portugal, 30 March - 1 April 2016 Presented at Chicano, F., Hu, B. and Garcia-Sanchez, P. eds.Evolutionary Computation in Combinatorial Optimization: 16th European Conference, EvoCOP 2016, Porto, Portugal, March 30 – April 1, 2016, Proceedings, Vol. 9595. Springer pp. 186-201., (10.1007/978-3-319-30698-8_13)
- Lewis, R. 2016. Graph colouring: an ancient problem with modern applications. Impact 3(1), pp. 47-50. (10.1080/2058802X.2016.11963998)
- Kheiri, A.et al. 2016. A Sequence-based selection hyper-heuristic: a case study in nurse rostering. Presented at: PATAT 2016: 11th International Conference on the Practice and Theory of Automated Timetabling, Udine, Italy, 23-26 August 2016 Presented at Burke, E. K. et al. eds.PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling. pp. 503-505.
2015
- Lewis, R. 2015. A guide to graph colouring: algorithms and applications.. Springer.
- Lewis, R. and Thompson, J. 2015. Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem. European Journal of Operational Research 240(3), pp. 637-648. (10.1016/j.ejor.2014.07.041)
- Lewis, R. 2015. Graph coloring and recombination. In: Kacprzyk, J. and Pedrycz, W. eds. Springer Handbook of Computational Intelligence.. Springer, pp. 1239-1254., (10.1007/978-3-662-43505-2_63)
- Rowse, E. L.et al. 2015. Applying set partitioning methods in the construction of operating theatre schedules. Presented at: International Conference on Theory and Practice in Modern Computing 2015, Las Palmas de Gran Canaria, Spain, 22-24 July 2015.
2014
- Smith-Miles, K.et al. 2014. Towards objective measures of algorithm performance across instance space. Computers & Operations Research 45, pp. 12-24. (10.1016/j.cor.2013.11.015)
- John, M. P., Mumford, C. L. and Lewis, R. 2014. An improved multi-objective algorithm for the urban transit routing problem. Presented at: EvoCOP 2014: 14th European Conference on Evolutionary Computation in Combinatorial Optimization, Granada, Spain, 23-25 April 2014 Presented at Blum, C. and Ochoa, G. eds.Evolutionary Computation in Combinatorial Optimisation: 14th European Conference, EvoCOP 2014, Granada, Spain, April 23-25, 2014, Revised Selected Papers, Vol. 8600. Lecture Notes in Computer Science Springer pp. 49-60., (10.1007/978-3-662-44320-0_5)
- Cooper, I.et al. 2014. Optimising large scale public transport network design problems using mixed-mode parallel multi-objective evolutionary algorithms. Presented at: IEEE Congress on Evolutionary Computation, Beijing, China, 6 - 11 July 2014Evolutionary Computation (CEC). IEEE pp. 2841-2848., (10.1109/CEC.2014.6900362)
2013
- Lewis, R. and Carroll, F. 2013. The "engaged" interaction: important considerations for the HCI design and development of a web application for solving a complex combinatorial optimization problem. World Journal of Computer Application and Technology 1(3), pp. 75-82.
2012
- Lewis, R.et al. 2012. A wide-ranging computational comparison of high-performance graph colouring algorithms. Computers & Operations Research 39(9), pp. 1933-1950. (10.1016/j.cor.2011.08.010)
- Song, X.et al. 2012. An incomplete m-exchange algorithm for solving the large-scale multi-scenario knapsack problem. Computers & Operations Research 39(9), pp. 1988-2000. (10.1016/j.cor.2011.09.012)
- Lewis, R. 2012. A time-dependent metaheuristic algorithm for post enrolment-based course timetabling. Annals of Operations Research 194(1), pp. 273-289. (10.1007/s10479-010-0696-z)
- Holborn, P. L., Thompson, J. M. and Lewis, R. 2012. Combining heuristic and exact methods to solve the vehicle routing problem with pickups, deliveries and time windows. Presented at: EvoCOP 2012: 12th European Conference on Evolutionary Computation in Combinatorial Optimization, Malaga, Spain, 11-13 April 2012 Presented at Hao, J. K. and Middendorf, M. eds.Evolutionary Computation in Combinatorial Optimization: 12th European Conference, EvoCOP 2012, Málaga, Spain, April 11-13, 2012. Proceedings, Vol. 7245. Lecture Notes in Computer Science Springer Verlag pp. 63-74., (10.1007/978-3-642-29124-1_6)
2011
- Lewis, R.et al. 2011. An investigation into two bin packing problems with ordering and orientation implications. European Journal of Operational Research 213(1), pp. 52-65. (10.1016/j.ejor.2011.03.016)
- Lewis, R. and Thompson, J. M. 2011. On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research 38(1), pp. 190-204. (10.1016/j.cor.2010.04.012)
- Lewis, R. and Pullin, E. J. 2011. Revisiting the restricted growth function genetic algorithm for grouping problems. Evolutionary Computation 19(4), pp. 693-704. (10.1162/EVCO_a_00040)
2010
- Song, X.et al. 2010. A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting. European Journal of Operational Research 202(2), pp. 368-378. (10.1016/j.ejor.2009.05.047)
2009
- McCollum, B.et al. 2009. Setting the Research Agenda in Automated Timetabling: The Second International Timetabling Competition. INFORMS Journal on Computing 22(1), pp. 120-130. (10.1287/ijoc.1090.0320)
- Lewis, R. 2009. A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing. Computers & Operations Research 36(7), pp. 2295-2310. (10.1016/j.cor.2008.09.004)
2007
- Lewis, R., Paechter, B. and McCollum, B. 2007. Post enrolment based course timetabling: a description of the problem model used for track two of the second International Timetabling Competition. Working paper. Cardiff: Cardiff University.
- Lewis, R. and Paechter, B. 2007. Finding feasible timetables using group-based operators. IEEE Transactions on Evolutionary Computation 11(3), pp. 397-413. (10.1109/TEVC.2006.885162)
- Lewis, R. 2007. A survey of metaheuristic-based techniques for university timetabling problems. OR Spectrum 30(1), pp. 167-190. (10.1007/s00291-007-0097-0)
- Lewis, R. 2007. Metaheuristics can solve sudoku puzzles. Journal of Heuristics 13(4), pp. 387-401. (10.1007/s10732-007-9012-8)
- Lewis, R. 2007. On the combination of constraint programming and stochastic search: the Sudoku case. In: Hybrid Metaheuristics.. Lecture Notes in Computer Science Vol. 4771. Springer, pp. 96-107., (10.1007/978-3-540-75514-2_8)
- Lewis, R., Paechter, B. and Rossi-Doria, O. 2007. Metaheuristics for university course timetabling. In: Dahal, K. P., Tan, K. C. and Cowling, P. I. eds. Evolutionary Scheduling.. Studies in Computational Intelligence Vol. 49. Springer, pp. 237-272., (10.1007/978-3-540-48584-1_9)
2005
- Lewis, R. and Paechter, B. 2005. Application of the grouping genetic algorithm to university course timetabling. Lecture Notes in Computer Science 3448, pp. 144-153. (10.1007/978-3-540-31996-2_14)
Undergraduate
- MA2900 Problem Solving (Coding Stream)
- MA3602 Algorithms and Heuristics
Postgraduate
- MAT002 Statistical Methods
Rhyd Lewis's research interests include:
- The application and analysis of metaheuristic and integer programming algorithms;
- Algorithmic graph theory;
- Graph colouring (including vertex colouring, edge colouring and happy colouring) -- see also his book on this topic;
- Operating theatre scheduling;
- School bus routing;
- Automated timetabling (course and exam) and related problems;
- Grouping/Partitioning problems;
- Sports timetabling, particularly round-robin scheduling;
- Solving sudoku problems with metaheuristics;
- Bin-packing, trapezoid (trapezium) packing, and the equal-piles problem;
- Vehicle routing and arc routing, particularly dynamic variants of the problem;
Find out more about his research and download resources at his personal website.
Research group
I am interested in supervising PhD students in the areas of:
- Combinatorial optimisation
- Algorithmic graph theory
- Graph colouring;
- Packing, scheduling, and timetabling problems
- Routing problems
Current supervision

Asyl Hawa
Research student

Monique Sciortino
Research student
Past projects
Previous PhD projects:
- Bradley Hardy: Thesis Title: "Heuristic methods for colouring dynamic random graphs"
- Penny Holborn: Thesis Title: "Dynamic vehicle routing problems with pickups, deliveries and time windows"
- Matthew John: Thesis Title: "Metaheuristics for designing efficient routes and schedules for urban transportation networks"
- Elizabeth Rowse: Thesis Title: "Robust optimisation of operating theatre schedules"
- Wasin Padungwech: Thesis Title: "Heuristic algorithms for dynamic capacitated arc routing"
- Lisa Taylor: Thesis Title: "Post-enrolment based course timetabling"