Assign seats of a train to passengers

We present the following application:

Using the application

Reservations can be added as well as deleted. The added reservations can be reserved - step by step - according to the chosen strategy. 

Users guide:

At first all reservation request should be added. Then they can be reserved one by one and the assigning process can be seen
The strategy can be changed at any time. The reservation requests become reassigned automatically.

Seat Reservation Application

[Application cannot run]
Here you can start the application.

Evaluation of strategies
Strategies try to assign seats in a way that the income from selling the tickets is maximized.
The upper bounds for the strategies can be achieved by setting up worst case scenarios. The bounds on the accommodating ratios can be observed at any time when reserving reservations.
Two cost models are implemented:
The Accommodating Ratio of a fair strategy given a sequence of reservation requests is
Accommodating means that the optimal strategy can accommodate all reservation requests. Fair means that the strategy must not reject a reservation request to wich it could a seatnumber.

Lower bounds are valid in all scenarios, upper bounds only in special scenarios. Our aim is to The current accommodating ratio in the Unit Cost Model and the Proportional Cost Model are always up to date.

The following strategies are available:
  • First Fit: Every reservation request is placed on the first seat that can accommodate the whole reservation request
  • Best Fit: Every reservation request is placed on the seat wich leaves the smallest gap. A gap is an consecutive number of station before and after the journey where every seat is free.
  • Random: From all possible seats one is chosen arbitrarily.

  • Results

    In the following section let the number of stations be k.

    Unit Cost Model

    Universal bounds

    Lower bound:
  • Theorem Any fair strategy for the seat reservation problem is 1/2 - accommodating
  • Upper bound:
  • Theorem No fair strategy for the seat reservation problem is more than 6/7 - accommodating, when k ≥ 4

  • First Fit

    Upper bound:
  • Theorem First Fit is no better than (2k-2)/(3k-6) - accommodating, when k ≥ 7 and k = 1 (mod 3)

  • Best Fit

    Upper bound:
  • Theorem Best Fit is no better than (2k-2)/(3k-6) - accommodating, when k ≥ 7 and k = 1 (mod 3)

  • Proportional Cost Model

    Universal bounds

    Lower bound:
  • Theorem Any fair strategy for the seat reservation problem is 1/(k - 1) - accommodating
  • Upper bound:
  • Theorem No fair strategy for the seat reservation problem is more than 11,211/(10,211+k) - accommodating, when k ≥ 4

  • First Fit

    Upper bound:
  • Theorem First Fit is no better than 4/(k+2) - accommodating.

  • Best Fit

    Obere Schranke:
  • Theorem Best Fit is no better than 4/(k+2) - accommodating.
  • Authors: Simone Lehmann, Rainer Penninger

    Bibliography:

    [1]:Joan Bojar, Kim S. Larsen.
    Paper on the Seat Reservation Problem.