News:

Simutrans Wiki Manual
The official on-line manual for Simutrans. Read and contribute.

Avoid Air Traffic Congestion

Started by Bernd Gabriel, October 09, 2017, 01:11:17 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Bernd Gabriel

Having about 240 airplanes in 26 lines flying between 14 airports I could no longer add more planes to raise the transport capacity as more and more planes were circling in the air waiting for landing.

a) The traditional way to overcome that bottleneck: Add another runway and change the destination tile of some of the concurrent lines to enforce using the new runway. If routing selected a free or at least less used runway it would ease off this bottleneck.

b) While some planes are circling some other planes are landing coming straight from somewhere. Wouldn't it be nice (and more real) if planes landed in order of arrival at the runway? Reserving the runway should resepct the order of arrival.

The code in my github branch avoid-air-traffic-congestion (based on aburch/simutrans) introduces "reservation scheduling" which is a solution for both a) and b):

a) When routing checks the way costs of runway tiles it checks if there is a free time slot for the estimated arrival time. If yes, this runway costs as usual. If not, this runway is very expensive. The more reservations for it the more expensive it is. In the finally calculated route 1 runway tile is reserved for the period from estimated arrival time until end of estimated usage time. This enforces using all available runways.

b) When the convoy checks if the runway can be reserved it checks if there are scheduled reservations and if yes if it is its reservation's turn.


This screenshot shows an airport with 4 runways for landing and another 4 for starting. While in unmodified Simutrans 120.2.3 it has a capacity of about 350 convoys with schedule reservation the airport achieves a capacity of about 580 convoys.

In case this code will be considered for integration into simutrans the scheduled reservations should be saved in saved games.
The journey is the reward!

Leartin

I see in your airport layout, all runways are connected with all 'gates'. Does your patch work if only some runways are connected to some gates?

Bernd Gabriel

It is still the same routing code. The patch just encourages using all runways that are connected with the one gate that is part of the convoy's/line's schedule.
The journey is the reward!

DrSuperGood

The idea sounds very good. How fesible is save/load of the required schedules, especially so they survive round trip intact? What about the added computation overhead, as path finding is already quite expensive?

Bernd Gabriel

Quote from: DrSuperGood on October 09, 2017, 10:51:41 PM
How fesible is save/load of the required schedules, especially so they survive round trip intact?
The schedule remembers convoyhandles and ticks. As the comment of karte_t::get_ticks() says "Time since map creation or the last load in ms." saved ticks should be relative to the saving time ticks. Then the loaded ticks are relative to the loading time ticks which are said to be 0.

Quote from: DrSuperGood on October 09, 2017, 10:51:41 PM
What about the added computation overhead, as path finding is already quite expensive?
Of course there is a little additional computation required, but very little. The scheduling is implemented in schiene_t and schedule items are added by the first air_vehicle_t only for exactly 1 runway tile per runway. In schiene_t::can_reserve() there is an additional check for scheduled reservations for all railways and airways if the way is not yet reserved. Most schedules are empty and no more checks are required.

The A* routing for taxiing planes may need a little longer as the routes may become a little longer, if the shortest routes are not the optimal ones according to the scheduled reservations.

The scheduling is implemented in schiene_t because it could be nice to extend the "starting schedule code" for planes to "enter block code" for trains. Sometimes trains in stations with lots of tracks are marked as blocked while trains that arrived later are leaving the station again. And it would balance the load of parallel routes to the same destination.
The journey is the reward!

TurfIt

Seems like a simple reasonable idea. But, I have issues with the implementation...

First functionality - using the 'The World-V2-102-2.sve' testgame from prissi I see anomalies:
1) a non-reserved runway, a plane on taxiway waiting for this runway, 3 circling planes all waiting. Finally after much time another plane from halfway across the map arrives, reserves the runway, lands. Then finally the other 4 planes go.  not first-come first-served as the code comments say.

2) a non-reserved runway, a plane on taxiway arrives at the runway and stops, waiting, just sitting there on the taxiway. Finally after some days it reserves the runway and proceeds.

3) some planes circling in holding are at full speed rather than the reduced holding speed.

4) a reserved runway, planes circling waiting to land, two planes waiting on the taxiway to takeoff. The runway is reserved by the second plane in line on the taxiway. deadlock.




Quote

+// Reservation scheduling is added to schiene_t to encourage using it for
+// fair scheduling (first come, first serve) in railway nets as well.

How do you envision this working with rails? I can't see the same departure and arrival parameters being useful here.


Quote from: Bernd Gabriel on October 10, 2017, 02:55:51 PM
The scheduling is implemented in schiene_t because it could be nice to extend the "starting schedule code" for planes to "enter block code" for trains. Sometimes trains in stations with lots of tracks are marked as blocked while trains that arrived later are leaving the station again. And it would balance the load of parallel routes to the same destination.
Such dynamic pathing is something strongly denied in the past. I can see the case for exception for airports given their nature, but not rails.

Anyway, no way the bloated overhead of 12 bytes per track/runway tile is justified. IMHO at a minimum for consideration of merging the bloat needs to be moved to runway_t.  Any rail usage would be future.




Semi brain dump of issues:

Departing and arriving aircraft end up with separate reservation queues at opposite ends of the runway. Intended?

Even with the queues on the runway end tiles, the reservation lists get accessed multiple times on every runway tile. Not performant. Perhaps a higher level air traffic control object containing the reservations instead of per tile?

I see many more iterations of the list than insertions. slist bad for that (Simutrans slist bad for everything actually). Suggest vector instead.

List iterated to remove an item, then immediately iterated again to add. Operation should be combined to one iteration.

Direct tick comparisons don't handle the wrap around that occurs on long running games. Subtractions to get the time differences needed as per all the other usages of world ticks.

Can we lose the @author and //BG, {date} superfluous clutter?

New variables should be in English.  '_ziel'

departure = arrival + duration?  huh.

In air_vehicle_t::calc_route(), changes to start_in_air, and old_state.  Stowaways in patch? bugfixes for trunk? or Newly required for this patch?


Bernd Gabriel

A first quick reply @TurfIt:

I tried an implementation with minimum changes to the existing code and in the existing code style.

Where can I get 'The World-V2-102-2.sve' to see the anomalies?
The journey is the reward!

Bernd Gabriel

Quote from: TurfIt on October 11, 2017, 02:08:47 AM
1) a non-reserved runway, a plane on taxiway waiting for this runway, 3 circling planes all waiting. Finally after much time another plane from halfway across the map arrives, reserves the runway, lands. Then finally the other 4 planes go.  not first-come first-served as the code comments say.

2) a non-reserved runway, a plane on taxiway arrives at the runway and stops, waiting, just sitting there on the taxiway. Finally after some days it reserves the runway and proceeds.
These waiting times are artifacts of the transition to reservation scheduling. They vanish as soon as all planes are scheduled resp. schedules will be loaded from savegames.

Quote from: TurfIt on October 11, 2017, 02:08:47 AM
4) a reserved runway, planes circling waiting to land, two planes waiting on the taxiway to takeoff. The runway is reserved by the second plane in line on the taxiway. deadlock.
Maybe another artifact of the transition to reservation scheduling? I have to investigate that. Where can I get this testgame?

Quote from: TurfIt on October 11, 2017, 02:08:47 AM
How do you envision this working with rails? I can't see the same departure and arrival parameters being useful here.
You're right. The timing is not important for e.g. leaving a station into a distinct direction. Only the order of leaving should be controlled.

Quote from: TurfIt on October 11, 2017, 02:08:47 AM
Departing and arriving aircraft end up with separate reservation queues at opposite ends of the runway. Intended?
The reservation schedules must be located in runway tiles that are part of the routing. The only runway tiles that are part of the routing are the last tiles of the routing, the first tiles of the starting and landing process. Actually I did not consider that runways may be used for both starting and landing asI always use separate runways even for small airports.

Quote from: TurfIt on October 11, 2017, 02:08:47 AM
Even with the queues on the runway end tiles, the reservation lists get accessed multiple times on every runway tile. Not performant. Perhaps a higher level air traffic control object containing the reservations instead of per tile?
I'd love to schedule per "block" (== complete runway) but currently there is nothing like block_t.

Quote from: TurfIt on October 11, 2017, 02:08:47 AM
Can we lose the @author and //BG, {date} superfluous clutter?
Of course, I just tried to copy the existing style and to mark the inserted code for simpler reviewing it.

Quote from: TurfIt on October 11, 2017, 02:08:47 AM
In air_vehicle_t::calc_route(), changes to start_in_air
Actually this is a fix for a bug detected in my first approach to use free runways, which tried to recalculate a new route to a free runway instead of cicrcling. If the rerouted plane was flying above a runway it was dropped down to ground.

Quote from: TurfIt on October 11, 2017, 02:08:47 AM
In air_vehicle_t::calc_route(), old_state.
This was required by the first approach as the new state while starting in the air was not always flying but also circling.
The journey is the reward!

TurfIt

Quote from: Bernd Gabriel on October 11, 2017, 10:18:46 AM
Where can I get 'The World-V2-102-2.sve' to see the anomalies?
prissi had made these test games available quite a while ago. Not sure if it was publicly... Hopefully he can chime in if they're still available, or if others can freely distribute them instead.


Quote from: Bernd Gabriel on October 11, 2017, 06:07:43 PM
These waiting times are artifacts of the transition to reservation scheduling. They vanish as soon as all planes are scheduled resp. schedules will be loaded from savegames.
As comments in the patch itself state, handling older savegames without the schedules needs to be. Perhaps a better schedule initialization is possible...
IMO if there's simply a short transition period with possibly strange behaviour, ok, but obviously deadlocks cannot be allowed.


Quote from: Bernd Gabriel on October 11, 2017, 06:07:43 PM
You're right. The timing is not important for e.g. leaving a station into a distinct direction. Only the order of leaving should be controlled.
I still can't picture what you envision for rail reservation scheduling.


Quote from: Bernd Gabriel on October 11, 2017, 06:07:43 PM
The reservation schedules must be located in runway tiles that are part of the routing. The only runway tiles that are part of the routing are the last tiles of the routing, the first tiles of the starting and landing process.
I'd love to schedule per "block" (== complete runway) but currently there is nothing like block_t.
block_t or something like it (air_traffic_control_t!) might be required to eliminate the unused data structures in the ways. It makes no sense to bloat up every object by 30% when the data is only useful on a couple of the ways.


prissi

I think one can preserve the idea without these problems. Indeed the change of destination runway at routing time, is a very nice idea. Still for actual runway reservation, the current code is used. The runwaz tiles just get an additional list (which is only populated at the end of turn tile). All planes add themselves to it either at routing or loading time and deregister either at passing or when disbanding. But this is only used for routing weight (cost) calculation.

Bernd Gabriel

A version of reservation scheduling moved to runway_t and using vector_tpl is available in branch avoid-air-traffic-congestion-2.
The journey is the reward!

Dwachs

#11
here is an updated patch, if anyone is interested. Took me a while to figure out how to get it directly from github.

I do not have The-World.sve either. Can anybody please upload this file?

Edit: should we upload the savegame to e.g. sourceforge?

Edit2: all the congestions in this savegame are due to poor ground control, imho, i.e., planes deadlocking the taxiways and runways

Edit3: there is problem when modifying reserved runways: for instance splitting very long runways into two.
Parsley, sage, rosemary, and maggikraut.

prissi

I liked the idea of marking of how many planes will use a runway. That leads also to balance the runways for takeoff without any signs needed. But here is a much easier take, that will also work well with existing games. It will not reserve time slots, but just balancce the load on all available runways.

Dwachs

Seems that this was comitted with r8454
Parsley, sage, rosemary, and maggikraut.

prissi

Sorry, I just realised this too. Was not my intent (otherwise I would not published a patch here), but please test it anyway.

Actually, I was wandering if adding a heftig malus for reserved tiles and using the "convois last month" would not be even enough.

Bernd Gabriel

if
Quote from: prissi on May 25, 2018, 07:53:59 AMusing the "convois last month"
worked, "convois last month" of all runways would be the same and thus would not work ;)
The journey is the reward!