# Relaxing RGV Scheduling Problem for Approximate Assessment of Transportation Rate

Shota Suginouchi, Kazuki Honda, Tomoya Hattori, Takahiro Sakai, Hajime Mizuyama

► To cite this version:

Shota Suginouchi, Kazuki Honda, Tomoya Hattori, Takahiro Sakai, Hajime Mizuyama. Relaxing RGV Scheduling Problem for Approximate Assessment of Transportation Rate. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2022, Gyeongju, South Korea. pp.235-243, 10.1007/978-3-031-16407-1_28 . hal-05386068

HAL Id: hal-05386068

https://inria.hal.science/hal-05386068v1

Submitted on 27 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Relaxing RGV Scheduling Problem
for Approximate Assessment
of Transportation Rate

Shota Suginouchi<fnref n="1" />(✉), Kazuki Honda<fnref n="1" />, Tomoya Hattori<fnref n="2" />, Takahiro Sakai<fnref n="2" />, and Hajime Mizuyama<fnref n="1" />(✉)

**Abstract.** How to quickly assess the transportation rate of an RGV system in the early design phase is an important issue. Thus, we propose an approach for evaluating the transportation rate of an RGV system based on mathematical optimization. We first present a formulation of the RGV transportation scheduling problem. The objective function is minimizing the makespan, whose reciprocal corresponds to the transportation rate. Then, we translate the original scheduling problem into four relaxation problems to shorten the calculation time. We further conduct computational experiments for characterizing the proposed approach.

**Keywords:** RGV systems · Heuristics · Mixed Integer Programming

## 1 Introduction

RGVs (Rail Guided Vehicles) are widely used in factories and distribution centers combined with an automated storage and retrieval system (AS/RS) to transport palletized materials between the AS/RS and other facilities efficiently. A typical RGV system is composed of a rail, several stations connecting the rail with the AS/RS or other facilities, several RGVs running along the rail, etc. The number of transportation jobs accomplished per unit time, i.e., the transportation rate, depends on various factors such as the physical layout of the system, the number of RGVs, and the distribution of the origin-destination pairs. The customer is primarily concerned with whether the transportation rate reaches the requirement under various constraints. Hence, in the business inquiry phase negotiating over various design options, the provider needs to evaluate the transportation rate of candidate designs of the system quickly.

Evaluating the transportation rate is not straightforward. For example, increasing the number of RGVs improves the rate but the effect gradually

<footnote n="1">¹ Aoyama Gakuin University, 5-10-1 Fuchinobe, Sagamihara 252-5258, Japan
suginouchi@ise.aoyama.ac.jp</footnote>

<footnote n="2">² Murata Machinery, Ltd., 2 Hashizume Nakajima, Inuyama 484-0076, Japan</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 1. Example of RGV system</figcaption></figure>

decreases, and finally, becomes negative. This is because multiple RGVs share a single rail. While an RGV is loading/unloading a job from/to a station, it must stop in front of it. Accordingly, if the next RGV traveling behind it approaches the station, the next one must also stop and wait for the first one to complete the loading operation. That is, traffic jams may occur. The higher the number of installed RGVs, the more frequent such jamming and thus the lower the effect of increasing RGVs. Though this qualitative effect trend is understood, we usually need to rely on extensive numerical simulation to quantify the effect, and it takes a long time.

Thus, in this paper, we propose an approximate approach for assessing the transportation rate of an RGV system but in a relatively short time based on mathematical optimization. RGV systems can be classified into two types: orbital type and shuttling type. Some authors formulated the scheduling problem of shuttling type RGV systems [1,2] and others estimated the transportation rate of orbital type systems based on simulation [3]. Ordinary single-loop AGV systems do not use a rail but are similar to the orbital type in the mathematical sense, and their guide-path design problems are dealt with by mathematical optimization [4–6]. However, to our best knowledge, no paper has tackled a scheduling problem for the orbital type by mathematical optimization approach. We formulate a mixed integer linear programming problem that determines a transportation schedule for an orbital type RGV system. The objective function is minimizing the makespan, whose reciprocal corresponds to the transportation rate. The solution consists of a sequence of jobs and a matching between RGVs and jobs. The larger the problem size, the longer the calculation time to obtain the exact solution, which increases exponentially. Hence, we also provide four relaxation problems by removing some constraints and decision variables from the original problem in stages, and evaluate the performance of the assessment approach using those relaxed problems through numerical experiments.

## 2 Discretized Model of RGV System

Figure 1 shows a discretized model of an example RGV system. In this model, the rail is divided into multiple cells, whose length is determined so that only one RGV can occupy a cell. Each RGV moves from one cell to another in the
specified direction along the rail, that is, cells 1, 2, etc. The time for the RGV to pass through a cell depends on the cell because the RGV needs to slow down for example at corners. The velocity of the RGV also depends on whether it holds a job or not. Each RGV can hold at most one job and can load/unload a job only while it stops at a cell connected with a loading/unloading station which is indicated by an upwards/downwards arrow in the figure. Further, it takes a specified time for the RGV to complete the loading/unloading operation. Even when an RGV is running at a slower speed, or stops, in front of another RGV, the latter cannot overtake the former.

The problem is to assess the transportation rate of this RGV system, on the assumption that the distribution of the origin-destination pairs of the jobs is known. We address this problem by solving the RGV scheduling problem for a set of jobs created according to the distribution. More specifically, we evaluate the transportation rate by the reciprocal of the obtained makespan.

# 3 RGV Scheduling Problem and Its Relaxation

## 3.1 Original Scheduling Problem

We first provide a formulation of the original RGV scheduling problem below.

**Instance** $\mathcal{I} = (\mathcal{C}, \mathcal{V}, \mathcal{J}, (IC_v)_{v \in \mathcal{V}}, (F_j, G_j)_{j \in \mathcal{J}}, (T_{0,c}, T_{1,c}, W_{0,c}, W_{1,c})_{c \in \mathcal{C}}, \mathcal{L})$

$\mathcal{C} \subset \mathbb{N}$ : Set of rail cells

$\mathcal{L} \subset \mathbb{N}$ : Set of laps

$\mathcal{V} \subset \mathbb{N}$ : Set of RGVs

$IC_v \in \mathcal{C}$ : Initial position of RGV $v$

$T_{0,c} \in \mathbb{R}_0^+$ : Time for an RGV to pass through cell $c$ when it does not hold a job

$T_{1,c} \in \mathbb{R}_0^+$ : Time for an RGV to pass through cell $c$ when it holds a job

$W_{0,c} \in \mathbb{R}_0^+$ : Time for an RGV to load a job at cell $c$

$W_{1,c} \in \mathbb{R}_0^+$ : Time for an RGV to unload a job at cell $c$

$\mathcal{J} \subset \mathbb{N}$ : Set of jobs

$F_j \in \mathcal{C}$ : Origin cell of job $j$

$G_j \in \mathcal{C}$ : Destination cell of job $j$

**Solution** $x_{v,l,c} \in \mathbb{R}_0^+$ : Arrival time of RGV $v$ at cell $c$ in its $l$th lap

$s_j \in \mathbb{R}$ : Start time of job $j$

$c_j \in \mathbb{R}$ : Completion time of job $j$

**CT** : Makespan

$sc_{v,l,j} \in \{0,1\}$ : Indicator variable whether RGV $v$ starts job $j$ in its $l$th lap

$cc_{v,l,j} \in \{0,1\}$ : Indicator variable whether RGV $v$ finishes job $j$ in its $l$th lap

$h_{v,l,c} \in \{0,1\}$ : Indicator variable whether RGV $v$ holds a job when it arrives at cell $c$ in its $l$th lap

## Objective Function and Constraints
$$ \min CT \qquad (1) $$

$$ \text{s.t. } c_j \le CT \qquad \forall j \quad (2) $$

$$ v' = \begin{cases} |V| & (\text{if } v = 1) \\ v - 1 & (\text{otherwise}) \end{cases} \qquad (3) $$

$$ l' = \begin{cases} l - 1 & (\text{if } v = 1 \land c \neq |C| \land 2 \le l) \\ l + 1 & (\text{if } v \neq 1 \land c = |C|) \\ l & (\text{otherwise}) \end{cases} \qquad (4) $$

$$ c' = \begin{cases} 1 & (\text{if } c = |C|) \\ c + 1 & (\text{otherwise}) \end{cases} \qquad (5) $$

$$ x_{v',l',c'} \le x_{v,l,c} \qquad \forall (v,l,c) \in \{(v,l,c)|2 \le l \lor (l = 1 \land IC_v \le c)\} \qquad (6) $$

$$ l'' = \begin{cases} l + 1 & (\text{if } c = |C|) \\ l & (\text{otherwise}) \end{cases} \qquad (7) $$

$$ ah_{l,c} = \begin{cases} 1 & (\text{if } l = |C| \land c = |C|) \\ 0 & (\text{otherwise}) \end{cases} \qquad (8) $$

$$ x_{v,l,c} + T_{0,c} \times (1 - h_{v,l,c}) + T_{1,c} \times h_{v,l,c} + \sum_{\forall j \in \{j' | G_{j'} = c\}} W_{0,c} \times sc_{v,l,j} \\ + \sum_{\forall j' \in \{j' | G_{j'} = c\}} W_{1,c} \times cc_{v,l,j'} \le x_{v,l'',c'} + M \times ah_{l,c} \qquad \forall (v,l,c) \qquad (9) $$

$$ c'' = \begin{cases} |C| & (\text{if } c = 1) \\ c - 1 & (\text{otherwise}) \end{cases} \qquad (10) $$

$$ l''' = \begin{cases} l - 1 & (\text{if } c = 1) \\ l & (\text{otherwise}) \end{cases} \qquad (11) $$

$$ ph_{v,l,c} = \begin{cases} 0 & (\text{if } c \le IC_v - 1 \land l = 1) \\ 1 & (\text{otherwise}) \end{cases} \qquad \forall (v,l,c) \qquad (12) $$

$$ h_{v,l,c} - ph_{v,l,c} \times h_{v,l'',c''} - \sum_{\forall j \in \{j' | G_{j'} = c\}} sc_{v,l,j} \\ + \sum_{\forall j' \in \{j' | G_{j'} = c\}} cc_{v,l,j'} = 0 \qquad \forall (v,l,c) \qquad (13) $$

$$ h_{v,1,IC_v} = 0 \qquad \forall v \qquad (14) $$

$$ x_{v,l,F_j} \le s_j + M \times (1 - sc_{v,l,j}) \qquad \forall (v,l,j) \qquad (15) $$

$$ s_j \le x_{v,l,F_j} + M \times (1 - sc_{v,l,j}) \qquad \forall (v,l,j) \qquad (16) $$

$$ x_{v,l,G_j} + W_{1,G_j} \times cc_{v,l,j} \le c_j + M \times (1 - cc_{v,l,j}) \qquad \forall (v,l,j) \qquad (17) $$
$$c_j - W_{1,G_j} \times cc_{v,l,j} \le x_{v,l,G_j} + M \times (1 - cc_{v,l,j}) \quad \forall (v,l,j) \quad (18)$$

$$\sum_{v=1}^{|V|} \sum_{l=1}^{|L|} sc_{v,l,j} = 1 \quad \forall j \quad (19)$$

$$\sum_{v=1}^{|V|} \sum_{l=1}^{|L|} cc_{v,l,j} = 1 \quad \forall j \quad (20)$$

$$\sum_{l=1}^{|L|} (sc_{v,l,j} - cc_{v,l,j}) = 0 \quad \forall (v,j) \quad (21)$$

$$0 \le s_j \le c_j \quad \forall j \quad (22)$$

$$x_{v,1,IC_v} = 0 \quad \forall v \quad (23)$$

Equation (1) expresses the objective function, which minimizes the makespan. The constraints are Eqs. (2)–(23). Equation (2) defines that the makespan CT is the latest completion time $c_j$ of all jobs $j$. Equations (3)–(6) express that RGV $v$ cannot overtake RGV $v'$ running in front of it. Equations (7)–(9) express that when an RGV holds/does not hold a job, the time for it to pass through cell $c$ is $T_{1,c}/T_{0,c}$. These equations also consider the time to load/unload a job. Equations (10)–(13) express that RGVs cannot hold two or more jobs at the same time. Equation (14) guarantees that RGVs do not hold any job at the initial condition. Equations (15) and (16) define the relationship between the starting time $s_j$ of job $j$ and the arrival time $x_{v,l,F_j}$ of RGV $v$ which carries out the job $j$ at cell $F_j$ in $l$th lap. Similarly, Eqs. (17) and (18) define the relationship between the completion time $c_j$ of job $j$ and the arrival time $x_{v,l,G_j}$ of RGV $v$ at cell $(l, G_j)$. Equation (19) and (20) guarantee that a job is transported once. Equation (21) guarantees that any job cannot be interrupted once started until finished. Equation (22) expresses that RGVs can unload a job only after loading the job. Equation (23) designates the initial position of every RGV $v$.

## 3.2 RP1: Relaxation of No Overtaking Constraints

We next relax the RGV scheduling problem in stages to shorten the calculation time. Relaxation Problem 1 (RP1) relaxes Eqs. (3)–(6) from the original problem. Accordingly, RGV $v$ is permitted to overtake RGV $v'$ running in front of it. The number of RP1’s constraints is lesser than that of the original problem but the number of RP1’s decision variables is the same as that of the original.

## 3.3 RP2: Relaxation of No Preemption Constraints

RP2 further allows RGVs to preempt the job at any cell on the way to its destination. The number of RP2’s decision variables is lesser than that of RP1. RP2 needs some notations in addition to those used in the original problem. The formulation of the RP2 is as follows:

Instance $A_{j,c} \in \{0,1\}$: Indicator variable whether cell $c$ is the origin $F_j$ of job $j$
$B_{j,c} \in \{0,1\}$: Indicator variable whether cell $c$ is the destination $G_j$ of job $j$

$D_{j,c} \in \{0,1\}$: Indicator variable whether the RGV holding job $j$ passes cell $c$

**Solution** $x_{v,j} \in \{0,1\}$: A decision variable whether RGV $v$ carries out job $j$

$y_{v,c} \subset \mathbb{N}$: Number of times that RGV $v$ passes cell $c$ without holding a job

$z_{v,c} \subset \mathbb{N}$: Number of times that RGV $v$ passes cell $c$ with holding a job

$AA_{v,c} \subset \mathbb{N}$: Number of times that RGV $v$ loads a job at cell $c$

$BB_{v,c} \subset \mathbb{N}$: Number of times that RGV $v$ unloads a job at cell $c$

$ct_v \subset \mathbb{N}$: Time when RGV $v$ finishes all jobs allocated to it

### Objective Function and Constraints

$$ \min CT \qquad (24) $$

$$ \text{s.t. } ct_v \le CT \qquad \forall v \quad (25) $$

$$ \sum_v x_{v,j} = 1 \qquad \forall j \quad (26) $$

$$ AA_{v,c} = \sum_j A_{j,c} \times x_{v,j} \qquad \forall (v, c) \quad (27) $$

$$ BB_{v,c} = \sum_j B_{j,c} \times x_{v,j} \qquad \forall (v, c) \quad (28) $$

$$ z_{v,c} = \sum_j D_{j,c} \times x_{v,j} \qquad \forall (v, c) \quad (29) $$

$$ z_{v,c} - z_{v,c'} \le y_{v,c'} \qquad \forall (v, c) \in \{(v, c) | c' \le c - 1\} \quad (30) $$

$$ z_{v,c} - z_{v,c'} - 1 \le y_{v,c'} \qquad \forall (v, c) \in \{(v, c) | c \le c'\} \quad (31) $$

$$ ct_v = \sum_c (T_{0,c} \times y_{v,c} + T_{1,c} \times z_{v,c} + W_{0,c} \times AA_{v,c} + W_{1,c} \times BB_{v,c}) \quad \forall v \quad (32) $$

## 3.4 RP3: Average Occupied Time per RGV

RP3 does not require solving an optimization problem, and instead needs a straightforward calculation. RP3 calculates the average traveling time per RGV. The makespan $CT$ means the average traveling time per RGV and is expressed by Eqs. (33)–(36) with using the number of times that an RGV passes cell $c$ with holding a job $z_c$ and the number of times that an RGV passes cell $c$ without loading a job $y_c$.

$$ CT = \frac{\{\sum_c (T_{1,c} \times z_c + \sum_j W_{0,c} \times A_{j,c} + \sum_j W_{1,c} \times B_{j,c})\}}{|V|} \quad (33) $$

$$ z_c = \sum_j D_{j,c} \qquad \forall c \quad (34) $$

$$ z_c - z_{c'} \le y_{c'} \qquad \forall c \in \{c | 1 \le c' \le c - 1\} \quad (35) $$

$$ z_c - z_{c'} - 1 \le y_{c'} \qquad \forall c \in \{c | c \le c' \le |C|\} \quad (36) $$
## 3.5 RP4: Maximum Occupied Time of Cells

RP4 also needs only a straightforward calculation. The makespan *CT* is the maximum occupied time of cells and is expressed by Eq. (37).

$$ CT = \max_c \left( \sum_j T_{1,c} \times D_{j,c} + \sum_j W_{0,c} \times A_{j,c} + \sum_j W_{1,c} \times B_{j,c} \right) \quad (37) $$

<table><caption>**Table 1.** Experimental conditions</caption><thead><tr><th></th><th>Exp. 1</th><th>Exp.2</th></tr></thead><tbody><tr><td>The number of RGVs</td><td>5,6</td><td>5,10,15</td></tr><tr><td>The number of jobs</td><td>7,8,...,12</td><td>20,30,...,100</td></tr><tr><td>The number of trials</td><td>20</td><td>10</td></tr><tr><td>Loading/Unloading time W<sub>0,c</sub>, W<sub>1,c</sub> [sec]</td><td>5.5–6.7</td><td>5.5–6.7</td></tr><tr><td>Travel time when not holding a job T<sub>0,c</sub> [sec]</td><td>0.3–1.5</td><td>0.3–1.5</td></tr><tr><td>Travel time when holding a job T<sub>1,c</sub> [sec]</td><td>0.4–1.5</td><td>0.3–1.5</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Calculation time of RP1, 2, 3 and 4</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Fig. 3. The ratio of the objective function value obtained by RPs to that by GA</figcaption></figure>

# 4 Numerical Experiments

We next investigate the features of the proposed approach through computational experiments taking up the example system shown in Fig. 1. Table 1 shows the experimental conditions. The system configuration and experimental conditions do not correspond to a real system but assume a fictive one. In the experiments, we employ Genetic Algorithm for solving the original problem of a large size, and CPLEX [7] for others, on 8 Core Apple M1 CPU 16GB memory computer. The distribution of the origin-destination pairs are as follows: Warehouse → Picking station is 20%, Picking station → Warehouse is 20%, Warehouse → Loading dock is 40%, and Loading dock → Warehouse is 20%.

Figure 2 shows the calculation time obtained with changing the number of RGVs $|V|$ and that of jobs $|J|$. Note that the scale of the vertical axis is different among the panes in the figure. We could not obtain the exact solution for RP1 and RP2 when the number of jobs $|J|$ is 13 or more. On the other hand, it took only less than 5[msec] to solve RP3 and RP4 even if the number of jobs $|J|$ is 100.

Figure 3 shows the ratio of the transportation rate estimated by solving RP3 and RP4 to that obtained by solving the original problem with GA. The larger the number of jobs $|J|$, the lesser the gap between the estimates obtained by RPs and GA. Further, a certain gap remains but the gap is stabilized when the number of jobs is close to 100. Thus, we should solve the RPs of 100 or more jobs to obtain a stable estimate of the transportation rate. Interestingly, the larger the number of RGVs $|V|$, the worse the estimation accuracy in RP3 but the better in RP4. This is because the total traveling time excluding the time consumed while jamming is divided by the number of RGVs $|V|$ in RP3. The larger the number of RGVs $|V|$, the longer the extra time consumed while jamming in general. Whereas, the estimate provided by RP4 does not depend on $|V|$ since it focuses on the cells instead of RGVs. Thus, RP3 and RP4 complement each other and both should be adopted for assessing the transportation rate.
# 5 Conclusions

In this paper, we presented a formulation of the scheduling problem for an orbital type RGV system and its relaxation problems. To obtain a stable estimate of the transportation rate, a scheduling problem of 100 or more jobs should be solved. The calculation time for solving RP1 and RP2 increases exponentially. RP3 and RP4 of up to 100 jobs can be solved within a reasonable time.

Future research directions include to apply a machine learning technique to establish a transportation rate prediction model using the solution data obtained by solving the relaxation problems as the training data.

# References

1. Hu, W., Mao, J., Wei, K.: Energy-efficient rail guided vehicle routing for two-sided loading/unloading automated freight handling system. Eur. J. Oper. Res. **258**(3), 943–957 (2017)

2. Hu, P., Chen, H., Wang, X., Shi, M.: Model and algorithm for co-scheduling of stackers and single RGV during retrieval process in AS/RS. In: IOP Conference Series: Materials Science and Engineering, vol. 688 (2019)

3. Lee, S., Souza, R., Ong, E.: Simulation modelling of a narrow aisle automated storage and retrieval system (AS/RS) serviced by rail-guided vehicles. Comput. Ind. **30**, 3241–253 (1996)

4. Sinriech, D., Tanchoco, J.M.A.: Solution methods for the mathematical models of single-loop AGV systems. Int. J. Prod. Res. **31**, 705–725 (1993)

5. Chen, M.T., McGinnis, L., Zhou, C.: Design and operation of single-loop dual-rail inter-bay material handling system. Int. J. Prod. Res. **37**(10), 2217–2237 (1999)

6. Asef-Vaziri, A., Laporte, G., Sriskandarajah, C.: The block layout shortest loop design problem. IIE Trans. **32**, 727–734 (2000)

7. IBM Web page: https://www.ibm.com/analytics/data-science/prescriptive-analytics/cplex-optimizer. Accessed 9 Apr 2022