![Rhydian Lewis BSc, PhD, FHEA](https://profiles-cardiff.imgix.net/attachments/4377?w=200&h=200&auto=format&crop=faces&fit=crop&q=90")
Professor Rhydian Lewis
BSc, PhD, FHEA
- Media commentator
- Available for postgraduate supervision
Teams and roles for Rhydian Lewis
Mathematician
Academic
Academic
Academic
Overview
Rhyd Lewis is a professor at the School of Mathematics, Cardiff University. His research interests are operational research, combinatorial optimisation and algorithmic graph theory. He is the author of the book A Guide to Graph Colouring: Algorithms and Applications (2021),
Administrative duties
- Director of Internationals
- Member of Operational Research Group and the Planning and Optimisation Group
Personal website
Publication
2025
- Corcoran, P. and Lewis, R. 2025. A user-centric model of connectivity in street networks. Computers and Operations Research 173 106846. (10.1016/j.cor.2024.106846)
- Corcoran, P. and Lewis, R. 2025. An analysis of the correctness and computational complexity of path planning in Payment Channel Networks. The Journal of Financial Technology
- Lewis, R. and Bonnet, L. 2025. Exact algorithms in bar nesting: How to cut general items from linear stocks so that wastage is minimised. Computers & Industrial Engineering 200 110838. (10.1016/j.cie.2024.110838)
- Lewis, R. and Palmer, G. 2025. GCol: A high-performance Python library for graph colouring. The Journal of Open Source Software 10 (108) 7871. (10.21105/joss.07871)
- Lewis, R. 2025. GCol: Official documentation of the Python library for graph coloring. Documentation. readthedocs.com. Available at: https://readthedocs.org/projects/gcol/downloads/pdf/latest/.
- Shekarriz, M. H. et al., 2025. Soft happy colourings and community structure of networks. Computers and Operations Research 174 106893. (10.1016/j.cor.2024.106893)
2024
- Bonnet, L. and Lewis, R. 2024. Exact bar nesting with industrial symmetry considerations. Presented at: 25e Congres Annuel de la Societe Francaise de Recherche Operationnelle et d'Aide a la Decision Amiens, France 4-7 March, 2024.
- Corcoran, P. and Lewis, R. 2024. Optimisation of livestock routing on farms. Computers & Industrial Engineering 188 109882. (10.1016/j.cie.2024.109882)
- Corcoran, P. and Lewis, R. 2024. Path planning in payment channel networks with multi-party channels. Distributed Ledger Technologies: Research and Practice 4 (4) 30. (10.1145/3702248)
- Dijkstra, L. et al. 2024. Digraphs and k-domination models for facility location problems in road networks: Greedy heuristics. Presented at: International Network Optimization Conference 2024 Dublin, Ireland 11-13 March 2024. Proceedings of the 11th International Network Optimization Conference (INOC). OpenProceedings. , pp.22-27. (10.48786/inoc.2024.05)
- Hambly, D. , Lewis, R. and Corcoran, P. 2024. Determining fixed-length paths in directed and undirected edge-weighted graphs. Presented at: Symposium on Experimental Algorithms (SEA) 2024 Vienna, Austria 24-26 July 2024. Published in: Liberti, L. ed. 22nd International Symposium on Experimental Algorithms (SEA 2024).. Vol. 301.Leibniz International Proceedings in Informatics (LIPIcs) , pp.15.1-15.11. (10.4230/LIPIcs.SEA.2024.15)
- Lewis, R. and Corcoran, P. 2024. Fast algorithms for computing fixed-length round trips in real-world street networks. SN Computer Science 5 (7) 868. (10.1007/s42979-024-03223-3)
- Lewis, R. 2024. Cardiff: Software solutions for designing school transport systems. [Online].Delft: Website of the European Consortium for Mathematics in Industry. Available at: https://ecmiindmath.org/2024/10/24/cardiff-software-solutions-for-designing-school-transport-systems/.
2023
- Corcoran, P. and Lewis, R. 2023. A navigability entropy model for street networks. Environment and Planning B: Urban Analytics and City Science 50 (8), pp.2171-2186. (10.1177/23998083231170191)
- Lewis, R. , Corcoran, P. and Gagarin, A. 2023. Methods for determining cycles of a specific length in undirected graphs with edge weights. Journal of Combinatorial Optimization 46 29. (10.1007/s10878-023-01091-w)
- Lewis, R. 2023. A comparison of Dijkstra's Algorithm using fibonacci heaps, binary heaps, and self-balancing binary trees. [Online].Preprint repository: ArXiv. Available at: https://arxiv.org/abs/2303.10034.
2022
- Carroll, F. and Lewis, R. 2022. Internet security aesthetics: can internet transparency afford social trust?. Presented at: 2022 International Conference on Computer Communications and Networks (ICCCN) 25-28 July 2022. 2022 International Conference on Computer Communications and Networks (ICCCN). IEEE. (10.1109/ICCCN54977.2022.9868880)
- Hawa, A. , Lewis, R. and Thompson, J. 2022. Exact and approximate methods for the score-constrained packing problem. European Journal of Operational Research 302 (3), pp.847-859. (10.1016/j.ejor.2022.01.028)
- Lewis, R. and Carroll, F. 2022. Exact algorithms for finding fixed-length cycles in edge-weighted graphs. Presented at: 2022 International Conference on Computer Communications and Networks (ICCCN) 25-28 July 2022. 2022 International Conference on Computer Communications and Networks (ICCCN). IEEE. (10.1109/ICCCN54977.2022.9868939)
- Lewis, R. and Corcoran, P. 2022. Finding fixed-length circuits and cycles in undirected edge-weighted graphs: an application with street networks. Journal of Heuristics 28 , pp.259-285. (10.1007/s10732-022-09493-5)
- Monique, S. , Lewis, R. and Thompson, J. 2022. A school bus routing heuristic algorithm allowing heterogeneous fleets and bus stop selection. SN Computer Science 4 74. (10.1007/s42979-022-01466-6)
- Thiruvady, D. and Lewis, R. 2022. Recombinative approaches for the maximum happy vertices problem. Swarm and Evolutionary Computation 75 101188. (10.1016/j.swevo.2022.101188)
2021
- Kheiri, A. et al., 2021. Constructing operating theatre schedules using partitioned graph colouring techniques. Health Systems 10 (4), pp.286-297. (10.1080/20476965.2020.1796530)
- Lewis, R. 2021. Finding attractive exercise circuits in street maps. Presented at: 29th Annual GIS Research UK Conference (GISRUK 2021) Cardiff, Wales 14-16 April 2021. (10.5281/zenodo.4665508)
- Lewis, R. , Thiruvady, D. and Morgan, K. 2021. The maximum happy induced subgraph problem: bounds and algorithms. Computers and Operations Research 126 105114. (10.1016/j.cor.2020.105114)
- Lewis, R. M. R. 2021. Guide to graph colouring. Texts in Computer Science Springer, Cham. (10.1007/978-3-030-81054-2)
- Lewis, R. 2021. DSatur algorithm for graph coloring. [Online].Geeks for Geeks. Available at: https://www.geeksforgeeks.org/dsatur-algorithm-for-graph-coloring/.
- Sciortino, M. , Lewis, R. and Thompson, J. 2021. A heuristic algorithm for school bus routing with bus stop selection. Presented at: EvoCOP 2021 Seville, Spain Apr 2021. Published in: Zarges, C. and Verel, S. eds. Evolutionary Computation in Combinatorial Optimization. Vol. 12692.Lecture Notes in Computer Science/Theoretical Computer Science and General Issues Springer Verlag. (10.1007/978-3-030-72904-2_13)
2020
- Lewis, R. 2020. A heuristic algorithm for finding attractive fixed-length circuits in street maps. Presented at: International Conference on Computational Logistics Enschede, The Netherlands 28–30 Sept 2020. Computational Logistics. Vol. 12433.Springer Verlag. , pp.384-395. (10.1007/978-3-030-59747-4_25)
- Lewis, R. 2020. A shortest path algorithm for graphs featuring transfer costs at their vertices. Presented at: International Conference on Computational Logistics Enschede, The Netherlands 28–30 Sept 2020. Computational Logistics. Vol. 12433.Springer Verlag. , pp.539-552. (10.1007/978-3-030-59747-4_35)
- Lewis, R. 2020. Algorithms for finding shortest paths in networks with vertex transfer penalties. Algorithms 13 (11) 269. (10.3390/a13110269)
- Lewis, R. 2020. Cite or be damned: some thoughts on reviewer-coerced citation. [Online].Scientists are Humans. Available at: http://rhydlewis.eu/papers/ReviewerCoercedCitation.pdf.
- Lewis, R. 2020. Editorial for the special issue on “Algorithms for graphs and networks”. Algorithms 13 (11), pp.292. (10.3390/a13110292)
- Lewis, R. 2020. Five degrees of separation from De Niro - charting the social networks of movie stars. The Conversation
- Lewis, R. 2020. Who is the centre of the movie universe? Using python and networkX to analyse the social network of movie stars. [Online].arXiv. Available at: https://arxiv.org/abs/2002.11103.
- Lewis, R. , Anderson, T. and Carroll, F. 2020. Can school enrolment and performance be improved by maximizing students' sense of choice in elective subjects?. Journal of Learning Analytics 7 (1), pp.75-87. (10.18608/jla.2020.71.6)
- Neis, P. and Lewis, R. 2020. Evaluating the influence of parameter setup on the performance of heuristics for the graph colouring problem. International Journal of Metaheuristics 7 (4), pp.352-378.
- Padungwech, W. , Thompson, J. and Lewis, R. 2020. Effects of update frequencies in a dynamic capacitated arc routing problem. Networks 76 (4), pp.522-538. (10.1002/net.21990)
- Thiruvady, D. , Lewis, R. and Morgan, K. 2020. Tackling the maximum happy vertices problem in large networks. 4OR: A Quarterly Journal of Operations Research 18 , pp.507-527. (10.1007/s10288-020-00431-4)
2019
- Lewis, R. , Thiruvady, D. and Morgan, K. 2019. Finding happiness: an analysis of the maximum happy vertices problem. Computers and Operations Research 103 (10.1016/j.cor.2018.11.015)
- Lewis, R. 2019. Want to mislead and confuse? use statistics!. [Online].Scientists are Humans. Available at: http://rhydlewis.eu/papers/statsArticle.pdf.
2018
- Hardy, B. , Lewis, R. and Thompson, J. 2018. Tackling the edge dynamic graph colouring problem with and without future adjacency information. Journal of Heuristics 24 , pp.321-343. (10.1007/s10732-017-9327-z)
- 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. Published in: 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. 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)
- 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. , 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. Published in: 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
- 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. Published in: 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)
- 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. Published in: Burke, E. K. et al., PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling. , pp.503-505.
- 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)
- Lewis, R. 2016. Graph colouring: an ancient problem with modern applications. Impact 3 (1), pp.47-50. (10.1080/2058802X.2016.11963998)
- 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. Published in: 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)
2015
- 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. M. R. 2015. A guide to graph colouring: algorithms and applications. Springer. (10.1007/978-3-319-25730-3)
- Lewis, R. 2015. Graph coloring and recombination. In: Kacprzyk, J. and Pedrycz, W. eds. Springer Handbook of Computational Intelligence. Springer. , pp.1239-1254.
- 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
- 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 2014. Evolutionary Computation (CEC). IEEE. , pp.2841-2848. (10.1109/CEC.2014.6900362)
- 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. Published in: 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)
- 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)
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
- 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. Published in: 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)
- 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)
- 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)
2011
- 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)
- 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)
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
- 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)
- 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)
2007
- 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. 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. , 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)
- 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.
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)
Articles
- Corcoran, P. and Lewis, R. 2023. A navigability entropy model for street networks. Environment and Planning B: Urban Analytics and City Science 50 (8), pp.2171-2186. (10.1177/23998083231170191)
- Corcoran, P. and Lewis, R. 2025. A user-centric model of connectivity in street networks. Computers and Operations Research 173 106846. (10.1016/j.cor.2024.106846)
- Corcoran, P. and Lewis, R. 2024. Optimisation of livestock routing on farms. Computers & Industrial Engineering 188 109882. (10.1016/j.cie.2024.109882)
- Corcoran, P. and Lewis, R. 2025. An analysis of the correctness and computational complexity of path planning in Payment Channel Networks. The Journal of Financial Technology
- Corcoran, P. and Lewis, R. 2024. Path planning in payment channel networks with multi-party channels. Distributed Ledger Technologies: Research and Practice 4 (4) 30. (10.1145/3702248)
- Hardy, B. , Lewis, R. and Thompson, J. 2018. Tackling the edge dynamic graph colouring problem with and without future adjacency information. Journal of Heuristics 24 , pp.321-343. (10.1007/s10732-017-9327-z)
- Hawa, A. , Lewis, R. and Thompson, J. 2022. Exact and approximate methods for the score-constrained packing problem. European Journal of Operational Research 302 (3), pp.847-859. (10.1016/j.ejor.2022.01.028)
- Kheiri, A. et al., 2021. Constructing operating theatre schedules using partitioned graph colouring techniques. Health Systems 10 (4), pp.286-297. (10.1080/20476965.2020.1796530)
- Lewis, R. , Corcoran, P. and Gagarin, A. 2023. Methods for determining cycles of a specific length in undirected graphs with edge weights. Journal of Combinatorial Optimization 46 29. (10.1007/s10878-023-01091-w)
- Lewis, R. , Thiruvady, D. and Morgan, K. 2019. Finding happiness: an analysis of the maximum happy vertices problem. Computers and Operations Research 103 (10.1016/j.cor.2018.11.015)
- Lewis, R. , Thiruvady, D. and Morgan, K. 2021. The maximum happy induced subgraph problem: bounds and algorithms. Computers and Operations Research 126 105114. (10.1016/j.cor.2020.105114)
- 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. 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)
- 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. 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)
- Lewis, R. 2020. Algorithms for finding shortest paths in networks with vertex transfer penalties. Algorithms 13 (11) 269. (10.3390/a13110269)
- Lewis, R. 2020. Editorial for the special issue on “Algorithms for graphs and networks”. Algorithms 13 (11), pp.292. (10.3390/a13110292)
- Lewis, R. 2020. Five degrees of separation from De Niro - charting the social networks of movie stars. The Conversation
- Lewis, R. 2007. Metaheuristics can solve sudoku puzzles. Journal of Heuristics 13 (4), pp.387-401. (10.1007/s10732-007-9012-8)
- Lewis, R. , Anderson, T. and Carroll, F. 2020. Can school enrolment and performance be improved by maximizing students' sense of choice in elective subjects?. Journal of Learning Analytics 7 (1), pp.75-87. (10.18608/jla.2020.71.6)
- Lewis, R. and Bonnet, L. 2025. Exact algorithms in bar nesting: How to cut general items from linear stocks so that wastage is minimised. Computers & Industrial Engineering 200 110838. (10.1016/j.cie.2024.110838)
- 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)
- Lewis, R. and Corcoran, P. 2024. Fast algorithms for computing fixed-length round trips in real-world street networks. SN Computer Science 5 (7) 868. (10.1007/s42979-024-03223-3)
- 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)
- 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)
- 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. and Palmer, G. 2025. GCol: A high-performance Python library for graph colouring. The Journal of Open Source Software 10 (108) 7871. (10.21105/joss.07871)
- 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)
- 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)
- 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. 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)
- Lewis, R. 2016. Graph colouring: an ancient problem with modern applications. Impact 3 (1), pp.47-50. (10.1080/2058802X.2016.11963998)
- 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.
- Lewis, R. and Corcoran, P. 2022. Finding fixed-length circuits and cycles in undirected edge-weighted graphs: an application with street networks. Journal of Heuristics 28 , pp.259-285. (10.1007/s10732-022-09493-5)
- 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)
- Monique, S. , Lewis, R. and Thompson, J. 2022. A school bus routing heuristic algorithm allowing heterogeneous fleets and bus stop selection. SN Computer Science 4 74. (10.1007/s42979-022-01466-6)
- Neis, P. and Lewis, R. 2020. Evaluating the influence of parameter setup on the performance of heuristics for the graph colouring problem. International Journal of Metaheuristics 7 (4), pp.352-378.
- Padungwech, W. , Thompson, J. and Lewis, R. 2020. Effects of update frequencies in a dynamic capacitated arc routing problem. Networks 76 (4), pp.522-538. (10.1002/net.21990)
- Shekarriz, M. H. et al., 2025. Soft happy colourings and community structure of networks. Computers and Operations Research 174 106893. (10.1016/j.cor.2024.106893)
- 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)
- 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)
- 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)
- Thiruvady, D. and Lewis, R. 2022. Recombinative approaches for the maximum happy vertices problem. Swarm and Evolutionary Computation 75 101188. (10.1016/j.swevo.2022.101188)
- Thiruvady, D. , Lewis, R. and Morgan, K. 2020. Tackling the maximum happy vertices problem in large networks. 4OR: A Quarterly Journal of Operations Research 18 , pp.507-527. (10.1007/s10288-020-00431-4)
Book sections
- Lewis, R. 2015. Graph coloring and recombination. In: Kacprzyk, J. and Pedrycz, W. eds. Springer Handbook of Computational Intelligence. Springer. , pp.1239-1254.
- 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)
Books
- Lewis, R. M. R. 2015. A guide to graph colouring: algorithms and applications. Springer. (10.1007/978-3-319-25730-3)
- Lewis, R. M. R. 2021. Guide to graph colouring. Texts in Computer Science Springer, Cham. (10.1007/978-3-030-81054-2)
Conferences
- Bonnet, L. and Lewis, R. 2024. Exact bar nesting with industrial symmetry considerations. Presented at: 25e Congres Annuel de la Societe Francaise de Recherche Operationnelle et d'Aide a la Decision Amiens, France 4-7 March, 2024.
- Carroll, F. and Lewis, R. 2022. Internet security aesthetics: can internet transparency afford social trust?. Presented at: 2022 International Conference on Computer Communications and Networks (ICCCN) 25-28 July 2022. 2022 International Conference on Computer Communications and Networks (ICCCN). IEEE. (10.1109/ICCCN54977.2022.9868880)
- 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 2014. Evolutionary Computation (CEC). IEEE. , pp.2841-2848. (10.1109/CEC.2014.6900362)
- Dijkstra, L. et al. 2024. Digraphs and k-domination models for facility location problems in road networks: Greedy heuristics. Presented at: International Network Optimization Conference 2024 Dublin, Ireland 11-13 March 2024. Proceedings of the 11th International Network Optimization Conference (INOC). OpenProceedings. , pp.22-27. (10.48786/inoc.2024.05)
- Hambly, D. , Lewis, R. and Corcoran, P. 2024. Determining fixed-length paths in directed and undirected edge-weighted graphs. Presented at: Symposium on Experimental Algorithms (SEA) 2024 Vienna, Austria 24-26 July 2024. Published in: Liberti, L. ed. 22nd International Symposium on Experimental Algorithms (SEA 2024).. Vol. 301.Leibniz International Proceedings in Informatics (LIPIcs) , pp.15.1-15.11. (10.4230/LIPIcs.SEA.2024.15)
- 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. Published in: 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)
- 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. Published in: 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)
- 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. Published in: 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)
- 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. Published in: 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)
- 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. Published in: Burke, E. K. et al., PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling. , pp.503-505.
- Lewis, R. 2021. Finding attractive exercise circuits in street maps. Presented at: 29th Annual GIS Research UK Conference (GISRUK 2021) Cardiff, Wales 14-16 April 2021. (10.5281/zenodo.4665508)
- Lewis, R. and Carroll, F. 2022. Exact algorithms for finding fixed-length cycles in edge-weighted graphs. Presented at: 2022 International Conference on Computer Communications and Networks (ICCCN) 25-28 July 2022. 2022 International Conference on Computer Communications and Networks (ICCCN). IEEE. (10.1109/ICCCN54977.2022.9868939)
- Lewis, R. 2020. A heuristic algorithm for finding attractive fixed-length circuits in street maps. Presented at: International Conference on Computational Logistics Enschede, The Netherlands 28–30 Sept 2020. Computational Logistics. Vol. 12433.Springer Verlag. , pp.384-395. (10.1007/978-3-030-59747-4_25)
- Lewis, R. 2020. A shortest path algorithm for graphs featuring transfer costs at their vertices. Presented at: International Conference on Computational Logistics Enschede, The Netherlands 28–30 Sept 2020. Computational Logistics. Vol. 12433.Springer Verlag. , pp.539-552. (10.1007/978-3-030-59747-4_35)
- 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. , 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. Published in: 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)
- 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. Published in: 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)
- 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.
- Sciortino, M. , Lewis, R. and Thompson, J. 2021. A heuristic algorithm for school bus routing with bus stop selection. Presented at: EvoCOP 2021 Seville, Spain Apr 2021. Published in: Zarges, C. and Verel, S. eds. Evolutionary Computation in Combinatorial Optimization. Vol. 12692.Lecture Notes in Computer Science/Theoretical Computer Science and General Issues Springer Verlag. (10.1007/978-3-030-72904-2_13)
Monographs
- Lewis, R. 2025. GCol: Official documentation of the Python library for graph coloring. Documentation. readthedocs.com. Available at: https://readthedocs.org/projects/gcol/downloads/pdf/latest/.
- 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.
Websites
- Lewis, R. 2020. Cite or be damned: some thoughts on reviewer-coerced citation. [Online].Scientists are Humans. Available at: http://rhydlewis.eu/papers/ReviewerCoercedCitation.pdf.
- Lewis, R. 2019. Want to mislead and confuse? use statistics!. [Online].Scientists are Humans. Available at: http://rhydlewis.eu/papers/statsArticle.pdf.
- Lewis, R. 2020. Who is the centre of the movie universe? Using python and networkX to analyse the social network of movie stars. [Online].arXiv. Available at: https://arxiv.org/abs/2002.11103.
- Lewis, R. 2023. A comparison of Dijkstra's Algorithm using fibonacci heaps, binary heaps, and self-balancing binary trees. [Online].Preprint repository: ArXiv. Available at: https://arxiv.org/abs/2303.10034.
- Lewis, R. 2024. Cardiff: Software solutions for designing school transport systems. [Online].Delft: Website of the European Consortium for Mathematics in Industry. Available at: https://ecmiindmath.org/2024/10/24/cardiff-software-solutions-for-designing-school-transport-systems/.
- Lewis, R. 2021. DSatur algorithm for graph coloring. [Online].Geeks for Geeks. Available at: https://www.geeksforgeeks.org/dsatur-algorithm-for-graph-coloring/.
Research
Rhyd Lewis's research interests include:
- Algorithmic graph theory;
- Combinatorial optimisation;
- Graph colouring;
- Metaheuristics and integer programming;
- Vehicle routing and arc routing;
- Shortest path algorithms;
- School bus routing;
- Automated timetabling and related problems;
- Grouping and partitioning problems;
- Operating theatre scheduling;
- Sports scheduling;
- Solving Latin square and Sudoku problems;
- Bin-packing, trapezoid (trapezium) packing, and the equal-piles problem.
Find out more about his research and download resources at his personal website.
Research group
Teaching
Undergraduate
- MA2760 Mathematical Investigations in Python
- MA3602 Algorithms and Heuristics
Postgraduate
- MAT004 Computational Methods
Rhyd Lewis is a fellow of the Higher Education Academy.
Biography
Rhyd Lewis is a professor in mathematics. He is the author of the book A Guide to Graph Colouring: Algorithms and Applications. He has a PhD from Edinburgh Napier University (2006), and a BSc (hons) in Computer Science from Swansea University (2002).
Professional memberships
- Fellow of the Higher Education Academy
Academic positions
- 2023 - Present: Personal Chair, School of Mathematics, Cardiff University
- 2019 - 2023: Reader, School of Mathematics, Cardiff University
- 2015 - 2019: Senior Lecturer, School of Mathematics, Cardiff University
- 2008 - 2015: Lecturer, School of Mathematics, Cardiff University
- 2006 - 2008: Lecturer, Cardiff Business School, Cardiff University
- 2003 - 2006: Postgraduate Demonstrator, School of Computing, Edinburgh Napier University
- 2003 - 2006: Postgraduate Researcher, School of Computing, Edinburgh Napier University
Committees and reviewing
- Associate Editor, International Journal of Metaheuristics.
- Programme commitee member for:
- Evolutionary Computation in Combinatorial Optimisation (EVOCOP).
- Practice and Theory of Automated Timetabling conference (PATAT).
- Genetic and Evolutionary Computation Conference (GECCO).
Supervisions
I am interested in supervising PhD students in the areas of:
- Combinatorial optimisation
- Algorithmic graph theory
- Graph colouring;
- Packing, scheduling, and timetabling problems
- Transportation and navigation problems
- Network analysis
Current supervision
Past projects
• Hawa, A. (2020) "Exact and evolutionary algorithms for the score-constrained packing problem".
• Hardy, B. (2018) "Heuristic methods for colouring dynamic random graphs".
• Padungwech, W. (2018) "Heuristic algorithms for dynamic capacitated arc routing".
• John, M. (2016) "Metaheuristics for designing efficient routes and schedules for urban transportation networks".
• Rowse, E. (2015) "Robust optimisation of operating theatre schedules".
• Holborn, P. (2013) "Heuristics for dynamic vehicle routing problems with pickups and deliveries and time windows".
• Taylor, L. (2013) "Local search methods for the post enrolment-based course timetabling problem".
Contact Details
Research themes
Specialisms
- Combinatorics and discrete mathematics
- Applied statistics
- Programming languages
- graph theory
