Re: [Rails-devel] Automatic route calculation

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

Hi Alex,

thanks for all the input below, it seems that there is really some more 
performance improvement possible. And without your proposals I would not have 
started such an implementation at all.

Unfortunately I do not have that much time now, but maybe some additions here 
are helpful, as I had some troubles understanding your approach first.

The major issue for me was how to get around the "switch" problem: A train is  
not allowed to turn around at the end of the switch and you have to leave the 
hex to the neighboring one. The major idea of my solution is the definition 
of a "greedy" edge: The "virtual" edges connecting the sides of the 
neighboring hexes force the traveller on their path, if they came 
in "non-greedy"  (those are the tracks inside the hex).

In the network graphs generated the non-greedy edges are those annotated with 
asteriks. A nice property is that greedyness is dominating if one merges two 
edges to eliminate a vertex with only two hexes. The new edge is greedy if at 
least one of them was greedy. This implies after optimization most edges are 
non-greedy, usually only the brown non-station tiles will be left. This and 
the dead-end elimination creates the optimized graphs in Rails.

I have attached the scenario (scenario A) that you talked below for reference 
for all others, with the rails save file (does only work with the CVS version 
due to the map corrections), a screenshot of the map and the optimized 
network graph.

Stefan

PS: I would like to compare the results and the performance of the two 
implementations (to know how much improvement is possible ...)

I did not use the exact specification I suggested (due to technical reasons):
There is only one token in E12 and I run an 8 and 10 train.

My solution run finished 12 minutes on my 4 year old laptop. Interestingly it 
found already 560 after 1 second, 570 after 1 minute and then 580 after 8 
minutes.

Revenue Value:580
Revenue run:{8=[E12.1, C10.SE, C10.NW, B9.1, B11.1, C10.NE, C10.W, C8.NE, 
D7.NE, D7.W, D5.1, F5.1, E6.NW, F7.NW, F7.SW, G6.SW, J5.1, K4.1, J3.1], 
10=[E12.1, H13.1, J11.W, J13.W, J13.SW, L11.1, M14.1, M10.1, M6.1, L5.SE, 
L5.NW, K4.1, L3.NE, L3.SW, M2.1, M4.NE, L3.SE, L3.NW, J3.1, J5.1]}

On Monday 12 April 2010 06:31:19 Alex Tikhonov wrote:
> Hi all,
>
> Sorry about my disappearance after raising this question couple of weeks
> ago. Things weren't standing still; I was in contact with Stefan, but
> unfortunately circumstances prevented quicker progress. Stefan has added
> some new functionality to Rails to lay some background framework and to
> simplify creation of "test problems". He has created few testing scenarios
> too. My original algorithm has proved to be marginal - on a relatively
> complex example the time was around 40 seconds. We've discussed various
> optimizations and I believe we have found good approach. The basic idea is
> to use two-phased process that runs on two different graphs. The first
> graph (let's call it primary graph) is built from the tiles and
> essentially follows one tile - 7 vertices principle (I've described this
> approach before and after some discussion with Stefan we've concluded that
> it's identical to the approach he had in mind). Essentially, one vertex is
> in the center of the tile and there are 6 vertices, one per tile edge. I
> was envisioning them inside of the tile, on the line connecting the center
> of the tile edge to the center of the tile (in fact, that's how I was
> visualizing them in my program) while Stefan was seeing the center of the
> tile's edge as such vertex (so adjacent tiles would have their vertices on
> the same spot and those vertices would be connected by [invisible] edge).
> This obviously describes exactly the same graph and the difference is only
> in how it can be thought of visually (or displayed).
>
> This primary graph is then used to generate secondary "coarse" graph. The
> only vertices coarse graph has corresponds to the nodes with some value
> (usually cities and towns). The edges of the coarse graph (I will call
> also them segments) are defined by possible distinct routes between its
> vertices. Thus there might be more than one edge connecting the same pair
> of vertices. This edges are built by running my original algorithm on the
> primary graph with the constraint requiring every route to contains
> exactly two nodes (vertices with value) - one at the start and another at
> the end. Essentially the list of these edges is the list of all possible
> two city/town routes. Each segment of this graph has additional
> characteristic - list of segments mutually exclusive with it. There are
> two types of exclusions - one forbids use of the related segment by any
> route and another forbids its use only by the same route. The first type
> of exclusion happens when two segments share some edge of the primary
> graph and the second type happens when only some vertex of the primary
> graph is shared (here we only consider non-terminating vertices - ones
> that are inside of the segment route, those vertices will have no value).
> This information forms coarse graph. There are multiple advantages in
> choosing this approach. The value of any route only depends on the nodes
> (vertices with values) visited, not the intermediate vertices. This
> considerably reduces number of possibilities to scan and it also allows to
> optimize the process by using "pre-packed" segment routes between the
> nodes. The coarse graph is company-independent - it has no token
> information and can be used to do route computations for any company. The
> coarse graph can be built incrementally. The most expensive part of
> building this graph is the search for all possible routes between every
> pair of nodes. This time can be saved if the coarse graph is updated
> incrementally when new tiles are laid (or upgraded). We only need to track
> the routes containing the newly added edges. All remaining routes are
> unaffected. On the "realistic" 1870 scenario we've used for testing it is
> taking 2-3 seconds to build coarse graph from scratch (on my rather
> average computer). If it's built incrementally, this time will virtually
> disappear. Of course, this leaves a question of game reloading (perhaps it
> makes more sense to rebuild it non-incrementally when the game is
> reloaded, or even save the coarse graph itself).
>
> The second phase of the process is to run optimal route search on the
> coarse graph. I am just running my original algorithm on this graph. This
> part takes care of source stations, hostile station blocking, visiting the
> same city twice and similar rules (as well as various bonus application).
> On the example described above this was taking 2-3 seconds. This phase has
> to be re-run every time on "Run trains" step of the operating round, but
> this response time seems acceptable. The run times I've mentioned are from
> my quickly put together implementation of this new approach, so I would
> imagine it's possible to do better just by refining the implementation and
> we haven't looked closely at possible algorithmic optimizations of phase 2.
>
> There are few possibly optimizations that can be applied to the primary
> graph too. Stefan has suggested "asterisk-edge" optimization. This is to
> simplify verification preventing backtracking. Idea is to mark all edges
> that are within the same tile with "asterisk" and then the rule preventing
> backtracking becomes very simple: two "asterisk" edges can be traveled
> consequently only if they're connected at the tile's center. This should
> help in phase 1 generation. There's some difficulty now though, because
> I'm using "transient vertex" optimization which can eliminate some edges
> and thus change adjacency of "asterisk" and "non-asterisk" edges. The
> transient vertex optimization works in the case when there's a vertex
> (without value) connected to exactly two other vertices (for example
> vertex B in A-B-C example). In this case vertex B can be removed and edges
> (A,B) and (B,C) replaced with (A,C) edge. This provides big benefit,
> because realistic track build normally has large amount of such vertices.
> Another (obvious) optimization is dead-end elimination (if vertex has no
> value and it is connected with one other vertex only it can be
> eliminated). This optimization should not be used when tracking validity
> of track lay (for obvious reasons).
>
> There were some other ideas, such as caching results of the optimal route
> search and trying to eliminate some possibilities based on the values of
> the cities/towns on the map, but we have no concrete approach to exploit
> them.
>
> Hopefully, I haven't forgotten anything important. Stefan, please free to
> add whatever I've missed.
>
> Thanks,
> Alex.
>
> ---------------------------------------------------------------------------
>--- Download Intel® Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel