Algorithms for Flows over Time with Scheduling Costs

In diesem Modell hat jeder Bogen eine Verzögerung bei der Durchquerung des Bogens und eine Grenze bei der Geschwindigkeit des Flusses, der in den Bogen eintritt; Flüsse sind zeitlich verschieden. Wir betrachten eine Einstellung, die in der verkehrsökonomischen Literatur sehr üblich ist, aber aus algorithmischer Sicht wenig Beachtung findet. Der Fluss besteht aus Benutzern, die in der Lage sind, ihre Route, aber auch ihre Abfahrtszeit zu wählen, und die ihr Ziel zu einem bestimmten Zeitpunkt erreichen möchten, wobei ihnen Planungskosten entstehen, wenn sie früher oder später ankommen. Die Gesamtkosten eines Benutzers sind dann eine Kombination aus der Zeit, die sie pendeln, und den Planungskosten, die ihnen entstehen. Wir stellen einen kombinatorialen Algorithmus für das natürliche Optimierungsproblem vor, nämlich die Minimierung der durchschnittlichen Gesamtkosten aller Benutzer (d.h. die Maximierung des sozialen Wohlergehens). Auf dieser Grundlage zeigen wir auch, wie man Mautgebühren festlegt, so dass dieser optimale Fluss als Gleichgewicht des zugrunde liegenden Spiels herbeigeführt wird.