Rhyd Lewis
Rhyd Lewis

Dr. Rhydian Lewis BSc, PhD, FHEA.

Senior Lecturer in Operational Research,
Cardiff School of Mathematics,
Cardiff University, Cardiff, CF24 4AG, WALES.
Tel: +44(0)29 208 74856
Email: LewisR9@cf.ac.uk

 

Link to school webpage

Welcome to my webpage. Below you will find information about my teaching, research, publications, and presentations. Some useful research resources, code, and problem instances can also be found by following the links below. If you would like to contact me on any of my research, please do so at the above email address.

Research and Teaching

Overview

I am a senior lecturer at Cardiff School of Mathematics and a member of the department's Operational Research Group. I am the director of two MSc programs in the School of Mathematics: the MSc in Operational Research and Applied Statistics, and the MSc in Operational Research, Applied Statistics and Risk. Here is a very nice short video highlighting some of the activities carried by the School.

I am currently leading a two-year £250k Health and Care Research Wales-funded project entitled "Prudent Elective Surgery Scheduling: A Whole Systems Approach". I am also an associate editor for the International Journal of Metaheuristics, having co-founded the journal in 2007. I am a member of the program committees for Evolutionary Computation in Combinatorial Optimisation, the Practice and Theory of Automated Timetabling, and the International Metaheuristics Conference series.

Teaching

I am currently teaching the following modules in the School of Mathematics: MAT002: Statistical Methods, MA0276: Visual Basic for Operational Research, and MA3602: Algorithms and Heuristics. Previous modules include MAT004: Computational Methods, and MA0105: Foundations of Probability (at the School of Mathematics), and BSP658 Business Statistics, BS0511 Quantitative Methods for Business, and BS1501 Applied Statistics and Mathematics for Economics and Business (at Cardiff Business School). I am a fellow of the Higher Education Academy.

Research Interests

- The application and analysis of metaheuristic algorithms;
- Graph colouring;
- 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;
- The Urban Transport Routing Problem (see here for more information);
- Bin-packing, trapezoid (trapezium) packing, and the equal-piles problem;
- Vehicle routing, particularly dynamic variants of the problem;
- Arc routing, again particularly dynamic variants of the problem.

Publications and Presentations

Books, Journal Articles and Chapters

2016

  • Lewis, R. and P. Holborn (2016) 'How to Pack Trapezoids: Exact and Evolutionary Algorithms'. IEEE Transactions on Evolutionary Computation, doi: 10.1109/TEVC.2016.2609000.
  • Lewis, R. (2016) 'Graph Colouring: An Ancient Problem with Modern Applications'. Impact, Spring 2016 (3), pp. 47-50, issn:2058-8030.
  • Lewis, R. and F. Carroll (2016) 'Creating Seating Plans: A Practical Application'. Journal of the Operational Research Society, advance online publication, April 27, doi:10.1057/jors.2016.34.
  • Padungwech, W., J. Thompson, and R. Lewis (2016) 'Investigating Edge-Reordering Procedures in a Tabu Search Algorithm for the Capacitated Arc Routing Problem'. In Hybrid Metaheuristics (Lecture Notes in Computer Science vol. 9668), Berlin: Springer-Verlag, pp. 62-74.
  • Hardy, B., R. Lewis, and J. Thompson (2016) 'Modifying Colourings Between Time-steps to Tackle Changes in Dynamic Random Graphs'. In Evolutionary Computation in Combinatorial Optimisation (Lecture Notes in Computer Science vol. 9595), Berlin: Springer-Verlag, pp. 186-201.
  • 2015

  • Lewis, R. (2015) A Guide to Graph Colouring: Algorithms and Applications. Berlin, Springer. ISBN: 978-3-319-25728-0.
  • Lewis, R. and J. Thompson (2015) 'Analysing the Effects of Solution Space Connectivity with an Effective Metaheuristic for the Course Timetabling Problem'. European Journal of Operational Research, vol. 240, pp. 637-648.
  • Lewis, R. (2015) 'Graph Coloring and Recombination'. Springer Handbook of Computational Intelligence, Springer, J. Kacprzyk and W. Pedrycz (Eds.), pp. 1239-1254, ISBN: 978-3-662-43504-5.
  • 2014

  • Smith-Miles, K., D. Baatar, B. Wreford, and R. Lewis (2014) 'Towards Objective Measures of Algorithm Performance Across Instance Space'. Computers and Operations Research, vol. 45, pp. 12-24.
  • John, M., C. Mumford, and R. Lewis (2014) 'An Improved Multi-objective Algorithm for the Urban Transit Routing Problem'. In Evolutionary Computation in Combinatorial Optimisation (Lecture Notes in Computer Science vol. 8600), Berlin: Springer-Verlag, pp. 49-60.
  • 2013

  • Carroll, F. and R. Lewis (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, vol. 1(3), pp. 75-82.
  • 2012

  • Holborn, P. L., J. M. Thompson, and R. Lewis (2012) 'Combining Heuristic and Exact Methods to Solve the Vehicle Routing Problem with Pickups, Deliveries and Time Windows'. In Evolutionary Computation in Combinatorial Optimisation (Lecture Notes in Computer Science vol. 7245), Berlin: Springer-Verlag, pp. 63-74.
  • Lewis, R., J. Thompson, C. Mumford, and J. Gillard (2012) 'A Wide-Ranging Computational Comparison of High-Performance Graph Colouring Algorithms'. Computers and Operations Research, vol. 39(9), pp. 1933-1950. (This work's companion paper can be found here; the source code can be found here.)
  • Song, X., R. Lewis, J. Thompson, and Y. Wu (2012) 'An Incomplete m-Exchange Algorithm for Solving the Large-scale Multi-Scenario Knapsack Problem'. Computers and Operations Research, vol. 39(9), pp. 1988-2000.
  • Lewis, R. (2012) 'A Time-Dependent Metaheuristic Algorithm for Post Enrolment-based Course Timetabling'. Annals of Operations Research, vol. 194(1), pp. 273-289.
  • 2011

  • Lewis, R., X. Song, K. Dowsland, and J. Thompson (2011) 'An Investigation into two Bin Packing Problems with Ordering and Orientation Implications'. European Journal of Operational Research, vol. 213, pp. 52-65.
  • Lewis, R. and E. Pullin (2011) 'Revisiting the Restricted Growth Function Genetic Algorithm for Grouping Problems'. Evolutionary Computation, vol. 19(4), pp. 693-704.
  • Lewis, R. and J. Thompson (2011) 'On the Application of Graph Colouring Techniques in Round-Robin Sports Scheduling'. Computers and Operations Research, vol. 38(1), pp. 190-204.
  • 2010

  • McCollum, B., A. Schaerf, B. Paechter, P. McMullan, R. Lewis, A. Parkes, L. Di Gaspero, R. Qu, and E. Burke (2010) 'Setting The Research Agenda in Automated Timetabling: The Second International Timetabling Competition'. INFORMS Journal on Computing, vol. 22(1), pp. 120-130.
  • Song, X., C. Chu, R. Lewis, Y. Nie, and J. Thompson (2010) 'A Worst Case Analysis of a Dynamic Programming-based Heuristic Algorithm for 2D Unconstrained Guillotine Cutting'. European Journal of Operational Research, vol. 202(2), pp. 368-378.
  • 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 and Operations Research, vol. 36(7), pp. 2295-2310.
  • 2008

  • Lewis, R. (2008) 'A Survey of Metaheuristic-based Techniques for University Timetabling Problems'. OR Spectrum, vol. 30(1), pp. 167-190.
  • 2007

  • Lewis, R. (2007) 'Metaheuristics can Solve Sudoku Puzzles'. Journal of Heuristics, vol. 13 (4), pp. 387-401.
  • Lewis, R., and B. Paechter. (2007) 'Finding Feasible Timetables Using Group-Based Operators'. IEEE Transactions on Evolutionary Computation, vol. 11(3), pp. 397-413.
  • Lewis, R., B. Paechter, and O. Rossi-Doria (2007) 'Metaheuristics for University Course Timetabling'. In Evolutionary Scheduling (Studies in Computational Intelligence, vol. 49), K. Dahal, Kay Chen Tan, P. Cowling (Eds.) Berlin: Springer-Verlag, pp. 237-272.
  • 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) T. Bartz-Beielstein, M. Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph, and M. Sampels (Eds.) Berlin: Springer-Verlag, pp. 96-107.
  • 2006

  • Lewis, R. (2006) 'Metaheuristics for University Course Timetabling'. Doctoral Thesis, Napier University, Edinburgh, Scotland.
  • 2005

  • Lewis, R. and B. Paechter (2005). 'Application of the Grouping Genetic Algorithm to University Course Timetabling'. In Evolutionary Computation in Combinatorial Optimisation (Lecture Notes in Computer Science vol. 3448), J. Gottlieb and G. Raidl (Eds.), Berlin: Springer-Verlag, pp. 144-153.
  • Selected Conference Papers and Technical Reports

  • Rowse, E., R. Lewis, P. Harper, and J. Thompson (2015) 'Applying Set Partitioning Methods in the Construction of Operating Theatre Schedules'. In Proceedings of the International Conference on Theory and Practice in Modern Computing 2015, Las Palmas de Gran Canaria, Spain, pp. 133-140. ISBN: 978-989-8533-39-5. (Recipient of the Outstanding Paper Award.)
  • Cooper, I., M. John, R. Lewis, C. Mumford and A. Olden (2014) 'Optimising large scale public transport network design problems using mixed-mode parallel multi-objective evolutionary algorithms'. In Proceedings of the 2014 IEEE Congress on Evolutionary Computation, Beijing, China, pp. 2841-2848. ISBN: 978-1-4799-6626-4.
  • Lewis, R. (2013) 'Constructing Wedding Seating Plans: A Tabu Subject'. Proceedings of the International Conference on Genetic and Evolutionary Methods (GEM'13), H. Arabnia et al. (Eds), pp. 24-32. ISBN: 1-60132-245-3.
  • Lewis, R., B. Paechter, and B. McCollum (2007) 'Post Enrolment based Course Timetabling: A Description of the Problem Model used for Track Two of the Second International Timetabling Competition'. Cardiff Working Papers in Accounting and Finance A2007-3, Cardiff Business School, Cardiff University, Wales, Aug. 2007. ISSN: 1750-6658.
  • Lewis, R. (2008) 'A Time-Dependent Metaheuristic Algorithm for Post Enrolment-based Course Timetabling'. In PATAT 2008, Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling. (A more recent version of this paper, published in Annals of Operations Research, is available here.)
  • Lewis, R. and B. Paechter (2005). 'An Empirical Analysis of the Grouping Genetic Algorithm: The Timetabling Case'. In Proceedings of the 2005 IEEE World Congress on Evolutionary Computation, Edinburgh, Scotland, pp. 2856-2863, ISBN: 0-7803-9363-5.
  • Lewis, R. and B. Paechter (2004). 'New Crossover Operators for Timetabling with Evolutionary Algorithms'. In Proceedings of the 5th International Conference on Recent Advances in Soft Computing (RASC 2004), A. Lofti (Ed.), Nottingham, England, pp. 189-195. ISBN: 1-84233-110-8.
  • Selected Presentations

  • Applying Set Partitioning Methods in the Construction of Operating Theatre Schedules. Talk given at International Conference on Theory and Practice in Modern Computing (TPMC) 2015, Las Palmas de Gran Canaria, July 2015.
  • A Survey of Various High-Performance Graph Colouring Algorithms and Related Timetabling Issues. Talk given at Operational Research 53 (OR53), Nottingham University, Nottingham, September 2011.
  • An Investigation into Trapezoid Packing. Talk given at Operational Research 52 (OR52), Royal Holloway University, London, September 2010.
  • On the Application of Graph Colouring techniques in Round-Robin Sports Scheduling. Talk given at a meeting of the LANCS Advisory Board in London, May 2010.
  • A Time-Dependent Metaheuristic Algorithm for Post Enrolment-based Course Timetabling. Talk given at the 7th International Conference on the Practice and Theory of Automated Timetabling, Montreal, August 2008.
  • On the Combination of Constraint Programming and Stochastic Search: The Sudoku Case. Talk given at Hybrid Metaheuristics, Dortmund, April 2007.
  • An Introduction to Metaheuristic Algorithms and the Problems they (try to) Solve. Talk given at the British Computing Society Lecture & Dinner, Cardiff Business School, October 2008.
  • Resources

    Graph Colouring:

    Illustration of the Graph Colouring ProblemIllustration of how a map can be coloured using just four colours.Graph colouring is the task of painting all vertices of a graph so that (a) all pairs of adjacent vertices are assigned different colours, and (b) the number of colours used is minimal. This problem has applications in many practical areas of operations research including university timetabling, sports scheduling, creating seating plans, and solving sudoku puzzles. It is also strongly related to the Four Colour Theorem, previously one of the most famous unsolved problems in all of mathematics.

    For further information on graph colouring and its applications, please refer to my 2015 book A Guide to Graph Colouring: Algorithms and Applications, ISBN: 978-3-319-25728-0. The suite of graph colouring algorithms used in this book is available here. These have been coded in C++, and the resource also contains compilation and usage instructions. Information on these algorithms can also be found in the paper: "Lewis, R., J. Thompson, C. Mumford, and J. Gillard (2012) 'A Wide-Ranging Computational Comparison of High-Performance Graph Colouring Algorithms'. Computers and Operations Research, vol. 39(9), pp. 1933-1950".

    A Guide to Graph Colouring: Algorithms and Applications Some short introductory videos into the field of graph colouring can be found at the following links:

    - An Introduction to Graph Colouring;
    - Constructive Algorithms for Graph Colouring;
    - Practical Applications of Graph Colouring.

    A useful bibliography on the graph colouring problem, maintained by Marco Chiarandini and Stefano Gualandi, can be found here. In addition, information on upper bounds for the DIMACS graph colouring instances can be found here.

    Timetabling:

    Some of my research has focussed on the production of efficient algorithms for timetabling problems. A large number of timetabling problem instances are available for this problem on the website of the Second International Timetabling Competition (ITC2007). Some hard timetabling instances can also be found here. This latter set contains sixty problem instances of varying sizes that are intended to be more difficult than the competition instances with regards to both finding feasibility and satisfying soft constraints. Source code and results for the algorithm presented in Lewis, R. and J. Thompson (2015) 'Analysing the Effects of Solution Space Connectivity with an Effective Metaheuristic for the Course Timetabling Problem'. European Journal of Operational Research, vol. 240, pp. 637-648 can be found here

    Bin Packing:

    Illustration of the one-dimensional bin packing problem In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers such that the minimum number of bins used. A good resource of benchmark problem instances for the one-dimensional bin packing problem can be found here in the problem repository of Scholl and Klein. The "uniform" and "triplet" bin packing instances of Falkenauer can also be found here and are stored on the Operational Research Library of Beasley.

    Trapezoid Packing:

    Example of a Trapezoid Packing ProblemThe Trapezoid Packing Problem is closely related to the one-dimensional bin packing problem. Here, items are trapezoidal in shape with a fixed height and variable width. A practical application arises in the roofing industry, where large numbers of roof trusses of different lengths and different "end angles" have to be cut from boards of a given length such that wastage is minimsed. Though similar to one-dimensional bin packing, the problem is complicated by the fact that the ends of the trapezoids need to be "nested" so that wastage between consecutive shapes is kept to a minimum. This problem was first introduced and analysed in the 2011 paper 'An Investigation into two Bin Packing Problems with Ordering and Orientation Implications'. The problem instances used in this paper can be downloaded here.

    In our 2016 publication 'How to Pack Trapezoids: Exact and Evolutionary Algorithms' significant improvements to the results reported in the 2011 paper were achieved by (a) designing and making use of an exact polynomial-time algorithm for optimally packing a set of fixed-height trapezoids into a single bin, and (b) by using a number of specialised evolutionary-based methods when packing across multiple bins. The source code and a detailed breakdown of the results of this work is available here.

    Constructing Operating Theatre Schedules:

    Operating Theatre SchedulingAn important part of our £250k Health and Care Research Wales-funded project "Prudent Elective Surgery Scheduling: A Whole Systems Approach", is the production of optimal surgery schedules at hospitals. When a patient enters a hospital for an elective operation, it is imperative that a bed is available for them to go into after surgery. However, sometimes all beds in the ward will be occupied, meaning that the operation will have to be cancelled. Our research has shown that cancellations occur far less frequently if operations are scheduled throughout the week appropriately. As part of this, our models also need to take into account various hospital requirements, the unexpected arrival or emergency patients, and the variability in the time patients take to recover after their operations. More information can be found in my list of publications.

    Sudoku:

    Converting Sudoku into Graph ColouringSome of my work has concerned the use of metaheuristics to help solve sudoku puzzles. The C++ code used for experiments described in "Lewis, R. (2007). 'Metaheuristics can Solve Sudoku Puzzles' Journal of Heuristics, vol. 13 (4), pp. 387-401", can be downloaded here. Code for the random sudoku problem instance generator used in this research can be downloaded here.

    Regarding Sudoku, here is a very useful Sudoku to Graph Coloring Converter. This program reads in a single sudoku problem (from a text file) and converts it into the equivalent graph coloring problem. The output file appears in the DIMACS format which can then be used as the input file for any suitable graph coloring algorithm. If a solution using the correct number of colours is found, this can then be easily converted back into the Sudoku representation, giving a valid solution to the original problem.

    Sports Scheduling:

    Previous work has also looked at the scheduling of sports events, and in particular round-robin leagues and tournaments. Here is a link to the ten sports scheduling benchmark problem files used in the paper "Lewis, R. and J. Thompson (2011) 'On the Application of Graph Colouring Techniques in Round-Robin Sports Scheduling'. Computers and Operations Research, vol. 38(1), pp. 190-204". Source code (C++) for the round-robin to graph colouring program, which was used to generate many of the graphs in the paper, can be found here.

    Making Seating Plans:

    Want to avoid sitting next to annoying guests at a party? See state of the art combinatorial optimisation techniques in action with this Wedding Seating Planner tool available at www.weddingseatplanner.com.

    Surfing

    Surfing somewhere in Wales
    Surfing a secret surf spot somewhere in Wales.


    Surfing a beachbreak
    Surfing at another break.


    Surfing another break
    ...And another break.