Author Topic: Avoid Air Traffic Congestion  (Read 938 times)

0 Members and 1 Guest are viewing this topic.

Offline Bernd Gabriel

  • *
  • Posts: 229
  • Total likes: 5
  • Helpful: 20
  • Addicted to Simutrans: since 2003
    • Fast Function Factory
  • Languages: DE, EN, C++
Avoid Air Traffic Congestion
« on: October 09, 2017, 01:11:17 PM »
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!

Offline Leartin

Re: Avoid Air Traffic Congestion
« Reply #1 on: October 09, 2017, 01:44:54 PM »
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?

Offline Bernd Gabriel

  • *
  • Posts: 229
  • Total likes: 5
  • Helpful: 20
  • Addicted to Simutrans: since 2003
    • Fast Function Factory
  • Languages: DE, EN, C++
Re: Avoid Air Traffic Congestion
« Reply #2 on: October 09, 2017, 01:51:24 PM »
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!

Offline DrSuperGood

Re: Avoid Air Traffic Congestion
« Reply #3 on: October 09, 2017, 10:51:41 PM »
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?

Offline Bernd Gabriel

  • *
  • Posts: 229
  • Total likes: 5
  • Helpful: 20
  • Addicted to Simutrans: since 2003
    • Fast Function Factory
  • Languages: DE, EN, C++
Re: Avoid Air Traffic Congestion
« Reply #4 on: October 10, 2017, 02:55:51 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.

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!

Offline TurfIt

Re: Avoid Air Traffic Congestion
« Reply #5 on: October 11, 2017, 02:08:47 AM »
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
Code: [Select]
+// 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.


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?


Offline Bernd Gabriel

  • *
  • Posts: 229
  • Total likes: 5
  • Helpful: 20
  • Addicted to Simutrans: since 2003
    • Fast Function Factory
  • Languages: DE, EN, C++
Re: Avoid Air Traffic Congestion
« Reply #6 on: October 11, 2017, 10:18:46 AM »
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!

Offline Bernd Gabriel

  • *
  • Posts: 229
  • Total likes: 5
  • Helpful: 20
  • Addicted to Simutrans: since 2003
    • Fast Function Factory
  • Languages: DE, EN, C++
Re: Avoid Air Traffic Congestion
« Reply #7 on: October 11, 2017, 06:07:43 PM »
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.

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?

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.

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.

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.

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.

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.

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!

Offline TurfIt

Re: Avoid Air Traffic Congestion
« Reply #8 on: October 12, 2017, 12:59:52 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.


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.


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.


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.


Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 8830
  • Total likes: 324
  • Helpful: 229
  • Languages: De,EN,JP
Re: Avoid Air Traffic Congestion
« Reply #9 on: October 12, 2017, 06:13:18 AM »
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.

Offline Bernd Gabriel

  • *
  • Posts: 229
  • Total likes: 5
  • Helpful: 20
  • Addicted to Simutrans: since 2003
    • Fast Function Factory
  • Languages: DE, EN, C++
Re: Avoid Air Traffic Congestion
« Reply #10 on: October 15, 2017, 10:28:47 AM »
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!

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4280
  • Total likes: 196
  • Helpful: 149
  • Languages: EN, DE, AT
Re: Avoid Air Traffic Congestion
« Reply #11 on: December 09, 2017, 07:58:54 PM »
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.
« Last Edit: December 09, 2017, 09:31:02 PM by Dwachs »
Parsley, sage, rosemary, and maggikraut.