[Rails-devel] Route calculation: Train length heuristic

[Stefan F. <ste...@we...>]

A year ago I suggested another heuristic to improve the speed of the revenue 
calculation.

The idea is to use what 1830 players automatically do: 
If you calculate a run for a 4 and a 3 train, you already know that you will 
end up with a longer route (more stations) for the 4 train and a shorter route 
for the 3 train. Similar for running a Diesel and a 5 train.

However this knowledge is not taken into account by the current algorithm.
Things unfortunately are not that easy for all 18xx as it are in 1830. 
For example in 1835 one cannot tell this ex-ante for a combination of a 5+5 
and a 6 train. That in fact is one the reasons why calculating the Preussian 
routes is not an easy task.

Another exceptions are: If trains score differently for the same route 
(Express (xE) and Double (xD) trains) or if hex trains run jointly with 
standard trains.

** The formal definition of train domination:

If the "better" train A can run all routes that the "weaker" train B and train 
A scores identical revenue on all routes as B, then I define that train A 
dominates train B.

If A dominates B I write this as A>B, otherwise the trains are either 
identical (A=B) or neither dominates (A<>B).

If train A dominates train B, the length of the route of train A will always 
be longer or at least equally long as that of train B.
(Length of the route is the number of stations scored.)

** Examples should make this clearer.

In 1830 it is easy:  D>6>5>4>3>2

In 1835 it is
6+6 > 5+5 > 4+4 > 3+3 > 2+2
6 > 5 > 4 > 3 > 2
6+6 > 6, 5+5 > 5, 4 +4 > 4, 3+3 > 3, 2+2 > 2
6 > 3+3, 4 > 2+2
But for example: 6 <> 5+5, 5 <> 3+3 etc.

** Implementation
The implementation is pretty straight forward and only requires a few lines of 
code in the revenue calculator. The major change is to order the trains by the 
criteria "train domination". Then the calculator assigns the initial train 
length for the dominated train not with the maximum length of that train, but 
with the (current) route length of the dominating train. This ensures that the 
dominating train will always have the longer route assigned.

** Speed improvement
I did run the scenarios of Aliza Panitz 1856 triple Diesel of CGR scenarios 
and came to the following running times (more statistics on number of routes 
evaluated and when the best solution was found see below).

For the simpler network (A) running times decrease from around 5 minutes to 
3.5 minutes (my CPU is more powerful than Alizas ...).
For the extensive network (B) running times decrease from around 1 hour to 
around 30 minutes.

Overall the improvement it seems that the speed is improved by around 50% to 
200%, so time to wait is down by 33% to 66%, which is not bad.

But as it can be clearly seen by comparison with a double Diesel scenarios the 
exponential characteristic of the algorithm is still very clear.

So I still hope that John Tamplin can give some hints on his lost flow 
algorithm for those who want to run triple Diesel more often.

Stefan

** Stats

=> Aliza Scenario 1856 A:
31 vertices with 41 edges
10 startvertices

Values:
Single D: 700
Double D: 920
Triple D: 1120

Single D: 0 second / 6.2k Evaluations, 6.2k Predictions

Without dominant trains:
Double D: 3 seconds / 1.3M Evaluations, 1.4M Predictions
Triple D: 290 seconds / 114.9M Evaluations, 129.5M Predictions
(Solution: 25 seconds / 13.4M Evaluations, 14.7M Predictions)

With dominant trains:
Double D: 1 second / 323k Evaluations, 385k Predictions
Triple D: 206 seconds / 87.4M Evaluations, 98.0M Predictions
(Solution: 20 seconds / 9.1M Evaluations, 10.0M Predictions)

=> Aliza Scenario 1856 B:
34 vertices with 50 edges
10 startvertices

Values:
Single D: 790
Double D: 1280
Triple D: 1440

Single D: 0 second / 53.3k Evaluations, 53.3k Predictions

Without dominant trains:
Double D: 12 seconds / 4.8M Evaluations, 5.1M Predictions
Triple D: 3551 seconds / 1473M Evaluations, 1709M Predictions
(Solution: 41 seconds / 16.9M Evaluations, 17.7M Predictions)

With dominant trains:
Double D: 5 seconds / 1.9M Evaluations, 2.3M Predictions
Triple D: 1926 seconds / 832M Evaluations, 962M Predictions
(Solution: 27 seconds / 11.7M Evaluations, 12.3M Predictions)

=> Scenario 1870:
This is the route network used for testing a year ago,

23 vertices with 57 edges
1 startvertex

Values:
Single 12: 380
Double 12: 690
Triple 12: 820

Single 12: 0 second / 11.5k Evaluations, 23.7k Predictions

Without dominant trains:
Double 12: 4 seconds / 1.4M Evaluations, 1.9M Predictions
Triple 12: 104 seconds / 23.4M Evaluations, 61.6M Predictions
(Solution: 13 seconds / 3.2M Evaluations, 6.2M Predictions)

With dominant trains:
Double 12: 4 seconds / 1.2M Evaluations, 1.7M Predictions
Triple 12: 49 seconds / 8.1M Evaluations, 30.0M Predictions
(Solution: 16 seconds / 3.0M Evaluations, 9.3M Predictions)