Re: [Rails-devel] Route calculation: Train length heuristic

[Edward S. R. <ed...@we...>]

Is there a copy of the rails file that Aliza's problem stems from?

I've been playing around with a few ideas for calculating optimal routes,
but I'd rather not write a long post explaining them without having tried
them out on a map which is already known to be tricky - much less risk of
making an ass out of myself that way :-)

On Tue, Aug 9, 2011 at 06:02, Stefan Frey <ste...@we...> wrote:

> 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)
>
>
> ------------------------------------------------------------------------------
> uberSVN's rich system and user administration capabilities and model
> configuration take the hassle out of deploying and managing Subversion and
> the tools developers use with it. Learn more about uberSVN and get a free
> download at:  http://p.sf.net/sfu/wandisco-dev2dev
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel
>