Re: [Rails-devel] Route calculation for huge runs

[Stefan F. <ste...@we...>]

This is a reply to the response of John Tamplin on Aliza's scenario.

On Monday, March 14, 2011 01:02:33 am John A. Tamplin wrote:
> 
> This is a known issue with the current brute-force algorithm -- it was
> brought up when it was being implemented.  Basically, when the number of
> trains and stops goes up, the number of possible routes goes up
> exponentially.

I agree.

The current implementation is a search-tree pruning method on an optimized 
multigraph. The heuristic used for tree-pruning is revenue prediction: Is it 
still possible with the following trains/stops to exceed the already found 
best solution?).

But even if the heuristic speeds up the search drastically, it shares the 
asymptotic behavior of brute force  that search time increases exponentially 
with trains and vertices.

> A long, long time ago, I implemented route calculation by transforming the
> problem to a flow graph and running the max-flow/min-cut algorithm on it
> (sorry, I no longer have this code), which avoids exponential time.

I think I can imagine how you approached this: You define the revenue of each 
node as negative cost of an edge inside the node and then minimize the costs 
(thus maximizing revenue) of the trains treated as flow.

Even if you do not have the code any longer, can you still remember how you 
treated the issue of train length? And how did you ensure that each train at 
least visits one home token. I guess that it was some tricky adjustment of the 
graph, but maybe you can give some clues here.

>  However, I don't know how to adapt this to all the exotic rules that have
> been added since then -- there may not be any better approach than brute
> force to make sure no solutions are missed.

I agree that it potentially  makes it much harder to implement the exotic 
rules. However I would be happy to implement such an algorithm if it allows to 
speed up those scenarios that might see double or triple long trains on an 
extensive network, but have otherwise pretty standard rules.

> 
> Perhaps the best approach is to take advantage of multiple cores by
> sharding testing alternate routes into threads and count on hardware
> getting faster
> 
> :).

That is easy ;-) 

Stefan