Creating Seating Plans: A Practical Application

Rhydian Lewis, Fiona Carroll

    Research output: Contribution to journalArticlepeer-review

    1253 Downloads (Pure)

    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 NP 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.
    Original languageEnglish
    Pages (from-to) 1353-1362
    Number of pages13
    JournalOperational Research Society
    Volume67
    Issue number11
    DOIs
    Publication statusPublished - 18 Oct 2016

    Keywords

    • Seating Plans
    • Integer Programming
    • Graph Colouring
    • Metaheuristics
    • Combinatorial Optimisation

    Fingerprint

    Dive into the research topics of 'Creating Seating Plans: A Practical Application'. Together they form a unique fingerprint.

    Cite this