# Real-Time Path Planning of Driverless Mining Trains with Time-Dependent Physical Constraints
## 3 Problem Description
### Time-Space Network  
We here consider a time-space network \(G=(N,A)\), where N denotes the node set and A denotes the arc set. For each node \(i\in N\), let \(Outb_{i}\subseteq A\) be the set of all the outbound arcs of node \(i\), and \(Inb_{i}\subseteq A\) be the set of all the inbound arcs of node \(i\). Given a physical network \(G^{*}\), we then can construct the time-space network \(G\) as follows:  
* For each load-out in \(s\in S_{l}\), we replace it with two separate node \(s_{in}\) (entry node) and \(s_{out}\) (exit node), and add a load-out link (\(s_{in}\), \(s_{out}\)) into W. Let \(W_{l}\subset W\) be the set of load-out links. By splitting the entry and exit point nodes for each load-out, we ensure that trains are staying at load-out for the required loading time. At the same time, we replace the related inbound links \((i,s)\in W\) to \((i,s_{in})\) and the related outbound links \((s,j)\in W\) to \((s_{out},j)\). Accordingly, we have \(f(i,s_{in})=f(i,s)\), \(f(j,s_{out})=f(j,s)\), and \(f(s_{in},s_{out})=P_{s}\), where \(P_{s}\) indicates the required loading time. * For each link \((i,j)\in W\) with capacity \(d_{ij}>1\), we break down the link into smaller links by adding \(\lfloor d_{ij}-1\rfloor\) dummy nodes into S and replacing the link \((i,j)\) with \(\lfloor d_{ij}-1\rfloor\) dummy links (with proportional travel time) as well. Note that after this operation, the capacity of each arc is 1. This operation guarantees that on every arc at any point of time only one train travels on that arc, which will in turn guarantee that trains maintain a safe headway separation while travelling in the same direction. * For each siding track \((i,j)\in W_{w}\), we add a siding node \(i^{\prime}\) to S and replace the siding track \((i,j)\) with two separate arcs \((i,i^{\prime})\) and \((i^{\prime},j)\). Let \(S_{w}\subset S\) be the set of siding nodes. Accordingly, we have \(f(i,i^{\prime})=f(i^{\prime},j)=f(i,j)/2\) and \(f(j,i^{\prime})=f(i^{\prime},i)=f(j,i)/2\). For each link \((i,j)\in W\), let \(Iden(i,j)\) be the set of identical arcs in \(A\). * For each node \(s\in S\), we add \(|Q|\) corresponding nodes \(\{s^{0},\ldots,s^{|Q|-1}\}\) in \(N\). For each train \(t\in T\), we add corresponding virtual source node \(s^{t}_{0}\) in \(N_{s}\in N\), where \(s^{t}_{0}\) represents the source node where train \(t\) departs. We also add one sink \(s_{1}\) into \(N\), where \(s_{1}\) represents the sink node where every train terminates its journey. * For each link \((i,j)\in W\), we add following transit arcs into \(Iden(i,j)\subset A\): \[(i^{k},j^{k+f(i,j)}),\ for\ all\ k=0,\ldots,|Q|-1\ and\ k+f(i,j)\leq|Q|-1\] and \[(j^{k},i^{k+f(i,j)}),\ for\ all\ k=0,\ldots,|Q|-1\ and\ k+f(j,i)\leq|Q|-1.\]
* For each link \((i,i^{{}^{\prime}})\in W_{w}\), we then update \(Iden(i,i^{{}^{\prime}})\) as follows: \[Iden(i,i^{{}^{\prime}})=Iden(i^{{}^{\prime}},j)=Iden(i,i^{{}^{\prime}})\cup Iden (i^{{}^{\prime}},j).\]
* For each siding node \(i\in N\), we add the following waiting arcs into \(A_{w}\subset A\). In this way, we allow trains to wait/dwell on sidings: \[(i^{k},i^{k+1}),\ for\ all\ k=0,\ldots,|Q|-2.\]
* For any load-out \(s\in S_{l}\) with loop capacity \(cap_{s}\), we add \((cap_{s}-1)\) waiting arcs between \((s^{k}_{in},s^{k}_{out})\), for all \(k=0,\ldots,|Q-2|\). In this way, we allow trains to wait/dwell in the loops. * For each station node \(i\in S_{u}\), we add an arc from that node to the sink, signifying that this allows train cancellation in case of deadlock (i.e., we can cancel a train with a very high penalty).