The Off-line Group Seat Reservation Problem

Tommy Clausen, Allan Nordlunde Hjorth, Morten Nielsen, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-review


    In this paper we address the problem of assigning seats in a train for a group of people traveling together. We consider two variants of the problem. One is a special case of two-dimensional knapsack where we consider the train as having fixed size and the objective is to maximize the utilization of the seats in the train. The second is a special case of two-dimensional bin packing where all requests must be accommodated while trying to minimize the number of passenger cars needed. For both variants of the problem we present a number of bounds and develop exact algorithms. Computational results are presented for various instances based on realistic data, and from the packing literature adapted to the problems addressed.
    Original languageEnglish
    JournalEuropean Journal of Operational Research
    Issue number3
    Pages (from-to)1244-1253
    Publication statusPublished - 2010


    • storehouse planning
    • two-dimensional packing problem
    • production planning
    • bin packing
    • Berth scheduling
    • seat reservation


    Dive into the research topics of 'The Off-line Group Seat Reservation Problem'. Together they form a unique fingerprint.

    Cite this