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

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

see below

On Tuesday, August 09, 2011 08:22:38 am John A. Tamplin wrote:
> On Sun, Aug 7, 2011 at 1:55 AM, Stefan Frey <ste...@we...> wrote:
> > > 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.
> 
> It has been 24 years -- I was taking a Graph Theory class in grad school,
> and one of the things we had to do was transform other traditional problems
> to graphs and solve them using graph theory algorithms.  At the time we
> were studying the Floyd-Fulkerson algorithm, so I am sure I used that. 
> Most of the transforms involved creating extra nodes to represent other
> constraints, or replacing each node in the base graph with a set of nodes
> to represent those constraints.  I don't remember the specifics of how I
> solved it, but it worked for 1830-style trains only (which was all I knew
> about at the time).

John,
thanks for your comments. 
Good thing to know that first you were able to solve it (I hate working on 
unsolvable problems in my free time) and second that it did not take anything 
too extraordinary graph theory stuff to solve it. Third it shows the direction 
to go to adjust the graph to incorporate the train constraints (I have some 
ideas how to do that). An alternative might be to use a linear programming 
algorithm to solve the flow problem which (potentially) makes adding other 
constraints easier.

Can I ask you for reviewing my proposals, this might even help you retrieve 
the ideas you had 24 years ago.
Stefan