# Alleviating the Collision States and Fleet Optimization by Introducing a New Generation of Automated Guided Vehicle Systems

Authors: Parham Azimi
Journal: Modelling and Simulation in Engineering
 (2011)

---

## Abstract

The aim of the current research is to propose a new generation of automated guided vehicle systems for alleviating the collision states in material handling systems where the automated guided vehicles movements are allowed to be both unidirectional and bidirectional. The objective function is to maximize the average annual profit in an FMS system using a simulation method. Despite several researches done in this field, this criterion has been studied rarely. The current study includes some new changes in AGV design for preventing some common problems such as congestions and deadlocks based on real profits/costs analysis in a flexible manufacturing system. For this reason, some experiments have been carried out to study the effects of several empty vehicle dispatching rules on average annual profit. The results show that the proposed framework is efficient and robust enough for industrial environments.


---

## Body

## 1. Introduction

In modern manufacturing systems, automated guided vehicles (AGVs) have become an integral part of material handling systems. In these systems, a number of AGVs—which are always called as fleet size—are dedicated to some workstations and storehouses in order to transport the materials in horizontal movements. One of the most important advantages of AGV systems is their high flexibility, because the guide path can be easily modified to respond to any changes in the flexible manufacturing system (FMS) where routine changes are inevitable. The AGV system studied here is a discrete event dynamic system (DEDS), that is, a dynamic system with state changes driven by occurrence of individual events. The DEDS is event driven, asynchronous and nondeterministic in nature. Since there are several events in an FMS that are nondeterministic, such as processing times, machine/AGV failures, and repair times, in the proposed design all parameters have been set as nondeterministic ones. If the AGVs can move in only one direction, the system is called unidirectional, and, if they can traverse a lane in two opposite directions, the system is bidirectional. However a bidirectional AGV system can improve the system performance but its cost, is more than the unidirectional one. However, it increases the risk of potential conflicts which of course results in more costs in order to solve the conflicts by manual interventions. There are some famous vehicle management issues like conflicts, deadlocks, collisions, and blockings which have been considered by researchers in the literature. If two AGVs are moving toward each other and the AGV controller system is being obliged to stop them, it is called a “conflict” and, because both of them cannot continue the transportation task, a manual intervention must be taken to keep the system ongoing otherwise a “deadlock” happens. Even in pick-up/delivery (P/D) points, it is possible that a deadlock happens while an empty AGV is passing a way where a loaded AGV is being unloaded at a delivery point. A through survey for avoiding these issues has been conducted by Vis [1]. According to his report, there are three main strategies for avoiding the issues: (i)
designing the guide path in a way that no deadlocks and conflicts can happen.(ii)
dividing the traffic area into several nonoverlapping zones where each zone is served by a dedicated vehicle and this is called “tandem AGV” system,(iii)
developing some heuristic strategies for avoiding any conflicts and deadlocks.Most machine scheduling studies either assume infinite number of transporters for delivering the materials or neglect the transportation time according to Lee and Chen [2]. The majority of researches which are available in the FMS literature consider the material processing through workstations only and assume uninterrupted possibility of AGVs and processing machines. Obviously, most of these assumptions are not realistic for an AGV-based system [3] and because the efficiency of an AGV system has great influence on the performance of FMS [4]; therefore using suitable strategies which involve material handling system (MHS) with FMS simultaneously can increase flexibility and productivity and decrease the cost price per unit [5], and therefore conducting more comprehensive studies which involve all of these fact and figures is inevitable. The earliest scheduling work has been done by Maggu and Das [6]. They considered a two-machine flow shop make-span problem with unlimited buffer spaces on both machines in which there are a sufficient number of transporters in a way that, when a job is completed on the first machine, it could be transported with a job-dependent transportation time to the second machine immediately. Kise [7] studied the same problem but with one transporter with the capacity of one and showed that the problem is NP-hard even with job-independent transportation time. Stern and Vitner [8] considered a two-machine flow shop make-span problem where there was only one transporter with a capacity of one. They formulated the problem as an asymmetric traveling salesman problem and gave a polynomial-time heuristic. As Vis [1] mentions, an AGV system involves several issues such as:(i)
guide path layout,(ii)
traffic management,(iii)
number of P/D points,(iv)
vehicle requirement,(v)
vehicle dispatching, routing, and scheduling,(vi)
positioning of idle vehicles,(vii)
battery management,(viii)
failure management(ix)
cost management.Guide path or flow path design can be seen at strategic level [9] and can influence the system performance. The fleet size, the make-span (time needed to complete a product), and the congestion degree are another important issues in AGV systems. The most used objective function for AGV-based systems is to minimize the total vehicle travel distance corresponding to a given layout and flows [10]. Rajotia et al. [11] studied a configuration of mixed unidirectional and bidirectional flow paths with the purpose of minimizing the total travelled distance. They showed some improvements in throughput rates and the size of vehicle fleet while vehicle congestions were increased. Gaskins and Tanchoco [10] were the first researchers who developed a 0-1 programming model for a unidirectional flow path layout in order to minimize total travelled distance. Kaspi and Tanchoco [12] enhanced the previously mentioned model with more constraints and solved it by branch and bound algorithm. Asef-Vaziri et al. [13] formulated the shortest loop design problem as an integer linear programming model and solved it by relaxation technique. Bilge and Ulusoy [14] considered an integrated MHS and FMS scheduling problem using time windows approach to minimize the make-span. Aized et al. [15] presented colored Petri net-based modeling and analysis of multiple-product FMS with resource breakdown and automated inspections. However this report did not consider the MHS and assumed uninterrupted availability of dedicated AGVs. Kesen and Baykoç [16] studied the impact of JIT philosophy in a job shop environment using simulation method. However they did not consider costs and breakdowns. In other recent works, one may see the works presented by Aized [17] where he used colored Petri net and response surface methods to model and maximize an integrated AGV system. The strength points are considering both MHS and material processing and trying to maximize some criteria to reach near optimum solutions. Again costs and battery usage of AGVs have not been considered. Shalaby et al. [18] developed an algorithm for zone formation which minimized the total costs. Farahani et al. [19] developed an efficient algorithm to define the zones in a tandem AGV system by minimizing the maximum workload. Maza and Castagna [20] proposed a two-phase algorithm for bidirectional AGV system. They used this method to combine both advantages of preplanning methods and the real-time methods and tested it by simulation. Martínez-Barberá and Herrero-Pérez [21] tested a new method in a warehouse environment which combines modern technology in electronics and mathematical science in October 2009. Their method has the maximum quality gained so far but they did not consider the cost of developing such a full mechanized system for an AGV system. In some works, one may realize good suggestions for AGV systems using electronic devices like several chip sets, boards, RFIDs, sensors and to prevent any deadlocks and collisions, but the cost of developing and handling of such a system is neglected. It is clear that the cost of production system should be minimized in the current market conditions to empower the competition capability. A similar work is the one presented by Hsueh [22]. He proposed a new concept of AGV systems called “Exchangeable AGV” for preventing any collisions with some modification in AGV structure to be controlled by an RFID system. All AGVs can exchange their loads in a collision state, and, even when both of them are loaded or unloaded, they can exchange their task in collision state. He tested his algorithm by simulation and showed that it is robust and efficient. Azimi et al. [23] verified several control strategies in an AGV system using simulation and fuzzy MADM techniques. To sum up, recent works try to combine mechatronics and heuristic algorithms to present new dimensions of AGV systems. In this study, the parameters of the model have been defined in a nondeterministic environment. These parameters include the feed rate of material, the processing times, the inspection system, failure rates, repair times, added values, and all costs related to the cost price of the products based on accounting standards to absorb the attentions to the cost-/benefit-oriented methods which is the main contribution of the current study.


## 2. The Rotator AGV

The rotator AGV or RAGV concept is designed as advanced material handling system for FMS environments to prevent several collision cases. Therefore, in designing the AGVs, there should be two new main changes which enable them to solve the collision states. According to the field research in a local car manufacturer company which uses more than 800 AGVs in different shops like paint shop 1, 2 (where the cars are coated and painted), body shop 1, 2 (where the body of the cars are produced); and three assembly lines, the design of such an AGV is feasible and simple and just increases the costs by 8% in comparison to the normal AGVs. These two changes are as follows.(1)
There should be a tape holder around the RAGV set to recognize any collision with the other RAGVs by installing suitable sensors.(2)
Based on the dimension of the RAGV and the available spaces around the route path, the RAGV must be able to turnθ° around a center of a circle to let the other RAGVs pass away in a collision state and then it turns back to the route path and keeps the way to carry out its task.These two new changes in AGVs could enable them to solve several collision states, quickly. Usually in collision cases, manual intervention is needed which is a time-consuming process, but this kind of automatic action with small costs can increase the flexibility of the FMS and save the time when two RAGVs are in a collision state. The RAGV concept has been demonstrated in Figures1 and 2.The shape ((a) is the above view and (b) is the front view) of an RAGV with tape holder around it. In (c) the turning process was shown in a collision state.
(a)(b)(c)Figure 2
Flow path layout of the FMS: the distance at the right cell is the same as that at the left one. All routes are bidirectional except the one between W8 and W9.Specially, when one compares the above design with the exchangeable AGV which was introduced by [22] and includes on-board microprocessors, obstacle sensors, wireless communication systems, and automatic operations to exchange loads on a collision state, the proposed design is much cheaper and simpler.


## 3. Offline and Online Control

For controlling the operations of AGVs, one should consider three main strategies: (1) dispatching loads to AGVs when loads are ready at workstations and ready to be transported, (2) selecting the best route for AGVs, and finally (3) scheduling of AGVs for the travel by defining the arrival and the departure time at workstations. Among these strategies, the easiest one is the route selection, because all AGVs in the model select the shortest path. But for the rest of strategies, one may use mathematical model to handle them. In this case when all parameters like processing times, origins, destinations, and transportation times are known in advanced, it is called “offline controlling” system. As it was mentioned in the literature review, several offline models have been developed, but because in an FMS environment there may be several nondeterministic events like AGV or machine breakdowns, real-time decisions must be made which is called “online controlling” system. Therefore, the online controlling system was used in the model to be able to be used in real-world applications. According to [10], for online controlling systems, there are two approaches: workstation initiated and vehicle initiated. The AGV dispatching rule is workstation initiated if the vehicle should be selected among idle ones (empty ones) for transportation, and the rule is vehicle initiated if a vehicle should select a load among some loads requested by the workstations. According to [1] several heuristics have been developed for both approaches which are categorized in Table 1.Table 1
Summary of AGV dispatching rules.
Vehicle initiatedWorkstation initiatedFirst-come-first-served (FCFS)Farthest vehicle (FV)First-encountered-first-served (FEFS)First available vehicle (FAFS)Largest queue size (LQS)Least cumulative idle time (LIT)Longest interarrival time (LIT)Least utilized vehicle (LUV)Longest travel time (LTT)Longest idle vehicle (LIV)Longest waiting time (LWT)Most cumulative idle vehicle (MIT)Maximum demand (MD)Nearest (Idle) vehicle (NV or NIV)Maximum outgoing queue size (MOQS)Random vehicle (RV)Minimum remaining outgoing queue (MROQS)Minimum work-in-queue (MWQ)Modified first-come-first-served(MFCFS)Random workstation (RW)Shortest time to travel first (STTF)Unit load shop arrival time (ULSAT)Vehicle looks for work (VLFW)However, it is difficult to say which rule is the best one, because it depends on demand patterns and guide path layout. On reviewing the literature, some researchers reported a special rule for a special layout in conventional AGV systems and some others reported other rules for other layouts. Nevertheless, it should be noticed that the proposed design for AGV is different from traditional AGV systems and the previous results may not work well here due to the changes made in AGVs design.Now, some situations when two different RAGVs are approaching to each other are verified, because it will cause a conflict. Here, there are some solutions for these cases.Situation 1 (two RAGVs are moving in opposite directions on the same guide path)
They keep going until the sensors on both the RAGVs understand a front-to-front collision state. In this case, both RAGVs stop immediately, and then the system selects an RAGV randomly to turn around the guide path and let the other one pass away; then it turns back again and keeps its guide path.Situation 2 (two RAGVs are moving in the same direction)
In this case, because all RAGVs in the model have the same speed, there will be no collision state.Situation 3 (two RAGVs are approaching the same workstation for loading or unloading)
Because the RAGV which is closer to workstation has the priority, when it stops at the workstation for loading or unloading, the next RAGV will keep closing to it until a front-to-back collision happens when it stops immediately. In this case, no turning occurs. The second RAGV waits until the completion of the first RAGV task. By the time the first RAGV leaves the workstation, the second RAGV keeps its mission.Situation 4 (two RAGVs are approaching the same intersection)
In this case a side-to-side or front-to-side collision happens between two RAGVs. In this case an RAGV is selected randomly and goes back enough (e.g.,K meters according to RAGVs dimension) to prepare the intersection to be safe enough for the other RAGV to pass away. Because it is a quick action, the RAGV controlling system defines a standard time (like S seconds) for the backwarded RAGV to wait, and then it keeps its mission.Situation 5 (when an RAGV needs to be recharged)
In this case, when the amount of energy reduces to a certain level, the RAGV stores the mission in its memory and goes to the recharge center. The minimum level of energy should be set based on the maximum distance needed to reach the recharge stations.
Therefore, in the proposed model many conflicts are solved automatically without any manual intervention as quickly as possible.


## 4. Simulation Flow Path

Here, the simulation flow path is represented. The proposed flow path has not any obligation for the guide paths to be unidirectional or bidirectional, so it combines both directions. The flow path layout for the RAGVs is shown in Figure2.The source workstation is W1 and the sink is W10; the rest of workstations have been denoted by W2,…,W9 which can process only one product at a time. Each workstation has a buffer of 2-unit size which helps the manufacturing system to be more efficient, that is, when the processes completed at a workstation, the load goes to the next workstation buffer and waits for processing there. The assumptions of the simulation model are listed as follows.(i)
The speed of all RAGVs is the same which is 1 m/s.(ii)
All RAGVs have the same dimension which is1×1×1 m3.(iii)
Since all RAGVs are automated, the loading, and unloading are fixed at 15 seconds.(iv)
Three different products are produced in the model.(v)
The capacity of all RAGVs has been set to carry one unit; however, it can be increased.(vi)
All RAGVs need recharging, and their consumption depends on the situation of the RAGV. When an RAGV is moving, it consumes more energy than when it waits for the next request. All RAGVs have the same battery capacity. In the model all capacity is set at 750 Ah, recharge level is set at 20%, driving consumption when loaded is 50 Ah, when unloaded is 20 Ah, when it is at standby mode is 10 Ah, and when loading or unloading at P/D points is 100 Ah according to the real data at the manufacturing body shop, and finally the recharging time for an AGV is fixed at 3600 seconds.(vii)
The warm-up period is 8 minutes and 30 replications are performed for each case; each replication covers a year.(viii)
All simulation experiments are executed using Enterprise Dynamics 8.1.(ix)
Table2 presents the processing time, sequencing, demands rate, failure rate, and repair time by random variables.(x)
When a product reaches W10, a value added of $190 for product 1, $220 for product 2, and $120 for product 3 is given to it. This task is done by defining an attribute in the simulation software for each product.(xi)
When a product leaves a workstation, an attribute which calculates the total variable cost is updated based on the workstation and the product type. The information used here is summarized in Table3.(xii)
The fixed costs including depreciation of all facilities, financial costs, maintenance costs, and the other overheads are listed in Table4.(xiii)
Each day includes 8 working hours, each month 25 working days, and each year 300 days.(xiv)
Because the company has invested for the purchased material (based on Table3), the interest rate for a year has been set to 12% based on each product (for calculating the financial costs).(xv)
The due date for each product is at maximum 4 hours after entering the production system, and a penalty of $1.4 per/hour has been set for any delay.Table 2
The nondeterministic variables and product sequence.
VariableWorkstations (W) or RAGVs or products (P)Distribution (seconds) or sequenceProcessing time at W2, W3WNormal (150, 5)Processing time at W4, W5, W6WNormal (100, 8)Processing time at W7, W8, W9WNegExp (90)All repair timeWNormal (2500, 110)Time between failureWNormal (140000, 986)All repair timeRAGVNormal (850, 80)Time between failureRAGVNormal(85000, 503)Demand per dayP1Normal (40, 5)Demand per dayP2Normal (31, 2)Demand per dayP3Normal (62, 8)SequenceP1W2, W3, W5, W7, W9SequenceP2W2, W3, W6, W4, W7, W8, W9SequenceP3W3, W5, W7, W8Table 3
Variable costs.
Variable costs adding at each workstationProductAmount in USDW1 (Material)P195W1 (Material)P2110W1 (Material)P362W2, W3P1,P2, P312W4, W5, W6P1, P2, P38W7, W8, W9P1, P2, P39Table 4
Fixed costs.
Fixed costs/(workstation or RAGV)Annual amount in USDW1, W1050,000W2, W385,000W4, W5, W660,000W7, W8, W940,000RAGV9000The only criterion is to maximize the average annual profit. However, the previous works used other criteria such as minimum workload, maximum utilization of AGVs, minimizing the maximum queue or workload, and maximizing the throughput rate. However, all these criteria for measuring the system performance are useful, but the selected criterion is the most important one from the top mangers point of view. The money dominates all other criteria and it is almost the first priority in any company for its own business.


## 5. Computational Results for Selecting the Best Dispatching Rule

For selecting the best controlling rule, five different dispatching rules including FCFS, LQS, LWT, NV, and FV were used according to Table1. The fleet size is six units, with 30 replications conducted for each rule and average annual profit computed based on the paired t-test with 5% as significance level, and finally the results are summarized in Table 5.Table 5
Results of the pairedt-test for different dispatching rules for average annual profit.
Paired rulesMean (USD)Stand. deviationsPvalueFCFS-LQS−7,101.22895.02.000FCFS-LWT−6,332.03450.89.000FCFS-NV−8,166.38312.21.000FCFS-FV+4,766.26229.15.235LQS-LWT+955.37188.97.171LQS-NV−1,034.22211.04.189LQS-FV+16,099.26411.25.000LWT-NV−899.56287.42.354LWT-FV+15,439.34289.45.000NV-FV+21,674.97428.47.000According to the results in Table5,(1)
LQS, NV and LWT are significantly better than FCFS rule.(2)
LQS, LWT, and NV are significantly better than FV rule,Therefore NV, LWT, and LQS have more ranks but if one compares the mean results for these three rules in Table3, then one finds that NV dominates the two other rules. NV is a vehicle-initiated rule and works better than workstation-initiated rules like LWT and LQS in the model. In the simulation model, the NV rule is used as dispatching rule. However, many researchers reported NV as the best rule in their similar works like [22, 23].


## 6. Computation Results for the SimulationModel

In this section, the fleet size optimization was carried out to obtain the optimum number of RAGVs. In general, when the fleet size increases, the fixed costs and handling costs increase accordingly, but it yields better throughputs and better profits, as well. So, for the layout presented in Figure2, the simulation model was run by 5, 6, 7, and 8 RAGVs, and then the results were compared based on the average annual profit.The results in Figure3 show that the best fleet size is 7 vehicles. For comparing the results with similar works, Figures 4 and 5 show the average total collisions in a day and the average make-span for the presented layout, accordingly. As Figure 4 shows, the number of collisions increases when the fleet size increases, but when the fleet size is increasing from 7 to 8, the slope of the diagram is lower, because some RAGVs are idle and fewer collisions could happen. Specially, when one compares the results of [22] with current research with 5 units as the fleet size, total collisions are more or less the same. However the flow path that was used here has more workstations. In Figure 5, the average make-span is presented which shows that when the fleet size increases, the make-span decreases accordingly. Again when the fleet size increases from 7 to 8, the make-span has no changes.Figure 3
The results of simulation for different fleet sizes.Figure 4
Average total collisions per day.Figure 5
Average make-span (minutes).


## 7. Conclusions

This paper presents a new generation of AGVs for material handling systems which is called rotating AGV or RAGV and tries to optimize the fleet size by maximizing the average annual profit in an FMS environment. The main contribution of the paper is to introduce the RAGVs concept which is quite suitable in FMS environment for preventing many conflicts in reasonable time and cost. The second contribution is considering all related costs in an FMS environment and added values together, based on a nondeterministic process where all workstations, RAGVs, demand rate, failure rate, repair time, and material input rate are stochastic and have been included. In the simulation model, all related costs have been included according to accounting standards based on a real environment at local car manufacturer body shops, paint shops, and assembly lines such as maintenance costs, depreciation costs, overheads, material costs, investing costs (financial costs), and lateness costs. All RAGVs used for MHS had battery capacity and consume the energy in different situations. Different collisions such as front-to front, back-to-front, and side-to-side states are described and the solutions presented. In fact, it was tried to cover the most real world issues happening in an FMS environment. However there were some restrictions for the model presented, such as considering only a fixed flow path, not considering different demand rates and added values based on the market conditions, like low season and high season conditions which can be removed in future studies. Another restriction at the study period was that the company had not any access to the data needed to calculate the total costs of the current collision states and manual interventions costs. This information could help us calculate the cost savings resulted from using an RAGV rather than a traditional AGV. Several experiments were carried out for selecting the best dispatching rule among five different rules and then the fleet size was optimized based on the average annual profit. The experimental results show that the recommended design of AGVs and the used criterion are robust enough to be applied in practice, in a world where the cost/benefit analysis is one of the most important factors for all top managers in any conditions.



---

*Source: 210628-2011-06-13.xml*