Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6898688 | European Journal of Operational Research | 2010 | 10 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Tommy Clausen, Allan Nordlunde Hjorth, Morten Nielsen, David Pisinger,