Bei der Zuteilung von Sitzplätzen in den Zügen der Bundesbahn geht es darum, den Ertrag zu maximieren, d.h., so viele Gäste wie möglich unterzubringen. Ein Zug fährt über viele Stationen von A nach B und die Reisenden können zu einem beliebigen Zeitpunkt vor ihrer Abfahrt einen Platz reservieren. Fairer Weise soll jedem Reisenden auch ein Platz zugewiesen werden, wenn ein Platz für die angefragte Teilstrecke frei ist. Da aber die späteren Reservierungsanfragen noch nicht bekannt sind, kann der Bahnbedienstete den Zug nicht optimal füllen, das führt zu Einbußen. Wir betrachten hier nur den etwas spezielleren Fall, daß der Zug eigentlich für die Anfragen ausreichen würde (Accomodating) und jedes Ticket den gleichen Preis hat (Unit-Price Problem).
Inhalt des Vortrags:
Literatur:
J.Boyar and K.S. Larsen, The Seat Reservation Problem
Algorithmica 1999 25, 403-417, relevant 403-411.
Betreuer:
Elmar Langetepe