# Path Planning of Rail-Mounted Logistics Robots Based on the Improved Dijkstra Algorithm
## 2 Materials and Methods
### The Improved Dijkstra Algorithm
#### 2.1.3 Introducing the Time Window Model into [PERSON]'s Algorithm  
In order to carry out path planning for multiple rail-mounted logistics robots in a global dynamic environment, the time window model [26] is introduced. The time from entering a station to leaving the station is taken as the time window of the station. The time window model is specified as follows:  
1. The traveling speed of the robot in orbit is 1 m/s;
2. The maximum number of on-orbit robots in the same section of the track is 4;
3. The start and stop times and reversing time of the robot are not considered;
4. Each station can only be entered by one robot at the same time, and the other robots can only enter after occupying the right to contact. The established time window model is as follows:  
\[T_{i}=\left\{t_{i}=\left[t_{i}^{\text{in}},t_{i}^{\text{out}}\right]\right\} \tag{9}\]  
where _Ti_ is the time window occupied by the I-th site, \(t_{i}\) is the time window occupied by site \(V_{i}\), \(t_{i}^{\text{out}}\) is the start time of the time window, and \(t_{i}^{\text{in}}\) is the end time of the time window. Assuming that the linear speed of the rail-mounted logistics robot in the orbit is \(v_{s}\), the turning speed is \(v_{g}\), the interval between adjacent stations is \(L_{n}\), and the length of the robot itself is \(L_{a}\), the specific calculation of the time window of the robot at each node is divided into the following cases as shown in Figure 2:  
Figure 1: Flowchart of improving [PERSON]’s algorithm. The time window of the robot's starting point from the initial site is set as \(t_{0}\), the time window of the straight line passing through the site is \(t_{s}\), the time window of the turning time is \(t_{g}\), the time window of entering the site is \(t_{e}\), the time window of driving from site \(V_{j}\) to site \(V_{k}\) is \(t_{jk}\), and the time window of passing through the compound path is \(t_{jk}\). Then, they can be listed as shown in Table 1: \begin{table}
\begin{tabular}{c c} \hline \hline
**Types of Time Window** & **Calculation** \\ \hline Drive out of the initial site & \(t_{0}=\frac{L_{a}+L_{a}}{L_{a}}\) \\ Go straight through a station & \(t_{s}=\frac{L_{s}+L_{a}}{v_{s}}\) \\ Turn to pass a station & \(t_{g}=\frac{L_{a}+(\pi/2L_{a})}{v_{g}}\) \\ Pull into the target station & \(t_{e}=\frac{L_{a}-L_{a}}{2v_{g}}\) \\ Drive straight into \(V_{k}\) from \(V_{j}\) & \(t_{jk}=\frac{L\left(V_{j}V_{k}\right)^{-L_{a}-L_{a}}}{v_{s}}\) \\ Turn into \(V_{k}\) from \(V_{j}\) & \(t_{jk}=t_{jk}+t_{g}+t_{gk}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Calculation of time window. Figure 2: The driving situation of the robot in different sites. (**a**) Driving out of the initial site; (**b**) going straight through a station; (**c**) turning to pass a station; (**d**) pulling into the target station; (**e**) driving straight into \(V_{k}\) from \(V_{j}\); (**f**) turning into \(V_{k}\) from \(V_{j}\). Therefore, the mathematical model for introducing the time window is as follows:  
\[ \begin{cases}\begin{matrix}minL^{\prime}\big{(}V_{0},V_{p}\big{)}=\sum\limits_{a=1 }^{i=0}(1+f(V_{i}))\cdot L\big{(}V_{0},V_{p}\big{)}\\ minT=\sum\limits_{i}^{n}r_{a}\Big{(}t_{ji}^{s}+t_{i}^{s}g+t_{ik}^{s}+t_{w} \Big{)}\end{matrix}\end{cases}  \tag{10}\]  
where \(L^{\prime}\) is the distance the robot runs in orbit, \(T\) is the time the robot runs in orbit, \(g\) is the number of turns the robot makes, and \(tw\) is the waiting time. If the time window of the robot \(r_{a}\) through the path \(L_{jk}\) is \(t_{jk}^{a}=\Big{[}t_{jk}^{a},t_{jk}^{a\text{out}}\Big{]}\), then the constraints in the time window \(t_{jk}^{a}\) are as shown in Table 2.  
Where \(N_{jk}^{t_{jk}^{a}}\) is the number of robots from site \(k\) to site \(j\) in the time window \(t_{jk}^{m}\) on the path \(L_{jk}\).