Re: [Rails-devel] Improved revenue prediction / different scenario

[Stefan F. (web.de) <ste...@we...>]

Hi Alex,
but you are still faster and get more scenic routes, thus you should not be 
too concerned :-)

And I did 565k evaluations plus 5,651k predictions, compared to this number it 
is only 10 times less. The only optimization (or better avoidance of 
unnecessary duplication) I have not talked about is that I keep the start 
vertices visited, when I move to the next start vertex. All possible routes 
which include the previous start vertex are already run from that vertex.

Otherwise we should go back to much simpler examples to compare, but I do not 
have much hope to get similar numbers as long as I do not have implemented 
the two-phase approach.

Stefan


On Tuesday 04 May 2010 07:37:39 alexti wrote:
> Hi Stefan,
>
> Thanks for the explanation. I think I understand what you're doing; I
> wasn't doing exactly the same and changing my algorithm brought some
> improvement, but as usual it was not that big - I'm starting to feel you
> have some kind of magic predictor ;-)
>
> I've run your scenario and my algorithm found the same set of routes,
> however it was able to find more scenic route between M6 and L11 for 5+5
> train :) It took 46s. Here are my stats.
>
> Routes found in 45.9643s
> [4:340] {E12,C10.SE,C10.NW,B9,B11,A10.N,A8.S,A8.N,A4.S,A4.N,A2.S}
> [8:290]
> {N1.SW,M2,L3.NE,L3.SW,K4,J3,J5,G6.NE,G6.NW,F5,E6.NE,E6.NW,D5,B3.SE,B3.NW,A2
>.SE} [10:230]
> {E12,H13,I14.NE,J13.SW,J13.NE,L11,M8,M10,M6,L5.SE,L5.NW,K4,J5,H3} [6:240]
> {N1.S,N3.N,N3.SW,M4.NE,M4.NW,L3.SE,L3.NW,J3,H3,F5,D5,D7.N,D7.NW,C6.SE,C6.SW
>,B7,B9,C8.SW,C8.S,C10.N,C10.SW,B11} 50,125,612 routes tried
>
> The frustrating (to me) part is that you've done only 564,805 while I did
> over 50 millions (almost 100 times more). I am not sure how you manage to
> eliminate so many possibilities. I know that my algorithm doesn't handle
> multiple stations efficiently - essentially it scales linearly with number
> of stations. I have not thought about it yet, but it still wouldn't
> explain the difference.
>
> Maybe I'm overlooking something. Or maybe I have some bug in the
> implementation that doesn't eliminate something I think it does :)
>
> Thanks,
> Alex.
>
> On Sun, 02 May 2010 13:20:14 -0600, Stefan Frey <ste...@we...> wrote:
> > Alex,
> > sorry for not answering earlier to the question about the improved
> > revenue
> > prediction.
> >
> > The scheme is simple.  Assume that N is the number of trains in the
> > trainset.
> > First I replace the maximum revenue potential of each single train by the
> > maximum results of running each train alone.
> >
> > If there are more than two trains to run:
> > Start with J=N-1 and decrease J with each step until J=1.
> > - Run the combined set of trains [J, ... N] and use the optimal result to
> > predict the maximum future revenue potential of that train set.
> >
> > Then run the combined optimization of all trains, given the maximum
> > revenue
> > potential for each set [J, N], with J > 1.
> >
> > I would like to compare another scenario based on the track network A to
> > check
> > if we get the same results.
> > The changes are:
> > - SLSF has 4 tokens now (D5, J3, L11, E12)
> > - Trains running are 6E, 8, 5+5, 4D
> > (E: ignores towns, D: ignores towns and double city and offboard values)
> > The best run I find is 1100. Total running time 78 sec.
> > Network runs (6E cyan, 8 pink, 5+5 orange, 4D gray)  and log is attached.
> >
> > Stefan