Creating seating plans: a practical application

Abstract

This paper examines the interesting problem of designing seating plans for large events such as weddings and gala dinners where, among other things, the aim is to construct solutions where guests are sat on the same tables as friends and family, but, perhaps more importantly, are kept away from those they dislike. This problem is seen to be -complete from a number of different perspectives. We describe the problem model and heuristic algorithm that is used on the commercial website www.weddingseatplanner.com. We present results on the performance of this algorithm, demonstrating the factors that can influence run time and solution quality, and also present a comparison with an equivalent IP model used in conjunction with a commercial solver.

Keywords:

• seating plans
• graph colouring
• combinatorial optimisation
• metaheuristics
• integer programming

Acknowledgements

The authors would like to thank the anonymous referee whose comments and suggestions helped to improve this manuscript.

Notes

1 Note that the k-partition problem is also variously known as the load balancing problem, the equal piles problem, or the multiprocessor scheduling problem.

2 For example, using the problem shown in Figure 2, V={v₂,v₃,…,v₉} and E′={{v₂,v₄}, {v₃,v₅}, {v₄,v₈}}.

3 Specifically, TABUCOL is executed for 20n iterations, using a tabu tenure t proportional to the current cost (t=0.6f₁+r, where r is randomly selected from the set {1,2,…,9}), as recommended by Galinier and Hao (1999).

4 That is, all vertices and colours involved in the move are marked as tabu in T. For speed’s sake, in our application a fixed-size tabu tenure of 10 is used along with an iteration limit of 10n.

5 That is, the graph G′ used in Stages 1 and 2 would comprise edge set E′={{u,v}∈E: w_uv⩾c}.