Mathematical methods for solving pair-wise cheapest path.

Question

Two trains need to go two different routes. The first train must start at $A_1$ and stop at $B_1$ and the second train $A_2$ and $B_2$. They start at the same time. Let us assume no two trains can be on the same track at the same time for risk of collision. How can we plan so that the total cost/time for traveling is minimized? The total cost/time is defined to be the sum of the costs/times for the individual trains and it is not necessarily symmetric.

---

A minimal example as requested by @quasi which should be easy to test all cases:

$$\left[\begin{array}{ccc}0&1&3\\3&0&1\\1&3&0\end{array}\right]$$

The matrix to be interpreted (row 1):

1. Go to 3 from 1 costs 3
2. Go to 2 from 1 costs 1
3. To stay at 1 costs 0.

And the objectives:

1. $T_1$ should go from $A_1 = 1$ to $B_1 = 3$

2. $T_2$ should go from $A_2 = 2$ to $B_2 = 1$

Unless I am having a major brain-fart, the solution should be

1. $T_1 : 1\to 2\to 3$ at cost $1+1=2$
2. $T_2 : 2\to 3\to 1$ at cost $1+1=2$

for a total cost of $2+2 = 4$

Answer 1

There is probably a better solution (in terms of computational complexity), but here is a nice theoretical reduction:

Construct a pair graph $G^2$, where vertices are pairs of nodes of $G$, and edges are $(v_1, v_2) \to (u_1, u_2)$ if $v_i \to u_i$ are edges in $G$ and there is no collision. The cost of such edge is obviously the sum of costs, and you want to find the cheapest route from $(A_1,A_2)$ to $(B_1, B_2)$.

Here is a concrete example (I've removed the loops, because even without them the diagram is quite complicated):

I hope this helps $\ddot\smile$