Thread: Re: [Rails-devel] Route calculation validations

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Hi Alex,
I have attached a document that contains the detailed numbers for several 
train combinations without and with the revenue prediction active.

The following figures are defined:
revenue evaluation: how often the revenue of all trains is evaluated
edges travelled: how many edges were followed during the search
predictions: how often the potential maximum revenue was predicted.

My desktop is even slower as my laptop, as it is slightly older and has an AMD 
processor.

It clearly shows that revenue predictions is strongest for train combinations 
and non-diesel trains. Running a diesel alone is not any faster, unless an 
optimal solution is found (early).

Stefan

I sent that to the develop list, as others might also be interested in those 
numbers. I extract the main figures below,
all runs on the test scenario A.

8 train alone:
without prediction: 3.8k evaluations, 16.4k edges, time: < 1 sec
with prediction: 62 evaluations, 858 predictions, 2.3k edges, < 1 sec

8 and 10 trains:
without prediction: 1.9M evaluations, 11.0M edges, time: 90 sec
with prediction: 25k evaluations, 143k predictions, 387k edges, time: 4 sec

This clearly shows the strong increase of possible solutions, if more than one 
train is involved. It is around 1:500!

Diesel train:
without prediction: 424k evaluations, 3.3M edges, time: 25 sec
with prediction: 335k evaluations, 753k predictions, 2.6M edges, time: 23 sec
(In this example an optimal solution is found, but late).

A diesel is less complicated than the combination of an 8 and 10, but the 
revenue prediction does no help.

Diesel and a 6 train:
without prediction: 7.3M evaluations, 52.5M edges, time: 480 sec
with prediction: 231k evaluations, 2.8M predictions, 6.2M edges, time: 56 sec

Adding a 6 train, increases the running time by 20 without prediction, but 
only a little more than doubles with prediction.

On Sunday 18 April 2010 17:44:04 you wrote:
> Hi Stefan,
>
> I would agree about the name of the first number.
>
> (1) should be ok, I do the same, and there is no good reason for the
> algorithm to try evaluating route that just extend already evaluated route
> by some stations the train can't reach anyway. Or we could run the test on
> "express" train that can skip anything. Express trains (or any train
> capable of skipping cities) actually make me wonder what are possible
> rules about visiting the same hex. In some games train is not allowed to
> visit the same hex twice (when there are 2 separate cities on the tile).
> If there is any game with this rule and with express trains, then there's
> a question - if the train skips one city in the hex and counts another -
> is it valid route?
>
> (2) I apply the same method to the routes, but I didn't evaluate "half"
> routes - I only evaluate complete route (consisting of those 2 parts). How
> can you do differently? - There might be bonus for visiting 2 cities in
> different halves, or something like east-west run.
>
> If it's difficult to extract this number from your code now, we could set
> up example with the station in the dead-end, so there's only one way to
> leave it.
>
> Number of segments is relevant to the two-phased approach only. It is
> number of edges in the "coarse" graph (which is the same as number of
> distinct ways to travel between any pair of cities). You were asking about
> this number earlier to evaluate amount of memory that would need to be
> stored.
>
> I've also done profiling and it appears that storing segment exclusions as
> a vector of segments excluded by each segment is fine - this is not a
> bottleneck. So I haven't tried 2D array of booleans approach. But maybe I
> should try some different cases (for example set of 4 trains (2,2,3 and 3)
> - that may have a bottleneck in different places comparing to the case of
> few long trains).
>
> Thanks,
> Alex.
>
> On Sun, 18 Apr 2010 13:28:24 -0600, Stefan Frey <ste...@we...> wrote:
> > Hi Alex,
> > I would call the first statistic "number of  route evaluations" and it
> > counts
> > every call to the evaluation function. This figure is also available for
> > multiple-train runs. If we have the same number, it is almost sure that
> > the
> > two algorithms work identical. If not, it proves nothing, see below.
> >
> > Potential problems:
> > 1) I terminate trains as soon as possible, thus numbers depend on the
> > sequence
> > of vertexes visited.
> >
> > 2) I have train runs divided in two half trains: First the head train
> > starts
> > and each station the train can return to its start token and then the
> > bottom
> > train runs. To avoid duplication of routes (due to symmetry) the bottom
> > train
> > can only start to the side with increased orientation. If I remember
> > that is
> > a different approach to yours.
> >
> > So if we want to compare figures we have to run a train with infinite
> > length
> > (to avoid termination) and is not allowed to run twice from the start
> > vertex.
> >
> > I will have to adjust my codes to accommodate for such a test.
> >
> > The other statistic I am not fully clear about: Wat is exactly the
> > number of
> > segments? If this is related to the two-phase approach I assume this is
> > the
> > maximum number of connections between two stations on the map?
> > And I guess, that this might be the answer to the unrelated question I
> > raised
> > before. This strengthens the case of your approach. I will implement it
> > as
> > soon as I have some time left, which will be most likely after the next
> > release.
> >
> > Stefan
> >
> > On Sunday 18 April 2010 06:34:51 you wrote:
> >> Hi Stefan,
> >>
> >> I thought it might be useful to compare how many routes we try during
> >> the
> >> complete route search. We should be getting the same number. If we are
> >> not
> >> it will indicate that one of us (or both) have a bug. I suppose to test
> >> it
> >> we would need to run a single sufficiently long train (or maybe try for
> >> various train lengths) on the same track.
> >>
> >> I've also checked on number of segments in two-phased approach. In the
> >> scenario B there are just 153 segments.
> >>
> >> Thanks,
> >> Alex.

Thread: Re: [Rails-devel] Route calculation validations

rails-devel