Assign seats of a train to passengers
We present the following application:
- Seat reservation in case of all reservations could be placed by an optimal strategy
Using the applicationReservations can be added as well as deleted. The added reservations can be reserved - step by step - according to the chosen strategy.
- Click Settings to adjust number of seats and number of stations
- Click Reserve to reserve the next reservation request
- Click Cancel to cancel the seat number assignment of the last reservation
- Click Remove to delete the last reservation request
- Click Add to add a new reservation request. Numbers of start- and endstation must be typed into the corresponding textfields
- Choose between 3 Views. Look at the whole scedule or select one specific seat or station
- Click Unit Cost to load a scenario which demonstrates the upper bound of the Unit Cost Model
- Click Proportional Cost to load a scenario which demonstrates the upper bound of the Proportional Cost Model
The strategy can be changed at any time. The reservation requests become reassigned automatically.
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:
- Unit Cost Model: Every trip has cost of 1 unit
- Proportional Cost Model: The cost of a trip is porportional to its length
The earn of the strategy divided by the earn of the optimal strategy.
Lower bounds are valid in all scenarios, upper bounds only in special scenarios. Our aim is to
- proove large lower bounds
- give examples with small lower bounds
The following strategies are available:
ResultsIn the following section let the number of stations be k.
Unit Cost ModelUniversal bounds
Proportional Cost ModelUniversal bounds
Authors: Simone Lehmann, Rainer Penninger
|:||Joan Bojar, Kim S. Larsen.|
Paper on the Seat Reservation Problem.