0

I am working on a simulator for a railway that is represented by a undirected graph where the edges are the train tracks and the vertices are the switches.

here is what the railway looks like

There is only one track between each switch which lets the train drive both directions.

For every train I calculate their directions by using Dijkstra single shortest path algorithm. But now I need to be able to detect collision with that result.

For example let's say there are 2 trains A and B

the path of A = (Gt Mx Lg Nm Lg) with current track being Gt

and for B = (Gk Lg Nm Bx A1)

You can easily see these trains will hit each other at a certain point and I am looking for a way to predict and prevent this.

Have looked into union find or maybe Knuth Algorithm x, but I hope any of you has a better idea of solving this.

user3163085
  • 9
  • 3
  • Does your algorithm need to take time into account ? Do you have a speed for each train ? – David Jan 13 '17 at 14:49
  • I do have the speed of every train as well as a function to calculate the distance between to vertices. it would be nice if it did but I'm already happy if it works without taking time in consideration. – user3163085 Jan 13 '17 at 14:50
  • Are you trying to find node-disjoint paths? – David Eisenstat Jan 13 '17 at 15:04
  • not necessarily because that wouldn't always mean there is a collision, one train can be using the path much later then the other train. in that case there is no collision. It's all about knowing when to put a lock on which track. – user3163085 Jan 13 '17 at 15:22

1 Answers1

0

If you are not interested by time constraints, then you can use mixed integer programming applied to networks.

Each train has one origin and one destination. For each train:

  • create one 'product' that can flow through your network.

  • create a 'source' at the origin node, outputting the product (capacity is 1)

  • create a 'sink' at the destination node, that eats this same product (capacity is 1)

Then set each edge's capacity to 1. Product flowing through each source and edge is an integer variable.

Then ask your maxflow solver to maximize the amount of product flowing through sinks. This will let you know the maximum amount of trains that can circulate on the network, as well as the paths used by each train to reach destination.

Once you have this information, you will know which tracks should be 'locked'.

Linear/Mixed integer programming for network modelling : http://home.ubalt.edu/ntsbarsh/opre640a/partIII.htm

For implementation details, you can use Google OR tools, which is fairly easy to bootstrap, and works for java, C#, C++: https://developers.google.com/optimization/

If you want to go Python, you can see this post : Python Mixed Integer Linear Programming

Community
  • 1
  • 1
David
  • 1,138
  • 5
  • 15