Menu
▾
▴
Re: [Rails-devel] Route calculation: Train length heuristic
|
From: Phil D. <de...@gm...> - 2011-08-09 10:24:36
|
Ed, I've forwarded it off-list Phil On 9 August 2011 10:48, Edward S. Rustin <ed...@we...> wrote: > 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 > > > ------------------------------------------------------------------------------ > 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 > > |
