The Off-line Group Seat Reservation Problem

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

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    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
    Volume207
    Issue number3
    Pages (from-to)1244-1253
    ISSN0377-2217
    DOIs
    Publication statusPublished - 2010

    Keywords

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

    Cite this