Dr. Rhydian Lewis BSc., PhD.
Cardiff School of Mathematics,Prifysgol Caerdydd/ Cardiff University,
Senghennydd Road, Cardiff, CF24 4AG,
WALES.
Tel: +44(0)29 208 74856
Fax: +44(0)29 208 74199
Email:
Welcome to my webpage. Here you can find information about my teaching, research, publications, and presentations. Some useful research resources can also be found by following the links below.
Overview
I am a lecturer at Cardiff School of Mathematics and member of the department's Operational Research Group. I am an associate editor for the International Journal of Metaheuristics and am a member of the program committees for Evolutionary Computation in Combinatorial Optimisation, EvoEnvironment, GECCO, the Congress of Evolutionary Computing and the Practice and Theory of Automated Timetabling.
Teaching
Currently, I teach the following modules in the School of Mathematics: MA0105: An Introduction to Probability; MA0276: Visual Basic for Operational Research; and MAT004: Computational Methods. The online teaching resources for MA0105 can be found here (created by Dr Rob Wilson). Previously I have taught the following modules at Cardiff University: BSP658 Business Statistics (MBA); BS0511 Quantitative Methods for Business; and BS1501 Applied Statistics and Mathematics for Economics and Business (all at Cardiff Business School).
Research Interests
- The application and analysis of metaheuristic algorithms;
- Automated timetabling (course and exam) and related problems;
- Grouping/Partitioning problems;
- Graph colouring;
- Sports timetabling, particularly round-robin scheduling;
- Solving sudoku problems with metaheuristics;
- Bin-packing, trapezoid (trapezium) packing, and the equal-piles problem;
- Vehicle routing;
- Problem difficulty and problem generation;
- Scheduling, routing, and constraint satisfaction.
Journal Publications and Book Chapters
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), J.-K. Hao and M. Middendorf (Eds.), 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.)
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.
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.
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 (2009) '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.
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.
Lewis, R. (2008) 'A Survey of Metaheuristic-based Techniques for University Timetabling Problems'. OR Spectrum, vol. 30(1), pp. 167-190.
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.
Lewis, R. (2006) 'Metaheuristics for University Course Timetabling'. Doctoral Thesis, Napier University, Edinburgh, Scotland.
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.
Conference Papers and Technical Reports
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.
Presentations
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.
Timetabling:
Some of my research has focused on the timetabling problem formulation used in the first International Timetabling Competition run in 2003. The twenty problem instances used in this competition can be found here. 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 the soft constraints. If anyone has been using these instances in their work then please let me know. A large number of other timetabling problem instances are also available on the website of the Second International Timetabling Competition (ITC2007), which I co-organised in 2007-2008.
Grouping/Partitioning Problems:
This section contains some resources concerned with my research on grouping problems, particulary graph colouring and bin packing problems. 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. Note that these latter instances contain information regarding the minimum number of bins required in optimal solutions, but in a small number of the "uniform" instances, the stated optima are incorrect and will need to be changed manually before use. The correct optima for these instances were determined by I. Gent (Gent, I. (1998) 'Heuristic Solution of Open Bin Packing Problems'. Journal of Heuristics, 3(4), pp. 299-304) and are specified within this publication.)
Moving on to the graph colouring problem, here are a number of comma delimited text files containing the experimental data gained in "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" (descriptions included). The graph colouring problem generator of Joe Culberson used in this work can also be downloaded from Joe Culberson's graph colouring resources page. As well as this tool, Joe Culberson's webpage also contains a variety of other programs and resources useful for graph colouring research, including solvers, generators and publications.
Sudoku:
As you will see from my publications list, some of my work has concerned the use of metaheuristics to help solve sudoku puzzles. If you want to download the c++ code used for the experiments described in "Lewis, R. (2007). 'Metaheuristics can Solve Sudoku Puzzles' Journal of Heuristics, vol. 13 (4), pp 387-401", it can be downloaded here as a .zip file. The c++ 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 your favourite 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:
Some of my previous work has 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. A description of the file layouts is also included in this resource. 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.
Trapezoid Packing:
Research has also been conducted on an interesting variant of the one-dimensional bin packing problem where items are trapezoidal in shape with a fixed height. A practical application of this problem 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 is introduced and analysed in the paper "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." The problem instances used in this paper can be downloaded here.
Other Useful Links
Online teaching resources for MA0105: An Introduction to Probability can be found here.
Somewhere in Wales
Welsh beach break
In Norway, January 2008