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

[alexti <al...@sh...>]

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
>


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/